Return the Levenshtein distance between two strings ──────────────────────────────────────────────────────────────────────────────
Syntax
GT_LevDist(<cStrA>, <cStrB>) --> nDist
Arguments:
<cStrA> - First string <cStrB> - Second String
Returns:
nDist - Levenshtein Distance.
Description:
Return the Levenshtein distance between two strings
The Levenshtein distance between two strings is the minimum number of operations (Insertions, Deletions or Substitutions) to transform one string to the other. The algoritm used to solve this problem is a prime example of dynamic programming. It is very similar approach to solving the shortest distance between two cities connected by a network of roads.
The algorithm is of order O(nm) where n and m are the lengths of the two strings. Therefore when the two strings are equal the algoritm is of order O(n²) so you should check for equality first before calling GT_LevDist()
REFERENCES Doctor Dobb's Journal #187, April 1992
IMPROVEMENTS The main improvements in this routine will be made by introducing a more complex operation costing.
ie. have three matrices that record the cost of adding or deleting a specific letter, and substituting a specified letter with another.
More improvements can be achieved but at the loss of the general purpose of the routine.
This is left as an exercise for the foolhardy or brave.
Examples:
? GT_LevDist("Axolotl", "Axl Rose") // prints 5
Axolotl -> Axl Rose in 5 operations
Axolotl Axolote SUB e for l Axolose SUB s for t AxoRose SUB R for l Ax Rose SUB space for o Axl Rose INS L