4 ms·

BTW, here are some implementations of the algorithm they seem to have had trouble implementing, in java; https://github.com/universal-automata/liblevenshtein-j

BTW, here are some implementations of the algorithm they seem to have had trouble implementing, in java; https://github.com/universal-automata/liblevenshtein-java/tree/master/src https://github.com/universal-automata/liblevenshtein-java/tr... Note there is also an algorithm in the same paper to do the calculation without actually constructing the automata for it, which is even cooler There are other implementations of the algorithm, like Moman, etc. (I believe Lucene eventually used Moman as a reference implementation to implement it) The paper is certainly "not easy" to understand, but it's doable.

jules 11y ago
I think that is an algorithm from a different paper, namely this one: https://www.fmi.uni-sofia.bg/fmi/logic/theses/mitankin-en.pdf https://www.fmi.uni-sofia.bg/fmi/logic/theses/mitankin-en.pd... It looks like that is still quite a bit more complicated; 40 lines vs 40+ files ;-)
- DannyBee 11y ago
  That one may be (I think this is the later 2004 paper by one of the same authors), but Moman definitely is an implementation of the algorithm they did (it turns out they mention this in a different blog post).
unhammer 11y ago
You can do all Levenshtein edits while looking up in a (minimised, acyclic) FSA, which is fairly easy to implement[1], but means instead of having one FSA-state per index in the word as you look it up, you now have a set of states (each with their N_edits counter). [1] If you want transpositions to count as a single edit you need some hackery though.