Fastest algorithm to test for 75%+ similarity of 2 strings?

user_13383443 0
Viewed 92

I need a function that takes in 2 strings and returns a boolean if they are more than 75% similar. Levenshtein works, but I find it WAY too slow for the amount of data that I am processing.

If I can somehow determine the 75%+ similar first, I can then run the Levenshtein for the exact similarity match.

EDIT

Here are some examples of what I mean by similarity:

isSimilar75("texts", "txts") //TRUE, 85% similar
isSimilar75("hello world", "hello word") //TRUE, 91% similar
isSimilar75("this is an example of longer text", "this is an example of a longer txt") //TRUE, 92% similar
isSimilar75("this is a test", "test what") //FALSE, 29% similar

The function calculates similarity similar to levenshtein. I simply need a more simple version of levenshtein that only returns whether or not a string is "around" 75% similar based on the amount of character operations (add, subtract, and substitute characters). The function does not need to return a percentage or do any exact calculations, I will only run the expensive levenshtein on results that return true from this function.

sorting algorithm
2 Answers

The Levenshtein distance between two words is lowerbounded by the L1 distance between their frequency vectors. So we could do something like

import collections
def possiblySimilar75(s1, s2):
    c1 = collections.Counter(s1)
    c2 = collections.Counter(s2)
    return sum(abs(c1[x] - c2[x]) for x in set(c1.keys()) | set(c2.keys())) <= max(len(s1), len(s2)) / 4
user_21446690

You could use a linear loop that compares two sorted strings using counters for

  1. the first string index, ai
  2. the second string index, bi
  3. the same characters
  4. the not same characters

function strDiff(a = "", b = "")
{ const _a =
    [...a.toLowerCase()].sort()
    
  const _b =
    [...b.toLowerCase()].sort()

  const loop = (same, not, ai, bi) =>
  ai > a.length && bi > b.length
      ? same / (same + not)
  : ai > a.length || bi > b.length 
      ? loop(same, not + 1, ai + 1, bi + 1)
  : _a[ai] < _b[bi]
      ? loop(same, not + 1, ai + 1, bi)
  : _a[ai] > _b[bi]
      ? loop(same, not + 1, ai, bi + 1)
  : loop(same + 1, not, ai + 1, bi + 1)
  
  return loop(0, 0, 0, 0)
}
  
console.log(strDiff("fooBar", "floBro")) // 0.75

It works like this -

strDiff("fooBar", "floBro")
// ...

_a = abfoor 
_b = bfloor

//   same  not  ai  bi    _a[ai]     _b[bi] 
loop(0,    0,   0,  0) // "a"        "b"
loop(0,    1,   1,  0) // "b"        "b"
loop(1,    1,   2,  1) // "f"        "f"
loop(2,    1,   3,  2) // "o"        "l"
loop(2,    2,   3,  3) // "o"        "o"
loop(3,    2,   4,  4) // "o"        "o"
loop(4,    2,   5,  5) // "r"        "r"
loop(5,    2,   6,  6) // undefined  undefined
loop(6,    2,   7,  7) // undefined  undefined
6 / (6 + 2)            // same / (same + not)
0.75                   // <- output
user_6331830
Related