Существует база данных с N строками фиксированной длины. Есть строка запроса той же длины. Проблема состоит в том, чтобы получить первые k строк из базы данных, которые имеют наименьшее расстояние Хэмминга до q.

N небольшое (около 400), строки длинные, фиксированные по длине. База данных не изменяется, поэтому мы можем предварительно вычислять индексы. Запросы сильно различаются, кэширование и / или предварительное вычисление не вариант. Их много в секунду. Нам всегда нужно k результатов, даже если результаты k-1 совпадают с 0 (сортировка по расстоянию Хэмминга и получение первых k, поэтому хеширование с учетом локальных особенностей и аналогичные подходы не подходят). kd-дерево и аналогичное разбиение пространства, вероятно, будут работать хуже, чем линейный поиск (строки могут быть очень длинными). BK-дерево в настоящее время является лучшим выбором, но оно все еще медленное и сложное, чем должно быть.

Такое ощущение, что существует алгоритм, который создаст индекс, который отбросит большинство записей за несколько шагов, оставляя k <= t << N записей для вычисления реального расстояния Хэмминга.

Люди, предлагающие нечеткое сопоставление строк на основе расстояния Левенштейна - спасибо, но проблема гораздо проще. Обобщенные подходы, основанные на метрике расстояния (например, BK-деревья), хороши, но, может быть, есть что-то, использующее факты, описанные выше (небольшие БД / длинные строки фиксированного размера, простое расстояние Хэмминга)

Ссылки, ключевые слова, статьи, идеи? знак равно