Cargando…

Recent Advances in Text-to-Pattern Distance Algorithms

Computing text-to-pattern distances is a fundamental problem in pattern matching. Given a text of length n and a pattern of length m, we are asked to output the distance between the pattern and every n-substring of the text. A basic variant of this problem is computation of Hamming distances, that i...

Descripción completa

Detalles Bibliográficos
Autor principal: Uznański, Przemysław
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7309496/
http://dx.doi.org/10.1007/978-3-030-51466-2_32
_version_ 1783549219162816512
author Uznański, Przemysław
author_facet Uznański, Przemysław
author_sort Uznański, Przemysław
collection PubMed
description Computing text-to-pattern distances is a fundamental problem in pattern matching. Given a text of length n and a pattern of length m, we are asked to output the distance between the pattern and every n-substring of the text. A basic variant of this problem is computation of Hamming distances, that is counting the number of mismatches (different characters aligned), for each alignment. Other popular variants include [Formula: see text] distance (Manhattan distance), [Formula: see text] distance (Euclidean distance) and general [Formula: see text] distance. While each of those problems trivially generalizes classical pattern-matching, the efficient algorithms for them require a broader set of tools, usually involving both algebraic and combinatorial insights. We briefly survey the history of the problems, and then focus on the progress made in the past few years in many specific settings: fine-grained complexity and lower-bounds, [Formula: see text] multiplicative approximations, k-bounded relaxations, streaming algorithms, purely combinatorial algorithms, and other recently proposed variants.
format Online
Article
Text
id pubmed-7309496
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-73094962020-06-23 Recent Advances in Text-to-Pattern Distance Algorithms Uznański, Przemysław Beyond the Horizon of Computability Article Computing text-to-pattern distances is a fundamental problem in pattern matching. Given a text of length n and a pattern of length m, we are asked to output the distance between the pattern and every n-substring of the text. A basic variant of this problem is computation of Hamming distances, that is counting the number of mismatches (different characters aligned), for each alignment. Other popular variants include [Formula: see text] distance (Manhattan distance), [Formula: see text] distance (Euclidean distance) and general [Formula: see text] distance. While each of those problems trivially generalizes classical pattern-matching, the efficient algorithms for them require a broader set of tools, usually involving both algebraic and combinatorial insights. We briefly survey the history of the problems, and then focus on the progress made in the past few years in many specific settings: fine-grained complexity and lower-bounds, [Formula: see text] multiplicative approximations, k-bounded relaxations, streaming algorithms, purely combinatorial algorithms, and other recently proposed variants. 2020-06-24 /pmc/articles/PMC7309496/ http://dx.doi.org/10.1007/978-3-030-51466-2_32 Text en © Springer Nature Switzerland AG 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
Uznański, Przemysław
Recent Advances in Text-to-Pattern Distance Algorithms
title Recent Advances in Text-to-Pattern Distance Algorithms
title_full Recent Advances in Text-to-Pattern Distance Algorithms
title_fullStr Recent Advances in Text-to-Pattern Distance Algorithms
title_full_unstemmed Recent Advances in Text-to-Pattern Distance Algorithms
title_short Recent Advances in Text-to-Pattern Distance Algorithms
title_sort recent advances in text-to-pattern distance algorithms
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7309496/
http://dx.doi.org/10.1007/978-3-030-51466-2_32
work_keys_str_mv AT uznanskiprzemysław recentadvancesintexttopatterndistancealgorithms