# Approximating the Levenshtein distance between two binary strings using the Fast Walsh-Hadamard Transform

I have come up with a simple technique of approximating the Levenshtein distance between two binary strings using the fast Walsh–Hadamard transform: given two binary strings $$a,b$$ with Walsh–Hadamard transforms $$\hat{a},\hat{b}$$ of length $$n_a,n_b$$, I propose to approximate the Levenshtein distance by $$\max \{ |\hat{a}(i)-\hat{b}(i)| : 0 \leq i \leq \min(n_a,n_b)-1 \},$$ This gives good results when $$a,b$$ are drawn at random from the range $$0,\ldots,199999$$: I seem to be getting a mean error of around 1.3 over 20000 trials.

Just wanted to ask if all this is actually helping with the complexity of the algorithm or not. The Walsh–Hadamard transform can be computed in $$O(n\log n)$$ time, and the rest is linear time.

• The "left alignment of pairs" to take the difference of looks arbitrary - why not centre? Jan 10 at 11:40
• Yeah it's arbitrary for now. Centering is good idea albeit a bit more complicated to implement. Jan 10 at 13:28
• Tried centering; it gives worse results. Jan 10 at 13:48
• Food for thought. Jan 10 at 13:48