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