دلته یو ستونزه ده: د مثال په توګه چې تاسو په ورځ کې په اړه د 4 میلیون Reddit تبصرې ونیسئ، او تاسو باید په واقعي وخت کې د 10،000 ځانګړي کلمه شتون کشف کړئ. د ناڅاپي ځواب واضح دی - د هر تبصرې او کلیدي کلمه په لټه کې. بشپړ. for comment in reddit_comments:
    for keyword in keywords:
        if keyword in comment:
            # alert user
 دا ساده دی. هم په ښایسته توګه چټک. حتی که تاسو د ریاضی په لټه کې ونیسئ، دا (د آسانه) د بیلابیلو لګښتونو پرتله کوي. د پیچیدو کچه مربع دی، او تاسو کولی شئ دا په یو کوچني VPS کې چلول کړئ. دا ستونزه دی چې لوئیس وینکل د F5Bot (د وړیا Reddit scraping خدمت) جوړولو په وخت کې راځي. او هغه د یو کوچني VPS سره د انیمیک CPU، نه ځینې beefy کلستر په کارولو سره. د حل؟ د 1975 algorithm په نامه دا تاسو ته اجازه ورکوي چې په یو واحد پاس کې د نمونې لپاره چمتو کړئ. د کورس د 600 ډالرو Bibliographer ستونزه د ستونزو په Bell Labs (1975) کې ښکاره شو، کله چې مارګریټ Corasick د دولت د سپارلو په ټیپونو کې د کلیدي کلماتو په لټه کې کار کوي. یو لیبلګراف د 600 ډالرو کارولو محدودیتونو ته ځي کله چې په یوه وخت کې د ډیری کلیدي کلماتو په لټه کې چمتو کیږي (او د پروګرام نه بشپړ شوی). هغه ډول ستونزه چې تاسو ته ځي کله چې ستاسو اګوریتم کثافیت نه کوي. Corasick د الګوریتم ډیزاین په اړه د انیمیشن کې ګډون وکړ، او دوی د Aho-Corasick الګوریتم په توګه پوه شي. د Bibliographer د څیړنې اوس د 25 ډالرو لپاره کارول. 24x speedup. چرا د مراقبت Aho-corasick په حقیقت کې یو خورا مشهور algorithm دی. د اصلي اجرا   Aho-Corasick. ویروس اسکنرونه دا کاروي ترڅو د ډیجیټل ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ ډالۍ fgrep د یوازې د 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)
 دا یو انعطاف دی چې زه به په هر وخت کې خوشحاله وي. څنګه کار کوي د بنسټیز مفکوره ده - که تاسو د ډیری کلیدي کلمهونو په لټه کې یاست، نو تاسو د لګښت کار کوي. اجازه ورکړئ چې تاسو په لټه کې یاست: د د د ناڅاپي لارښوونې په کارولو سره، تاسو به خپل متن درې ځله سکن کړئ - د هر کلمه لپاره یو ځل. "art" "cart" "ted" که تاسو په دې وخت کې د او تاسو پوهیږئ چې دا دلته دی، تاسو کولی شئ دلته پیل کړئ. یوازې یو پایلې حالت ماشین جوړ کړئ او د مشترکه لګښتونو څخه ګټه واخلئ. په اصل کې، یو ټری (د لګښتونو) چې هر نوټ ستاسو د کلیدي کلمه یو لګښت وړاندې کوي. لکه څنګه چې تاسو ستاسو د متن ځانګړنو له ځانګړنو له لارې سکاټ کړئ، تاسو په دې ګراف کې حرکت وکړئ. دا د ټری په څیر ښودل کیږي؟ دا ځکه چې دا یو ټری دی! "art" هغه څه چې هوښيار دی دا algorithm د نښانونو تر منځ "د ناکام لنډونه" جوړوي. په انګلیسي کې، دا دی - "که بل د ځانګړتیاوو په پرتله نږدې نه وي، له رنګ څخه پیل نه کوي. په ټرین کې د دې بل نښان ته ورسئ چې د اوږد تر ټولو اوږد شاوخوا شریک کوي." اجازه ورکړم تاسو ته یو ساده مثال. که تاسو په لټه کې ، د algorithm يو trie جوړوي (د مخکښ ټری) او د اضافي لنډونه اضافه کوي چې تاسو په بلیو / سبز کې وګورئ: {a, ab, b, bc, bca, c, ca, caa} که تاسو د A دا یوازې د A اضافه په دې توګه، تاسو کولی شئ په چټکۍ سره د اوږد تر ټولو اوږد مطابقت پړاو ته ورسئ په ځای کې د کلمه څخه د ریټ څخه بیا سکنئ. اجازه ورکړئ چې تاسو د څیړنې لپاره چمتو کړئ ، تاسو د دې trie (automaton) له لارې ځي، د karakter له character. The text is only scanned once - so you end up with a time complexity of O(n); where n is the length of the text. trie د نښلیدو "abccab" یو ناخودانه لارښود به تاسو ته د کلمې په لټه کې ونیسئ؛ O(n * m * k) کله چې m د کلمې شمیره ده او k د دوی د متوسط اوږدوالي ده. Aho-Corasick ده O(n + m + z)، کله چې z د لګښتونو شمیره ده. حتی که تاسو د میلیونونو کلمې ته چمتو کړئ، Aho-Corasick دا په لنډ ډول کار کوي. تطبیق تاسو کولی شئ د په زما وروستۍ پروژې کې، چې زه دا لپاره د جنم فایبر کې د 9 بدلونونو (د نمونې) (د اصل کې 4M ځانګړتیاوې) د څیړنې لپاره تنظیم کړم، او دا په 0.75s کې ټولې څه چمتو کړ. البته، د نمونې چې زه کاروي کوچنی دي، مګر دا ډیره سرعت دی! ساده implementation زه یو ساده مثال ښيي نو تاسو پوه شئ چې دا څنګه کار کوي.  
