Есть ли что-то быстрее BK-Tree?

Question

[Аркадий]

Я собираюсь хранить много данных для поиска по ним с помощью «расстояния хемминга».


Объем ~1 000 000. Решил использовать BK дерево, но при том-же миллионе поиск получается долгий, примерно 10-20 секунд.


Само дерево: dumpz.org/192335/ (Cython)


Может есть другие, более быстрые алгоритмы?

Comments

[Аркадий]

Уточню: Есть хеши 256 битные, они нужны для поиска похожих (или дубликатов) картинок

Answer 1

[Mrrl]

Какого порядка расстояния, которые предполагаются в запросе?
Я бы взял обычное бинарное дерево (ветвление по значению какого-нибудь бита; в каждом узле указано, по какому биту ветвиться). Тогда поиск(дерево,d)=поиск(поддерево с правильным значением бита,d)+поиск(поддерево с неправильным значением бита,d-1).

Comments

[Mrrl]

еще в узле можно хранить маску битов, которая в данный момент общая для всех данных в этом поддереве. Позволит быстро отсекать совсем неправильные пути.

[Аркадий]

Порог может быть 5-15.

Ваше решение немного не понял, можно чуть чуть подробней? (если возможно то с примером).

[Mrrl]

Питона я, к сожалению, не знаю. На псевдо-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».
Как-то так. Дальше надо уже экспериментировать.

[Mrrl]

Попробовал реализовать на массивах на C. Получилось примерно 0.25 сек на поиск для D=15 (среднее число ответов — около 60000, поскольку множество масок было линейно связным в Z2^256)

[Mrrl]

Когда расстояние между соседними масками увеличилось до 10, то на поиск при D=15 стало тратиться 0.7 сек (и среднее число ответов — 3: сама маска и две соседних).

[Аркадий]

Вот спасибо, это действительно получается быстро. Только я нормально не могу осилить что-то реализацию этого дерева :( Если вас не затруднит, можете показать мне Ваш тестовый пример на C.

[Mrrl]

Соптимизировал вычисление расстояния между масками — скорость возросла до 0.057 сек/поиск (при D=15).
Программа здесь: astr73.narod.ru/Files/testham.cpp. Правда, она без комментариев. Там функция FillBase как-то заполняет базу (параметры — число масок и расстояние между соседними масками), PrepareTree готовит базу к поиску, а Find — ищет соседей данной маски (результат скапливается в массиве Res, nres — число найденных соседей). В примере маски для поиска берутся из самой базы, но это не обязательно.

[Аркадий]

Спасибо! *ушел разбираться*

[Mrrl]

Удачи! Она очень пригодится :)

Answer 2

[AxisPod]

А к примеру воспользоваться специализированными средствами, например sphinx?

Comments

[Аркадий]

А как в свинксе вычислить расстояние хемминга?

Answer 3

[akzhan]

VP-tree. stackoverflow.com/questions/6389841/efficiently-find-binary-strings-with-low-hamming-distance-in-large-set

Comments

[Аркадий]

VP-tree не сильно быстрее, это сказано даже по вашей ссылке