This word list will be referenced, by a foreign key constraint, from a large narrow table that records where the various entities that are associated with the word are stored, so that relevant matches, maybe a link, a phrase, a description or an image, can be returned to the user. This second table usually records at least the location of the text and the sequence number of the word in the text, where it occurs. It is the inversion table, containing the list of words, that we\u2019ll focus on in this article.<\/p>\n
The task<\/h1>\n
When users search the site, even if they are using a single language, they will misspell or use national spellings. They will also use dialect words, or specialist words, for the widget, and even then they may get the spelling wrong. They will use argot or even textspeak (\u2018I H8 U 4 UR HCC\u2019).<\/p>\n
In short, your “fuzzy search” algorithm ought to be able to cope with a lot of creative ways to search for the same thing, for example:<\/p>\n
- \n
- dialect differences<\/strong> \u2013 crayfish, crawfish, \u00e9crevisse, crawdads, yabbies<\/li>\n
- national spelling differences<\/strong> \u2013 yoghourt, yogurt and yoghurt<\/li>\n
- national word differences<\/strong> \u2013 pants and trousers<\/li>\n
- multiple valid spellings<\/strong> \u2013 encyclopaedia, encyclopedia<\/li>\n
- misspellings<\/strong> \u2013 definitely often rendered as definitly, definately or defiantly<\/li>\n
- mistyping<\/strong> \u2013 computer as copmuter or comptuer.<\/li>\n<\/ul>\n
We\u2019ll use three basic techniques to cope with all this: the \u2018edit difference\u2019, the hardcoded \u2018common misspelling\u2019 lookup, and the sound-alike. Although some of the ways that words become difficult to match are dealt with by the lookup, and the \u2018edit difference\u2019 approach is good for interpreting mistyping, in truth, both that and the sound-alike technique work together to catch a wide variety of errors.<\/p>\n
The Test-bed<\/h1>\n
To set this up, we\u2019ll have our inversion table. We\u2019ll also need a function to generate metaphones for when we get to the \u2018sound-alike\u2019 techniques<\/p>\n
All we need to start is a list of all the common words in the English language. To this we can then add the common mistypings and \u2018aliases\u2019(by which I mean dialect words or national differences). The list of common words can be found all over the internet but is here in the SQL of Scrabble and Rapping<\/a> or the Fireside Fun of Decapitations<\/a>. Common Mistypings and common misspellings are available in the public domain. Dialect words and national differences are dependent on your location. You\u2019ll also need to load the code for the metaphone function from here<\/p>\n
CREATE TABLE words\r\n (word VARCHAR(40) PRIMARY KEY,\r\n CanonicalVersion VARCHAR(40),\r\n Metaphone VARCHAR(10) NULL, \r\n Word_id int IDENTITY UNIQUE\r\n ) \r\n ALTER TABLE dbo.Words \r\n ADD CONSTRAINT FK_canonical FOREIGN KEY (CanonicalVersion) \r\n REFERENCES dbo.words(Word) \r\n ; \r\n GO \r\n \/* this is just a temporary expedient *\/\r\n CREATE TABLE #words\r\n (word VARCHAR(40)\r\n ) \r\n \/* we unpack the wordlist and put it in a directory\r\n on the server hosting our SQL Server instance *\/\r\n INSERT INTO #words(word)\r\n EXECUTE master..xp_cmdshell \r\n 'type OurDirectory\\wordlist.txt'\r\n DELETE FROM #words WHERE word IS NULL\r\n insert INTO words (word,Metaphone)\r\n SELECT word, dbo.metaphone(word) FROM #words\r\n -- now we need an index on the metaphone\r\n CREATE INDEX idxMetaphone ON words (metaphone)\r\n DROP TABLE #words<\/pre>\n
You can then insert your secondary \u2018alias\u2019 words like this<\/p>\n
INSERT INTO words(word, Metaphone)\r\n SELECT good, dbo.metaphone(good)\r\n FROM (VALUES\r\n ('across','accross' ),\r\n ('aggressive','agressive'),\r\n ('aggression','agression'),\r\n ('apparently','apparantly'),\r\n ('appearance','appearence'),\r\n ('argument','arguement'),<\/pre>\n\u2026and so on through to<\/p>\n
('wherever','whereever'),\r\n ('which','wich'))f(good,bad)<\/pre>\nNow, you can select both the standard \u2018canonical\u2019 words and the \u2018aliases\u2019<\/p>\n
SELECT COALESCE(words.CanonicalVersion, words.word) FROM dbo.words\r\n WHERE words.word = @Searchterm;<\/pre>\n
Or you may want to just search the canonical words by excluding the aliases by adding the condition<\/p>\n
AND words.CanonicalVersion IS NULL<\/pre>\n
Edit Difference<\/h1>\n
We can use the ‘edit difference’ technique to cope with simple mistyping or misspelling errors.<\/p>\n
When you compare words, and need a measure of how alike they are, you generally calculate how many single-character edits, deletions, transpositions, replacements and insertions you would need to make to get from one to the other. It is commonly believed that to search for a word, you need to calculate the number of edits required to change your candidate word to any other word in the inversion table. Well, no. This would take at least thirteen seconds on our word list, with the full Damerau-Levenshtein algorithm.<\/p>\n
A much simpler and faster technique is to select just the candidates that are one \u2018edit difference\u2019, or Levenshtein Distance, away because you only want candidate matches that are similar.<\/p>\n
You just produce all the character strings that are one edit distance away and do an inner join with your table of words to eliminate the vast majority that aren\u2019t legitimate words in your table. This deals with the majority of errors. No fuss at all.<\/p>\n
Here is the code<\/p>\n
IF OBJECT_ID (N'dbo.OneEditDifferenceTo') IS NOT NULL\r\n DROP FUNCTION dbo.OneEditDifferenceTo\r\n GO\r\n CREATE FUNCTION dbo.OneEditDifferenceTo(@Word Varchar(40))\r\n \/**\r\n summary: >\r\n Returns all common words that are one edit difference away from the input word. The routine generates all the character strings that are one edit distance away and does an inner join with the table of words.\r\n Author: Phil Factor\r\n Revision: 1.0\r\n date: 16\/02\/2017\r\n example:\r\n Select * from dbo.OneEditDifferenceTo('osd')\r\n Select * from dbo.OneEditDifferenceTo('acheeve')\r\n Select * from dbo.OneEditDifferenceTo('erty')\r\n returns: >\r\n a table containing strings\r\n Dependency: WORDS. A table of common words\r\n **\/\r\n RETURNS @candidates TABLE \r\n (\r\n Candidate VARCHAR(40)\r\n )\r\n AS\r\n -- body of the function\r\n BEGIN\r\n DECLARE @characters TABLE ([character] CHAR(1) PRIMARY KEY)\r\n DECLARE @numbers TABLE (number int PRIMARY KEY)\r\n INSERT INTO @characters([character])\r\n SELECT character FROM (VALUES \r\n ('a'),('b'),('c'),('d'),('e'),('f'),('g'),('h'),('i'),('j'),('k'),('l'),('m'),\r\n ('n'),('o'),('p'),('q'),('r'),('s'),('t'),('u'),('v'),('w'),('x'),('y'),('z'))F(character)\r\n INSERT INTO @numbers(number)\r\n SELECT number FROM (VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11),(12),(13),\r\n (14),(15),(16),(17),(18),(19),(20),(21),(22),(23),(24),(25),(26),(27),(28),(29),\r\n (30),(31),(32),(33),(34),(35),(36),(37),(38),(39),(40))F(number)\r\n INSERT INTO @Candidates(candidate)\r\n SELECT DISTINCT word FROM \r\n (--deletes\r\n SELECT STUFF(@word,number,1,'') FROM @numbers WHERE number <=LEN(@Word)\r\n UNION ALL--transposes\r\n SELECT STUFF(@word,number,2,SUBSTRING(@word,number+1,1)+SUBSTRING(@word,number,1)) \r\n FROM @numbers WHERE number <LEN(@Word)\r\n UNION ALL --replaces\r\n \tSELECT DISTINCT STUFF(@word,number,1,character) \r\n \t FROM @numbers CROSS JOIN @characters WHERE number <=LEN(@Word)\r\n UNION ALL --inserts \r\n \tSELECT STUFF(@word,number,0,character) \r\n \t FROM @numbers CROSS JOIN @characters WHERE number <=LEN(@Word)\r\n UNION ALL --inserts at end of string\r\n \tSELECT @word+character \r\n \t FROM @characters \r\n \t)allcombinations(generatedWord)\r\n INNER JOIN dbo.words ON generatedWord=word\r\n \tWHERE words.CanonicalVersion IS null\r\n RETURN\r\n END\r\n GO<\/pre>\nWith a test bank of 147 common misspellings, the function failed to come up with the correct version only thirteen times. That is less than a ten percent failure rate. In all, it took 380 ms on a slow test server to find all the one-edit-difference matches for 147 words. That\u2019s roughly 2.6 ms each<\/p>\n
![](\"https:\/\/www.red-gate.com\/simple-talk\/wp-content\/uploads\/2017\/02\/hits.jpg\")
<\/p>\nThis might be all you need for some applications, but we can pick up most of the mis-spellings that the edit-difference search failed to find, such as phonetic misspellings, using sound-alike.<\/p>\n
Sound-Alike<\/h1>\n
For words that are mis-typed phonetically, there is the Metaphone algorithm. There are more advanced and much more complicated versions of this, but I\u2019m using the early public-domain form. I have a SQL Version here<\/a>. Soundex, which is built-in to SQL, isn\u2019t much use because it was developed for hand-coding, before computers, and isn\u2019t discriminating enough.<\/p>\n
The sample word table has the metaphone stored with each word. This means that all you need to do is to find the metaphone for the word and search the metaphone column.<\/p>\n
Lets return to our extreme example from the introduction.<\/p>\n
SELECT COALESCE(words.CanonicalVersion,words.word) AS candidate FROM words \r\n WHERE metaphone =dbo.metaphone('sossyjez')<\/pre>\n![](\"https:\/\/www.red-gate.com\/simple-talk\/wp-content\/uploads\/2017\/02\/word-image-18.png\")
<\/p>\nWe aren\u2019t always that lucky in getting just one candidate that matches. If we” by the same technique:<\/p>\n
SELECT COALESCE(words.CanonicalVersion,words.word) AS candidate FROM words \r\nWHERE metaphone =dbo.metaphone('tendancy')<\/pre>\n![](\"https:\/\/www.red-gate.com\/simple-talk\/wp-content\/uploads\/2017\/02\/word-image-19.png\")
<\/p>\nWe can get the most likely ones listed first in the candidate list by ordering the candidates by their edit difference:<\/p>\n
SELECT COALESCE(words.CanonicalVersion,words.word) AS candidate FROM words \r\n WHERE metaphone =dbo.metaphone('tendancy')\r\n ORDER by COALESCE(dbo.DamLev(word,'tendancy',3),4) --order by their ascending edit difference\r\n --but only up to three edit differences<\/pre>\n![](\"https:\/\/www.red-gate.com\/simple-talk\/wp-content\/uploads\/2017\/02\/word-image-20.png\")
<\/p>\nIn a simple test run, for 30 common misspellings, a fifth of the misspellings in total, the metaphone comparison showed a different metaphone for the common misspelling than for the correct spelling. Only three of these were misspellings that the edit-difference approach also failed to resolve correctly, but it means that it was quite likely to suggest the wrong word, if used by itself. In other words, the metaphone approach would be no good on its for resolving those common misspellings, but is still a good fall back for when the edit-difference approach fails to deliver.<\/p>\n
The general problem with the metaphone approach comes from the language itself in that a great number of common words sound alike if one eliminates the \u2018syllabic peak or nucleus\u2019, by making vowels all alike. As a Metaphone tries to represent the sounds, in some cases it is very discriminating, too discriminating in fact, and in other cases it would come up with fifty matches.<\/p>\n
- national spelling differences<\/strong> \u2013 yoghourt, yogurt and yoghurt<\/li>\n