Najbardziej efektywny sposób wyszukiwania częściowych dopasowań ciągów w dużym pliku ciągów (python)

Question

Pobrałem plik tytułów artykułów z Wikipedii zawierający nazwę każdego artykułu w Wikipedii. Muszę wyszukać wszystkie tytuły artykułów, które mogą pasować do siebie. Na przykład, mogę mieć słowo "hokej", ale artykuł z Wikipedii na temat hokeja, którego bym chciał, to "Ice_hockey". To powinno być również wyszukiwanie niewrażliwe na wielkość liter.

Używam Pythona, i czy istnieje bardziej wydajny sposób niż po prostu przeszukiwanie linii po linii? Będę to robić najlepiej jak 500 lub 1000 razy na minutę. Jeśli linia po linii jest moją jedyną opcją, czy są jakieś optymalizacje, które mogę zrobić w tym zakresie?

Myślę, że w pliku znajduje się kilka milionów wierszy.

Wszelkie pomysły?

Dzięki.

Answer 1

Odpowiedź Grega jest dobra, jeśli chcesz dopasować pojedyncze słowa. Jeśli chcesz dopasować podciągi, potrzebujesz czegoś bardziej skomplikowanego, jak drzewo przyrostków (http://en.wikipedia.org/wiki/Suffix_tree). Po skonstruowaniu drzewo sufiksów może efektywnie odpowiadać na zapytania dotyczące dowolnych podłańcuchów, więc w twoim przykładzie może pasować do "Ice_Hockey", gdy ktoś szuka "hock".

Answer 2

Jeśli masz stały zestaw danych i zapytania o zmienne, to zwykłą techniką jest przeorganizowanie zestawu danych w coś, co można łatwiej przeszukiwać. Na poziomie abstrakcyjnym można podzielić każdy tytuł artykułu na pojedyncze małe litery i dodać każdy z nich do struktury danych słownika Python. Następnie, gdy pojawi się zapytanie, zamień słowo kluczowe na małe i wyszukaj je w słowniku. Jeśli każda pozycja słownikowa jest listą tytułów, wówczas możesz łatwo znaleźć wszystkie tytuły pasujące do danego słowa zapytania.

To działa dla prostych słów, ale musisz rozważyć, czy chcesz dopasować podobne słowa, takie jak znalezienie "palenia", gdy zapytanie jest "dymne".

Answer 3

Proponuję umieścić swoje dane w bazie danych SQLite i użyć wyszukiwanego przez użytkownika zapytania SQL do wyszukiwania.