наиболее эффективный способ найти частичные совпадения строк в большом файле строк (python)

Question

Я скачал файл заголовков статей в Википедии, который содержит название каждой статьи в Википедии.Мне нужно найти все заголовки статей, которые могут быть возможными.Например, у меня могло бы быть слово "хоккей", но статья Wikipedia для хоккея, которую я хотел бы, - "Ice_hockey".Это также должен быть поиск без учета регистра.

Я использую Python, и есть ли более эффективный способ, чем просто построчный поиск?Я буду выполнять этот поиск как 500 или 1000 раз в минуту в идеале.Если строка за строкой - мой единственный вариант, могу ли я выполнить некоторые оптимизации в этом случае?

Я думаю, что в файле несколько миллионов строк.

Есть идеи?

Спасибо.

Answer 1

Грег ответит хорошо, если вы хотите сопоставить отдельные слова.Если вы хотите сопоставить подстроки, вам нужно что-то более сложное, например, дерево суффиксов (http://en.wikipedia.org/wiki/Suffix_tree). После создания дерево суффиксов может эффективно отвечать на запросы для произвольных подстрок, поэтому в вашем примере оно может соответствовать "Ice_Hockey", когдакто-то искал "скакательный сустав".

Answer 2

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

Это работает для простых слов, но вам придется подумать, хотите ли вы сопоставить похожие слова, например, найти "курение", когда запрос "курить".

Answer 3

Я бы посоветовал вам поместить ваши данные в базу данных sqlite и использовать для поиска оператор SQL like.