Вот быстрый и простой метод, затем вариант с лучшей производительностью за счет увеличения объема памяти.
In: массив Uint X [], например, 1M 32-битные слова
Требуется: функцияnear( Uint q ) -> j с небольшим hammingdist( q, X[j] )
Метод: двоичный поиск q в отсортированном X, затем линейный поиск блока вокруг него.
Псевдокод:
def near( q, X, Blocksize=100 ):
preprocess: sort X
Uint* p = binsearch( q, X ) # match q in leading bits
linear-search Blocksize words around p
return the hamming-nearest of these.
Это быстро - Бинарный поиск 1M слов + ближайший хеммингдист в блоке размером 100 занимает <10 нас на моем компьютере Mac.(Это сильно зависит от кэша - ваш пробег <em>будет варьироваться.)
Насколько близко это будет к нахождению истинного ближайшего X [j]?Я могу только экспериментировать, не могу сделать математику:
для 1M случайных запросов в 1M случайных слов, ближайшее совпадение в среднем на 4-5 разрядов, против 3 для истинного ближайшего (линейное сканирование все 1M):
near32 N 1048576 Nquery 1048576 Blocksize 100
binary search, then nearest +- 50
7 usec
distance distribution: 0 4481 38137 185212 443211 337321 39979 235 0
near32 N 1048576 Nquery 100 Blocksize 1048576
linear scan all 1048576
38701 usec
distance distribution: 0 0 7 58 35 0
Запустите ваши данные с размерами блоков, скажем, 50 и 100, чтобы увидеть, как уменьшаются расстояния совпадений.
Чтобы стать еще ближе, за счет удвоения памяти,
сделайте копию
Xswap из
X с заменой верхнего / нижнего полуслов и верните лучшее из
near( q, X, Blocksize )
near( swap q, Xswap, Blocksize )
С большим объемом памяти можно использовать гораздо больше битовых копий X, например, 32 вращения.
Я понятия не имею, как меняется производительность с Nshuffle и Blocksize - вопрос для теоретиков LSH.
(добавлено): для почти полного соответствия строк битов, скажем, 320 бит, 10 слов, составляют 10 массивов указателей, отсортированных по слову 0, слову 1 ... и поисковым блокам с помощью binsearch, как указано выше:
nearest( query word 0, Sortedarray0, 100 ) -> min Hammingdist e.g. 42 of 320
nearest( query word 1, Sortedarray1, 100 ) -> min Hammingdist 37
nearest( query word 2, Sortedarray2, 100 ) -> min Hammingdist 50
...
-> e.g. the 37.
Это, конечно, будет пропускать близкие совпадения, где нет ни одного словазакрыть, но это очень просто, а sort и binsearch невероятно быстро.Массивы указателей занимают ровно столько же места, сколько биты данных.100 слов, 3200 битов будут работать точно так же.
Но: это работает, только если есть приблизительно равные числа 0 бит и 1 бит, а не 99% 0 бит.