Помогите найти идею для решения задачи!
Задача такова:
Дан список B битовых последовательностей длиной N, этот список достаточно велик (десятки и сотни тысяч).
На вход поступает битовая последовательность A такой же длины N, требуется найти все битовые последовательности из B расстояние по Хэммингу до которых от A меньше k и сделать это быстро (желательно в логарифмическое время).

-последовательный перебор происходит недопустимо долго
-хотелось бы как-нибудь сгруппировать последовательности из B, чтобы сделать индекс и быстро получать доступ к близким к A последовательностям, но что-то не придумывается простой индекс...
-в принципе можно ограничиться поиском ближайшей к A последовательности (идея в том, чтобы построить на последовательностях из B минимальное остовное дерево, найти ближайшее к A и затем смотреть по дереву до всех других последовательностей, расстояние до которых меньше k плюс расстояние между ближайшим к A и A)

кажется, эта задача может быть классической

заранее благодарен за любые идеи!

Здравствуйте, Аноним, Вы писали:

А>На вход поступает битовая последовательность A такой же длины N, требуется найти все битовые последовательности из B расстояние по Хэммингу до которых от A меньше k и сделать это быстро (желательно в логарифмическое время).

можно посмотреть в сторону метрических деревьев. гугли bk-tree, m-tree. критическим моментом при построении таких структур является выбор разбивающего элемента(-ов)

А>можно посмотреть в сторону метрических деревьев. гугли bk-tree, m-tree. критическим моментом при построении таких структур является выбор разбивающего элемента(-ов)

спасибо! хорошая идея с метрическими деревьями — к счастью, уже давно найдены алгоритмы даже в более общем виде для моей задачи