home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / sys / amiga / programmer / 3095 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.1 KB
  1. Path: soap.news.pipex.net!pipex!usenet
  2. From: m.hendry@dial.pipex.com (Mathew Hendry)
  3. Newsgroups: comp.sys.amiga.programmer
  4. Subject: Re: "Fuzzy" string searching
  5. Date: Sun, 11 Feb 96 00:31:40
  6. Organization: Private node.
  7. Distribution: world
  8. Message-ID: <19960211.4F6A38.F17@am141.du.pipex.com>
  9. References: <311cf85e@beachyhd.demon.co.uk>
  10. NNTP-Posting-Host: am141.du.pipex.com
  11. X-Newsreader: TIN [AMIGA 1.3 950726BETA PL0]
  12.  
  13. Adam@beachyhd.demon.co.uk wrote:
  14. : I wish to write a function that will perform a 'fuzzy' search for one string
  15. : within another.
  16. : 
  17. : The most simple level of search is to just check if the 'search' string is in
  18. : the 'source' string. So if I'm searching for 'test' in the string 'this is a
  19. : test', it will obviously be found.
  20. : 
  21. : But I need to go further than that, and provide more intelligent searching. If
  22. : I search for the word 'recent' in the string 'currency/recency', I still want a
  23. : very close match to be indicated.
  24. : 
  25. : This becomes more difficult when searching (for example) for the word
  26. : 'workload' in the string 'high work-load'. Never more than 4 characters match
  27. : at any time, though obviously this should provide a very close match.
  28. : 
  29. : The idea is similar to that used in spell-checkers.. When the program doesn't
  30. : recognise your word, it manages to search its dictionary for things it thinks
  31. : are very close.
  32. : 
  33. : Does anyone have any suggestions or code that might allow me to perform this
  34. : sort of search? Ideally a function that I pass two strings to, and which
  35. : returns a score value within a given range (say, 0 to 100)..?
  36.  
  37. Have a look at:
  38. AGrep204.lha       util/sys    35K 155+Fastest available Grep (>1MB, >=2.0)
  39.  
  40. which is a version of grep supporting inexact matching of substrings. When
  41. run, you are able to specify a number of character alterations / insertions /
  42. deletions to the search pattern when testing for a match.
  43.  
  44. Source is not included in that archive, but I believe there are pointers to
  45. public source in the archive.
  46.  
  47. As a side effect, AGrep is also the fastest grep around (someone based their
  48. PhD thesis around the searching algorithms used in it...).
  49.  
  50. -- Mat.
  51.