Хеш, который находит близкие результаты

Question

У меня есть таблица, которая содержит около 10000 записей, каждая запись имеет почти 100 логических значений.Пользователь устанавливает флажок для множества логических значений и надеется получить результат, соответствующий его запросу.Если эта запись не существует, я хочу показать им, может быть, 5 записей, которые близки (имеют только одно или два значения разные).Есть ли хорошая система хеширования или структура данных, которая может помочь мне найти эти результаты.

Answer 1

Растровые индексы. Google для бумаги, если вы хотите полный фон, это не просто, но стоит прочитать. По сути, создайте битовые значения для ваших логических значений, например:

010110101010
110100010100
000101001100

А затем просто XOR ваш фильтр через них, сортировка по количеству совпадений, возврат. Поскольку все операции выполняются безумно быстро (около одного цикла на элемент, а структура данных использует (редактирует) 100 бит памяти на элемент), это обычно работает, даже если оно линейно.

Приложение: Как сделать XOR. (исправлена ​​ошибка)

000101001100 source
000101001010 target
000000000110 result of XOR

 int n = 0; if (v) do { n++; } while (v &= (v-1)); return(n);

Две единицы говорят вам, что есть 2 ошибки и m-2 совпадения, где m - количество битов.

Answer 2

Что вы описываете - это поиск ближайшего соседа : на основе записи найдите 5 ближайших записей на основе функции произвольного расстояния (например, количества различных значений).

Функция хеширования преднамеренно отбрасывает любую информацию, кроме «эти значения равны», поэтому на самом деле это не тот путь.

Попробуйте вместо этого использовать структуру данных, оптимизированную для поиска ближайших соседей, например kd-дерево или vp-дерево .Если существует высокая вероятность того, что запись уже существует в списке, вы можете сначала использовать хеш-таблицу для ее поиска, а затем вернуться к дереву kd, если оно не существует.

Answer 3

Это основано на ответе Кданского.

Create a dynamic array of entries.
Create a cache.

for each lookup,
   check the cache.
   return the cache entry if the value exists.
   otherwise for each value in the dynamic array,
       if hamming distance is less than threshold add to the result list
   cache the value against the result
   return the result

, чтобы найти расстояние Хемминга: xor и найти вес Хемминга http://en.wikipedia.org/wiki/Hamming_weight