Поиск строк, где расстояние Хэмминга меньше порогового значения

Question

В настоящее время я работаю над приложением, где у меня есть большое количество хеш-значений (строк).
Когда задано хэш-значение запроса (строка), процесс поиска проходит через эти строки и возвращает строки, где Hamming Distance между строкой запроса и строкой результата меньше заданного порогового значения.

• Хеш-значения не двоичные строки. например "1000302014771944008"
• Все значения хэша (строки) имеют одинаковую фиксированную длину.
• Пороговые значения не являются небольшими (обычно t>25) и могут варьироваться.

Я хочу реализовать этот процесс поиска, используя эффективный алгоритм, а не используя метод грубой силы.
Я прочитал некоторые исследовательские работы (например, this & this), но они предназначены для двоичных строк или для низких пороговых значений. Я также попробовал Locality-sensitive hashing, но реализации, которые я нашел, были сосредоточены на двоичных строках.

Существуют ли какие-либо алгоритмы или структуры данных для решения этой проблемы?
Любые предложения также приветствуются. Заранее спасибо.

.

Дополнительная информация

Расстояние Хемминга между небинарных строк

string 1: 0014479902266110001131133 
string 2: 0014409902226110001111133 
      ------------------------- 
       1  1  1 = 3 <-- hamming distance 

Считается перебором подход

1. вычислить расстояние Хэмминга между первой хэш строки а строка хеша запроса.
2. , если расстояние Хэмминга меньше порога, затем добавьте строку хеша в список результатов.
3. повторите шаги 1 и 2 для всех хэш-строк.

Answer 1

Что-то вроде этого может сработать для вас.

http://blog.mafr.de/2011/01/06/near-duplicate-detection/

Answer 2

Читать 7-й раздел этого документа:

"HmSearch: Эффективное расстояние Хэмминга Query Processing Алгоритм".

Состояния-искусства результата для задачи d-запрос можно найти по адресу:

«Словарь согласования и индексации с ошибками и не важен», который решает проблему д-запрос во время O (м + log (nm)^d + occ) с использованием пространства O (n * log (nm)^d), где occ - это число результатов запроса.

Если пороговые значения не являются мелкими, существуют практические решения для двоичных строк, найденных в HmSearch.

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