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

Question

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

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

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

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

Answer 1

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

  a--t
 / \ 
c   r
 \
  o--w

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

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

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

Answer 2

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

Answer 3

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

Answer 4

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

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

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

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

Answer 5

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

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