| 130 | |
| 131 | |
| 132 | int cStringUtil::EditDistance(const cString & string1, const cString & string2) |
| 133 | { |
| 134 | const int size1 = string1.GetSize(); |
| 135 | const int size2 = string2.GetSize(); |
| 136 | |
| 137 | if (size1 == 0) return size2; |
| 138 | if (size2 == 0) return size1; |
| 139 | |
| 140 | int * cur_row = new int[size1]; // The row we are calculating |
| 141 | int * prev_row = new int[size1]; // The last row we calculated |
| 142 | |
| 143 | // Initialize the previous row to record the differece from nothing. |
| 144 | for (int i = 0; i < size1; i++) prev_row[i] = i + 1; |
| 145 | |
| 146 | // Loop through all of the other rows |
| 147 | for (int i = 0; i < size2; i++) { |
| 148 | // Initialize the first entry in the current row. |
| 149 | if (string1[0] == string2[i]) cur_row[0] = i; |
| 150 | else cur_row[0] = (i < prev_row[0]) ? (i+1) : (prev_row[0] + 1); |
| 151 | |
| 152 | // Move down the cur_row and fill it in. |
| 153 | for (int j = 1; j < size1; j++) { |
| 154 | // If the values are equal, keep the value in the upper left. |
| 155 | if (string1[j] == string2[i]) { |
| 156 | cur_row[j] = prev_row[j-1]; |
| 157 | } |
| 158 | |
| 159 | // Otherwise, set the current position the the minimal of the three |
| 160 | // numbers to the upper right in the chart plus one. |
| 161 | else { |
| 162 | cur_row[j] = (prev_row[j] < prev_row[j-1]) ? prev_row[j] : prev_row[j-1]; |
| 163 | if (cur_row[j-1] < cur_row[j]) cur_row[j] = cur_row[j-1]; |
| 164 | cur_row[j]++; |
| 165 | } |
| 166 | } |
| 167 | |
| 168 | // Swap cur_row and prev_row. (we only really need to move the cur row |
| 169 | // over to prev, but this saves us from having to keep re-allocating |
| 170 | // new rows. We recycle! |
| 171 | int * temp_row = cur_row; |
| 172 | cur_row = prev_row; |
| 173 | prev_row = temp_row; |
| 174 | } |
| 175 | |
| 176 | // Now that we are done, return the bottom-right corner of the chart. |
| 177 | |
| 178 | const int value = prev_row[size1 - 1]; |
| 179 | |
| 180 | delete [] cur_row; |
| 181 | delete [] prev_row; |
| 182 | |
| 183 | return value; |
| 184 | } |
| 185 | |
| 186 | int cStringUtil::EditDistance(const cString & string1, const cString & string2, |
| 187 | cString & info, const char gap) |