Computable Bounds and Monte Carlo Estimates of the Expected Edit Distance
Information · 14.07.2026 · 17 (7) · 685
DOI: 10.3390/info17070685 ↗Kurz gefasst
Fachartikel in der Zeitschrift Information, online erschienen am 14.07.2026. Verfasst von Gianfranco Bilardi und 1 weiteren Autor:innen. Die Arbeit nennt 39 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: European Union, Ministry of University and Research, University of Padova.
Abstract (Originalsprache)
The edit distance is a metric of dissimilarity between strings, widely applied in computational biology, speech recognition, and machine learning. Let ek(n) denote the average edit distance between random, independent strings of n characters from an alphabet of size k. This paper is concerned with the efficient computation of αk(n)=ek(n)/n as well as of αk=limn→∞αk(n). It is shown that αk(n)−Θ(logn/n)≤αk≤αk(n) and that αk is computable. An algorithm for the exact computation of αk(n) is presented with running time T=O(n2kmin(3n,kn)) thus, of limited practical use. An analysis of Monte Carlo estimates, based on McDiarmid’s inequality, shows how αk(n) can be evaluated with good accuracy and high confidence level, for rather large values of n. In particular, 99.9% confidence intervals of width approximately 10−2 are obtained for αk. An efficiently computable lower bound βk* to αk is derived, with limk→∞βk*=1. For k greater than a few dozens, significant bounds on αk can be obtained faster via βk* than by statistical methods. The above techniques yield improvements on most previous numerical estimates as well as results for alphabet sizes and string lengths not reported before.
Förderung
- European Union
- Ministry of University and Research
- University of Padova
- IBM
Zitieren
APA
Bilardi, G., & Schimd, M. (2026). Computable Bounds and Monte Carlo Estimates of the Expected Edit Distance. Information, 17(7), 685. https://doi.org/10.3390/info17070685
Vancouver
Bilardi G, Schimd M. Computable Bounds and Monte Carlo Estimates of the Expected Edit Distance. Information. 2026;17(7):685. doi:10.3390/info17070685
BibTeX
@article{Bilardi2026,
author = {Bilardi, Gianfranco and Schimd, Michele},
title = {Computable Bounds and Monte Carlo Estimates of the Expected Edit Distance},
journal = {Information},
year = {2026},
volume = {17},
number = {7},
pages = {685},
doi = {10.3390/info17070685}
}
EUVIMED