@burntsushi wrote a nice blog post about (Levenshtein) automata and a Rust crate:
https://blog.burntsushi.net/transducers/#levenshtein-automata https://github.com/BurntSushi/fst
I also made a Java library for dictionary/Levenshtein automata:
https://github.com/danieldk/dictomaton
Sadly, it is largely unmaintained since I left my last (and only) full-time Java job ~ five years ago.
While we’re on this topic, can someone explain to me why laziness makes this Haskell implementation in the bottom here so fast? It’s really fast for comparing [1..1000] with [2..1001], which most implementations are very slow with.
[1..1000]
[2..1001]
https://wiki.haskell.org/Edit_distance
I’ve wondered how to reimplement this in a different language, but I can’t understand enough Haskell to translate it.
@burntsushi wrote a nice blog post about (Levenshtein) automata and a Rust crate:
https://blog.burntsushi.net/transducers/#levenshtein-automata https://github.com/BurntSushi/fst
I also made a Java library for dictionary/Levenshtein automata:
https://github.com/danieldk/dictomaton
Sadly, it is largely unmaintained since I left my last (and only) full-time Java job ~ five years ago.
While we’re on this topic, can someone explain to me why laziness makes this Haskell implementation in the bottom here so fast? It’s really fast for comparing
[1..1000]with[2..1001], which most implementations are very slow with.https://wiki.haskell.org/Edit_distance
I’ve wondered how to reimplement this in a different language, but I can’t understand enough Haskell to translate it.