Approximating general metric distances between a pattern and a text

zbMATH Open1192.68499arXiv0802.1427MaRDI QIDQ3579401FDOQ3579401

Authors: Ely Porat, Klim Efremenko 

Publication date: 6 August 2010

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

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

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)

Cited In (11)

• Order-preserving pattern matching indeterminate strings
• Recent advances in text-to-pattern distance algorithms
• Order-preserving pattern matching indeterminate strings
• Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics
• Approximating Approximate Pattern Matching
• Approximate matching in the \(L_{\infty }\) metric
• Mismatch sampling
• Title not available (Why is that?)
• Order-preserving matching
• A simple algorithm for approximating the text-to-pattern Hamming distance
• Combinatorial Pattern Matching

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)