Algorytm Fuzzy Matching wielu fraz Word w akapicie - baza danych, ciąg, algorytm, wyszukiwanie, fuzzy-search

Po pierwsze, nie szukam rzeczywistego algorytmu dopasowania rozmytego, używamy obu współczynników kości i odległości Levenshteina, szukam najmądrzejszego sposobu wykorzystania tych algorytmów.

Cel:

Próbuję wykryć nazwy miast wakapit tekstu, w kolejności, w jakiej występują. Mamy listę ~ 1 miliona nazw lokalizacji. Chcę przeszukać akapit tekstu i wykryć, kiedy jedna z tych lokalizacji jest obecna, a następnie zapisać to miasto. Nazwy lokalizacji mogą być pojedynczymi lub wieloma słowami.

Przykładowy akapit:

Cześć mamo! Sam i ja myślimy o drodze potykającej się Kanada w w następnym miesiącu. Wiemy, że możemy już zostać w domu Johna Quebec Miasto. Wiem, że dużo podróżowałeś Kanada, więc chciałem dostać Twoja rada.

Tak jak powiedziałem, zaczynaliśmy w Quebec City, a potem prawdopodobnie jedziemy Miramichi przed wyruszeniem do Halifax. Po 2 dniach chcemy iść Cape Breton. Na koniec chcemy sprawdzić Advocate Harbour zobaczyć rzeczy takie jak Bay of Fundy, Digbyi Molo św. Elżbiety

Porozmawiaj z Tobą wkrótce!

oczekiwane rezultaty

• Kanada
• Quebec City
• Kanada
• Miramichi
• Halifax
• Cape Breton
• Advocate Harbour
• Bay of Fundy
• Digby
• Molo św. Elżbiety

Problem

Moja aktualna blokada na wyłączność polega na wykrywaniu nazw lokalizacji wieloma słowami. Wiem, że mogę podzielić akapit na słowa, a następnie porównać je z moją listą, na przykład:

1. Fuzzy dopasowuje pierwsze słowo do mojej listy nazw lokalizacji
2. Jeśli nie pasuje, rozmyte dopasowanie (pierwsze słowo + drugie słowo) na mojej liście nazw lokalizacji
3. Jeśli nie pasuje, rozmyte dopasowanie (pierwsze + drugie + trzecie słowo) na mojej liście nazw lokalizacji
4. ...itp

Takie jest moje obecne podejście, ale jest ono niezwykle powolne i nieefektywne. Czy istnieje sprytny sposób, w jaki mogę osiągnąć to, czego szukam?

Odpowiedzi:

Myślę, że algorytm dopasowywania ciągów działa doskonale dla ciebie,

Oto lista dla nich: Algorytmy dopasowywania ciągów

W twoim przypadku myślę, że potrzebujesz wielu ciągów pasujących do jednego, takich jak Algorytm Aho-Corasicka