1
$\begingroup$

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

$\endgroup$
1

3 Answers 3

3
+25
$\begingroup$

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'])
$\endgroup$
3
  • $\begingroup$ can you please update your code to produce the numeric value? (as opposed to putting all the MinHashes in a dict $\endgroup$ Mar 22 at 20:46
  • $\begingroup$ The MinHashes are in a list. You can index the list to get the numeric value - hashes[0].hashvalues $\endgroup$ Mar 23 at 23:59
  • $\begingroup$ Apologies for not awarding the bounty in time - I wasn't aware that it would expire, and now that I came here again it's too late $\endgroup$ Apr 20 at 19:15
1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ thank you, added a clarification as to why we can't do distance metrics $\endgroup$ Mar 15 at 18:12
  • $\begingroup$ Thank you. Could you detail what you want to achieve in this numerical space ? I am curious to understand the limitations of using the distance metrics $\endgroup$
    – etiennedm
    Mar 16 at 6:53
  • $\begingroup$ we have hundreds of millions of strings, if we do pair wise we'll have that many operations squared, which would be infeasible. I'm looking for a clever mathematical solution rather than build a massively parallelized string distance calculator system $\endgroup$ Mar 17 at 21:04
  • $\begingroup$ How representative is your example? In particular, do any two "similar" strings differ by only a few typos? $\endgroup$ Mar 18 at 4:08
  • $\begingroup$ if we do pair wise: You don't need to do pair wise, you could use BallTree-like approaches in the search of nearest neighbors. we have hundreds of millions of strings: could you give us more context about the data you have and what you want to achieve in this numerical space ? $\endgroup$
    – etiennedm
    Mar 18 at 16:09
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.