Almost Linear Size Edit Distance Sketch

Michal Koucký, Michael Saks

Edit distance is an important measure of string similarity. It counts the number of insertions, deletions and substitutions one has to make to a string $x$ to get a string $y$. In…