© Thomas Mailund 2020
T. MailundString Algorithms in Chttps://doi.org/10.1007/978-1-4842-5920-7_5

5. Approximate search

Thomas Mailund1 
Aarhus N, Denmark

We are not always satisfied with finding locations where a pattern matches exactly. Sometimes we could, for example, want to find all occurrences of a word and include occurrences where the word is misspelt. Searching for “almost matches” is called approximate search. We will look at a suffix tree–based approach and a BWT-based approach. Considering the experimental results from the last chapter, it might seem odd to consider a BWT approach instead of a suffix array approach, but there is a reason for this: we can add a trick to the BWT approach to make it faster than the suffix tree solution ...

Get String Algorithms in C: Efficient Text Representation and Search now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.