Narito ang isang problema: ibig sabihin na inilagay mo ng halos 4 milyong mga komento sa Reddit araw-araw, at kailangan mong i-detect ang presence ng 10,000 anumang keywords sa halos real-time. Ang naive na solusyon ay malinaw - loop sa pamamagitan ng bawat komento at keyword. for comment in reddit_comments:
    for keyword in keywords:
        if keyword in comment:
            # alert user
 Ang mga ito ay simple, at ang mga ito ay slow. Gayunpaman kung i-ignorate ang matematika, ito ay (matagal na) paggawa ng bilyong mga paghahambing ng string. Ang kompleksidad ay square, at walang paraan na maaari mong i-execute ito sa isang maliit na VPS. Ito ay ang problema na natagpuan ni Lewis Van Winkle kapag bumuo ng F5Bot (ang isang libreng Reddit scraping service). At siya ay gumagana ito sa isang maliit na VPS na may isang anemic CPU, hindi isang ilang beefy cluster. Ang solusyon? Ang isang algorithm mula sa 1975 na tinatawag na Ito ay nagbibigay-daan sa iyo para sa paghahanap ng mga pattern sa isang single pass. Ipinanganak ko Ang problema ng $ 600 bibliographer Ang problema ay dumating sa Bell Labs (1975) kapag si Margaret Corasick ay nagtatrabaho sa isang tool upang makakuha ng mga keywords sa mga tape na ibinigay ng pamahalaan. Ang isang bibliographer ay nagtatampok ng limitasyon ng paggamit ng $ 600 habang naghahanap para sa mga hundred ng keywords sa isang pagkakataon (at ang programa ay hindi na dumating). Si Corasick ay nanirahan sa isang seminar sa algorithm design ni Alfred Aho, at sila ay dumating sa kung ano ang alam namin bilang ang Aho-Corasick algorithm. Ang paghahanap ng bibliographer ngayon ay naglalakbay para sa $ 25. 24x speedup. Bakit ang Care Ang Aho-corasick ay sa katunayan ay isang napaka-popular na algorithm. Ang orihinal na implementasyon ng   Aho-Corasick. Virus scanners gamitin ito upang i-scan para sa mga libu-libong malware signatures. F5Bot gumagamit ito upang i-monitor ang mga komento mula sa Reddit at Hacker News. fgrep ay Tingnan lamang ang benchmark mula sa 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)
 Ito ay isang flex na gusto kong magkaroon ng anumang araw. Paano ito gumagana Ang pangunahing ideya ay - kung ikaw ay naghahanap para sa ilang mga keywords, ikaw ay gumagawa ng redundant na trabaho. Sabihin mo na ikaw ay naghahanap para sa: na ang na ang Upang gamitin ang naive na paraan, i-scan ang iyong teksto sa pamamagitan ng tatlong beses - isang beses para sa bawat keyword. "art" "cart" "ted" Kung ikaw ay naghahanap para sa at alam mo na ito ay nasa itaas, maaari mong magsimula dito. I-build lamang ang isang finite state machine at i-exploit ang shared suffixes. Basically, isang tree (of strings) kung saan ang bawat node ay nagpapakita ng isang prefix ng isa sa iyong mga keywords. Kapag i-scan ang iyong teksto na character sa pamamagitan ng character, ikaw ay lumabas sa pamamagitan ng graph na ito. Naging nalalaman ng isang trie? Ito ay dahil ito ay isang trie! "art" Ano ang smart ay na ang algorithm ay lumikha ng "failure links" sa pagitan ng mga nodes. Sa Ingles, na ito ay - " kung ang susunod na character ay hindi matatagpuan, huwag magsimula mula sa root. Magbigay ng inspirasyon sa kontemporaryong designer ay maaaring gumawa ng kahit ano, kahit ano, at ang New Year - ay walang exception. , ang algorithm ay lumikha ng isang trie (prefix tree) at ilagay ang mga extra links na makita mo sa blue/green: {a, ab, b, bc, bca, c, ca, caa} Kung ikaw ay kilala sa isang Ito ay isang add-on a Sa halip na ito, maaari mong instantly pumunta sa pinakamalaking matching suffix sa halip ng pag-scan ang salitang mula sa root. , ikaw ay pumunta sa pamamagitan ng trie (automaton) ito isang beses, character sa character. Ang teksto ay i-scan lamang isang beses - kaya ikaw ay umuwi sa isang time complexity ng O(n); kung saan n ay ang length ng teksto. trie ang link "abccab" Ang isang naive na approach ay dapat mong i-scan ang salita nang higit pa at higit pa; O(n * m * k) kung saan m ay ang bilang ng mga keywords at k ay ang kanilang average na panahon. Aho-Corasick ay O(n+m+z), kung saan z ay ang bilang ng mga match. Halimbawa kung ikaw ay naghahanap para sa milyon-milyong mga keywords, Aho-Corasick nagtatrabaho ito linearly. Implementasyon Maaari mong makita ang isang sa aking nakaraang proyekto, kung saan ayusin ko ito para sa paghahanap ng 9 mutations (patterns) sa isang file ng genome (karaniwang 4M mga character), at ito ay paghahanap ang buong bagay sa 0.75s. Sigurado, ang mga pattern na ginagamit ko ay maliit, ngunit ito ay medyo mabilis! Simple ang implementasyon Ipinapakita ko ang isang simpleng halimbawa para makikita mo kung paano ito gumagana.  
