LIPIcs.CPM.2021.2.pdf
- Filesize: 321 kB
- 1 pages
Document
Computing Edit Distance (Invited Talk)
Author
Michal Koucký 
-
Part of:
Volume:
32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Annual Symposium on Combinatorial Pattern Matching (CPM) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-06-30
File
Document Identifiers
Author Details
Cite AsGet BibTex
Michal Koucký. Computing Edit Distance (Invited Talk). In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CPM.2021.2
https://doi.org/10.4230/LIPIcs.CPM.2021.2
Abstract
The edit distance (or Levenshtein distance) between two strings x, y is the minimum number of character insertions, deletions, and substitutions needed to convert x into y. It has numerous applications in various fields from text processing to bioinformatics so algorithms for edit distance computation attract lot of attention. In this talk I will survey recent progress on computational aspects of edit distance in several contexts: computing edit distance approximately, sketching and computing it in streaming model, exchanging strings in communication complexity model, and building error correcting codes for edit distance. I will point out many problems that are still open in those areas.
Subject Classification
ACM Subject Classification
- Theory of computation → Pattern matching
Keywords
- edit distance
- streaming algorithms
- approximation algorithms
- sketching
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads