Какого порядка расстояния, которые предполагаются в запросе?
Я бы взял обычное бинарное дерево (ветвление по значению какого-нибудь бита; в каждом узле указано, по какому биту ветвиться). Тогда поиск(дерево,d)=поиск(поддерево с правильным значением бита,d)+поиск(поддерево с неправильным значением бита,d-1).
еще в узле можно хранить маску битов, которая в данный момент общая для всех данных в этом поддереве. Позволит быстро отсекать совсем неправильные пути.
Питона я, к сожалению, не знаю. На псевдо-C++ основной класс и функция поиска могли бы выглядеть так (пример упрощенный, для 32-битных масок. И не проверялся):
struct tree{
int mbit,cmask,cbits;
tree *z0,*z1;
void find(int targ,int dist,ResAcc &res){
if(dist<0) return;
int d=hamdist(targ&cmask,cbits&cmask);
if(d>dist) return;
if(cmask==-1){ res.Add(cbits); return; }
int h=(targ&mbit) ? 1 : 0;
z0->find(targ&~mbit,dist-h,res);
z1->find(targ|mbit,dist-1+h,res);
}
}
Здесь mbit — маска бита, по которому происходит ветвление в данном узле дерева, cmask — маска битов, которые в данный момент одинаковы во всем поддереве, начинающемся с этого узла, а cbits — значения этих одинаковых битов. z0 — поддерево, для всех элементов которого бит mbit равен 0, а z1 — поддерево элементов, для которых он равен 1. Листья характеризуются тем, что в них cmask=-1, а z0=z1=NULL (в остальных узлах обе ссылки z0,z1 ненулевые). Значение, лежащее в листе — cbits.
К сожалению, эта структура тратит в 4-6 раз больше памяти, чем просто список масок. И понятно, что для длинных масок ее можно улучшить: хранить бит как индекс в массиве+маску в элементе массива, а расстояние считать тоже с учетом маски, не выполняя предварительно «and».
Как-то так. Дальше надо уже экспериментировать.
Попробовал реализовать на массивах на C. Получилось примерно 0.25 сек на поиск для D=15 (среднее число ответов — около 60000, поскольку множество масок было линейно связным в Z2^256)
Когда расстояние между соседними масками увеличилось до 10, то на поиск при D=15 стало тратиться 0.7 сек (и среднее число ответов — 3: сама маска и две соседних).
Вот спасибо, это действительно получается быстро. Только я нормально не могу осилить что-то реализацию этого дерева :( Если вас не затруднит, можете показать мне Ваш тестовый пример на C.
Соптимизировал вычисление расстояния между масками — скорость возросла до 0.057 сек/поиск (при D=15).
Программа здесь: astr73.narod.ru/Files/testham.cpp. Правда, она без комментариев. Там функция FillBase как-то заполняет базу (параметры — число масок и расстояние между соседними масками), PrepareTree готовит базу к поиску, а Find — ищет соседей данной маски (результат скапливается в массиве Res, nres — число найденных соседей). В примере маски для поиска берутся из самой базы, но это не обязательно.
Простой
