Ево проблема: рецимо да конзумирате око 4 милиона коментара на Реддит-у дневно, а потребно је да откријете присуство 10.000 специфичних кључних речи у скоро реалном времену. Naivni odgovor je očigledan – proučavajte svaki komentar i ključnu reč. for comment in reddit_comments:
    for keyword in keywords:
        if keyword in comment:
            # alert user
 То је једноставно. такође видљиво споро. Чак и ако игноришете математику, то (лако) ради милијарде поређења низова. сложеност је квадратна, и нема начина да бисте је могли покренути на малом ВПС-у. То је проблем са којим се Луис Ван Винкле сусрео приликом изградње Ф5Бот-а (бесплатне услуге гребања Реддит-а).И он га је покренуо на малом ВПС-у са анемичним ЦПУ-ом, а не неком говеђим кластером. Алгоритам из 1975. године назван Омогућава вам да претражујете обрасце у једном пролазу. Корасицк Библиографски проблем од 600 долара Проблем се појавио у Белл Лабс-у (1975) када је Маргарет Цорасицк радила на алату за претраживање кључних речи на државним тракама.Библиограф је погодио ограничења за употребу од 600 долара док је претраживала стотине кључних речи одједном (а програм није био завршен). Корасицк је присуствовао семинару о алгоритамском дизајну Алфреда Ахоа, и дошли су до онога што знамо као Ахо-Корасицк алгоритам. Претрага библиографа сада је радила за $ 25. 24к убрзање. Zašto brinuti Aho-corasick је заправо веома популаран алгоритам.   Aho-Corasick. Вирусни скенери га користе за скенирање хиљада потписа злонамерног софтвера. F5Bot га користи за праћење коментара из Реддит-а и Хакер Невс-а. fgrep Био Само погледајте бенчмарк од Ф5Бот. 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)
 То је флексибилност коју бих био срећан да имам било који дан. Kako funkcioniše Основна идеја је - ако тражите више кључних речи, радите вишак посла. Recimo da tražite: , , Користећи наиван приступ, скенирали бисте свој текст три пута - једном за сваку кључну реч. "art" "cart" "ted" Ако сте већ тражили и знате да је тамо, можете да почнете тамо. Само изградите машину коначног стања и искористите заједничке суфиксе. У основи, дрво (струча) у којем сваки чвор представља префикс једне од ваших кључних речи. Како скенирате свој текстуални карактер по карактеру, крећете се кроз овај графикон. Звучи ужасно слично трију? То је зато што је трију! "art" Оно што је паметно је да алгоритам гради "везе за неуспех" између чворова.На енглеском, то је - "ако се следећи лик не поклапа, не почните од корена. Дозволите ми да вам покажем једноставан пример.Ако тражите , алгоритам гради трие (префиксно дрво) и додаје додатне везе које видите у плавом / зеленом: {a, ab, b, bc, bca, c, ca, caa} Ако сте упознати са а To samo dodaje a На тај начин, можете одмах прескочити на најдужи одговарајући суфикс уместо да поново скенирате реч из корена. Текст се скенира само једном - тако да завршите са временском сложеношћу О(н); где је н дужина текста. trie Линк неуспех "abccab" Наиван приступ би вас скенирао реч изнова и изнова; О(н * м * к) где је м број кључних речи и к је њихова просечна дужина. Ахо-Цорасицк је О(н + м + з), где је з број подударања. Чак и ако сте претражили милионе кључних речи, Ахо-Цорасицк га линеарно обрађује. имплементација Možete naći a у мом недавном пројекту, где сам га прилагодио за претраживање 9 мутација (узорак) у геномској датотеци (у основи 4М карактера), и претражио је целу ствар у 0.75с. једноставна имплементација Pokazujem vam jedan jednostavan primer kako biste videli kako to funkcioniše.  
# 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
 Мислим да је имплементација око 60 редова стварног кода. Постоји и нова библиотека - ; То је супер лако користити. pyahocorasick Koristite ovo kada Ne moraš da spamiraš Када тражите три кључне речи у параграфу, користите га када: ahocorasick 
 
 
 Tražite hiljade ključnih reči koje se ne menjaju često (F5Bot usecase) Потребно је често радити (мислити на токове) Затварање мисли Aho-Corasick је измислила Маргарет са оловком и папиром пре 50 година, без икаквог АИ. Данас су рачунари милионе пута бржи, а проблем претраге од 600 долара би данас био тривијалан.Али ако обрађујете милионе Реддит коментара дневно на малом ВПС-у, не можете само бацити хардвер на проблем. Храна за размишљање, вероватно постоји 50-годишњи алгоритам који решава ваш проблем боље од свега што ћете имплементирати. Footnotes: 
 
 
 
 
 
 Оригинални документ из 1975. године Ефикасно усклађивање низова: Помоћ у библиографској претрази је изненађујуће читљив. Докторска дисертација Маргарет Ј. Цорасицк (1974) била је "обезбеђивање власничких података у отвореним системима" - рана информациона сигурност. жао ми је што она нема своју Википедију страницу, упркос свом алгоритму и Алфред Ахо (она је "А" у АВК - Ахо, Ваинбергер, Керниган) оба имају своје Википедију странице. Постоји Питон библиотека под називом пиахоцорасицк која се имплементира у Ц за производњу. Сигуран сам да је много бржи од моје верзије, али принципи су идентични. КМП (Кнутх-Морис-Пратт) користи сличан приступ за компилацију образаца у коначну аутомата. У основи ahocorasick за један образац. И прерачунају структуру и искористе префиксе који се појављују. Ахо-Цорасицк аутомат може постати масиван - О(укупни знаци у свим кључним речима). Ако имате милионе образаца, можда ће вам требати значајна меморија.

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

Овај аудио је произведен на оригиналном језику приче!

Алгоритам из 1975. године још увек превазилази бруталну силу у модерној претрази кључних речи

About Author

КОМЕНТАРИ

ХАНГ ТАГС

ОВАЈ ЧЛАНАК ЈЕ ПРЕДСТАВЉЕН У

Related Stories

Scaling Web Testing with Automation: Srikanth Srinivas’s Digital Strategy Breakthrough

Building the Cloud Future: Sreedevi Velagala's Trek in AWS Architecture

Leadership Success Story: Srinath Muralinathan's Transformative Projects at Amazon

Building a website with React and Bulma

Scaling Web Testing with Automation: Srikanth Srinivas’s Digital Strategy Breakthrough

Building the Cloud Future: Sreedevi Velagala's Trek in AWS Architecture

Leadership Success Story: Srinath Muralinathan's Transformative Projects at Amazon

Building a website with React and Bulma

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps