mapping similar strings to same number values

Question

I need a way to map strings to a numeric space, where the mapping moves similar strings to the same number.

For example:

in

str1 = 'some random string one'
str2 = 'some rzndom string one'
str3 = 'some rndom string one'
str4 = 'a very different string'

we would want [str1, str2, str3] all to be mapped to the same number, while str4 be mapped to a relatively distant number

We can assume all the strings are lowercase and have no punctuation.

What I've tried

So far, I've come up with using the sum of the ascii values and rounding down by some factor:

class StringMapper(TestCase):
    def translate_string_to_numeric_space(self, strr: str, granularity: int) -> int:
        list_of_char_vals = [ord(c) for c in strr]
        sum_of_chars = sum(list_of_char_vals)
        granularity_reduced_sum = self.round_down_to_nearest_multiple_of(sum_of_chars, granularity)
        return granularity_reduced_sum

    @staticmethod
    def round_down_to_nearest_multiple_of(num: int, multiple: int) -> int:
        return num - (num % multiple)

Then we get:

vals = [self.translate_string_to_numeric_space(s, 100) for s in [str1, str2, str3, str4]]

[2100, 2100, 2000, 2200]

What works in this solution:

1. it allowed a single typo ('a' -> 'z' in str1, str2)

What didn't work in this solution:

1. it did not allow for omissions (str3 was not grouped with str1 and str2)
2. it did not create sufficient distance between str4 and the others

Welcoming any ideas, thank you!!

---

Clarification String-to-string comparison such as jaro-winkler or levenstein is not an option, as we have a very large number of strings, and pair-wise comparison squares the number of operations

Answer 1

It might be useful to frame this problem using common terminology. Hashing is mapping an object, a string in this case, to an integer. What you want are collisions (i.e., similar objects are mapped to the same integer bucket). The goal is to pick a hashing function that does that based on the number of shared letters in the string.

A scalable implementation of this idea is MinHash and locality-sensitive hashing (LSH).

Here is a rough version using Python's datasketch library:

from datasketch import MinHash, MinHashLSH

str1 = 'some random string one'
str2 = 'some rzndom string one'
str3 = 'some rndom string one'
str4 = 'a very different string'
strings = [str1, str2, str3, str4]

# Hash each string, letter-by-letter
hashes = []
for s in strings:
    m = MinHash(num_perm=128)
    for c in s:
        m.update(c.encode('utf8')) 
    hashes.append(m)

# Create LSH storage
lsh = MinHashLSH(threshold=0.8, num_perm=128)
for n, hash_value in enumerate(hashes, 1):
    lsh.insert(f"str{n}", hash_value)

# Test that the queries for the hash values return expected neighbors
hash_str1 = hashes[0]
assert set(lsh.query(hash_str1)) == set(['str1', 'str2', 'str3'])
hash_str4 = hashes[3]
assert set(lsh.query(hash_str4)) == set(['str4'])

Answer 2

It seems that a string similarity metric might help.

The Levenshtein distance could be useful and it has a python module:

from Levenshtein import distance

str1 = 'some random string one'
str2 = 'some rzndom string one'
str3 = 'some rndom string one'
str4 = 'a very different string'

print(distance(str1, str2))
print(distance(str1, str3))
print(distance(str1, str4))

Output:

1
1
18

You might need further investigation as it only gives you relative distances, not an absolute mapping. Maybe using Nearest Neighbors with the Levenshtein distance will work.

Hope it helps

Answer 3

For most cases, the following code will work:

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int main()
{
    vector<string> s;
    s.push_back("some random string one");
    s.push_back("some rzndom string one");
    s.push_back("some rndom string one");
    s.push_back("a very different string");
    s.push_back("it doesn'n work");
    s.push_back("it works");
    s.push_back("money back");
    s.push_back("back money");
    for (auto c : s) {
        vector<double> v;
        v.resize(c.size());
        double d = 0;
        for (int i=0; i<c.size()-1; i++) {
          v[i] = c[i]-c[i+1];
        }
        v[v.size()-1] = c[c.size()-1]-c[0];
        for (int i=0; i<v.size(); i++) {
          d += exp(-(v[i]*v[i]));
        }
        d *= pow(1.0/v.size(),1.0/v.size());
        cout << d << endl;
    }
    return 0;
}

Results for this example will be: 0.687062 0.687062 0.683994 1.53064 0.0153933 9.5162e-05 0.62808 0.613531