Dotted Suffix Trees A Structure for Approximate Text Indexing

摘要

In this work, the problem we address is text indexing for approximate matching. Given a text Τ which undergoes some preprocessing to generate an index, we can later query this index to identify the places where a string occurs up to a certain number of errors κ(edition distance). The indexing structure occupies space O(n log~k n) in the average case, independent of alphabet size. This structure can be used to report the existence of a match with k errors in O(3~km~(k+1)) and to report the occurrences in O(3~km~(k+1) + ed) time, where m is the length of the pattern and ed and the number of matching edit scripts. The construction of the structure has time bound by O(kN|∑|), where N is the number of nodes in the index and |∑| the alphabet size.