I like using levenshtein distance for building out bayseian networks. Its works well in conjunction with other distance/ similarity metrics that are better for continuous data.
I became intimately acquainted with Levenshtein's distance for my summer internship project, and have implemented it myself a few times for interviews. It was central to an event de-duplication system I built. Amazing how such a seemingly trivial idea can actually be a) non-trivial to implement and b) be so powerful.
EDIT: By 'seemingly trivial', I mean that if you explain it to a lay person it seems easy at first blush - not that it is actually trivial.
The problem with "trivial" is that it's in the eye of the beyolder. And everything can seem "trivial" after you've studied it long enough ;-) For instance, I'd say the matrix implementation of Levenshtein is quite trivial...
I'm surprised this page and the page on "string metrics" don't say more about the mathematical implications of defining a distance metric on strings. Something interesting must pop up if you apply theorems about metric spaces from analysis and topology to the set of strings with edit distance.
This metric induces the discrete topology, which isn't very useful. Regarding its metric structure, you could apply the contraction mapping theorem but I can't think of any interesting contractions off the top of my head.
I'm just spit-balling here... but when a natural metric induces the discrete topology then it's probably more useful to look at connectivity graphs induced by the metric. For instance the graph on all strings with two strings connected by an edge if their edit distance equals 1. Restrict to words in a dictionary and you have a basic spelling suggestion algorithm.
Edit: the analyst in me really wants a translation-invariant abelian group structure ... then we can do Fourier analysis...
I’m kind of tacking this on here, but does anyone have a good recommendation for notes or a book on applied topology for someone with a decent but not extensive background in applied math? In particular, my goal is to more deeply understand manifold learning techniques like MDS and UMAP.
The implications are more practical, rather than theoretical. As others have said, the theoretical implications are mostly for continuous spaces, which strings are not.
From the practical side, there are a lot of algorithms designed to work on vectors that can work on sets of strings. It depends on whether the algorithm really needs to use the underlying vector, or whether it just uses distances.
For example: Clustering! By using string metrics, you can group sets of strings into clusters using standard algorithms. Some algorithms like K-means won't work (in general, you can't find the string half-way in-between two strings), but some algorithms can apply, especially hierarchical clustering.
I think you could apply MDS to sets of strings the same way, but I'm a little less familiar with the guts of that algorithm.
Yes. I have used clustering on Levenshtein distance in this way to find misspellings in user-entered data fields, in order to canonicalize the data for more analysis.
Yes, it is a metric. The following is BS "proof by restatement of requirements".
1. Always >= 0 (what is a negative character edit?)
2. It satisfies identiy in that if no edits are required to make them equal, metric distance is 0 and they are equal (applies to either ordering of strings A->B and B->A)
3. It is symmetric (run the edits backwards to get B->A instead of A->B)
4. It satisfies triangle inequality. exercise left to reader, but intuitive since the edit distance is always the "shortest path" through character changes between two strings A and B, and deviating to visit an intermediate string C would not decrease number of edits from A->C->B vs original path A->B
I'm sleep deprived due to "offspring induced insomnia" so take this with a grain of salt.
lucky you :) there was no wikipedia when I first ran into this algorithm. Foxpro for DOS & Novell Netware had an implementation of Levenshtein distance that I ended up using as part of a college project on database basics. I used it to detect typos in data entry by comparing entered names with all names already in the table. It was blazingly fast because we never exceeded 30 names (the size of our class) and my profs were super impressed because they thought I did something way more complicated than I had.
Very nice! If you're looking for one more variant to add: LD with a limit on the acceptable distance can be done more efficiently, and is nearly always what you want in practice.
> This implementation only computes the distance if it's less than or equal to the
threshold value, returning -1 if it's greater. The advantage is performance: unbounded
distance is O(nm), but a bound of k allows us to reduce it to O(km) time by only
computing a diagonal stripe of width 2k + 1 of the cost table.
It is also possible to use this to compute the unbounded Levenshtein distance by starting
the threshold at 1 and doubling each time until the distance is found; this is O(dm), where
d is the distance.
That's pretty cool, especially the doubling scheme. I'm using a modified form of Levenshtein Distance for comparing lines when diffing files, and that's pretty expensive since code files that are thousands of lines long are not uncommon. Since you are usually comparing one file to another version of itself, the differences are often small though, so an incremental approach would really pay off.
Yup, it's used a lot in machine translation to compare different systems, and to a lesser extent in natural language generation (where it's completely inappropriate...)
I've used Levenshtein distance to sort fuzzysearch results by order of relevance. Worked very well combined with a special-case to sort exact matches first.
It's an autocompletion for emoji, so several letters will be missing regardless.
I'm that case, a long word like "helicopter" will be placed at a greater distance than "elipsis" despite being what I want "heli" to actually match, so I just added a "startsWith" check to override such issues.
Have you experimented with n-grams for approximate matching? I've found it works very well, especially if you add special characters to the alphabet to mark "start of string" and "end of string": like "heli" would have trigrams {"^he", "hel", "eli", "li$"}, which would certainly be a better trigram match to "helicopter" than to "elipsis" (sic).
Postgres has support for trigrams and indexes on them. I used them to help match addresses at a previous company, worked fantastically for the part we used them for.
Here's a helpful tip in case it comes in handy one day:
If you need to run Levenshtein Distance over tens of thousands of strings, perhaps as part of a fuzzy search, and you only need to match on distances of 0 or 1, not any distance in general, then there's an optimization on Levenshtein Distance where you hard code the function just for distances of 0 or 1. It's not difficult to do and the payoff might enable new applications of what would otherwise be too costly.
If you're fuzzily looking up members in a fixed corpus, you can also employ the trick from https://github.com/wolfgarbe/SymSpell, which is essentially just to, for each string in your corpus, enumerate all of the variants of that string with one letter removed, and put both the original string and each variant in a hashtable as a key, with the original string as the value. To do a lookup, you do the same enumeration (original query plus each variant with one letter dropped), and look all of them up in your hashtable. The values you get out of that are a list of all of the strings in your corpus at edit distances 0 or 1, and potentially some at edit distance 2; you can do a subsequent Levenshtein calculation on each to weed out the distance-2 strings, but you only have to do it on this massively reduced set rather than on your whole corpus.
So like, to index a string "hello", you'd add all of {"hello":"hello","ello":"hello","hllo":"hello","helo":"hello","hell":"hello"} into your table, and for the query "gello", you'd look up all of ["gello", "ello", "gllo", "gelo", "gell"], and get a match on "ello"->"hello", then do a Levenshtein calculation dist("gello","hello") to confirm it's within ED=1 (it is), and be done. (Bonus: the same method works with Damerau-Levenshtein distance as well.)
Does this work if you want to look up multiple words and grade them?
For example if the input query is "ello" and there is a dict.txt with millions of entries, it should output the words that are closest to the query: "hell", "hello", "fellowship", "mellow" and their respective matching scores (e.g 0.8, 0.9, 0.3, 0.7 respectively). The scores are just random numbers in this case.
Can't think on a real word example, but abc would match bcd in the above algo, as both permute to bc, but they are distance 2. So, any case where one letter is deleted and another is added at a different position.
There's a specialized algorithm specifically for running levenshtein distance over tens of thousands of strings called bitap[1]. I wrote an impl in rust a while back[2].
But your advice still applies! Run time scales with max distance.
Interesting. I used a similar trick to compute a lower bound on the levenshtein distance. I was able to skip the real levenshtein distance calculation, if the lower bound already exceeded a threshold ( I used it for clustering ).
We used this when building an app to determine 'meaningful' discrepencies between prelimary radiology reports (done by Residents) and final reports (done by attending radiologists). It's a fun algorithm to implement that isn't as simple as it seems. I think there's lots of uses for it.
Only application I've used this for so far is a technique for defining and recognizing gestures. They're called "flash gestures" (or that's what the page where I read about them called them) where you find the closest of 8 directions to the gesture direction and encode each gesture as a sequence of digits 1-8 corresponding to these closest directions, then use the Levenshtein distance algorithm to find the closest matching pattern.
EDIT: Found the reference I used to implement this.
The names 'edit distance' and 'levenshtein distance' are a bit unfortunate.
When I was trying to match batches of OCR'd strings to known strings, I knew some algorithm like this had to exist, but I could not find it. My searches kept turning up Jaccard similarity and Hamming distance again and again.
(Once I found it and began working on an implementation, I started noticing my compiler would find miss-typed variable names and suggest the correctly-spelled variable for me.)
There are a lot of unhelpfully named metrics, algorithms, etc. but I actually think “edit distance” is fairly illustrative as these things go.
Another good one is Manhattan distance (or better yet, city block distance) in place of Hamming distance. It gives a nice mental picture of the number of road segments you’d need to travel in a city to get from point A to point B.
One step further (multi-layer Manhattan distance) will also get you optimal DNA, RNA and protein sequence alignment (Myers, Gotoh and others, 1977-1981). The edit path (often discarded) can be repurposed for simulating RNA and protein folding, as well as calculating DNA melting points (used for DNA-DNA hybridization studies).
If you consider strings as list of characters you can abstract levenshtein to work on any two lists. For example i use this with list of types to provide a hoogle-like search for some programming languages stdlib. Ironically i don't know what hoogle actually uses but i think they atleast considered such an approach.
I was once asked in an interview how I'd find a row in a relational database where the value in one column was the shortest levenshtein distance away from a search key, and I was absolutely stumped when I realized I didn't really know a sort/search that optimized that way. Of course, by the time I realized I could email the interviewer for the answer an awkward amount of time had passed.
So now I ask HN: is there any "good" way to do this short of some kind of answer like "find a database that natively offers levenshtein distance search"? Are there actually sorting algorithms for sorting by levenshtein distance (other than just using L as a sort function in a traditional sort function)? Are there search algorithms that work well for searching by L distance?
Wouldn't call it 'good' but it would be better than applying L on each row.
Instead enumerate all unique permutations of the search term, calculate it's levensten distance and then search through for a match...doing it one by one starting from distance 0 to max and returning the first match.
If the variable in complexity size is the number of rows then it's better to enumerate all permutations and do a single search over all rows, ordering results by distance and returning only the first match
I can't think of any clever optimizations, unless there are some convenient constraints on the database or search query values. You could just precompute a lot of stuff to help you narrow down the search, but that's really not going to be feasible unless you have some constraints or some metrics on what sort of searches are being performed.
I don't think that there is a way to index by levenshtein distance generally because there is a many-to-many mapping between search terms and keys to match and there is potentially an infinite number of either.
What I've seen databases that need to do fuzzy matching on strings do more often is index a list of substrings of keys and match on those. So hypothetically if I had a row identified with the string 'abc', I would have a separate table with the strings: 'a', 'b', 'c', 'ab', 'bc', 'abc' all mapped to the row in question and an index built on them.
If you had a cap on the edit distance you knew was acceptable for searches, you could do something similar with levenshtein distance, where you could save every string with an edit distance less than say, 3, to a separate table along with the edit distance. This would be expensive in terms of space though, if your keys were very large. I suppose you could optimize it by just pre-computing the distance on a prefix (say the first three or four characters) and using that to narrow the search space.
sort/index the db table by string length, start your search with the closest length strings (bigger and smaller) and then stop if you find a levenshtein distance that's smaller than that the length difference between the key and the next closest length string? In many(most?) cases you'd still end up searching the whole table but at least in some cases you could end the search early.
That may be a wrong question to ask. If do not need exact levenshtein distance, but some measure of similarity then there are a lot of options. For example postgres has index-supported similarity based on amount of common trigrams.
If you only care about the row with the shortest distance (and assuming no precomputed optimizations) you can save compute cycles by exiting the algorithm as soon as the distance is guaranteed to be larger or equal to the shortest distance thus far. For very large searches the algorithmic complexity drops to roughly linear in the number of rows, the length of the search string, and the shortest distance thus far (the distance to any strings whose length differs by more than the shortest distance thus far need not be computed at all).
Suffix trees are a cool algorithm for fuzzy text matching. There is a linux tool called 'sary' that implements approximate grep, but it takes some time and space to convert plain text to suffix array format.
Not sure how it's supposed to be solved, but I thought of a cute hack in the special case where the character set of the strings is limited, e.g. lowercase ASCII only.
Let A be the alphabet used. Precompute the "letter sum" of each string and store it. Then given two strings with letter sums c1 and c2, they cannot have Levenshtein distance k if |c1-c2| > k|A|. This could allow you to skip a lot of rows.
The sum forms a necessary but not sufficient condition for being within a certain Levenshtein distance. In your example, the inequality I gave above does not apply since |c1-c2| = 0. You would have to calculate the Levenshtein distance. In cases where the inequality is satisfied, you do not have to calculate the Levenshtein distance at all.
The idea is that any edit operation on a string will at most change the letter sum by |A|.
Depending on the RDBMS and the target text (ideally, you’re looking to compare an entire column to the search text, and in a known character set, and known casing, etc.), I’d take one of two approaches:
1) write a UDF—in C, or for SQL Server, in pretty much any managed language—that returned the Levenshtein distance between a passed param and a column name, with a “max distance” param to aid in optimizing (e.g., maybe it doesn’t bother calculating the distance if the length difference exceeds the max Levenshtein distance)
Then you could write a query that looks something like:
SELECT product, description WHERE levenshtein(`fobar`, product, 2) <= 2
-or-
2) if you only care about a distance of 1 or 2, create a set of secondary tables where you’d pre-calculate the permutations of every word, with a FK pointing back to the PK of the actual row.
Alternately, a combination of a Levenshtein distance function and an RDBMS that already supports fuzzy text matching seems (to me) to be ideal.
I think sometimes it is easy to forget that SQL is but an abstraction over algorithmic processing and shaping of data. A UDF is only a way to extend the built in algorithms, albeit, one which may not be fully integrated with a given query engine architecture and therefore cannot be fully optimized without having access to the engines internals.
I would argue your answer is the best as as far as doing an actual Levenshtein distance calculation.
That being said, sort orders are implemented algorithmically by the query engine. ORDER BY in SQL Server, as I recall implements up to 7 different algorithms built in, depending on the case, as far as I recall. But those algorithms are optimized for the engine and have access to the internals.
I can think of two interesting ways to look at this, one being how one could use an open source database to extend the built in sort algorithms in the query engine, perhaps controlled by collation settings, to get a native levenshtein sort implemented that has access to internals. Collations defining the rules for sort order, but this would probably be within a column, not against a value (although if you’re extending the query engine, why not). Example of collation settings [1] and how they control the rules of sort order - perhaps a SET command to define levenshtein order and then a native extension to the Postgres query engine, and now you can sort a column by Levenshtein distances.
The other thing I was thinking was word vectors (but this is similar to Levenshtein distance) and still in a relational database requires something special. Maybe some of the full text search implementations in database could do this out of the box.
Levenshtein distance is a metric [1] and discrete metrics can be indexed with BK trees, taking advantage of the triangle inequality. For a detailed explanation, see [2].
I know of no real world implementation of this, however.
For some reason the wikipedia article does not mention the more efficient Myers diff approach. I have recently implemented it here: https://jasonhpriestley.com/array-distance-and-recursion (for edit distance but Levenshtein should work similarly)
Ugh. At a past job I was tasked with matching records, based on street addresses and business names, from various systems. Levenshtein Distance was pretty instrumental in helping find potential matches once we had cleaned up the address format and business name as much as possible.
I did the same thing. I was merging our billing db with that of a business we had just bought. Due to the nature of our business, customers could exist in both.
So I had a routine that normalized the address, as best I could anyway, didn't help that it was all just one varchar field. Then implimented Levenshtein Distance, messed with the weighting a bit to fit our particular data and away it went. Saved a bunch of headaches. It wasn't perfect, but it was better than hand matching a couple thousand accounts.
At my first professional programming gig the company I worked for was selling items on Amazon. The listings were big ticket items that had several sellers competing on them. Any seller could change some of the details of the listing, so suddenly all their competition would be shipping the item with wrong specs. I wrote a program that periodically grabbed the titles of our live Amazon listings and compared them to our database of what we actually wanted the title to read. I used Levenshtein Distance as a sort of "severity of change" metric, the program would sort the changes accordingly and send an email to a person on the sales team. It was fun implementing Levenshtein Distance, but it wasn't a perfect metric for this use case. Some of the most severe changes would be a single digit changing; e.g. "2gb" vs "8gb"
You can modify the basic algorithm to weight changes differently. I had the opposite case--differing numbers were more likely to be what the user was looking for. I made digit changes cost 1 point, one string being longer cost 1 point per character (suffixes were another case where it was likely the objective) and everything else cost 2.
Someday I want to write a diff utility specifically for code. Whitespace addition/removal cost like .1, addition/removal of a curly brace .5. There are a handful of other things default diff does that make it really annoying for code.
I did this for a school project, because students would "cheat" on group projects by exclusively changing whitespace in diffs, or moving code around, thereby making it look like they had large commits.
We tracked code "moves", whitespace changes, and "trivial" changes via Levenshtein distance--which isn't great for capturing most simple renamings--and then marked them up separately in an "augmented diff".
We briefly looked into doing AST edit-distance, but that turned out to be infeasible for many reasons.
Over-all it helped the prof grade faster, at least in the degenerate cases.
Measuring a student's impact by a project on the number of lines of code they committed can be very misleading.
Sure, in the extremes it will give sensible results (someone wrote only 3 lines, or wrote 90% of the code base).
But minor, questionably motivated refactorings can create huge commits, while someone may come up with some great design while walking around for hours and sketching on paper, which all ultimately boils down to a short function.
Dumb metrics like this cannot replace actually talking with the students, asking questions about their choices and alternatives, having them do presentations or lab notebooks/logbooks etc.
> Dumb metrics like this cannot replace actually talking with the students, asking questions about their choices and alternatives, having them do presentations or lab notebooks/logbooks etc.
As said in the parent:
>> Over-all it helped the prof grade faster, at least in the degenerate cases.
I never actually used any of these, but have stumbled upon some tools which create/apply diffs on ASTs of your source rather than lines[1]. I think the keywords to search is "semantic diff/patch/merge", "AST diff" or some combination of these.
This link was gray for me because I recently used Levenshtein distance to sort an arbitrary list of strings by finding a "comparison word" that gave the ordering that I wanted. Definitely more of a cutesy (and difficult to explain) way of doing things rather than practical but Case statements are so boring. It was nice that Presto had it built in.
Did some more digging to see if there was a unique comparison word that would enable me to sort any group of strings but found that it was impossible. Still a fun afternoon of learning.
My first job at Microsoft was to make a system that could catalog the “contracts” or “extension points” installed in Windows. I’d define a category of extensions, such as a COM object registration and my program used normalized levenshtein difference to warn about potential typos. After removing all matching fields names from the instance & class I compared the edit distance in the remaining cross product. If any had a normalized distance < N it produced a warning. It even helped me find a mistyped GUID in a prerelease copy of Windows.
I love this algorithm -- it's so elegant and succinct.
Slightly off-topic, but one of the algorithms I'm most proud of coming up with as an engineer was an offshoot of Levenshtein distance where I had to find all pairs of strings in a set of ~1m strings which were fairly similar. 1m x 1m x O(n^2) is very slow. There turned out be a good way to figure out a lower bound on distances using some precomputation, and that eliminated almost all of the pairwise O(n^2) Levenshtein computations.
That wasn't the actual use case and we didn't store passwords in plaintext. But I didn't want to give away the actual use case. In hindsight, passwords are definitely a bad fake example.
128 comments
[ 0.20 ms ] story [ 202 ms ] threadhttps://docs.marklogic.com/spell.levenshteinDistance
EDIT: By 'seemingly trivial', I mean that if you explain it to a lay person it seems easy at first blush - not that it is actually trivial.
I'm just spit-balling here... but when a natural metric induces the discrete topology then it's probably more useful to look at connectivity graphs induced by the metric. For instance the graph on all strings with two strings connected by an edge if their edit distance equals 1. Restrict to words in a dictionary and you have a basic spelling suggestion algorithm.
Edit: the analyst in me really wants a translation-invariant abelian group structure ... then we can do Fourier analysis...
Yep.
https://norvig.com/spell-correct.html
From the practical side, there are a lot of algorithms designed to work on vectors that can work on sets of strings. It depends on whether the algorithm really needs to use the underlying vector, or whether it just uses distances.
For example: Clustering! By using string metrics, you can group sets of strings into clusters using standard algorithms. Some algorithms like K-means won't work (in general, you can't find the string half-way in-between two strings), but some algorithms can apply, especially hierarchical clustering.
I think you could apply MDS to sets of strings the same way, but I'm a little less familiar with the guts of that algorithm.
https://en.wikipedia.org/wiki/Taxicab_geometry
https://en.wikipedia.org/wiki/Metric_(mathematics)
Also, this looks like could be related to the Hamming Code ? Error correcting codes.
https://en.wikipedia.org/wiki/Hamming_distance
1. Always >= 0 (what is a negative character edit?)
2. It satisfies identiy in that if no edits are required to make them equal, metric distance is 0 and they are equal (applies to either ordering of strings A->B and B->A)
3. It is symmetric (run the edits backwards to get B->A instead of A->B)
4. It satisfies triangle inequality. exercise left to reader, but intuitive since the edit distance is always the "shortest path" through character changes between two strings A and B, and deviating to visit an intermediate string C would not decrease number of edits from A->C->B vs original path A->B
I'm sleep deprived due to "offspring induced insomnia" so take this with a grain of salt.
https://github.com/cbartley/diffy/blob/master/src/diffy/diff...
I wrote a commented version years back that might be a handy reference; it's since been deprecated because we moved it out of StringUtils, but the original code is here https://github.com/apache/commons-lang/blob/master/src/main/...
That's pretty cool, especially the doubling scheme. I'm using a modified form of Levenshtein Distance for comparing lines when diffing files, and that's pretty expensive since code files that are thousands of lines long are not uncommon. Since you are usually comparing one file to another version of itself, the differences are often small though, so an incremental approach would really pay off.
I'm that case, a long word like "helicopter" will be placed at a greater distance than "elipsis" despite being what I want "heli" to actually match, so I just added a "startsWith" check to override such issues.
https://en.wikipedia.org/wiki/N-gram#n-grams_for_approximate...
[0]: https://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance
If you need to run Levenshtein Distance over tens of thousands of strings, perhaps as part of a fuzzy search, and you only need to match on distances of 0 or 1, not any distance in general, then there's an optimization on Levenshtein Distance where you hard code the function just for distances of 0 or 1. It's not difficult to do and the payoff might enable new applications of what would otherwise be too costly.
So like, to index a string "hello", you'd add all of {"hello":"hello","ello":"hello","hllo":"hello","helo":"hello","hell":"hello"} into your table, and for the query "gello", you'd look up all of ["gello", "ello", "gllo", "gelo", "gell"], and get a match on "ello"->"hello", then do a Levenshtein calculation dist("gello","hello") to confirm it's within ED=1 (it is), and be done. (Bonus: the same method works with Damerau-Levenshtein distance as well.)
For example if the input query is "ello" and there is a dict.txt with millions of entries, it should output the words that are closest to the query: "hell", "hello", "fellowship", "mellow" and their respective matching scores (e.g 0.8, 0.9, 0.3, 0.7 respectively). The scores are just random numbers in this case.
(edited for clarity)
But your advice still applies! Run time scales with max distance.
[1] https://en.wikipedia.org/wiki/Bitap_algorithm [2] https://github.com/heyimalex/bitap
[1] https://en.wikipedia.org/wiki/Memoization
EDIT: Found the reference I used to implement this.
https://books.google.com/books?id=_1rSBQAAQBAJ&pg=PA85&lpg=P...
When I was trying to match batches of OCR'd strings to known strings, I knew some algorithm like this had to exist, but I could not find it. My searches kept turning up Jaccard similarity and Hamming distance again and again.
(Once I found it and began working on an implementation, I started noticing my compiler would find miss-typed variable names and suggest the correctly-spelled variable for me.)
Another good one is Manhattan distance (or better yet, city block distance) in place of Hamming distance. It gives a nice mental picture of the number of road segments you’d need to travel in a city to get from point A to point B.
So now I ask HN: is there any "good" way to do this short of some kind of answer like "find a database that natively offers levenshtein distance search"? Are there actually sorting algorithms for sorting by levenshtein distance (other than just using L as a sort function in a traditional sort function)? Are there search algorithms that work well for searching by L distance?
Instead enumerate all unique permutations of the search term, calculate it's levensten distance and then search through for a match...doing it one by one starting from distance 0 to max and returning the first match.
If the variable in complexity size is the number of rows then it's better to enumerate all permutations and do a single search over all rows, ordering results by distance and returning only the first match
What I've seen databases that need to do fuzzy matching on strings do more often is index a list of substrings of keys and match on those. So hypothetically if I had a row identified with the string 'abc', I would have a separate table with the strings: 'a', 'b', 'c', 'ab', 'bc', 'abc' all mapped to the row in question and an index built on them.
If you had a cap on the edit distance you knew was acceptable for searches, you could do something similar with levenshtein distance, where you could save every string with an edit distance less than say, 3, to a separate table along with the edit distance. This would be expensive in terms of space though, if your keys were very large. I suppose you could optimize it by just pre-computing the distance on a prefix (say the first three or four characters) and using that to narrow the search space.
https://en.wikipedia.org/wiki/W-shingling
https://www.postgresql.org/docs/11/pgtrgm.html
http://sary.sourceforge.net/
Let A be the alphabet used. Precompute the "letter sum" of each string and store it. Then given two strings with letter sums c1 and c2, they cannot have Levenshtein distance k if |c1-c2| > k|A|. This could allow you to skip a lot of rows.
Think "atc" and "cat". Same sum.
The idea is that any edit operation on a string will at most change the letter sum by |A|.
1) write a UDF—in C, or for SQL Server, in pretty much any managed language—that returned the Levenshtein distance between a passed param and a column name, with a “max distance” param to aid in optimizing (e.g., maybe it doesn’t bother calculating the distance if the length difference exceeds the max Levenshtein distance)
Then you could write a query that looks something like:
-or-2) if you only care about a distance of 1 or 2, create a set of secondary tables where you’d pre-calculate the permutations of every word, with a FK pointing back to the PK of the actual row.
Alternately, a combination of a Levenshtein distance function and an RDBMS that already supports fuzzy text matching seems (to me) to be ideal.
I would argue your answer is the best as as far as doing an actual Levenshtein distance calculation.
That being said, sort orders are implemented algorithmically by the query engine. ORDER BY in SQL Server, as I recall implements up to 7 different algorithms built in, depending on the case, as far as I recall. But those algorithms are optimized for the engine and have access to the internals.
I can think of two interesting ways to look at this, one being how one could use an open source database to extend the built in sort algorithms in the query engine, perhaps controlled by collation settings, to get a native levenshtein sort implemented that has access to internals. Collations defining the rules for sort order, but this would probably be within a column, not against a value (although if you’re extending the query engine, why not). Example of collation settings [1] and how they control the rules of sort order - perhaps a SET command to define levenshtein order and then a native extension to the Postgres query engine, and now you can sort a column by Levenshtein distances.
The other thing I was thinking was word vectors (but this is similar to Levenshtein distance) and still in a relational database requires something special. Maybe some of the full text search implementations in database could do this out of the box.
[1] https://docs.microsoft.com/en-us/sql/relational-databases/co...
I know of no real world implementation of this, however.
[1] https://en.wikipedia.org/wiki/Metric_(mathematics) [2] http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK...
So I had a routine that normalized the address, as best I could anyway, didn't help that it was all just one varchar field. Then implimented Levenshtein Distance, messed with the weighting a bit to fit our particular data and away it went. Saved a bunch of headaches. It wasn't perfect, but it was better than hand matching a couple thousand accounts.
We tracked code "moves", whitespace changes, and "trivial" changes via Levenshtein distance--which isn't great for capturing most simple renamings--and then marked them up separately in an "augmented diff".
We briefly looked into doing AST edit-distance, but that turned out to be infeasible for many reasons.
Over-all it helped the prof grade faster, at least in the degenerate cases.
Sure, in the extremes it will give sensible results (someone wrote only 3 lines, or wrote 90% of the code base).
But minor, questionably motivated refactorings can create huge commits, while someone may come up with some great design while walking around for hours and sketching on paper, which all ultimately boils down to a short function.
Dumb metrics like this cannot replace actually talking with the students, asking questions about their choices and alternatives, having them do presentations or lab notebooks/logbooks etc.
As said in the parent:
>> Over-all it helped the prof grade faster, at least in the degenerate cases.
[1] https://lwn.net/Articles/315686/
https://www.gnu.org/software/diffutils/manual/html_node/Whit...
Did some more digging to see if there was a unique comparison word that would enable me to sort any group of strings but found that it was impossible. Still a fun afternoon of learning.
Slightly off-topic, but one of the algorithms I'm most proud of coming up with as an engineer was an offshoot of Levenshtein distance where I had to find all pairs of strings in a set of ~1m strings which were fairly similar. 1m x 1m x O(n^2) is very slow. There turned out be a good way to figure out a lower bound on distances using some precomputation, and that eliminated almost all of the pairwise O(n^2) Levenshtein computations.
I'm anyone's interested, here the description: https://www.quora.com/What-is-the-best-programming-algorithm...
> "At Google, say we had 1 million plaintext passwords..."