Levenshtein Automata (2010)

http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata

by tosh • 8 years ago

172 11 8 years ago

blog.notdot.net

iamgopal• 8 years ago

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.

billwashere• 8 years ago

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

PavlikPaja• 8 years ago

It's the same site.

tosh• 8 years ago

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

michaelmior• 8 years ago

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

vanderZwan• 8 years ago

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/

btown• 8 years ago

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!

mgliwka• 8 years ago

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

dang• 8 years ago

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

dvirsky• 8 years ago

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...

cmyr• 8 years ago

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

Levenshtein Automata (2010)

Related Stories