Быстрый выигрыш Расстояния Хемминга

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

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

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

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

Ссылки, ключевые слова, бумаги, идеи?=)