Быстрый подсчет очков Хэмминга

Имеется база данных с N строками фиксированной длины. Существует строка запроса той же длины. Проблема состоит в том, чтобы извлечь первые k строк из базы данных, которые имеют наименьшее расстояние Хэмминга до q.

N мало (около 400), строки длинны, фиксированы по длине. База данных не изменяется, поэтому мы можем предварительно вычислить индексы. Запросы сильно различаются, кеширование и/или предварительное вычисление - это не вариант. Их много в секунду. Нам всегда нужны k результатов, даже если результаты k-1 имеют совпадение 0 (сортировка на расстоянии Хэмминга и первое значение k, поэтому нечувствительные к местоположению хэширование и подобные подходы не будут выполняться). kd-дерево и подобное разбиение пространства, вероятно, будут работать хуже, чем линейный поиск (строки могут быть очень длинными). BK-дерево в настоящее время является лучшим выбором, но оно все еще медленное и сложное, чем должно быть.

Похоже, что существует алгоритм, который будет строить индекс, который будет отбрасывать большинство записей за очень немногие шаги, оставив k <= t < N записей для вычисления реального расстояния Хэмминга.

Люди, предлагающие нечеткое соответствие строк, основанное на расстоянии Левенштейна, - спасибо, но проблема намного проще. Обобщенные методы, основанные на метрических расстояниях (например, BK-деревья), хороши, но, возможно, есть что-то, использующее описанные выше факты (небольшие строки с фиксированными размерами DB/long, простое расстояние Хэмминга)

Ссылки, ключевые слова, документы, идеи? =)

Ответ 1

Это похоже на задачу, в которой может работать Vantage Point (дерево VP)... поскольку расстояние от хамминга должно удовлетворять теореме о неравенстве треугольника, вы должны иметь возможность применить его... его также хорошо для определения k-ближайшего. Я видел это в настройках базы данных индексирования изображений... вы можете проверить раздел 5 эту статью в качестве примера того, что я говорю (хотя и в другом поле).

Ответ 2

Все расстояния помех могут быть произведены в O (K ^ 2/D) с использованием кода python ниже.
В некоторых случаях это происходит быстрее, чем тривиальный код, который является O (N * K).

Где N - количество строк фиксированной длины
K - длина каждой строки и D - размер словаря.

# DATABASE is a tuple of the strings
# eg. ('asdfjjajwi...', 'hsjsiei...', ...)

# SINGLE is the string you are matching
# eg. 'jfjdkaks...'

SIZE_OF_STRING = 5000
NUMBER_OF_STRINGS = 400
FIRST_K_REQUIRED = 100

def setup_index():
  index = []
  for x in xrange(SIZE_OF_STRING):
    index_dict = {}
    for y in xrange(NUMBER_OF_STRINGS):
      temp = index_dict.get(DATABASE[y][x], [])
      temp.append(y)
      index_dict[DATABASE[y][x]] = temp
    index.append(index_dict)
  return index

index = setup_index()

output = []
for x in xrange(NUMBER_OF_STRINGS):
  output.append([SIZE_OF_STRING, x])

for key, c in enumerate(SINGLE):
  for x in index[key][c]:
    output[x][0] -= 1

output.sort()
print output[:FIRST_K_REQUIRED]

Это более быстрый метод, только если SIZE_OF_STRING/DICTIONARY_SIZE < NUMBER_OF_STRINGS.

Надеюсь, что это поможет.

EDIT: Сложность приведенного выше кода неверна.

Расстояния Хэмминга могут быть произведены в O (N * K/D) в среднем.
Это быстрее в случаях ALL, чем тривиальный код, который является O (N * K).

Где N - количество строк фиксированной длины
K - длина каждой строки и D - размер словаря.

Ответ 3

По моему мнению, деревья BK отлично подходят для поиска всех строк не более, чем "разницы" K из строки запроса. Это другой вопрос, чем поиск ближайших элементов X. Вероятно, это является причиной проблем с производительностью.

Мое первое наклонение состоит в том, что, если скорость действительно важна, конечной целью должно быть построение (DFA) для обработки этого проблема. Дональд Кнут работал над связанной проблемой и разработал метод Trie, который имитирует DFA. Этот метод особенно хорош, когда у вас есть много возможных слов в стартовом словаре для поиска. Я думаю, что ваша проблема может быть интересным продолжением этой работы. В своей первоначальной работе целью DFA была попытка сопоставить входную строку со словами в словаре. Я считаю, что то же самое можно было бы сделать для этой проблемы, но вместо этого вернуло бы самые близкие элементы K к запросу. По сути, мы расширяем определение принимающего состояния.

Можно ли это делать, зависит от количества принимающих состояний, которые необходимо включить. Я думаю, что ключевая идея - это совместимые наборы. Например, представьте на числовой строке, что у нас есть элементы 1,2,3,4,5, и для любого запроса нужны два ближайших элемента. Элемент 2 может быть в двух возможных наборах (1,2) или (2,3), но 2 никогда не может быть множеством с 4 или 5. Поздно, поэтому я не уверен, что лучший способ построить такой как DFA на момент. Похоже, в ответе может быть достойная бумага.

Ответ 4

Эта проблема, по-видимому, сильно связана с алгоритмом Knuth "trie", для которого существует несколько весьма оптимальных специальных решений, в основном связанных с их когерентностью кэш-памяти и ускорением процессора (побитовое).

A trie - отличное решение для связанной проблемы - сходство начала строки, что, конечно, делает ее идеальным решением для поиска набора минимально уникальных строковых решений из любой точки, начинающейся с начала строки. Побитовое trie в этом случае имеет среднюю производительность O (1) на практике, наихудший случай O (m), где M - длина ключа. В целом его производительность для поиска, вставки и удаления такая же, как и хеш, за исключением того, что у нее нет проблем с конфликтом чистого хэшированного массива.

Я столкнулся с этим вопросом, потому что искал информацию о побитовых попытках и реализовал их сходство с некоторыми алгоритмами хамминга, поэтому, возможно, этот класс алгоритмов станет для вас плодотворной областью изучения. Удачи.