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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.