Changeset 7238 for code/branches/consolecommands3/src/libraries/util/StringUtils.cc

Timestamp:

Aug 28, 2010, 4:48:48 PM (15 years ago)

Author:

landauf

Message:

added a function to compute the Levenshtein distance between two strings to StringUtils.
used this in CommandEvaluation to correct misspelled commands (not automatically though, just to print a suggestion to the user)

File:

• code/branches/consolecommands3/src/libraries/util/StringUtils.cc (modified) (2 diffs)

code/branches/consolecommands3/src/libraries/util/StringUtils.cc

@@ -514 +514 @@
         @return Number of replacements
     */
-    _UtilExport size_t replaceCharacters(std::string& str, char target, char replacement)
+    size_t replaceCharacters(std::string& str, char target, char replacement)
     {
         size_t j = 0;
@@ -527 +527 @@
         return j;
     }
+
+    /**
+        @brief Calculates the Levenshtein distance between two strings.
+
+        The Levenshtein distance is defined by the number of transformations needed to convert str1
+        into str2. Possible transformations are substituted, added, or removed characters.
+    */
+    unsigned int getLevenshteinDistance(const std::string& str1, const std::string& str2)
+    {
+        size_t cols = str1.size() + 1;
+        size_t rows = str2.size() + 1;
+        int matrix[rows][cols];
+
+        for (size_t r = 0; r < rows; ++r)
+            for (size_t c = 0; c < cols; ++c)
+                matrix[r][c] = 0;
+
+        for (size_t i = 1; i < cols; ++i)
+            matrix[0][i] = i;
+        for (size_t i = 1; i < rows; ++i)
+            matrix[i][0] = i;
+
+        for (size_t r = 1; r < rows; ++r)
+            for (size_t c = 1; c < cols; ++c)
+                matrix[r][c] = (str1[c-1] != str2[r-1]);
+
+        for (size_t r = 1; r < rows; ++r)
+            for (size_t c = 1; c < cols; ++c)
+                matrix[r][c] = std::min(std::min(matrix[r-1][c] + 1, matrix[r][c-1] + 1), matrix[r-1][c-1] + (str1[c-1] != str2[r-1]));
+
+        return matrix[rows-1][cols-1];
+    }
 }