Approximating general metric distances between a pattern and a text

MaRDI QIDQ3579401zbMATH OpenFDO

Authors Ely Porat, Klim Efremenko

Publication date 6 August 2010

Full work available at URL https://arxiv.org/abs/0802.1427

zbMATH Keywords

approximation algorithmpatternfinite alphabetcalculation of sum of distances between the symbols of patterns and the symbols of substrings

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Randomized algorithms (68W20) Information theory (general) (94A15) Combinatorics on words (68R15)

Recommendations

• Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics
• Approximate matching in the \(L_{\infty }\) metric
• Combinatorial Pattern Matching
• A simple algorithm for approximating the text-to-pattern Hamming distance
• Towards unified approximate pattern matching for Hamming and \(L_1\) distance

Cited in

(11)

• Order-preserving matching
• Combinatorial Pattern Matching
• Approximating Approximate Pattern Matching
• Mismatch sampling
• Order-preserving pattern matching indeterminate strings
• Recent advances in text-to-pattern distance algorithms
• scientific article; zbMATH DE number 3881896 (Why is no real title available?)
• Order-preserving pattern matching indeterminate strings
• A simple algorithm for approximating the text-to-pattern Hamming distance
• Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics
• Approximate matching in the \(L_{\infty }\) metric

This page was built for publication: Approximating general metric distances between a pattern and a text

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3579401)