EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Computable Bounds and Monte Carlo Estimates of the Expected Edit Distance

Gianfranco Bilardi, Michele Schimd

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →