python: быстрый поиск слов в словаре с подстановочными знаками*

Учитывая текст, который разбит на список слов, я хочу найти каждое слово в словаре слов, который также читается из текстового файла и split('\n').

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

Производительность в данном случае имеет решающее значение. Я хотя и Btree ... но

  1. Какой пакет и тип данных лучше всего подходит для быстрой реализации на Python.
  2. Пожалуйста, предоставьте примеры кода

person Lorenz Lo Sauer    schedule 03.10.2011    source источник
comment
Похоже, вам нужен пакет trie   -  person Voo    schedule 03.10.2011
comment
Подстановочный знак всегда будет медленнее наверняка. Дикты работают с хешами (постоянное время доступа).   -  person JBernardo    schedule 03.10.2011
comment
@JBernardo: нет, это просто означает, что элементы должны начинаться с того, что стоит перед «звездой».   -  person Lorenz Lo Sauer    schedule 03.10.2011
comment
Вот почему вы потеряете постоянный поиск по времени. то есть это будет медленнее.   -  person JBernardo    schedule 03.10.2011


Ответы (2)


Используйте dawg, который более эффективен, чем Trie, с точки зрения пустой траты места. Существует несколько реализаций Python, но для начала посмотрите здесь.

person hymloth    schedule 03.10.2011
comment
С веб-сайта: ...Если вас не волнует память или скорость[sic!], просто сохраните свои слова... Это быстрее? - person Lorenz Lo Sauer; 03.10.2011
comment
Дог однозначно быстрее. Цитата с сайта иронична. просто сохраните свои слова в базе данных SQL или разверните 100 машин в облаке. Я не против. Больше сил вам! - person hymloth; 03.10.2011

Вы хотите попробовать. Используйте пакет PyTrie.

person Petr Viktorin    schedule 03.10.2011