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...
Autor principal: | |
---|---|
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 |