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

Question

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

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

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

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

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

Answer 1

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

Answer 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

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

---

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

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

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

Answer 3

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

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

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

Answer 4

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

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

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