A Black Box for Online Approximate Pattern Matching

R Clifford, Efremenko Klim, Porat Benny, Porat Ely

Research output: Contribution to journalArticle (Academic Journal)peer-review

11 Citations (Scopus)

Abstract

We present a deterministic black box solution for online approximate matching. Given a pattern of length m and a streaming text of length n that arrives one character at a time, the task is to report the distance between the pattern and a sliding window of the text as soon as the new character arrives. Our solution requires time for each input character, where T(n,m) is the total running time of the best offline algorithm. The types of approximation that are supported include exact matching with wildcards, matching under the Hamming norm, approximating the Hamming norm, k-mismatch and numerical measures such as the L 2 and L 1 norms. For these examples, the resulting online algorithms take O(log2 m), , O(log2 m/ε 2), , O(log2 m) and time per character respectively. The space overhead is O(m) which we show is optimal.
Translated title of the contributionA Black Box for Online Approximate Pattern Matching
Original languageEnglish
Pages (from-to)143 - 151
Number of pages9
JournalCombinatorial Pattern Matching
Volume5029/2008
DOIs
Publication statusPublished - 2008

Fingerprint

Dive into the research topics of 'A Black Box for Online Approximate Pattern Matching'. Together they form a unique fingerprint.

Cite this