I wrote a very brief prototype of a simple locality sensitive hashing algorithm in python. However there are a few caveats and you may want to optimize some pieces as well. I'll mention them when we see them.
Assume all your strings are stored in strings
.
import random
from collections import Counter
MAX_LENGTH = 500
SAMPLING_LENGTH = 10
def bit_sampling(string, indices):
return ''.join([string[i] if i<len(string) else ' ' for i in indices])
indices = random.sample(range(MAX_LENGTH),SAMPLING_LENGTH)
hashes = [bit_sampling(string, indices) for string in strings]
counter = Counter(hashes)
most_common, count = counter.most_common()[0]
while count > 1:
dup_indices = [i for i, x in enumerate(hashes) if x == most_common]
# You can use dup_indices to check the edit distance for original groups here.
counter.pop(most_common)
most_common, count = counter.most_common()[0]
First of all, this is a slight variant of bit sampling that works best for the general hamming distance. Ideally if all your string are of the same length, this can give a theoretical probability bound for the hamming distance. When the hamming distance between two string is small, it is very unlikely that they will have different hash. This can be specified by the parameter SAMPLING_LENGTH
. A larger SAMPLING_LENGTH
will make it more likely to hash similar string to different hash but also reduce the probability of hashing not very similar string to the same hash. For hamming distance, you can calculate this trade-off easily.
Run this snippet multiple times can increase your confident on no similar strings since each time you will sample different places.
To accommodate your purpose to compare different length strings, one possible approach is to left padding space on shorter strings and make copies of them.
Though all of the operation in this snippet are linear (O(n)), it may still consume significant memory and running time and it might be possible to reduce a constant factor.
You might also want to consider using more complicated locality sensitive hashing algorithm such as surveyed here: https://arxiv.org/pdf/1408.2927.pdf
ratio
orpartial_ratio
from pypi.python.org/pypi/fuzzywuzzy work for you? Or you need edit distance only?