наиболее эффективный способ найти частичные совпадения строк в большом файле строк (python)
Я загрузил файл заголовков статей Википедии, который содержит название каждой статьи Википедии. Мне нужно найти все названия статей, которые могут совпадать. Например, у меня может быть слово "хоккей", но статья Википедии для хоккея, которую я бы хотел, - это "Ice_hockey". Это также должен быть поиск без учета регистра.
Я использую Python,и есть ли более эффективный способ, чем просто выполнить поиск по строке? Я буду выполнять этот поиск, как 500 или 1000 раз в минуту в идеале. Если строка за строкой - мой единственный вариант, есть ли какие-то оптимизации, которые я могу сделать в этом?
Я думаю, что в файле есть несколько миллионов строк.
Есть идеи?
Спасибо.
3 ответов:
Ответ Грега хорош, если вы хотите сопоставить отдельные слова. Если вы хотите сопоставить подстроки, вам понадобится что-то более сложное, например суффиксальное дерево (http://en.wikipedia.org/wiki/Suffix_tree однажды построенное суффиксное дерево может эффективно отвечать на запросы произвольных подстрок, поэтому в вашем примере оно может соответствовать "Ice_Hockey", когда кто-то искал "hock".
Если у вас есть фиксированный набор данных и переменные запросы, то обычный метод состоит в том, чтобы реорганизовать набор данных в нечто, что можно искать более легко. На абстрактном уровне можно разбить заголовок каждой статьи на отдельные строчные слова и добавить каждое из них в структуру данных словаря Python. Затем, всякий раз, когда вы получаете запрос, преобразуйте слово запроса в нижний регистр и посмотрите его в словаре. Если каждое значение словарной статьи представляет собой список названий, то вы можете легко найти все заголовки, соответствующие заданному слову запроса.
Это работает для простых слов, но вам нужно будет подумать, хотите ли вы сделать сопоставление на похожих словах, например найти "курение", когда запрос "дым".
Я бы предложил вам поместить свои данные в базу данных sqlite и использовать оператор SQL 'like' для поиска.
Comments