Быстрая проверка большой базы данных на сходство расстояния редактирования

Я написал очень краткий прототип простого алгоритма хеширования с учетом местоположения на Python. Однако есть несколько предостережений, и вы также можете оптимизировать некоторые части. Я упомяну их, когда мы их увидим.

Предположим, что все ваши строки хранятся в 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]

Прежде всего, это небольшой вариант битовой выборки, который лучше всего подходит для общего расстояния Хэмминга. В идеале, если все ваши строки имеют одинаковую длину, это может дать теоретическую оценку вероятности для расстояния Хэмминга. Когда расстояние Хэмминга между двумя строками мало, очень маловероятно, что они будут иметь разный хэш. Это можно указать параметром SAMPLING_LENGTH. Чем больше SAMPLING_LENGTH, тем больше вероятность хэширования похожей строки в другой хэш, но также снижается вероятность хеширования не очень похожей строки в тот же хэш. Для расстояния Хэмминга вы можете легко рассчитать этот компромисс.

Запустив этот фрагмент несколько раз, вы сможете повысить свою уверенность в отсутствии похожих строк, поскольку каждый раз вы будете пробовать разные места.

Чтобы удовлетворить вашу цель сравнения строк разной длины, один из возможных подходов состоит в том, чтобы оставлять пустое пространство для более коротких строк и создавать их копии.

Хотя все операции в этом фрагменте являются линейными (O(n)), они по-прежнему могут потреблять значительный объем памяти и времени выполнения, и может быть возможно уменьшить постоянный коэффициент.

Вы также можете рассмотреть возможность использования более сложного алгоритма хеширования с учетом местоположения, например описанного здесь: https://arxiv.org/pdf/1408.2927.pdf