Chapter 4. Fuzzy string matching
In this chapter
- Finding fuzzy string matches with prefixes and n-grams
- Prefix matching used to perform query type-ahead
- N-gram matching and string matching applied in query spell-checking
- String matching techniques applied in a record matching task
One of the most difficult aspects of dealing with text is the approximate nature of many of the tasks you’d like to perform. Whether this is the relevance of search results or the clustering of similar items, what exactly is meant by relevance or similarity is difficult to specify in a way that’s both intuitive and specific. In language, we encounter this phenomenon all the time, typically with little consideration. For example, you’ll hear a new band described as, “They’re like Radiohead, only different.” Typically you just nod, taking whatever interpretation that comes to mind, not considering the vast range of other potential and valid interpretations.