Levenshtein Automata (2010)

https://github.com/intel/hyperscan/ implements this along multiple regex matching and a pcre pattern compatible engine (chimera).

A really cool trick! FYI Elasticsearch implements this technique when you use the `fuzzy` query: https://www.elastic.co/guide/en/elasticsearch/guide/master/f... - but it's important to know about if you ever want to do this with in-memory or relational data!

I've implemented this a while ago as part of RediSearch and integrated into a Trie. This is a super powerful algorithm. https://github.com/RedisLabsModules/RediSearch/tree/master/s...

Another great post on this topic, by the other of ripgrep: https://blog.burntsushi.net/transducers/

Lots more at https://hn.algolia.com/?query=Levenshtein%20Automata%20point...

Nice post. 2010. Years back, this blog was started by Nick for app engine tutorials etc, as he was one of the first in Google app engine support, when he worked for Google. Time flies. Tons of other good posts on that blog.

Everyone this cool website gets posted I point them to this - http://blog.notdot.net/tag/damn-cool-algorithms