Oto problem: powiedzmy, że spożywasz około 4 milionów komentarzy na Reddit dziennie i musisz wykryć obecność 10 000 określonych słów kluczowych w czasie niemal rzeczywistym. Odpowiedź jest oczywista - przewijanie przez każdy komentarz i słowo kluczowe. for comment in reddit_comments:
    for keyword in keywords:
        if keyword in comment:
            # alert user
 Jest to proste, a także widoczne powolne. Nawet jeśli zignorujesz matematykę, to (łatwo) robi miliardy porównań strun. złożoność jest kwadratowa i nie ma sposobu, abyś mógł ją uruchomić na małym VPS. To jest problem, z którym spotkał się Lewis Van Winkle podczas budowy F5Bot (bezpłatna usługa skrapienia Reddit). Rozwiązanie: algorytm z 1975 roku Umożliwia wyszukiwanie wzorów w jednym przejściu. Śląsk-Corasick Problemy 600-dolarowego bibliografa Problem pojawił się w Bell Labs (1975) kiedy Margaret Corasick pracowała nad narzędziem do wyszukiwania słów kluczowych na taśmach dostarczanych przez rząd. bibliograf uderzył w limity użytkowania 600 $ podczas wyszukiwania setek słów kluczowych na raz (a program nie został zakończony). Corasick uczestniczył w seminarium na temat projektowania algorytmów Alfred Aho, a oni wymyślili to, co znamy jako algorytm Aho-Corasick. Wyszukiwanie bibliografa odbyło się teraz za 25 $ 24x speedup. Dlaczego opieka Aho-corasick jest w rzeczywistości bardzo popularnym algorytmem.   Aho-Corasick. skanery wirusów używają go do skanowania tysięcy podpisów złośliwego oprogramowania. F5Bot używa go do monitorowania komentarzy z Reddit i Hacker News. fgrep był Wystarczy spojrzeć na wyniki F5Bot. Loaded 3000 keywords to search on a text of 19377 chars

searching with strpos (naive):  0.384 seconds
searching with aho-corasick:    0.055 seconds (7x faster)
 Jest to elastyczność, którą chciałbym mieć każdego dnia. Jak to działa Podstawowym pomysłem jest - jeśli szukasz wielu słów kluczowych, robisz nadmierną pracę. Załóżmy, że szukasz na: , , Korzystając z naiwnego podejścia, skanujesz swój tekst trzy razy - raz dla każdego słowa kluczowego. "art" "cart" "ted" Jeśli szukasz już i wiesz, że jest tam, możesz tam zacząć. Po prostu zbuduj maszynę stanu skończonego i wykorzystaj udostępnione sufiksy. W zasadzie drzewo (z strun), w którym każdy węzeł reprezentuje prefiks jednego z twoich słów kluczowych. Gdy skanujesz przez swój znak tekstowy według postaci, przechodzisz przez ten wykres. Brzmi strasznie podobnie do trie? "art" Co mądre jest to, że algorytm buduje „łącza niepowodzenia” między węzłami. W języku angielskim, to jest - „jeśli następny znak nie pasuje, nie zaczynaj od korzenia. Pozwól, że pokażę ci prosty przykład. Jeśli szukasz , algorytm tworzy trie (drzewo prefiksowe) i dodaje dodatkowe linki, które widzisz w kolorze niebieskim/zielonym: {a, ab, b, bc, bca, c, ca, caa} Jeśli jesteś zaznajomiony z To tylko dodaje a W ten sposób możesz natychmiast przejść do najdłuższego dopasowanego dopasowania zamiast ponownie skanować słowo od korzenia. Tekst jest skanowany tylko raz - więc kończy się to złożonością czasu O(n); gdzie n jest długością tekstu. trie niepowodzenie link "abccab" Naivne podejście spowodowałoby skanowanie słowa raz po raz; O(n * m * k) gdzie m jest liczbą słów kluczowych, a k jest ich średnią długością. Aho-Corasick jest O(n+m+z), gdzie z jest liczbą meczów. Wdrożenie Możesz znaleźć a w moim niedawnym projekcie, gdzie dostosowałem go do wyszukiwania 9 mutacji (wzorców) w pliku genomowym (głównie 4M znaków), i przeszukał całą rzecz w 0.75s. Proste wdrożenie Pokażę Ci prosty przykład, abyś dowiedział się, jak to działa.  
# naive approach
for comment in reddit_comments:
    for keyword in keywords:
        if keyword in comment:
            # alert user
 
# with aho-corasick
step 1: build an automaton (trie) using patterns
step 2: add failure links (with bfs)
step 3: search automaton by following failure links, and return patterns that matched
 Myślę, że wdrożenie to około 60 linii rzeczywistego kodu. Znajduje się tu również biblioteka - Jest super łatwy w użyciu. pyahocorasick Użyj tego, gdy Nie musisz spamać W poszukiwaniu trzech słów kluczowych w akapicie użyj go, gdy: ahocorasick 
 
 
 szukasz tysięcy słów kluczowych, które nie zmieniają się często (F5Bot usecase) Potrzebuje często biegać (myśl o strumieniach) Zamknięcie myśli Aho-Corasick został wynaleziony przez Margaret z długopisem i papierem 50 lat temu, bez żadnej sztucznej inteligencji. Komputery są dziś miliony razy szybsze, a problem wyszukiwania w wysokości 600 dolarów byłby dziś trivialny. ale jeśli przetwarzasz miliony komentarzy Reddit dziennie na małym VPS, nie możesz po prostu rzucić sprzętu na problem. Jedzenie do myślenia, istnieje prawdopodobnie 50-letni algorytm, który rozwiązuje twój problem lepiej niż cokolwiek, co masz zamiar wdrożyć. Footnotes: 
 
 
 
 
 
 Oryginalny artykuł z 1975 roku Efficient string matching: An aid to bibliographic search jest zaskakująco czytelny. Doktorat Margaret J. Corasick (1974) był „zapewnienie własnych danych w otwartych systemach” - wczesne bezpieczeństwo informacji. szkoda, że nie ma własnej strony Wikipedii, pomimo algorytmu i Alfred Aho (jest „A” w AWK - Aho, Weinberger, Kernighan) oba mają własne strony Wikipedii. Istnieje biblioteka Python o nazwie pyahocorasick, która jest wdrażana w C do użytku produkcyjnego. Jestem pewien, że jest o wiele szybsza niż moja wersja, ale zasady są identyczne. KMP (Knuth-Morris-Pratt) używa podobnego podejścia do kompilowania wzorców w skończony automat. Zasadniczo ahocorasick dla pojedynczego wzorca. Oba prekomputują strukturę i wykorzystują pojawiające się prefiksy. Automat Aho-Corasick może stać się masywny - O(w sumie znaków we wszystkich słowach kluczowych).

This story contains new, firsthand information uncovered by the writer.

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

Read My Stories

Ten dźwięk jest produkowany w oryginalnym języku historii!

1975 algorytm nadal bije brutalną siłę w nowoczesnym wyszukiwaniu słów kluczowych

About Author

UWAGI

ZAWIEŚĆ TAGI

ARTYKUŁ TEN ZOSTAŁ PREZENTOWANY W

Related Stories

Pleasures of the telescope by Garrett Putman Serviss - Table of Links

Verified Writers

Meet Sora: HackerNoon Company of the Week

Meet Beldex: HackerNoon Company of the Week

Pleasures of the telescope by Garrett Putman Serviss - Table of Links

Verified Writers

Meet Sora: HackerNoon Company of the Week

Meet Beldex: HackerNoon Company of the Week

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps