Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I thought about this, and have been trying to come up with solutions on how to fuzzy search a database, if for say example a user types a spelling mistake. Any glaring problems with the logic behind this? Will it work and has it been done before?

Our table we wish to search:

**tblArticles**
Body - Soundex_Body - CharacterCoded_Body

So we store the raw text body for physical display. The other 2 columns are used for searches which are precomputed the following way:

Soundex

Body is split into it's words, and translated to it's soundex version. IE, resulting body might be something like:

H252 B54 C23 E33... etc

So someone might enter 'dinosore', and the article body reads 'dinosaur' these both evaluate to B26. We then run a LIKE on the soundex value of search term.

Character Coded

Given a character mapping that maps chars to prime numbers, IE:

h = 2
e = 3
l = 5
o = 7
p = 11
c = 13

help = 2*3*5*11     =   330
hello = 2*3*5*5*7   =   1050
hell = 2*3*5*5      =   150
hlep = 2*5*3*11     =   330
cello = 13*3*5*5*7  =   6825

If a user meant to type 'hello' but they switched two or more characters around for example 'hlelo', they would evaluate to the same number. Split raw body into words, prime encode every word and store in database giving you a field that looks like:

330 6825 330 1050... etc

We can then like search on this value to match mistypes.

Benefits

  • Typos protected against
  • Phonetic incorrect spellings protected against
  • More non native english speaking friendly
  • Will work in any language (where soundex works)

Comments and thoughts? A sort of multilayered search. You can of course weight return values to make it even better (IE a literal text body match is worth more), but is this a good solution for spelling errors and non native english speakers doing searches?

share|improve this question
    
Would be interesting to see how this compares with Trigram Search. –  Rich Mar 3 '11 at 16:05
    
I'd love to have something like this for wordpress... –  Kit Menke Mar 3 '11 at 16:19
    
Does using primes for your hashing function make it impossible to have any word collisions that don't include identical methods? It seems that it should be possible to to have a long word with lots of low-value letters to it that hashed to the same value as a short word with a few high-value letters, but I don't know much number theory so it's probably well proven one way or another... –  glenatron Mar 3 '11 at 16:59
1  
@Glen Afaik multiplying primes together always generates a unique number. Anagrams will collide though but idk how much of a problem that is, that's basically the point of it to find anagrams quickly. –  Tom Mar 3 '11 at 17:01
    
@Glen: See the unique factorization theorem for uniqueness. –  Steve Evers Mar 3 '11 at 19:18
add comment

4 Answers

up vote 2 down vote accepted

There are a number of other search algorithms. Smith-Waterman is one of the better ones for human text, while BLAST is (so far) the best for searching DNA sequences. When you are presented text with various spelling errors such as hlep instead of help, then you are looking for the minimum edit distance.

For a library to implement a number of these functions in CLR in SQL Server 2005 (and later), look at the source forge project SimMetrics. Blog post about SimMetrics.
http://staffwww.dcs.shef.ac.uk/people/S.Chapman/simmetrics.html

Soundex was developed because the primary differences between regional speech variations was almost exclusively in the vowels - which is why it tosses vowels out. It isn't good at coping with transposed letters.

share|improve this answer
add comment

Apache Solr, supports synonyms and spelling corrections - although it's still a bit rough around the edges.

Fuzzy Searches can be implemented using Ngrams,

Porter Stemmer: http://tartarus.org/~martin/PorterStemmer/

and a language database such as http://wordnet.princeton.edu/

... but projects such as Xapian and Solr handle much of this for you.

If you do want to build your own word search term parsing / searching engine I would suggest putting the tokens or terms you generate into an existing database that is designed to perform language search.

share|improve this answer
add comment

I did something like that a while back for addresses that would check how many changes it would take to transform one string into another string, and return a numeric value between 0 and 1 as to how closely the two matched.

It worked out great since it would return a high value for items such as N/North, St/Street, EastMain/MainEast, etc. The idea came from this CodeProject link

share|improve this answer
add comment

If you are matching names, or people or places, a synonym list can work a lot better.

Soundex will not match "Dick==Richard" "Kit==Christopher" or "Ms.==Mrs."

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.