Approximate string matching with stuck address bits

A string S ∈ Σ m can be viewed as a set of pairs { ( s i, i ) ∣ s i ∈ S, i ∈ { 0, …, m − 1 } }. We follow the recent work on pattern matching with address errors and 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 to the content itself ( s i ). Specifically, we continue the work on string matching in the presence of address bit errors. In this paper, we consider the case where bits of i may be stuck, either in a consistent or transient manner. We formally define the corresponding approximate pattern matching problems, and provide efficient algorithms for their resolution.

Authors

• Amihood Amir
• Estrella Eisenberg
• Orgad Keller
• Avivit Levy
• Ely Porat

Keywords

• Pattern matching
• String rearrangement metrics
• Approximate string matching
• Address errors