Approximate string matching with address bit errors

A string S ∈ Σ m can be viewed as a set of pairs S = { ( σ i, i ): i ∈ { 0, …, m − 1 } }. We consider approximate pattern matching problems arising from the setting where errors are introduced to the location component ( i ), rather than the more traditional setting, where errors are introduced into the content itself ( σ i ). In this paper, we consider the case where bits of i may be erroneously flipped, either in a consistent or transient manner. We formally define the corresponding approximate pattern matching problems, and provide efficient algorithms for their resolution, while introducing some novel techniques.

Authors

• Amihood Amir
• Yonatan Aumann Bar-Ilan University
• Oren Kapah
• Avivit Levy
• Ely Porat

Keywords

• Approximate string matching
• Address errors
• Strings rearrangement metrics