home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / programm / 3445 < prev    next >
Encoding:
Text File  |  1993-01-12  |  1.9 KB  |  54 lines

  1. Path: sparky!uunet!mcsun!sun4nl!and!jos
  2. From: jos@and.nl (Jos Horsmeier)
  3. Newsgroups: comp.programming
  4. Subject: Re: Help With String Comparisons
  5. Message-ID: <4340@dozo.and.nl>
  6. Date: 12 Jan 93 10:09:46 GMT
  7. References: <1993Jan11.224515.24729@dragon.acadiau.ca>
  8. Organization: AND Software BV Rotterdam
  9. Lines: 43
  10.  
  11. In article <1993Jan11.224515.24729@dragon.acadiau.ca> 890584r@dragon.acadiau.ca (Barrie Rody) writes:
  12.  
  13. |    I am writing a database and I need some help in comparing strings.
  14. |What I need is an algorithm to compare 2 strings {PChar, array[]of Char}.
  15. |I need this algorithm to be able to identify similar strings.
  16. |ie. a misspelled word would be found in a list.
  17. |    I am writing this in Turbo Pascal for Windows.  Any pseudocode,
  18. |Pascal, C, C++ or text answers would be greatly appreciated.
  19.  
  20. Two approached come to mind:
  21.  
  22. - Soundex matching:
  23.  
  24.   1) Map the consonants to their respective classes:
  25.  
  26.   - gutturals: g, h, k, q, r, x
  27.   - dentals  : c, d, s, t, z
  28.   - labials  : b, f, j, l, m, n, p, v, w
  29.  
  30.   2) Remove identical adjacent phonemes and compare the two resulting strings
  31.  
  32. - `Gestalt' matching (function P):
  33.  
  34.   1) Given two strings V and W, find the largest substring X, such that
  35.      V= Vl X Vr and W = Wl X Wr. In case of a tie, take one X at random.
  36.      Let S equal 2*|X| (the length of the largest substring X)
  37.  
  38.   2) Let L be the value of P applied to Vl and Wl (if both not empty)
  39.      and let R be the value of P applied to Vr and Wr (if both not empty)
  40.  
  41.   3) The 'match value' is (L+S+R)/(|V|+|W|)
  42.  
  43. An example may clarify the second method a bit. Consider two strings
  44. `color' and `colour'. The largest substring is `colo'. There are no
  45. prefix substrings and the two suffix substrings are `r' and `or'. 
  46. Applying the same method to those strings yields the value 1 (`r'). 
  47. So, the total `match value' is (2*0+2*4+2*1)/(5+6) = 10/11. 
  48.  
  49. I hope this helps a bit,
  50.  
  51. kind regards,
  52.  
  53. Jos aka jos@and.nl
  54.