Upper bounds on the average edit distance between two random strings
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929437149233152 |
|---|---|
| author | Rosenfeld, Matthieu |
| author_facet | Rosenfeld, Matthieu |
| contents | We study the average edit distance between two random strings. More precisely, we adapt a technique introduced by Lueker in the context of the average longest common subsequence of two random strings to improve the known upper bound on the average edit distance. We improve all the known upper bounds for small alphabets. We also provide a new implementation of Lueker technique to improve the lower bound on the average length of the longest common subsequence of two random strings for all small alphabets of size other than $2$ and $4$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_18113 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Upper bounds on the average edit distance between two random strings Rosenfeld, Matthieu Combinatorics Discrete Mathematics We study the average edit distance between two random strings. More precisely, we adapt a technique introduced by Lueker in the context of the average longest common subsequence of two random strings to improve the known upper bound on the average edit distance. We improve all the known upper bounds for small alphabets. We also provide a new implementation of Lueker technique to improve the lower bound on the average length of the longest common subsequence of two random strings for all small alphabets of size other than $2$ and $4$. |
| title | Upper bounds on the average edit distance between two random strings |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2407.18113 |