# 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
 Ang implementation ay tungkol sa 60 linya ng actual code. Ito ay isang library - ; ito ay super madaling gamitin. pyahocorasick Gawin ito kapag Hindi mo na kailangan ng spam sa paghahanap para sa tatlong mga keywords sa isang paragraph. gamitin ito kapag: ahocorasick 
 
 
 ikaw ay naghahanap para sa mga libu-libong mga keywords na hindi mababago karaniwang (F5Bot usecase) Kailangan mo ng regular na pag-iisip (think streams) Pumunta sa mga pensyon Ang Aho-Corasick ay inihintulutan ng Margaret na may isang pen at papel 50 taon na ang nakalipas, walang anumang AI. Gayunpaman, ang mga pangunahing ideya ay hindi nagbabago ng maraming sa multi-pattern string matching. Ang mga computer ngayon ay milyon-milyong beses mas mabilis, at ang problema ng paghahanap ng $ 600 ay trivial ngayon. Ngunit kung nagproseso ka ng milyong mga komento sa Reddit araw-araw sa isang maliit na VPS, hindi ka maaaring lamang ilagay ang hardware sa problema. Matapos maihanda sa table lahat ng foods at drinks. si Joey pagtinatanong sa nararamdaman niya kay Dani ay lagi nitong sinasabi na he’s doing all his power to win back her heart. Footnotes: 
 
 
 
 
 
 Ang orihinal na 1975 paper Efficient string matching: An aid to bibliographic search ay mahirap na makikita. Si Margaret J. Corasick's PhD disertation (1974) ay "pag-aari ng mga proprietary data sa ilalim ng mga open systems" - early information security. Malaki na siya ay hindi magkaroon ng kanyang sarili Wikipedia pahina, kahit na ang kanyang algorithm at Alfred Aho (na siya ang 'A' sa AWK - Aho, Weinberger, Kernighan) ang parehong may kanilang sarili Wikipedia pahina. May isang library ng Python na tinatawag na pyahocorasick na inilapat sa C para sa produksyon ng paggamit. Ako ay sigurado na ito ay mas mabilis kaysa sa aking bersyon, ngunit ang mga prinsipyo ay parehong. Ang KMP (Knuth-Morris-Pratt) ay gumagamit ng isang katulad na pamamaraan para sa pag-compiling ng mga pattern sa isang finite automata. Basically ahocorasick para sa isang single pattern. Ang parehong precomput a structure at exploit prefixes na nagpapakita. Ang Aho-Corasick automaton ay maaaring maging massive - O(total na mga character sa lahat ng mga keywords). Kung mayroon kang milyong mga pattern, maaaring kailangan ito ng malaking memory.

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

Ang audio na ito ay ginawa sa orihinal na wika ng kuwento!

Ang isang 1975 algorithm ay patuloy sa brute force sa modernong paghahanap ng mga keyword

About Author

MGA KOMENTO

HANG TAGS

ANG ARTIKULONG ITO AY IPINAKITA SA

Related Stories

Getting intimate with Ethereum tokens

State of the Noonion: The Year of Profitability and Product Renaissance

How I deployed my spark document classification(Logistic Regression) model/s as a standalone app…

Hosting a DNS domain on the blockchain

Getting intimate with Ethereum tokens

State of the Noonion: The Year of Profitability and Product Renaissance

How I deployed my spark document classification(Logistic Regression) model/s as a standalone app…

Hosting a DNS domain on the blockchain

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps