Python: поиск совпадений парциальных строк в большом корпусе строк

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

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

matches = [s for s in allfiles if s.startswith(input)]

Я бы хотел, чтобы условие было гибким; например. вместо строгой startswith, это будет совпадение, если все буквы на входе отображаются в s в том же порядке. Что лучше, чем метод грубой силы, который я показываю здесь?

5 Solutions collect form web for “Python: поиск совпадений парциальных строк в большом корпусе строк”

Для точного сопоставления, как правило, способ реализовать что-то вроде этого – это сохранить ваш корпус в trie . Идея состоит в том, что вы храните каждую букву в виде узла в дереве, ссылаясь на следующую букву словом. Поиск матчей – это просто ходить по дереву и показывать всех детей вашего текущего местоположения. например. «кошка», «корова» и «автомобиль» будут храниться как:

  a--t / \ cr \ o--w

Когда вы получаете ac, вы начинаете с узла c, a затем переводит вас на узел c / a (дети «t» и «r», делая кошки и машины в качестве ваших завершений).

Обратите внимание, что вам также нужно будет пометить узлы, которые являются полными словами для обработки имен, которые являются подстроками других (например, «автомобиль» и «тележка»)

Чтобы получить желаемое нечеткое совпадение, вам может потребоваться внести некоторые изменения.

Я использовал Lucene для автозаполнения текстового поля с более чем 100 тысячами возможностей, и я воспринимал его как мгновенное.

Возможно, модуль readline – это то, что вы ищете. Это интерфейс для библиотеки текстовых библиотек GNU Python Documentation . Возможно, вы можете предоставить свою собственную функцию завершения с помощью set_completer() .

Гибкость, которую вы хотите для соответствия вашей строке, называется Fuzzy Matching или Fuzzy Search . Я не знаю о какой-либо реализации python (но я не смотрел глубоко в теме), но есть реализации C / C ++, которые вы можете использовать повторно, например TRE, которые поддерживают regexp с нечеткими параметрами.

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

(обращаясь только к строке, соответствующей части вопроса)

Если вы хотите попробовать что-то быстро, почему бы не создать несколько словарей, каждый из которых отображает исходные шаблоны в списки строк, где

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

Таким образом, когда пользователь набрал три символа, например, вы смотрите в словаре с ключами длиной 3. Если есть совпадение, это означает, что у вас есть от 1 до 10 возможностей, доступных сразу.