An Almost-Linear Approximation Scheme for Edit Distance

We give a uniform randomized approximation scheme for unit-cost edit distance. For every fixed rational $\epsilon \in (0,1)$, it estimates the distance between arbitrary explicitly stored strings of total length N within a factor $1+\epsilon$ with probability at least 2/3, in worst-case expected time $N^{1+o(1)}$ on a logarithmic-word RAM. The algorithm supports polynomially bounded integer alphabets and returns zero deterministically on equal strings.