Zde je problém: řekněme, že konzumujete přibližně 4 miliony komentářů na Redditu denně a potřebujete detekovat přítomnost 10 000 konkrétních klíčových slov v téměř reálném čase. Naivní odpověď je zřejmá - projděte každým komentářem a klíčovým slovem. for comment in reddit_comments:
    for keyword in keywords:
        if keyword in comment:
            # alert user
 Je to jednoduché, viditelně i pomalé. Dokonce i když ignorujete matematiku, dělá (snadno) miliardy řetězových srovnání.Složitost je čtvercová a není žádný způsob, jak byste ji mohli spustit na malém VPS. To je problém, se kterým se Lewis Van Winkle setkal při vytváření F5Bot (bezplatná služba škrabání na Redditu). Algoritmus z roku 1975 nazvaný Umožňuje vyhledávat vzory v jediném průchodu. Aho-Corasicková Problém 600 dolarů bibliografů Problém se objevil v Bell Labs (1975) když Margaret Corasicková pracovala na nástroji pro vyhledávání klíčových slov na vládních páskách. bibliograf narazil na limit 600 dolarů při vyhledávání stovek klíčových slov najednou (a program nebyl dokončen). Corasick navštívil seminář o designu algoritmů od Alfreda Aho a přišli s tím, co známe jako Aho-Corasick algoritmus. Vyhledávání bibliografu se nyní uskutečnilo za 25 dolarů. Proč péče Aho-corasick je vlastně velmi populární algoritmus.   Aho-Corasick. Virusové skenery ho používají k skenování tisíců podpisů malwaru. F5Bot ho používá k monitorování komentářů z Redditu a Hacker News. fgrep Bylo Podívejte se na referenční hodnotu od 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)
 Je to flex, který bych rád měl kdykoliv. Jak to funguje Základní myšlenka je - pokud hledáte více klíčových slov, děláte nadbytečnou práci. Řekněme, že hledáte pro: , , , , Pomocí naivního přístupu byste prohledali svůj text třikrát - jednou pro každé klíčové slovo. "art" "cart" "ted" Pokud jste již hledali a víte, že je tam, můžete tam začít. Stačí vybudovat konečný stav stroj a využít sdílené následky. V podstatě, strom (z řetězců), kde každý uzel představuje předponu jednoho z vašich klíčových slov. Když prohledáte svůj textový znak podle znaků, pohybujete se tímto grafem. Zní hrozně podobně jako trie? To je proto, že je trie! "art" Co je chytré, je to, že algoritmus vytváří "zlyhavé odkazy" mezi uzly. V angličtině to znamená - "pokud se další znak neshoduje, nezačínejte od kořene. Dovolte mi, abych vám ukázal jednoduchý příklad. Pokud hledáte , algoritmus vytváří trie (předponový strom) a přidává další odkazy, které vidíte v modré/zelené: {a, ab, b, bc, bca, c, ca, caa} Pokud jste obeznámeni s Jednoduše přidává a Tímto způsobem můžete okamžitě skočit na nejdelší odpovídající příponu namísto skenování slova z kořene znovu. Text je skenován pouze jednou - takže skončíte s časovou složitostí O(n); kde n je délka textu. trie Neúspěšný link "abccab" Naivní přístup by vás mělo skenovat slovo znovu a znovu; O(n * m * k) kde m je počet klíčových slov a k je jejich průměrná délka. Aho-Corasick je O(n+m+z), kde z je počet shod. I když jste hledali miliony klíčových slov, Aho-Corasick to řeší lineárně. Implementace Můžete najít a v mém nedávném projektu, kde jsem ho přizpůsobil pro vyhledávání 9 mutací (vzorců) v souboru genomu (v podstatě 4M znaků), a vyhledal celou věc v 0.75s. Jednoduchá implementace Ukážu vám jednoduchý příklad, abyste zjistili, jak to funguje.  
# 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
 Myslím, že implementace je asi 60 řádků skutečného kódu. K dispozici je také knihovna - Je to super snadné používat. pyahocorasick Použijte to, když Nemusíte spamovat Když hledáte tři klíčová slova v odstavci, použijte ji, když: ahocorasick 
 
 
 hledáte tisíce klíčových slov, která se často nemění (F5Bot usecase) je třeba běžet často (přemýšlejte proudy) Zavírání myšlenek Aho-Corasick byl vynalezen Margaret s pero a papírem před 50 lety, bez jakéhokoli AI. Počítače jsou dnes milionykrát rychlejší a problém s vyhledáváním ve výši 600 dolarů by byl dnes triviální, ale pokud zpracováváte miliony komentářů na Redditu denně na malém VPS, nemůžete jen hodit hardware na problém. Jídlo pro myšlenku, je pravděpodobně 50 let starý algoritmus, který řeší váš problém lépe než cokoliv, co se chystáte implementovat. Footnotes: 
 
 
 
 
 
 Původní článek z roku 1975 Efficient string matching: An aid to bibliographic search je překvapivě čitelný. Margaret J. Corasicková doktorská práce (1974) byla „zajištění vlastních dat v otevřených systémech“ - raná bezpečnost informací. Škoda, že nemá svou vlastní stránku na Wikipedii, a to navzdory jejímu algoritmu a Alfred Aho (on je „A“ v AWK - Aho, Weinberger, Kernighan) oba mají své vlastní stránky na Wikipedii. Existuje knihovna Python s názvem pyahocorasick, která je implementována v C pro výrobní použití.Jsem si jistý, že je mnohem rychlejší než moje verze, ale principy jsou totožné. KMP (Knuth-Morris-Pratt) používá podobný přístup k kompilaci vzorů do konečného automatu. V podstatě ahocorasick pro jeden vzor. Oba předběžně vypočítávají strukturu a využívají předpony, které se objevují. Aho-Corasick automaton se může stát masivní - O(celkové znaky ve všech klíčových slovech). Pokud máte miliony vzorů, může potřebovat značnou paměť.

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

Tento zvuk je produkován v původním jazyce příběhu!

Algoritmus z roku 1975 stále porazil hrubou sílu v moderním vyhledávání klíčových slov

About Author

KOMENTÁŘE

ZAVĚŠIT ZNAČKY

TENTO ČLÁNEK BYL PŘEDSTAVEN V

Related Stories

Coinshift Launches csUSDL, Announces Strategic Partnerships

Coinshift Launches csUSDL, Announces Strategic Partnerships

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps