Самый быстрый способ извлечь совпадающие строки - PullRequest
Новая
       6

Самый быстрый способ извлечь совпадающие строки

0 голосов
/ 28 апреля 2018

Я хочу найти слова, которые соответствуют заданному слову в списке (пример ниже). Однако, скажем, есть список, который содержит миллионы слов. Каков наиболее эффективный способ выполнить этот поиск? Я думал о том, чтобы пометить каждый список и поместить слова в хеш-таблицу. Затем выполните поиск / совпадение слов и получите список слов, которые содержат это слово. Из того, что я вижу, эта операция займет O (n) операций. Есть ли другой путь? может быть без использования хеш-таблиц?. 

words_list = ['yek', 'lion', 'opt'];
# e.g. if we were to search or match the word "key" with the words in the list we should get the word "yek" or a list of words if there many that match

Кроме того, есть ли библиотека Python или сторонний пакет, который может выполнять эффективный поиск?

1 Ответ

0 голосов
/ 28 апреля 2018

Не совсем понятно, когда вы подразумеваете под «сопоставлением» здесь, но если вы можете уменьшить это до сравнения идентификаторов, проблема сводится к поиску набора, который составляет O (1) время.

Например, если «совпадение» означает «имеет точно такой же набор символов»: 

words_set = {frozenset(word) for word in words_list}

Затем, чтобы найти слово: 

frozenset(word) in words_set

Или, если это означает «имеет точно такой же мультимножество символов» (т. Е. Подсчет дубликатов, но игнорирование порядка): 

words_set = {sorted(word) for word in words_list}

sorted(word) in words_set

… или, если вы предпочитаете: 

words_set = {collections.Counter(word) for word in words_list}

collections.Counter(word) in words_set

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

Конечно, преобразование списка занимает O (N) времени (если только вы сначала не построите преобразованный набор вместо создания списка, а затем преобразуете его), но вы можете использовать его снова и снова, и это займет O (1) время каждый раз вместо O (N), что звучит так, как будто вы заботитесь о нем.

Если вам нужно вернуть соответствующее слово, а не просто знать, что оно есть, вы все равно можете сделать это с помощью набора, но это проще (если вы можете позволить себе потратить немного места) с помощью слова: 

words_dict = {frozenset(word): word for word in words_list}

words_dict[frozenset(word)] # KeyError if no match

Если может быть несколько совпадений, просто измените dict на multidict: 

words_dict = collections.defaultdict(set)
for word in words_list:
    words_dict[frozenset(word)].add(word)

words_dict[frozenset(word)] # empty set if no match

Или, если вы явно хотите, чтобы это был список, а не набор: 

words_dict = collections.defaultdict(list)
for word in words_list:
    words_dict[frozenset(word)].append(word)

words_dict[frozenset(word)] # empty list if no match

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

import blist # pip install blist to get it

words_dict = blist.sorteddict()
for word in words_list:
    words_dict.setdefault(word, set()).add(word)

words_dict[frozenset(word)] # KeyError if no match

Это выглядит почти идентично, за исключением того факта, что не совсем тривиально оборачивать defaultdict вокруг blist.sorteddict - но это занимает всего несколько строк кода. (И, может быть, вам на самом деле нужен KeyError, а не пустой набор, поэтому я решил, что стоит показать где-то как defaultdict, так и обычный dict с setdefault, так что вы можете выбрать.)

Но под прикрытием он использует гибридный вариант B-дерева вместо хеш-таблицы. Хотя это время O (log N) вместо O (1), в некоторых случаях оно на самом деле быстрее, чем dict.

...