<p>I'm looking for an efficient way (using PHP with a Mysql Database) to suggest alternative spelling for a query.</p>

<p>I know I can use services such as <a href="http://developer.yahoo.com/search/web/V1/spellingSuggestion.html" rel="nofollow noreferrer">Yahoo's Spelling Suggestion</a> but I want the suggestions to be based on what is currently available in the database. </p>

<p>For example: The user has to fill a form with a "City" field, and I want to make sure that everyone will use the same spelling for said city, (so I don't end up with people filling in "Pitsburgh" when what they mean is "Pittsburgh" ). </p>

<p>This was only an example but, basically I want to search what is already in the database for entries where the spelling is really close to what the user entered...</p>

<p>Any algorithm, tutorials or ideas on how to achieve this?</p>

[{'answer_id': 81060, 'author': 'perimosocordiae', 'author_id': 10601, 'author_profile': 'https://Stackoverflow.com/users/10601', 'pm_score': 1, 'selected': False, 'text': '<p>I would do it as the user types and suggest by prefix (ala Google Suggest). A <a href="http://en.wikipedia.org/wiki/Trie" rel="nofollow noreferrer" title="wiki article">trie</a> would be nice for this. It wouldn\'t help to correct misspelled first letters, but those are pretty rare.</p>\n'}, {'answer_id': 81098, 'author': 'Guido', 'author_id': 12388, 'author_profile': 'https://Stackoverflow.com/users/12388', 'pm_score': 0, 'selected': False, 'text': '<p>Please, take a look to the <a href="http://developer.yahoo.com/yui/autocomplete/" rel="nofollow noreferrer">Yahoo! UI Library Autocomplete Component</a>. I think it is just what you\'re looking for.  The section "Using DataSources" explains how to use different kind of data sources, including server side based ones like yours.</p>\n'}, {'answer_id': 81189, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 0, 'selected': False, 'text': '<p>Have a look at <a href="http://www.javascript-examples.com/autocomplete-demo/" rel="nofollow noreferrer">Javascript Examples</a> it lists 13 different autocompleting field code.</p>\n\n<p>I\'ve used something similar on one of my sites, I essentially have a div layer set up under the text box, as a user types this fires of an Ajax based HTTP request to my SQL query script which updates each letter they type. The div gets updated with any matching DB entries which the user can click on to select.</p>\n'}, {'answer_id': 81205, 'author': 'Matthias Winkelmann', 'author_id': 4494, 'author_profile': 'https://Stackoverflow.com/users/4494', 'pm_score': 1, 'selected': False, 'text': "<p>MySQL has a built-in function to find the Levenshtein edit distance, it's quite slow though. I'd use the auto-complete function offered above, or simply edit entries after-the-fact every week or so.</p>\n"}, {'answer_id': 81231, 'author': 'daniels', 'author_id': 9789, 'author_profile': 'https://Stackoverflow.com/users/9789', 'pm_score': 1, 'selected': False, 'text': '<p>Maybe this will help <a href="http://jquery.bassistance.de/autocomplete/demo/" rel="nofollow noreferrer">http://jquery.bassistance.de/autocomplete/demo/</a>\nIt uses JQuery (client side) and php (serverside).\nThe example feeds from an array but can be easily modified so it will use a MySQL database. </p>\n'}, {'answer_id': 81254, 'author': 'sven', 'author_id': 46, 'author_profile': 'https://Stackoverflow.com/users/46', 'pm_score': 1, 'selected': False, 'text': '<p>Spelling alternatives are often implemented by using the <a href="http://www.merriampark.com/ld.htm" rel="nofollow noreferrer">Levenshtein distance</a> between two words (the one the user typed, en the one inside, for example, your database)</p>\n\n<p>here is the pseudocode for the algorithm\n(<a href="http://en.wikipedia.org/wiki/Levenshtein_distance" rel="nofollow noreferrer">from wikipedia</a>):</p>\n\n<pre><code>int LevenshteinDistance(char s[1..m], char t[1..n])\n   // d is a table with m+1 rows and n+1 columns\n   declare int d[0..m, 0..n]\n\n   for i from 0 to m\n       d[i, 0] := i\n   for j from 0 to n\n       d[0, j] := j\n\n   for i from 1 to m\n       for j from 1 to n\n       {\n           if s[i] = t[j] then cost := 0\n                          else cost := 1\n           d[i, j] := minimum(\n                                d[i-1, j] + 1,     // deletion\n                                d[i, j-1] + 1,     // insertion\n                                d[i-1, j-1] + cost   // substitution\n                            )\n       }\n\n   return d[m, n]\n</code></pre>\n\n<p>and here you can find the <em>real</em> implementation for all sorts of languages: <a href="http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Levenshtein_distance" rel="nofollow noreferrer">http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Levenshtein_distance</a></p>\n'}, {'answer_id': 81840, 'author': 'Buzz', 'author_id': 13113, 'author_profile': 'https://Stackoverflow.com/users/13113', 'pm_score': 1, 'selected': False, 'text': '<p>I\'ve used the pspell <a href="http://uk.php.net/pspell" rel="nofollow noreferrer">http://uk.php.net/pspell</a> package to do this. Take the search term, check the spelling. If its not OK, PSPELL will make suggestions. </p>\n\n<p>You can even run the suggestions though your search, count the results, and then say: Your search for "foo" returned 0 results. Did you mean "baz" (12 results) or "bar" (3 result).</p>\n\n<p>If you are worried about performance, only do this when a search returns 0 results. </p>\n'}, {'answer_id': 243404, 'author': 'Oddthinking', 'author_id': 8014, 'author_profile': 'https://Stackoverflow.com/users/8014', 'pm_score': 0, 'selected': False, 'text': '<p>I believe <a href="http://en.wikipedia.org/wiki/Soundex" rel="nofollow noreferrer" title="WIkipedia explanation of SoundEx">SoundEx</a> is a better fit than Levenshtein distance.</p>\n\n<p>SoundEx is a function that produces a hash of a word/phrase based on the sound it would make in English. It is great for helping people who can\'t spell match the canonical spelling.</p>\n\n<p>I have used it very successfully to find when two people registered the same company in a database with slightly different variants on the name.</p>\n\n<p>SoundEx is built into MySql. Here is one tutorial on its <a href="http://www.madirish.net/?article=85" rel="nofollow noreferrer" title="Using SoundEx with MySQL">use</a>.</p>\n'}]
['https://Stackoverflow.com/questions/81021', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/14981/']