# Fast text comparison algorithm for long texts

I want to calculate a similarity ratio between two long texts (by "long", I imply something around 1000 characters or higher). For example, two texts with only one word changing should have a ratio approaching 100%, and a text compared to [the same one + another being the same size] should be 50%.

I know about texts comparison algorithms like Levenshtein or Jaro, but they tend to be too computationally-expensive in my case, given that I am doing comparisons of one text with several thousands of other ones.

I tried to experiment with ssdeep library (for those who do not know: it is an algorithm that splits a blob into several parts, hash each of these parts, then regroup them in a summary hash; this is an example of "fuzzy hashing"). It was promising since it reduces the text to an hash we just have to compare with another. However, since it deals on a binary level, the characters are often cut, which makes the comparison inaccurrate. Plus, the comparison does not work if the texts have a different size.

Is there a better solution that could fit this case, given that as I stated, I am privileging the low complexity over the complete accuracy?

• – D.W.
Jul 28 '21 at 22:57