How do you implement a “Did you mean”? [duplicate]

by

Actually what Google does is very much non-trivial and also at first counter-intuitive. They don’t do anything like check against a dictionary, but rather they make use of statistics to identify “similar” queries that returned more results than your query, the exact algorithm is of course not known.

There are different sub-problems to solve here, as a fundamental basis for all Natural Language Processing statistics related there is one must have book: Foundation of Statistical Natural Language Processing.

Concretely to solve the problem of word/query similarity I have had good results with using Edit Distance, a mathematical measure of string similarity that works surprisingly well. I used to use Levenshtein but the others may be worth looking into.

Soundex – in my experience – is crap.

Actually efficiently storing and searching a large dictionary of misspelled words and having sub second retrieval is again non-trivial, your best bet is to make use of existing full text indexing and retrieval engines (i.e. not your database’s one), of which Lucene is currently one of the best and coincidentally ported to many many platforms.

More Related Contents:

  1. What are some simple NLP projects that a CS undergrad can try implementing? [closed]
  2. Detecting syllables in a word
  3. Stemmers vs Lemmatizers
  4. How do I do word Stemming or Lemmatization?
  5. How do I open multiple instances of Visual Studio Code?
  6. Anyone know of some good Word Sense Disambiguation software? [closed]
  7. What is the difference between lemmatization vs stemming?
  8. How to use Bert for long text classification?
  9. OpenAI GPT-3 API: How do I make sure answers are from a customized (fine-tuning) dataset?
  10. How to use Stanford Parser in NLTK using Python
  11. Calculate cosine similarity given 2 sentence strings
  12. How to compute the similarity between two text documents?
  13. How does the Google “Did you mean?” Algorithm work? [closed]
  14. Creating a new corpus with NLTK
  15. Python NLTK pos_tag not returning the correct part-of-speech tag
  16. How can I split multiple joined words?
  17. Stopword removal with NLTK
  18. How to determine the language of a piece of text?
  19. Convert words between verb/noun/adjective forms
  20. How to read values from numbers written as words?
  21. NLTK Named Entity recognition to a Python list
  22. Is there an algorithm that tells the semantic similarity of two phrases
  23. How do I tokenize a string sentence in NLTK?
  24. How to train the Stanford NLP Sentiment Analysis tool
  25. Saving nltk drawn parse tree to image file
  26. Creating a custom categorized corpus in NLTK and Python
  27. TreeTagger installation successful but cannot open .par file
  28. Using my own corpus instead of movie_reviews corpus for Classification in NLTK
  29. Fast n-gram calculation
  30. Using the Python NLTK (2.0b5) on the Google App Engine

Leave a Comment