Faster Approximate Pattern Matching: A Unified Approach
Faster Approximate Pattern Matching: A Unified Approach
复制标题
更快的近似模式匹配：统一方法
DOI：
10.1109/focs46700.2020.00095
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Philip Wellnitz
中科院分区：
文献类型：
--
作者：
P. Charalampopoulos;Tomasz Kociumaka;Philip Wellnitz
In the approximate pattern matching problem, given a text <tex>$T$</tex>, a pattern <tex>$P$</tex>, and a threshold <tex>$k$</tex>, the task is to find (the starting positions of) all substrings of <tex>$T$</tex> that are at distance at most <tex>$k$</tex> from <tex>$P$</tex>. We consider the two most fundamental string metrics: Under the Hamming distance, we search for substrings of <tex>$T$</tex> that have at most <tex>$k$</tex> mismatches with <tex>$P$</tex>, while under the edit distance, we search for substrings of <tex>$T$</tex> that can be transformed to <tex>$P$</tex> with at most <tex>$k$</tex> edits. Exact occurrences of <tex>$P$</tex> in <tex>$T$</tex> have a very simple structure: If we assume for simplicity that <tex>$\vert P\vert < \vert T\vert \leq {{}^{3}}/_{2}\vert P\vert$</tex> and that <tex>$P$</tex> occurs both as a prefix and as a suffix of <tex>$T$</tex>, then both <tex>$P$</tex> and <tex>$T$</tex> are periodic with a common period. However, an analogous characterization for occurrences with up to <tex>$k$</tex> mismatches was proved only recently by Bringmann et al. [SODA'19]: Either there are <tex>$\mathcal{O}(k^{2}) k$</tex>-mismatch occurrences of <tex>$P$</tex> in <tex>$T$</tex>, or both <tex>$P$</tex> and <tex>$T$</tex> are at Hamming distance <tex>$\mathcal{O}(k)$</tex> from strings with a common string period of length <tex>$\mathcal{O}(m/k)$</tex>. We tighten this characterization by showing that there are <tex>$\mathcal{O}(k) k$</tex>-mismatch occurrences in the non-periodic case, and we lift it to the edit distance setting, where we tightly bound the number of <tex>$k$</tex>-edit occurrences by <tex>$\mathcal{O}(k^{2})$</tex> in the non-periodic case. Our proofs are constructive and let us obtain a unified framework for approximate pattern matching for both considered distances. In particular, we provide meta-algorithms that only rely on a small set of primitive operations. We showcase the generality of our meta-algorithms with results for the fully compressed setting, the dynamic setting, and the standard setting.
In the approximate pattern matching problem, given a text <tex>$T$</tex>, a pattern <tex>$P$</tex>, and a threshold <tex>$k$</tex>, the task is to find (the starting positions of) all substrings of <tex>$T$</tex> that are at distance at most <tex>$k$</tex> from <tex>$P$</tex>. We consider the two most fundamental string metrics: Under the Hamming distance, we search for substrings of <tex>$T$</tex> that have at most <tex>$k$</tex> mismatches with <tex>$P$</tex>, while under the edit distance, we search for substrings of <tex>$T$</tex> that can be transformed to <tex>$P$</tex> with at most <tex>$k$</tex> edits. Exact occurrences of <tex>$P$</tex> in <tex>$T$</tex> have a very simple structure: If we assume for simplicity that <tex>$\vert P\vert < \vert T\vert \leq {{}^{3}}/_{2}\vert P\vert$</tex> and that <tex>$P$</tex> occurs both as a prefix and as a suffix of <tex>$T$</tex>, then both <tex>$P$</tex> and <tex>$T$</tex> are periodic with a common period. However, an analogous characterization for occurrences with up to <tex>$k$</tex> mismatches was proved only recently by Bringmann et al. [SODA'19]: Either there are <tex>$\mathcal{O}(k^{2}) k$</tex>-mismatch occurrences of <tex>$P$</tex> in <tex>$T$</tex>, or both <tex>$P$</tex> and <tex>$T$</tex> are at Hamming distance <tex>$\mathcal{O}(k)$</tex> from strings with a common string period of length <tex>$\mathcal{O}(m/k)$</tex>. We tighten this characterization by showing that there are <tex>$\mathcal{O}(k) k$</tex>-mismatch occurrences in the non-periodic case, and we lift it to the edit distance setting, where we tightly bound the number of <tex>$k$</tex>-edit occurrences by <tex>$\mathcal{O}(k^{2})$</tex> in the non-periodic case. Our proofs are constructive and let us obtain a unified framework for approximate pattern matching for both considered distances. In particular, we provide meta-algorithms that only rely on a small set of primitive operations. We showcase the generality of our meta-algorithms with results for the fully compressed setting, the dynamic setting, and the standard setting.