hash function to index similar text

Question

I'm searching about a sort of hash function to index similar text. So for example if we have two very long text called "A" and "B" where A and B differ not so much, then the hash function (called H) applied to A and B should return the same number.

So H(A) = H(B) where A and B are similar text.

I tried the "DoubleMetaphone" (I use italian language text), but I saw that it depends very strong from the string prefixes. For example:

A = "This is the very long text that I want to hash" B = "This is the very"

==> doubleMetaPhone(A) = doubleMetaPhone(B)

And this is not so good for me, beacause strings with the same prefix could be compared as similar and I don't want this.

Could anyone suggest me any other way?

Answer 1

You problem is (close to) insoluble for many distance functions between strings.

Most distance functions (e.g. edit distance) allow you to transform a string into another string via a sequence of 1-distance transformations:

"AAAA" -> "AAAB" -> "AAABC"

according to your requirements, the first and second strings should have the same hash value. But so must the second and the third, and so on. So all the strings will have to have the same hash, if we allow a pair with distance=1 to have the same hash value.

Even if we impose a higher threshold on the distance (maybe in relation to string length), we'll end up with a messy result.

A better (IMO) approach is to find an equivalence relation on the set of strings, such that each string in each equivalence class has the same hash. A possibility is to define classes by their distance to a predefined string (e.g. edit distance from "AAAAA"), and the distance itself would be the hash value. Probably this approach would not be the best in your case, but maybe with some extra info on the problem we can come up with a better equivalence relation.

Answer 2

I need to process a natural language text and to find an hash that groups "similar" text. Your strategy to find a "distance" to a predefined string could be good.

"distance" function could use this strategy:

Example:

0-string: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.......N" where N = strlen(my_string)

my-string: "this is the text that I need to compare and the distance could be the hash value"

Algorithm:

* ALGO *

• TO_UPPER_CASE(my_string);

• DELETE_SPACES(mystring);

• X=SUMM_VALUE_BIG(NOT_VOWELS);

• Y=SUMM_VALUE(VOWELS);

• VALUE = (X+Y)/LEN(MY_STRING);

• HASH = ALGO(my_string)-ALGO(0-string)

• Where: SUMM_VALUE_BIG = For every CAR (SUM = CAR at first step) => SUM = SUM * 11

* ALGO *

So the not_vowels has a higher weight than the vowels...

What do you think about this strategy?