# 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 دا کارول کله چې تاسو اړتیا نلري SPAM کله چې په یوه پارامتر کې د درې کلیدي کلمه وګورئ. دا کارول کله چې: ahocorasick 
 
 
 تاسو کولی شئ د ډیرو کلمهونو لپاره چمتو کړئ چې معمولا بدلون نلري (F5Bot usecase) دا باید په اغیزمنه توګه چلول شي (think streams) د فکر بندولو Aho-Corasick د مرګریټ له خوا د 50 کاله مخکې د قلم او کاغذ له خوا اختراع شوی، د هر AI پرته. که څه هم، د عمده خیالات د ډیرو نمونې string matching په اړه ډیر بدلون نلري. امروزه کمپیوټرونه میلیونونو ځله چټک دي، او د 600 ډالرو څیړنې ستونزه به امروزه بیلابیلو وي. مګر که تاسو په یو کوچني VPS کې په ورځ کې میلیونونو Reddit تبصرې پروسس کړئ، تاسو کولی شئ یوازې د ستونزو ته هارډویر ته ورسیږي. د فکر لپاره خوراکي، احتمالا یو 50 کاله الګوریتم شتون لري چې ستاسو د ستونزو د هر څه څخه ښه حل کوي. که تاسو په دې وخت کې وګورئ، نو اجازه ورکړئ که تاسو پوه شئ چې هغه الګوریتم چې تاسو یې حیرانتیا لرئ! Footnotes: 
 
 
 
 
 
 د اصل 1975 کاغذ د اغیزمن string matching: A aid to bibliographic search په حیرانتیا سره ښکاره ده. د مارګټ J. Corasick د PhD ډیزاین (1974) "د پرانیستې سیسټمونو کې د مالکیت ډاټا ډاټا ډاټا ډاټا ډاټا ډاټا" - د لومړي معلوماتو خوندیتوب. ډاډ چې هغه خپل ویکیپیڈیا پاڼه نه لري، د هغې algorithm او Alfred Aho (او د AWK کې د "A" دی - Aho، Weinberger، Kernighan) هر دوی د خپل ویکیپیڈیا صفحات لري. د Python کتابتون په نوم pyahocorasick دی چې په C کې د تولید لپاره کارول کیږي. زه ډاډم چې دا د زما نسخه څخه ډیر سرعت دی، مګر د اصولو ورته دي. زه به په لوړه وخت کې د نمونې کار وکړي. KMP (Knuth-Morris-Pratt) د موډلونو په بشپړ اتومات کې رامینځته کولو لپاره ورته روښانه لاره کاروي. په اصل کې د واحد موډل لپاره ahocorasick. هر دوی د جوړښت لپاره مخکښ وکاروي او د مخکښونو څخه کار واخلئ چې ښودل کیږي. د Aho-Corasick انټرنیټون کولی شي لوی وي - O(د ټولو کلیدي کلمه کې کلک کارپوه). که تاسو میلیونونو نمونې لرئ، دا ممکن مهم یادښت ته اړتيا لري.

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 algorithm اوس هم په عصري کلمه د څیړنې کې د بریښنا ځواک غړي

About Author

تبصرې

hang tags

دا مقاله په کې وړاندې شوې وه

Related Stories

Tran Hung is HackerNoon's Altcoin Champion of 2021

Psychopathology of Everyday Life by Sigmund Freud - Table of Links

Kindness is a Gift that Should Always be Paid Forward - Interview With Samiran Mondal

Building Inclusive Tech: Interview with HackerNoon Contributor of the Year IOT 2021

Tran Hung is HackerNoon's Altcoin Champion of 2021

Psychopathology of Everyday Life by Sigmund Freud - Table of Links

Kindness is a Gift that Should Always be Paid Forward - Interview With Samiran Mondal

Building Inclusive Tech: Interview with HackerNoon Contributor of the Year IOT 2021

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps