Fast and Easy Levenshtein distance using a Trie (2011)

ssebg 4 days ago 17 commentsRead Article on stevehanov.ca

HI version is available. Content is displayed in original English for accuracy.

⚡ Community Insights

Discussion Sentiment

67% Positive

Analyzed from 610 words in the discussion.

Discussion (17 Comments)Read Original on HackerNews

Mithriil•28 minutes ago

The Google's n-gram dataset link is outdated. You can get them here: https://storage.googleapis.com/books/ngrams/books/datasetsv3...

kristianp•about 5 hours ago

The author also has an interesting discussion of Succinct Data Structures at https://stevehanov.ca/blog/succinct-data-structures-cramming...

dvh•about 8 hours ago

I made myself plugin that shows new news in wikipedia's current event page and I was using levenshtein originally (they often edit couple of words in article over span of few days so I compare each new article with previous ones for similarity) but after few days it became too slow (~20s) because O(m*n), so I switched to sorensen-dice instead which is O(m+n) and it's much faster and works very similar way, even tho they do slightly different thing.

kelseydh•about 7 hours ago

I needed a fuzzy string matching algorithm for finding best name matches among a candidate list. Considered Normalized Levenshtein Distance but ended up using Jaro-Winkler. I'm curious if anybody has good resources on when to use each fuzzy string matching algorithm and when.

leeoniya•about 1 hour ago

Levenshtein distance is often a poor way to fuzzy match or rank. i suspect that in js, even the trie approach would incur significant GC/alloc thrashing or cost of building a huge trie index.

i tried fuzzy matching using a cleverly-assembled regexp approach which works surprisingly well: https://github.com/leeoniya/uFuzzy

vintermann•about 4 hours ago

Levenshtein distance is rarely the similarity measure you need. Words usually mean something, and it's usually the distance in meaning you need.

As usual, examples from my genealogy hobby: many sites allow you to upload your family tree as a gedcom file and compare it to other people's trees or a public tree. Most of these use Levenshtein distance on names to judge similarity, and it's terrible. Anne Nilsen and Anne Olsen could be the same person, right? No!! These tools are unfortunately useless to me because they give so many false positives.

These days, an embedding model is the way to go. Even a small, bad embedding model is better than Levenshtein distance if you care about the meaning of the string.

jppittma•about 2 hours ago

It depends on if or not you're trying to correct for typos, or do something semantic. Also, embedding distance is much much more expensive.

RobinL•about 4 hours ago

There's a section in the docs of our FOSS record linkage software that covers this: https://moj-analytical-services.github.io/splink/topic_guide...

localhoster•about 7 hours ago

This article surface every once in a while, and I love it. What the author suggests is very clever. I have implemented an extended version of that in Go as an experiment. Instead of using a trie, I used a radix tree. Functions the same, but it's much more compressed (and faster).

fergie•about 8 hours ago

Very cool and satisfying.

gregman1•about 7 hours ago

2011

saagarjha•about 7 hours ago

Added

consomida•about 5 hours ago

Using a trie to calculate Levenshtein distance is such a clever optimization. Clear explanation and practical examples make it easy to understand and implement

sminchev•about 4 hours ago

A few years ago, before the AI boom I needed to create a de-duplication app, as a PoC. To be able to compare fast millions of contact data and to search for the duplicates. The clients' approach was taking, in best case, a day to compare everything and generate a report.

What we do was a combination of big data engine, like Apache Spark, a few comparison algorithms like Levenshtein, and ML. AI was not treated as an option to do such things at all! :)

What we did was to use Apache Spark to apply the static algorithms, if we get confident results like less than 10% equality or more than 90% of equality, we treated those as sure signs for records be duplicated or not. Records that were somewhere in the middle, we sent to Machine Learning libraries for analysis. Of course some education was needed for statistical basis. And hard to be automatically analyzed, we placed in a report for human touch ;)

We got relatively good results. It was a Scala based app, as far as I remember :)

Now with AI, it is much more easy... And boring! :D No complexities, no challenges.

arnorhs•about 4 hours ago

That's an interesting story, but I'm really at a loss for how this relates to the post you are commenting on.

sminchev•about 2 hours ago

Thank you for your question. At least there is one person who shares opinion, when down-voting. This is good, because I know what I did wrong, and I highly respect any respectable feedback ;)

I really hate, when people down-vote, without giving any feedback what they don't like.

Levenshtein, in combination with Machine Learning and big data engines, like Apache Sparks, can do a good job comparing content as well ;)

Wanted to share another approach, and ideas to people who are interested in comparing strings, doing fuzzy searches, and searching for duplicated content.

devmor•about 2 hours ago

I think they just forgot to link their train of thought. I have also used Levenshtein distance for deduplication comparisons so I can guess where the story came from.