home *** CD-ROM | disk | FTP | other *** search
/ Power CD-ROM!! 7 / POWERCD7.ISO / prgmming / clipper / levensht.prg < prev    next >
Text File  |  1993-10-14  |  5KB  |  197 lines
  1. /*
  2.  * GT CLIPPER STANDARD HEADER
  3.  *
  4.  * File......: levensht.prg
  5.  * Author....: Andy M Leighton
  6.  * BBS.......: The Dark Knight Returns
  7.  * Net/Node..: 050/069
  8.  * User Name.: Andy Leighton
  9.  * Date......: $Date$
  10.  * Revision..: $Revision$
  11.  *
  12.  * This is an original work by Andy Leighton and is placed in the
  13.  * public domain.
  14.  *
  15.  * Modification history:
  16.  * ---------------------
  17.  *
  18.  * $Log$
  19.  *
  20.  */
  21.  
  22. /*  $DOC$
  23.  *  $FUNCNAME$
  24.  *       GT_LEVDIST()
  25.  *  $CATEGORY$
  26.  *       String
  27.  *  $ONELINER$
  28.  *       Return the Levenshtein distance between two strings
  29.  *  $SYNTAX$
  30.  *       GT_LevDist(<cStrA>, <cStrB>) --> nDist
  31.  *  $ARGUMENTS$
  32.  *       <cStrA>     -  First string
  33.  *       <cStrB>     -  Second String
  34.  *  $RETURNS$
  35.  *       nDist       -  Levenshtein Distance.
  36.  *  $DESCRIPTION$
  37.  *       Return the Levenshtein distance between two strings
  38.  *
  39.  *       The  Levenshtein  distance  between  two  strings  is  the
  40.  *       minimum  number  of  operations  (Insertions, Deletions or
  41.  *       Substitutions) to transform one string to the other.   The
  42.  *       algoritm used to solve this problem is a prime example  of
  43.  *       dynamic  programming.   It  is  very  similar  approach to
  44.  *       solving  the   shortest  distance   between  two    cities
  45.  *       connected by a network of roads.
  46.  *
  47.  *       The algorithm  is of  order O(nm)  where n  and m  are the
  48.  *       lengths  of  the  two  strings.   Therefore  when  the two
  49.  *       strings are equal  the algoritm is  of order O(n²)  so you
  50.  *       should   check   for   equality   first   before   calling
  51.  *       GT_LevDist()
  52.  *
  53.  *       REFERENCES
  54.  *       Doctor Dobb's Journal #187, April 1992
  55.  *
  56.  *       IMPROVEMENTS
  57.  *       The  main  improvements  in  this  routine will be made by
  58.  *       introducing a more complex operation costing.
  59.  *
  60.  *       ie. have three matrices that record the cost of adding  or
  61.  *           deleting  a  specific   letter,  and  substituting   a
  62.  *           specified letter with another.
  63.  *
  64.  *       More improvements can be achieved  but at the loss of  the
  65.  *       general purpose of the routine.
  66.  *
  67.  *       This is left as an exercise for the foolhardy or brave.
  68.  *  $EXAMPLES$
  69.  *       ? GT_LevDist("Axolotl", "Axl Rose")      // prints 5
  70.  *
  71.  *       Axolotl -> Axl Rose in 5 operations
  72.  *
  73.  *          Axolotl
  74.  *          Axolote     SUB e for l
  75.  *          Axolose     SUB s for t
  76.  *          AxoRose     SUB R for l
  77.  *          Ax Rose     SUB space for o
  78.  *          Axl Rose    INS L
  79.  *  $SEEALSO$
  80.  *       GT_LEVCOST()
  81.  *  $END$
  82.  */
  83.  
  84. #include "gt_LIB.ch"
  85. #include "levensht.ch"
  86.  
  87. static matrix := {}
  88.  
  89. function GT_LevDist(cA, cB)
  90.  
  91.    local nDistance
  92.  
  93.    gGT_initMatrix(cA, cB)
  94.    gGT_calcMatrix(cA, cB)
  95.  
  96.    nDistance := DIST(len(cB) + 1, len(cA) + 1)
  97.  
  98.    matrix := NIL
  99.  
  100. return nDistance
  101.  
  102. /*
  103.  * INTERNAL FUNCTION: gGT_initMatrix()
  104.  *
  105.  * initialise the matrix before calculating Levenshtein distance
  106.  */
  107.  
  108. static function gGT_initMatrix(cA, cB)
  109.  
  110.    local i, j
  111.  
  112.    matrix := array(len(cA) + 1, len(cB) + 1, 2)
  113.  
  114.    for i := 1 to len(cA) + 1
  115.       matrix[i][1][1] := i - 1
  116.       matrix[i][1][2] := LV_INS
  117.    next
  118.    for i := 1 to len(cB) + 1
  119.       matrix[1][i][1] := i - 1
  120.       matrix[1][i][2] := LV_DEL
  121.  
  122.       for j := 2 to len(cA) + 1
  123.          matrix[j][i][1] := 0
  124.          matrix[j][i][2] := 0
  125.       next
  126.    next
  127.  
  128. return NIL
  129.  
  130. /*
  131.  * INTERNAL FUNCTION: gGT_calcMatrix()
  132.  *
  133.  * calculate the matrix of distances
  134.  */
  135.  
  136. static function gGT_calcMatrix(cA, cB)
  137.  
  138.    local nRow
  139.    local nCol
  140.  
  141.    for nCol := 2 to len(cA) + 1
  142.       for nRow := 2 to len(cB) + 1
  143.          gGT_calcCell(cA, cB, nRow, nCol)
  144.       next
  145.    next
  146.  
  147. return NIL
  148.  
  149. /*
  150.  * INTERNAL FUNCTION: gGT_calcCell()
  151.  *
  152.  * calculate just one cell of the matrix.
  153.  * this is where all the work is done.
  154.  *
  155.  * To step through this whole algorithm in english text would
  156.  * be much longer than the code below and IMHO would be much
  157.  * harder to follow.  It also involves a mathematical expression
  158.  * that is difficult to represent in straight ASCII.
  159.  */
  160.  
  161. static function gGT_calcCell(cA, cB, row, col)
  162.  
  163.    local nDistNW  := DIST(row - 1, col - 1)
  164.    local nDistW   := DIST(row, col - 1)
  165.    local nDistN   := DIST(row - 1, col)
  166.    local nOp
  167.  
  168.    if nDistW < nDistN
  169.       if nDistW < nDistNW
  170.          matrix[col][row][2] := LV_INS
  171.          matrix[col][row][1] := nDistW + gGT_Cost(LV_INS)
  172.       else
  173.          if substr(cA, col - 1, 1) == substr(cB, row - 1, 1)
  174.             nOp := LV_MATCH
  175.          else
  176.             nOp := LV_SUB
  177.          endif
  178.          matrix[col][row][2] := nOp
  179.          matrix[col][row][1] := nDistNW + gGT_Cost(nOp)
  180.       endif
  181.    else
  182.       if nDistN < nDistNW
  183.          matrix[col][row][2] := LV_DEL
  184.          matrix[col][row][1] := nDistN + gGT_Cost(LV_DEL)
  185.       else
  186.          if substr(cA, col - 1, 1) == substr(cB, row - 1, 1)
  187.             nOp := LV_MATCH
  188.          else
  189.             nOp := LV_SUB
  190.          endif
  191.          matrix[col][row][2] := nOp
  192.          matrix[col][row][1] := nDistNW + gGT_Cost(nOp)
  193.       endif
  194.    endif
  195.  
  196. return NIL
  197.