Super Fast and Accurate string distance algorithm: Sift4
Warning: the algorithm works perfectly well and is better than Sift3, however you might want to consider it in beta, as I am still looking for better implementation solutions that might change the structure of the code.
Try the Javascript implementation here:
Algorithm: Levenstein Sift3 Sift4 MaxOffset:
String 1: String 2:
Result:
Update 28 Mar 2015: I've changed the algorithm significantly. The transpositions are now computed differently and the cost of a transposition in the final result is 1, rather than 0.5. Also, while I think a value of 1 is better conceptually, I noticed that Sift4 approximates Levenshtein a little better when the cost of a transposition is either 2 or a function depending on the offset difference between c2 and c1, especially when maxOffset grows. This can be now changed via the new options function transpositionCostEvaluator. The problem I am having now is more false positives when the letters/tokens of the two strings are the same, but their positions are jumbled differently. With small maxOffset values, like 5 or 10, the result is much better than Sift3, however when maxOffset grows, lots of matches can be found and the cost of transpositions becomes very important.
Update 27 Mar 2015: Thanks to Emanuele Bastianelli who discovered a bug that appeared in an edge case, I've updated the algorithms. Now, at the end of the while loop there is an extra check to prevent the algorithm existing prematurely, before computing remaining tokens.
A really long time ago I wrote the third version of Sift, the string distance algorithm. It so happens that I am going to make a small presentation, here in Ispra, about this algorithm, so I had the opportunity to review it. I found some inconsistencies and I actually did some research in the field that gave more more ideas. So before giving the presentation I thought of publishing what I think is the fourth version. What's new:
Before I get into the details, I am publishing the algorithm here for the moment, no Codeplex or PasteBin or GitHub or whatever. Also, it is written in Javascript now, the C# and T-SQL version pending. Of course, it would be great if, as before, the community of people using the algorithm would go into implementing it into various programming languages, however I am a bit apprehensive because more often than not people came with their own improvements or interpretations when translating the algorithm into another language. But support is always welcome!
I created a test that used random strings, but also a huge list of commonly used English phrases as well as mutations on these strings, adding or removing small bits and so on. I then implemented Sift3, Levenstein and the new algorithm and computed the error distance between the Levenstein distance and the two Sift variants. This permitted me to see how the error evolves when changing the algorithm and the parameters. One thing I noticed is that when increasing the maxOffset value to large values like 15 or 20, the accuracy of Sift3 was going down. Also, as pointed out by one commenter on the Sift3 post, there are cases when Sift3(a,b) is different from Sift3(b,a). There are edge cases, but this one in particular grated me.
After implementing Sift4, I can now tell you that the simple version is slightly better than Sift3 for small maxOffset values like 5, but it gets better as the value increases. The common version is a bit more complex, but the error decreases with 33% and maintains a low error for large maxOffset values. The extended or general version receives an options object that can change almost everything, but most important is the tokenizer function. Imagine that you want to compute the distance based not on letters, but on n-grams (groups of n characters). Or that you want to compare them by the words in the text, maybe even their synonyms. This can all be achieved just by changing the tokenizer function. The other parameters involve defining what it means for two tokens to match and what is the value of their match, etc.
One of the new concepts implemented is taken from the Jaro distance. Jaro seems a lot like Sift in the way that it considers two characters to match if they are in close proximity. Also, if "the streams cross", like 'ab' vs 'ba', one considers them transpositions and removes some of their value from the distance. Actually, if I look at the implementation, it might be that I have independently discovered the Jaro distance. I will research this further. I don't know if the transposition calculation is the most optimal. At the moment it uses an array of all matches found until a point, clearing it of values as the cursors move along the string. The difference between the simple and the common versions of Sift4 is that the simple version is not computing the transpositions at all and has no concept of maxDistance. In that respect it is a slightly fixed up Sift3.
Another new concept added is the one of local substring. Imagine that the Largest Common Subsequence that Sift is actually trying to find in order to determine the distance is made of substrings, separated by non matching characters. Each of these substrings can be used to improve the distance function. For example one could argue that 'abcdex' is closer to 'abcde' than 'abcxde', because even if the largest common subsequence is 5, the largest common substring is 5 for the first string and only 3 for the second. The extended version of the algorithm allows for changing the value of each substring individually.
Well, here they are, the three versions. The extended version has some examples at the end for possible parameters.
Simplest Sift4:
Common Sift4:
Extended/General Sift4:
As always, I will be most happy to know if you used my algorithm and how it performed, as well as receive any suggestion that you might have.
Here is some explanation for the options of the general algorithm.
It no longer searches for characters, but for tokens. That is why the default tokenizer function splits the values into characters so that the algorithm would work on an array of one character long tokens. Other options are possible, like splitting the strings by empty spaces so that the comparisons are done on words or transforming a string into an array of strings N characters long, the so called N-grams. The tokenizer can be anything, like the characterFrequencyTokenizer, which turns each word in an array of 25 values representing the number of letters in the word for each letter a-z.
The tokenMatcher function returns true if two tokens are matching. They can be fuzzy matched, for example the sift4tokenMatcher uses Sift inside Sift to determine the character distance between two tokens and returns true if they match more than 70%.
The matchingEvaluator is a function that returns the value that will be added to the "common substring" length value when two tokens match. The default is 1, but one can use some other metric, like the similarity, for example. Of course, the common substring length has lost its meaning when these functions change, but the variable local_cs is still used.
The lengthEvaluator is taking the length value of the local common substring and returns a value that will be added to the longest common subsequence value. Usually it returns the same value as the one provided, but some functions could reward longer substrings.
FAQ:
Q: Can you make Sift4 to work case insensitive?
A: Just turn the strings to lower or upper case before you compare them. Since this algorithm is more general, the concept of 'case' might not apply.
Q: Can you make Sift4 to compare strings based on their meaning, like using synonyms?
A: Use a tokenizer function that splits the strings into words, then replaces them with the first of their synonyms. A more complex solution would require to analyse the strings beforehand and turn them into some ordered synonym or equivalent expressions equivalents, then use Sift4 with a word tokenizer (one is provided in the Extended algorithm source)
Q: I need an implementation for this programming language, can you help?
A: I can, but I might not have the time. Ask anyway, maybe I can be persuaded :)
Q: I have been using Sift3 until now, how do I upgrade to Sift4?
A: The best way I can think of is to implement Sift4 Simplest, as it needs only the Sift3 code and some minor changes. Since you never needed tokens before, I doubt you need them now. But if you do, I can help, see the above question.
Q: How can I reward you for this fantastic piece of software engineering?
A: While I did this for free and I don't expect to make any money out of it and while this algorithm is completely free to use and change as you see fit, I don't mind having a beer every now and then ;)
Q: Your algorithm really sucks because... reasons.
A: It may. I would be glad to discuss the reasons, though, and try to fix any problem you encounter.
Q: I compared Sift4 with another algorithm that is much more exact and there are differences.
A: Of course, they are different algorithms. This is a fuzzy distance calculator, it doesn't give you the exact value. There are still edge cases. But the idea of Sift is to be fast and relatively accurate, rather than very accurate. You need more accuracy, try to combine Sift with Levenshtein for example, computing Levenshtein only where Sift says the strings are above a certain similarity.
Q: I want to make maxOffset dependent on the length of the strings compared. Can you do that?
A: That is a perfect example why maxOffset should be a parameter of the function rather than a member of the class. Since this implementation is so far Javascript only, just compute the maxOffset that is convenient to you before you compare.
Q: I want to vary the weight of matches based on the position of the match, for example matches at the beginning of the string could be more valuable than those at the end.
A: The position of the match is indeed not sent to the functions that can be specified in the options object of the Sift4 Extended, but that can be trivially changed in the code. I don't think this particular request is very common, though, and I prefer to keep it out of the published implementation to make the code easier to understand.
Q: I found a bug!
A: Let me know it and I will try and fix it.
Q: If you need to compare large lists of strings, it is better to precompute some things, like specific hashes or suffix trees, etc. This will speed up the comparison tremendously!
A: Sift is what is called an online algorithm. It does not precompute anything, it just gets the two strings and the parameters for its functioning and returns the distance. You are correct in what you are saying, but that kind of solution is not in the scope of Sift, at least not version 4.
Q: What are the edge cases for Sift?
A: Probably there are several, but I didn't really spot them. One of them is that one might find both letters at a position matching letters at other positions, but only one will count. Example 'abxx' and 'bayy'. The algorithm will look at position 0, find no match, then try to find the closest match for each letter. Starting with position 0 in the first string it will find 'a' matched in position 1 in the second. It will increase both counters and lcss will be increase as well. Next check will be 'b', the character at position 1 in the first string matched with position 2 in the second string. No match, therefore both counters will be reset to 1, and starting search again. The 'b' match is lost and distance is 3 instead of 2. Also I think there might be some situations where the counters are not equal and the biggest of them reaches the end of its string, thus terminating the algorithm, but there could have been more matches. Incidentally I tried to fix both these issues and the error from Levenshtein was not really affected, but I am not 100% sure of the implementation.
Q: The algorithm continues to be asymmetric, Sift4(s1,s2) can be different from Sift4(s2,s1).
A: Yes. This is one of the artifacts of the linear nature of the algorithm. There is a function that is symmetric and that is Math.min(Sift4(a,b),Sift4(b,a)), however it is twice as slow, obviously.
Implementations in other languages:
Powershell implementation of simple Sift4, by Kirk Sayre:
Thanks to Hugo Amaro, a C++ implementation:
You can find a Go implementation here, written by Jason W. Hutchinson.
There is also a Swift implementation here.
A Perl 6 implementation can be found here.
Try the Javascript implementation here:
Algorithm: Levenstein Sift3 Sift4 MaxOffset:
String 1: String 2:
Result:
Update 28 Mar 2015: I've changed the algorithm significantly. The transpositions are now computed differently and the cost of a transposition in the final result is 1, rather than 0.5. Also, while I think a value of 1 is better conceptually, I noticed that Sift4 approximates Levenshtein a little better when the cost of a transposition is either 2 or a function depending on the offset difference between c2 and c1, especially when maxOffset grows. This can be now changed via the new options function transpositionCostEvaluator. The problem I am having now is more false positives when the letters/tokens of the two strings are the same, but their positions are jumbled differently. With small maxOffset values, like 5 or 10, the result is much better than Sift3, however when maxOffset grows, lots of matches can be found and the cost of transpositions becomes very important.
Update 27 Mar 2015: Thanks to Emanuele Bastianelli who discovered a bug that appeared in an edge case, I've updated the algorithms. Now, at the end of the while loop there is an extra check to prevent the algorithm existing prematurely, before computing remaining tokens.
A really long time ago I wrote the third version of Sift, the string distance algorithm. It so happens that I am going to make a small presentation, here in Ispra, about this algorithm, so I had the opportunity to review it. I found some inconsistencies and I actually did some research in the field that gave more more ideas. So before giving the presentation I thought of publishing what I think is the fourth version. What's new:
- 33% more accurate
- three different variants: simple, common and general
- new concepts added
- support for own value and matching functions, different tokenizer functions, etc.
- actually tested with a (slightly more) serious test
- more robust, working better for large values of maxOffset
Before I get into the details, I am publishing the algorithm here for the moment, no Codeplex or PasteBin or GitHub or whatever. Also, it is written in Javascript now, the C# and T-SQL version pending. Of course, it would be great if, as before, the community of people using the algorithm would go into implementing it into various programming languages, however I am a bit apprehensive because more often than not people came with their own improvements or interpretations when translating the algorithm into another language. But support is always welcome!
I created a test that used random strings, but also a huge list of commonly used English phrases as well as mutations on these strings, adding or removing small bits and so on. I then implemented Sift3, Levenstein and the new algorithm and computed the error distance between the Levenstein distance and the two Sift variants. This permitted me to see how the error evolves when changing the algorithm and the parameters. One thing I noticed is that when increasing the maxOffset value to large values like 15 or 20, the accuracy of Sift3 was going down. Also, as pointed out by one commenter on the Sift3 post, there are cases when Sift3(a,b) is different from Sift3(b,a). There are edge cases, but this one in particular grated me.
After implementing Sift4, I can now tell you that the simple version is slightly better than Sift3 for small maxOffset values like 5, but it gets better as the value increases. The common version is a bit more complex, but the error decreases with 33% and maintains a low error for large maxOffset values. The extended or general version receives an options object that can change almost everything, but most important is the tokenizer function. Imagine that you want to compute the distance based not on letters, but on n-grams (groups of n characters). Or that you want to compare them by the words in the text, maybe even their synonyms. This can all be achieved just by changing the tokenizer function. The other parameters involve defining what it means for two tokens to match and what is the value of their match, etc.
One of the new concepts implemented is taken from the Jaro distance. Jaro seems a lot like Sift in the way that it considers two characters to match if they are in close proximity. Also, if "the streams cross", like 'ab' vs 'ba', one considers them transpositions and removes some of their value from the distance. Actually, if I look at the implementation, it might be that I have independently discovered the Jaro distance. I will research this further. I don't know if the transposition calculation is the most optimal. At the moment it uses an array of all matches found until a point, clearing it of values as the cursors move along the string. The difference between the simple and the common versions of Sift4 is that the simple version is not computing the transpositions at all and has no concept of maxDistance. In that respect it is a slightly fixed up Sift3.
Another new concept added is the one of local substring. Imagine that the Largest Common Subsequence that Sift is actually trying to find in order to determine the distance is made of substrings, separated by non matching characters. Each of these substrings can be used to improve the distance function. For example one could argue that 'abcdex' is closer to 'abcde' than 'abcxde', because even if the largest common subsequence is 5, the largest common substring is 5 for the first string and only 3 for the second. The extended version of the algorithm allows for changing the value of each substring individually.
Well, here they are, the three versions. The extended version has some examples at the end for possible parameters.
Simplest Sift4:
// Sift4 - simplest version // online algorithm to compute the distance between two strings in O(n) // maxOffset is the number of characters to search for matching letters function sift4(s1, s2, maxOffset) { if (!s1||!s1.length) { if (!s2) { return 0; } return s2.length; } if (!s2||!s2.length) { return s1.length; } var l1=s1.length; var l2=s2.length; var c1 = 0; //cursor for string 1 var c2 = 0; //cursor for string 2 var lcss = 0; //largest common subsequence var local_cs = 0; //local common substring while ((c1 < l1) && (c2 < l2)) { if (s1.charAt(c1) == s2.charAt(c2)) { local_cs++; } else { lcss+=local_cs; local_cs=0; if (c1!=c2) { c1=c2=Math.max(c1,c2); //using max to bypass the need for computer transpositions ('ab' vs 'ba') } for (var i = 0; i < maxOffset && (c1+i<l1 || c2+i<l2); i++) { if ((c1 + i < l1) && (s1.charAt(c1 + i) == s2.charAt(c2))) { c1+= i; local_cs++; break; } if ((c2 + i < l2) && (s1.charAt(c1) == s2.charAt(c2 + i))) { c2+= i; local_cs++; break; } } } c1++; c2++; } lcss+=local_cs; return Math.round(Math.max(l1,l2)- lcss); }
Common Sift4:
// Sift4 - common version // online algorithm to compute the distance between two strings in O(n) // maxOffset is the number of characters to search for matching letters // maxDistance is the distance at which the algorithm should stop computing the value and just exit (the strings are too different anyway) function sift4(s1, s2, maxOffset, maxDistance) { if (!s1||!s1.length) { if (!s2) { return 0; } return s2.length; } if (!s2||!s2.length) { return s1.length; } var l1=s1.length; var l2=s2.length; var c1 = 0; //cursor for string 1 var c2 = 0; //cursor for string 2 var lcss = 0; //largest common subsequence var local_cs = 0; //local common substring var trans = 0; //number of transpositions ('ab' vs 'ba') var offset_arr=[]; //offset pair array, for computing the transpositions while ((c1 < l1) && (c2 < l2)) { if (s1.charAt(c1) == s2.charAt(c2)) { local_cs++; var isTrans=false; //see if current match is a transposition var i=0; while (i<offset_arr.length) { var ofs=offset_arr[i]; if (c1<=ofs.c1 || c2 <= ofs.c2) { // when two matches cross, the one considered a transposition is the one with the largest difference in offsets isTrans=Math.abs(c2-c1)>=Math.abs(ofs.c2-ofs.c1); if (isTrans) { trans++; } else { if (!ofs.trans) { ofs.trans=true; trans++; } } break; } else { if (c1>ofs.c2 && c2>ofs.c1) { offset_arr.splice(i,1); } else { i++; } } } offset_arr.push({ c1:c1, c2:c2, trans:isTrans }); } else { lcss+=local_cs; local_cs=0; if (c1!=c2) { c1=c2=Math.min(c1,c2); //using min allows the computation of transpositions } //if matching characters are found, remove 1 from both cursors (they get incremented at the end of the loop) //so that we can have only one code block handling matches for (var i = 0; i < maxOffset && (c1+i<l1 || c2+i<l2); i++) { if ((c1 + i < l1) && (s1.charAt(c1 + i) == s2.charAt(c2))) { c1+= i-1; c2--; break; } if ((c2 + i < l2) && (s1.charAt(c1) == s2.charAt(c2 + i))) { c1--; c2+= i-1; break; } } } c1++; c2++; if (maxDistance) { var temporaryDistance=Math.max(c1,c2)-lcss+trans; if (temporaryDistance>=maxDistance) return Math.round(temporaryDistance); } // this covers the case where the last match is on the last token in list, so that it can compute transpositions correctly if ((c1 >= l1) || (c2 >= l2)) { lcss+=local_cs; local_cs=0; c1=c2=Math.min(c1,c2); } } lcss+=local_cs; return Math.round(Math.max(l1,l2)- lcss +trans); //add the cost of transpositions to the final result }
Extended/General Sift4:
// Sift4 - extended version // online algorithm to compute the distance between two strings in O(n) // maxOffset is the number of positions to search for matching tokens // options: the options for the function, allowing for customization of the scope and algorithm: // maxDistance: the distance at which the algorithm should stop computing the value and just exit (the strings are too different anyway) // tokenizer: a function to transform strings into vectors of tokens // tokenMatcher: a function to determine if two tokens are matching (equal) // matchingEvaluator: a function to determine the way a token match should be added to the local_cs. For example a fuzzy match could be implemented. // localLengthEvaluator: a function to determine the way the local_cs value is added to the lcss. For example longer continuous substrings could be awarded. // transpositionCostEvaluator: a function to determine the value of an individual transposition. For example longer transpositions should have a higher cost. // transpositionsEvaluator: a function to determine the way the total cost of transpositions affects the final result // the options can and should be implemented at a class level, but this is the demo algorithm function sift4(s1, s2, maxOffset, options) { options=extend(options,{ maxDistance:null, tokenizer: function(s) { return s?s.split(''):[]; }, tokenMatcher: function(t1,t2) { return t1==t2; }, matchingEvaluator: function(t1,t2) { return 1; }, localLengthEvaluator: function(local_cs) { return local_cs; }, transpositionCostEvaluator: function(c1,c2) { return 1; }, transpositionsEvaluator: function(lcss,trans) { return lcss-trans; } }); var t1=options.tokenizer(s1); var t2=options.tokenizer(s2); var l1=t1.length; var l2=t2.length; if (l1==0) return l2; if (l2==0) return l1; var c1 = 0; //cursor for string 1 var c2 = 0; //cursor for string 2 var lcss = 0; //largest common subsequence var local_cs = 0; //local common substring var trans = 0; //number of transpositions ('ab' vs 'ba') var offset_arr=[]; //offset pair array, for computing the transpositions while ((c1 < l1) && (c2 < l2)) { if (options.tokenMatcher(t1[c1],t2[c2])) { local_cs+=options.matchingEvaluator(t1[c1],t2[c2]); var isTrans=false; //see if current match is a transposition var i=0; while (i<offset_arr.length) { var ofs=offset_arr[i]; if (c1<=ofs.c1 || c2 <= ofs.c2) { // when two matches cross, the one considered a transposition is the one with the largest difference in offsets isTrans=Math.abs(c2-c1)>=Math.abs(ofs.c2-ofs.c1); if (isTrans) { trans+=options.transpositionCostEvaluator(c1,c2); } else { if (!ofs.trans) { ofs.trans=true; trans+=options.transpositionCostEvaluator(ofs.c1,ofs.c2); } } break; } else { if (c1>ofs.c2 && c2>ofs.c1) { offset_arr.splice(i,1); } else { i++; } } } offset_arr.push({ c1:c1, c2:c2, trans:isTrans }); } else { lcss+=options.localLengthEvaluator(local_cs); local_cs=0; if (c1!=c2) { c1=c2=Math.min(c1,c2); //using min allows the computation of transpositions } //if matching tokens are found, remove 1 from both cursors (they get incremented at the end of the loop) //so that we can have only one code block handling matches for (var i = 0; i < maxOffset && (c1+i<l1 || c2+i<l2); i++) { if ((c1 + i < l1) && options.tokenMatcher(t1[c1+i],t2[c2])) { c1+= i-1; c2--; break; } if ((c2 + i < l2) && options.tokenMatcher(t1[c1],t2[c2+i])) { c1--; c2+= i-1; break; } } } c1++; c2++; if (options.maxDistance) { var temporaryDistance=options.localLengthEvaluator(Math.max(c1,c2))-options.transpositionsEvaluator(lcss,trans); if (temporaryDistance>=options.maxDistance) return Math.round(temporaryDistance); } // this covers the case where the last match is on the last token in list, so that it can compute transpositions correctly if ((c1 >= l1) || (c2 >= l2)) { lcss+=options.localLengthEvaluator(local_cs); local_cs=0; c1=c2=Math.min(c1,c2); } } lcss+=options.localLengthEvaluator(local_cs); return Math.round(options.localLengthEvaluator(Math.max(l1,l2)) - options.transpositionsEvaluator(lcss,trans)); //add the cost of found transpositions } function extend(obj,def) { var result={}; for (var prop in def) { if (!obj||!obj.hasOwnProperty(prop)) { result[prop]=def[prop]; } else { result[prop]=obj[prop]; } } return result; } // possible values for the options // tokenizers: function nGramTokenizer(s,n) { //tokenizer:function(s) { return nGramTokenizer(s,2); } var result=[]; if (!s) return result; for (var i=0; i<=s.length-n; i++) { result.push(s.substr(i,n)); } return result; } function wordSplitTokenizer(s) { //tokenizer:wordSplitTokenizer if (!s) return []; return s.split(/\s+/); } function characterFrequencyTokenizer(s) { //tokenizer:characterFrequencyTokenizer (letters only) var result = []; for (var i=0; i<=25; i++) { var val=0; if (s) { for (j=0; j<s.length; j++) { var code=s.charCodeAt(j); if (code==i+65 || code==i+97) val++; } } result.push(val); } return result; } //tokenMatchers: function sift4TokenMatcher(t1,t2) { //tokenMatcher:sift4TokenMatcher var similarity=1-sift4(t1,t2,5)/Math.max(t1.length,t2.length); return similarity>0.7; } //matchingEvaluators: function sift4MatchingEvaluator(t1,t2) { //matchingEvaluator:sift4MatchingEvaluator var similarity=1-sift4(t1,t2,5)/Math.max(t1.length,t2.length); return similarity; } //localLengthEvaluators: function rewardLengthEvaluator(l) { if (l<1) return l; //0 -> 0 return l-1/(l+1); //1 -> 0.5, 2-> 0.66, 9 -> 0.9 } function rewardLengthEvaluator2(l) { return Math.pow(l,1.5); // 0 -> 0, 1 -> 1, 2 -> 2.83, 10 -> 31.62 } //transpositionCostEvaluators: function longerTranspositionsAreMoreCostly(c1,c2) { return Math.abs(c2-c1)/9+1; }
As always, I will be most happy to know if you used my algorithm and how it performed, as well as receive any suggestion that you might have.
Here is some explanation for the options of the general algorithm.
It no longer searches for characters, but for tokens. That is why the default tokenizer function splits the values into characters so that the algorithm would work on an array of one character long tokens. Other options are possible, like splitting the strings by empty spaces so that the comparisons are done on words or transforming a string into an array of strings N characters long, the so called N-grams. The tokenizer can be anything, like the characterFrequencyTokenizer, which turns each word in an array of 25 values representing the number of letters in the word for each letter a-z.
The tokenMatcher function returns true if two tokens are matching. They can be fuzzy matched, for example the sift4tokenMatcher uses Sift inside Sift to determine the character distance between two tokens and returns true if they match more than 70%.
The matchingEvaluator is a function that returns the value that will be added to the "common substring" length value when two tokens match. The default is 1, but one can use some other metric, like the similarity, for example. Of course, the common substring length has lost its meaning when these functions change, but the variable local_cs is still used.
The lengthEvaluator is taking the length value of the local common substring and returns a value that will be added to the longest common subsequence value. Usually it returns the same value as the one provided, but some functions could reward longer substrings.
FAQ:
Q: Can you make Sift4 to work case insensitive?
A: Just turn the strings to lower or upper case before you compare them. Since this algorithm is more general, the concept of 'case' might not apply.
Q: Can you make Sift4 to compare strings based on their meaning, like using synonyms?
A: Use a tokenizer function that splits the strings into words, then replaces them with the first of their synonyms. A more complex solution would require to analyse the strings beforehand and turn them into some ordered synonym or equivalent expressions equivalents, then use Sift4 with a word tokenizer (one is provided in the Extended algorithm source)
Q: I need an implementation for this programming language, can you help?
A: I can, but I might not have the time. Ask anyway, maybe I can be persuaded :)
Q: I have been using Sift3 until now, how do I upgrade to Sift4?
A: The best way I can think of is to implement Sift4 Simplest, as it needs only the Sift3 code and some minor changes. Since you never needed tokens before, I doubt you need them now. But if you do, I can help, see the above question.
Q: How can I reward you for this fantastic piece of software engineering?
A: While I did this for free and I don't expect to make any money out of it and while this algorithm is completely free to use and change as you see fit, I don't mind having a beer every now and then ;)
Q: Your algorithm really sucks because... reasons.
A: It may. I would be glad to discuss the reasons, though, and try to fix any problem you encounter.
Q: I compared Sift4 with another algorithm that is much more exact and there are differences.
A: Of course, they are different algorithms. This is a fuzzy distance calculator, it doesn't give you the exact value. There are still edge cases. But the idea of Sift is to be fast and relatively accurate, rather than very accurate. You need more accuracy, try to combine Sift with Levenshtein for example, computing Levenshtein only where Sift says the strings are above a certain similarity.
Q: I want to make maxOffset dependent on the length of the strings compared. Can you do that?
A: That is a perfect example why maxOffset should be a parameter of the function rather than a member of the class. Since this implementation is so far Javascript only, just compute the maxOffset that is convenient to you before you compare.
Q: I want to vary the weight of matches based on the position of the match, for example matches at the beginning of the string could be more valuable than those at the end.
A: The position of the match is indeed not sent to the functions that can be specified in the options object of the Sift4 Extended, but that can be trivially changed in the code. I don't think this particular request is very common, though, and I prefer to keep it out of the published implementation to make the code easier to understand.
Q: I found a bug!
A: Let me know it and I will try and fix it.
Q: If you need to compare large lists of strings, it is better to precompute some things, like specific hashes or suffix trees, etc. This will speed up the comparison tremendously!
A: Sift is what is called an online algorithm. It does not precompute anything, it just gets the two strings and the parameters for its functioning and returns the distance. You are correct in what you are saying, but that kind of solution is not in the scope of Sift, at least not version 4.
Q: What are the edge cases for Sift?
A: Probably there are several, but I didn't really spot them. One of them is that one might find both letters at a position matching letters at other positions, but only one will count. Example 'abxx' and 'bayy'. The algorithm will look at position 0, find no match, then try to find the closest match for each letter. Starting with position 0 in the first string it will find 'a' matched in position 1 in the second. It will increase both counters and lcss will be increase as well. Next check will be 'b', the character at position 1 in the first string matched with position 2 in the second string. No match, therefore both counters will be reset to 1, and starting search again. The 'b' match is lost and distance is 3 instead of 2. Also I think there might be some situations where the counters are not equal and the biggest of them reaches the end of its string, thus terminating the algorithm, but there could have been more matches. Incidentally I tried to fix both these issues and the error from Levenshtein was not really affected, but I am not 100% sure of the implementation.
Q: The algorithm continues to be asymmetric, Sift4(s1,s2) can be different from Sift4(s2,s1).
A: Yes. This is one of the artifacts of the linear nature of the algorithm. There is a function that is symmetric and that is Math.min(Sift4(a,b),Sift4(b,a)), however it is twice as slow, obviously.
Implementations in other languages:
Powershell implementation of simple Sift4, by Kirk Sayre:
function Calc-Sift4Distance {
<#
.SYNOPSIS
Compute the edit distance between 2 strings using the sift4 string
edit distance algorithm.
.PARAMETER s1
The 1st string
.PARAMETER s2
The 2nd string
.PARAMETER maxOffset
The maximum common substring length for which to search. The default
is 10.
.RETURN
The # of edits needed to make the given 2 strings equal.
#>
Param(
[Parameter(Mandatory = $True, ValueFromPipelineByPropertyName = $True)]
[String]
$s1,
[Parameter(Mandatory = $True, ValueFromPipelineByPropertyName = $True)]
[String]
$s2,
[Parameter(ValueFromPipelineByPropertyName = $True)]
[Int]
$maxOffset = 10
)
# Handle null or empty strings.
if ((-not $s1) -or ($s1.length -eq 0)) {
if (-not $s2) {
return 0
}
return $s2.length
}
if ((-not $s2) -or ($s2.length -eq 0)) {
return $s1.length
}
# Initialization.
$l1 = $s1.length
$l2 = $s2.length
$c1 = 0 # Cursor for string 1.
$c2 = 0 # Cursor for string 2.
$lcss = 0 # Largest common subsequence.
$local_cs = 0 # Local common substring.
# Scan strings.
while (($c1 -lt $l1) -and ($c2 -lt $l2)) {
if ($s1[$c1] -eq $s2[$c2]) {
$local_cs++
}
else {
$lcss += $local_cs
$local_cs = 0
if ($c1 -ne $c2) {
# Using max to bypass the need for computer transpositions ('ab' vs 'ba').
$c1 = $c2 = (@($c1, $c2) | Measure -Max).Maximum
}
for ($i = 0; (($i -lt $maxOffset) -and ((($c1 + $i) -lt $l1) -or (($c2 + $i) -lt $l2))); $i++) {
if ((($c1 + $i) -lt $l1) -and ($s1[$c1 + $i] -eq $s2[$c2])) {
$c1 += $i
$local_cs++
break
}
if ((($c1 + $i) -lt $l2) -and ($s1[$c1] -eq $s2[$c2 + $i])) {
$c2 += $i
$local_cs++
break
}
}
}
$c1++
$c2++
}
$lcss += $local_cs
return [math]::Round((@($l1, $l2) | Measure -Max).Maximum - $lcss)
}Thanks to Hugo Amaro, a C++ implementation:
struct sift_offset {
int c1;
int c2;
bool trans;
};
template<typename T>
int sift4(T * s1, int s1_size, T * s2, int s2_size, int maxOffset, int maxDistance) {
if (!s1 || !s1_size) {
if (!s2) {
return 0;
}
return s2_size;
}
if (!s2 || !s2_size) {
return s1_size;
}
int l1 = s1_size;
int l2 = s2_size;
int c1 = 0; //cursor for string 1
int c2 = 0; //cursor for string 2
int lcss = 0; //largest common subsequence
int local_cs = 0; //local common substring
int trans = 0; //number of transpositions ('ab' vs 'ba')
std::vector<sift_offset> offset_arr; //offset pair array, for computing the transpositions
while ((c1 < l1) && (c2 < l2)) {
if (s1[c1] == s2[c2]) {
local_cs++;
bool isTrans = false;
//see if current match is a transposition
int i = 0;
while (i<offset_arr.size()) {
sift_offset ofs=offset_arr[i];
if (c1<=ofs.c1 || c2 <= ofs.c2) {
// when two matches cross, the one considered a transposition is the one with the largest difference in offsets
isTrans=std::abs(c2-c1)>=std::abs(ofs.c2-ofs.c1);
if (isTrans)
{
trans++;
}
else
{
if (!ofs.trans) {
ofs.trans = true;
trans++;
}
}
break;
}
else {
if (c1>ofs.c2 && c2>ofs.c1) {
offset_arr.erase(offset_arr.begin()+i);
}
else {
i++;
}
}
}
offset_arr.push_back({
c1,
c2,
isTrans
});
}
else {
lcss += local_cs;
local_cs = 0;
if (c1 != c2) {
c1 = c2 = (int)min(c1, c2); //using min allows the computation of transpositions
}
//if matching characters are found, remove 1 from both cursors (they get incremented at the end of the loop)
//so that we can have only one code block handling matches
for (int i = 0; i < maxOffset && (c1+i<l1 || c2+i<l2); i++) {
if ((c1 + i < l1) && (s1[c1 + i] == s2[c2])) {
c1+= i-1;
c2--;
break;
}
if ((c2 + i < l2) && (s1[c1] == s2[c2 + i])) {
c1--;
c2+= i-1;
break;
}
}
}
c1++;
c2++;
if (maxDistance)
{
int temporaryDistance=(int)max(c1,c2)-lcss+trans;
if (temporaryDistance>=maxDistance) return std:round(temporaryDistance);
}
}
// this covers the case where the last match is on the last token in list, so that it can compute transpositions correctly
if ((c1 >= l1) || (c2 >= l2))
{
lcss += local_cs;
local_cs = 0;
c1 = c2 = (int)min(c1, c2);
}
}
lcss += local_cs;
return std::round((int)max(l1, l2) - lcss + trans); //add the cost of transpositions to the final result
}
You can find a Go implementation here, written by Jason W. Hutchinson.
There is also a Swift implementation here.
A Perl 6 implementation can be found here.
It was inevitable, both Naruto and Sasuke were getting ridiculously strong. In the end they fought the mother of all chakra and... of course they won, then they fought each other, but it was kind of underwhelming, since their power prevented any subtlety and they just went cowboy punching each other. The last color chapter is about how they leave it all to the next generation, although it is hard to think of anything more they could do to top their parents. I loved the entire series and it is easy to understand why: simple concept, positive feelings like friendship and camaraderie and weird magical ninja fights. I was a teen when I started watching the anime and now I am freakishly old. Well, life happens. After I got kind of tired of watching the anime, even if it was really well done and followed the manga faithfully, I went with reading the manga. I like to use Mangastream for my reading purposes, so you can read the entire thing here: 