10 ms·

> Problem statement: the Levenshtein distance is a string metric for measuring the difference between two sequences Another variant is "I have a bunch of words

by Radim 5y ago

> Problem statement: the Levenshtein distance is a string metric for measuring the difference between two sequences Another variant is "I have a bunch of words (a dictionary) and one query word, and want to find all words from the dictionary that are close to the query word". This leads to another interesting class of problems, because you can do clever things where you precompute search structures (e.g. Levenshtein automata [0], [1]) from the dictionary. The similarity queries then run (much) faster. In production, performance matters. We recently merged a PR like that into Gensim [2]. This gave a ~1,500x speed-up compared to naively comparing all pairwise strings with Levenshtein distance. A difference between the training step running for months (=unusable) and minutes. [0] http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levensht... [1] Mihov, Stoyan & Schulz, Klaus. (2004). Fast Approximate Search in Large Dictionaries: https://www.aclweb.org/anthology/J04-4003.pdf https://www.aclweb.org/anthology/J04-4003.pdf [2] https://github.com/RaRe-Technologies/gensim/pull/3146 https://github.com/RaRe-Technologies/gensim/pull/3146

CornCobs 5y ago
Yea pairwise string matching for problems like record linkage is O(n^2) and is really infeasible for larger data. I once had to deal with a problem like this (matching business entity names against a large database) and ended up preprocessing the names into vectors of trigram (3-letter groups) counts, performing TF-IDF on the trigrams and then taking cosine similarity (which is simply matrix multiplication which though O(mnp) is much faster) The new solution also gave speedups in the 1000-2000x ballpark and had some nice properties: 1. Inverse document frequency naturally filtered out less important "mispellings" (e.g. PTE LTD vs PRIVATE LIMITED) 2. Trigrams maintain order within words but are less concerned about order between words, which happened to matter less in names
- schlupa 5y ago
  That's similar to what I do on our translation memory at the Commission. The issue we have is that we search for sentences, not words and the medium length of sentences in the database is around 120 characters and we have around 1.5 billion sentences in the database. A pairwise Levenshtein would be completely impossible as added to that we have to take care of replaceables in the segments (dates, numbers, months, weekdays, etc). To accelerate the search we use fuzzy keys which are trigram counts based and have them organized in a ternary tree. For the fuzzy distance, a simple difference calculation between 2 fuzzy keys is close enough to Levenhstein distance that we don't need more fancy metrics (for short sentences it is relatively bad but short sentences are mostly irrelevant for translation memories). Our fuzzy index reduces our search space for the Levenshtein distance calculation by 4 to 5 order of magnitudes (a sentence search is done on a space of 100K-300K sentences, after filtering the number of candidates rarely go beyond 100).
  - CornCobs 5y ago
    Interesting! What I noticed when approaching the problem was that there is quite little information on scaling up. I also don't think there are good out-of-the-box solutions covering a wide range of use cases. Dedup (basically cross-product) and linkage (highly dependent on the relative sizes of your search set and backing data) have very different optimizations when your data is large
fishmaster 5y ago
There's a quite amusing blog post about implementing the automaton for Lucene: http://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is-100-times-faster.html http://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is... As an aside, I know one of the authors of the original paper personally. Quite interesting guy, and the remark about the paper being "nearly unintelligible" is fitting.
- Radim 5y ago
  Dramatic post ;) It'd be interesting to see concrete benchmarks of the Lucene implementation, on some public dataset we could try outside of Lucene too. Btw I didn't find the Schulz & Mihov paper that cryptic. You can check its implementation in Python [0], pretty straightforward IMO. But I should note that in the end, we chose a simpler approach: the FastSS index. FastSS bypasses constructing / intersecting Levenshtein automata altogether, and is super fast [1]. [0] https://github.com/antoinewdg/pyffs https://github.com/antoinewdg/pyffs [1] Boytsov, Leonid. (2011). Indexing methods for approximate dictionary searching: Comparative analysis. http://boytsov.info/pubs/sisap2012.pdf http://boytsov.info/pubs/sisap2012.pdf

by Radim 5y ago

CornCobs 5y ago

Yea pairwise string matching for problems like record linkage is O(n^2) and is really infeasible for larger data. I once had to deal with a problem like this (matching business entity names against a large database) and ended up preprocessing the names into vectors of trigram (3-letter groups) counts, performing TF-IDF on the trigrams and then taking cosine similarity (which is simply matrix multiplication which though O(mnp) is much faster) The new solution also gave speedups in the 1000-2000x ballpark and had some nice properties: 1. Inverse document frequency naturally filtered out less important "mispellings" (e.g. PTE LTD vs PRIVATE LIMITED) 2. Trigrams maintain order within words but are less concerned about order between words, which happened to matter less in names

schlupa 5y ago
That's similar to what I do on our translation memory at the Commission. The issue we have is that we search for sentences, not words and the medium length of sentences in the database is around 120 characters and we have around 1.5 billion sentences in the database. A pairwise Levenshtein would be completely impossible as added to that we have to take care of replaceables in the segments (dates, numbers, months, weekdays, etc). To accelerate the search we use fuzzy keys which are trigram counts based and have them organized in a ternary tree. For the fuzzy distance, a simple difference calculation between 2 fuzzy keys is close enough to Levenhstein distance that we don't need more fancy metrics (for short sentences it is relatively bad but short sentences are mostly irrelevant for translation memories). Our fuzzy index reduces our search space for the Levenshtein distance calculation by 4 to 5 order of magnitudes (a sentence search is done on a space of 100K-300K sentences, after filtering the number of candidates rarely go beyond 100).
- CornCobs 5y ago
  Interesting! What I noticed when approaching the problem was that there is quite little information on scaling up. I also don't think there are good out-of-the-box solutions covering a wide range of use cases. Dedup (basically cross-product) and linkage (highly dependent on the relative sizes of your search set and backing data) have very different optimizations when your data is large

fishmaster 5y ago

There's a quite amusing blog post about implementing the automaton for Lucene: http://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is-100-times-faster.html http://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is... As an aside, I know one of the authors of the original paper personally. Quite interesting guy, and the remark about the paper being "nearly unintelligible" is fitting.

Radim 5y ago
Dramatic post ;) It'd be interesting to see concrete benchmarks of the Lucene implementation, on some public dataset we could try outside of Lucene too. Btw I didn't find the Schulz & Mihov paper that cryptic. You can check its implementation in Python [0], pretty straightforward IMO. But I should note that in the end, we chose a simpler approach: the FastSS index. FastSS bypasses constructing / intersecting Levenshtein automata altogether, and is super fast [1]. [0] https://github.com/antoinewdg/pyffs https://github.com/antoinewdg/pyffs [1] Boytsov, Leonid. (2011). Indexing methods for approximate dictionary searching: Comparative analysis. http://boytsov.info/pubs/sisap2012.pdf http://boytsov.info/pubs/sisap2012.pdf