10

I have a database of 350,000 strings with an average length of about 500. The strings are not made up of words, they are an essentially random assortment of characters.

I need to make sure no two of the strings are too similar, where similarity is defined as edit distance divided by avg length of string. The division is because smaller edit distances are more acceptable for smaller strings. It is fine if a different metric is used for performance reasons, but edit distance is the preferred baseline metric.

Naively, we calculate edit distance with runtime O(a*b), where a,b are the length of the two strings. We do this for all n^2 pairs, which gives an overall runtime of O(n^2*a*b), clearly too large with n=350,000, a,b=500.

The database is in the form of a Python list read from a csv file. I'd like to process it in a Pythonic way, if possible.

How can this be sped up? I'm not sure how long the naive algorithm will take to finish (on the order of weeks) but it ideally should take less than a day to run.

15
  • 1
    Constructing an FST will allow you to do the search much faster. Commented Feb 16, 2018 at 7:20
  • Can you tell us more about the database? Is it a DBMS? NOSQL? What are we dealing with here? Are you trying to write a query to do this, or are you loading all the strings from the DB and doing your calculations in the python code itself? How much does it need to be sped up?
    – mypetlion
    Commented Feb 20, 2018 at 0:35
  • @mypetlion Updated. Commented Feb 20, 2018 at 0:36
  • 1
    Does ratio or partial_ratio from pypi.python.org/pypi/fuzzywuzzy work for you? Or you need edit distance only? Commented Feb 20, 2018 at 8:42
  • 1
    It seems like that you might want to use some sort of en.wikipedia.org/wiki/Locality-sensitive_hashing . There are developed ones for hamming distance.
    – Haochen Wu
    Commented Feb 20, 2018 at 18:12

1 Answer 1

4
+50

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

14
  • Question before I implement and play around with this (and then accept your answer): have you runtime tested this with some strings (350,000 @ 500 each)? Commented Feb 20, 2018 at 20:33
  • Just run on a synthetic dataset and it takes less than 1 min without problem. You might still want to wait a bit before accepting just in case others might have better answer, but you can start to play with it cause it's really fast.
    – Haochen Wu
    Commented Feb 20, 2018 at 20:45
  • True. Your explanation was very clean and concise and I appreciate the arxiv source as well. Thanks. Commented Feb 20, 2018 at 20:46
  • I have a possible issue with the approach provided. Since the maximum length is 500, a sampling length of 500 should not show any duplicates. However, I find that counter has only 85,701 entries from a dataset of 350,820 using the above parameters. Is this expected behavior? Commented Feb 20, 2018 at 21:42
  • 1
    @EvanWeissburg I am glad it worked well for you. I just saw your chat discussions, as you are working on biological data hamming distance will work unless there are lots of insertions and deletions.
    – viz12
    Commented Feb 21, 2018 at 17:30

Your Answer

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

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