2010 | OriginalPaper | Buchkapitel
Approximate String Matching with Stuck Address Bits
verfasst von : Amihood Amir, Estrella Eisenberg, Orgad Keller, Avivit Levy, Ely Porat
Erschienen in: String Processing and Information Retrieval
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A string
S
∈ Σ
m
can be viewed as a set of pairs
$\{ (s_i , i) \mid s_i\in S,\ i\in \{ 0,\ldots, 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.