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

This was a really great series. It's a shame the author didn't continue.

I love blogs like this. Some people are really good at hitting that sweet spot of explaining things in a way that mixes theory with application in such a way that the insight becomes easier to grok.

Reg "raganwald" Braithwaite's blog is another one:

http://raganwald.com/

It is a link to the set of all posts in the "Damn Cool Algorithms" series