הנה בעיה: נניח שאתה לוקח בערך 4 מיליון תגובות Reddit ליום, ואתה צריך לזהות את הנוכחות של 10,000 מילות מפתח ספציפיות בזמן כמעט אמיתי. התשובה הנאצית היא ברורה - לגלוש דרך כל הערה ומילה מפתח. for comment in reddit_comments:
    for keyword in keywords:
        if keyword in comment:
            # alert user
 זה פשוט, אבל גם איטי מאוד. גם אם אתה מתעלם מתמטיקה, זה (בקלות) עושה מיליארדי השוואות string.The מורכבות היא מרובע, ואין דרך אתה יכול להפעיל את זה על VPS קטן. זוהי הבעיה של לואיס ואן וינקל התגלה בעת בניית F5Bot (שירות סריקה חינם של Reddit). אלגוריתם משנת 1975 שנקרא זה מאפשר לך לחפש דפוסים בפסקה אחת. קוריאנית הבעיה של ספריית 600 דולר הבעיה הופיעה ב-Bell Labs (1975) כאשר מרגרט קוראסיק עבד על כלי לחפש מילות מפתח בקלטות הממשלתיות. Corasick השתתף בסמינר על עיצוב אלגוריתמים על ידי אלפרד Aho, והם הגיעו עם מה שאנו מכירים כאלגוריתם Aho-Corasick. החיפוש של הספרייה עבר עכשיו עבור $ 25. 24x speedup. למה לטפל Aho-corasick הוא למעשה אלגוריתם פופולרי מאוד.   Aho-Corasick. סורקים וירוסים להשתמש בו כדי לסרוק אלפי חתימות תוכנות זדוניות. F5Bot משתמש בו כדי לפקח על תגובות מ Reddit ו Hacker News. 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" מה שימושי הוא שהאלגוריתם בונה "קישורים לכישלון" בין הצמיגים באנגלית, כלומר - "אם הדמות הבאה לא מתאימה, אל תתחיל מהשורש. תן לי להראות לך דוגמה פשוטה, אם אתה מחפש , האלגוריתם בונה trie (עץ הקדמה) ומוסיף את הקישורים הנוספים שאתה רואה כחול / ירוק: {a, ab, b, bc, bca, c, ca, caa} אם אתם מכירים את A זה רק מוסיף a בדרך זו, אתה יכול מיד לקפוץ למילוי התואם הארוך ביותר במקום לסרוק את המילה מהשורש שוב. הטקסט סורק רק פעם אחת - כך שאתה בסופו של דבר עם מורכבות זמן של O(n); שבו n הוא אורך הטקסט. trie כישלון קישור "abccab" גישה נאיבית תהיה לך לסרוק את המילה שוב ושוב; O(n * m * k) שבו m הוא מספר מילות המפתח ו k הוא האורך הממוצע שלהם. Aho-Corasick הוא O(n + m + z), שבו z הוא מספר התאמות. יישום אתה יכול למצוא A בפרויקט האחרון שלי, שבו התאמת אותו לחיפוש 9 מוטציות (תבניות) בקובץ גנום (בסיס 4M תווים), והוא חיפש את כל הדברים ב 0.75s. יישום פשוט אני מראה לך דוגמה פשוטה כדי שתוכל להבין איך זה עובד.  
# 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 השתמשו בזה כאשר אתה לא צריך לספאם כאשר מחפשים שלוש מילות מפתח בסעיף, השתמשו בו כאשר: ahocorasick 
 
 
 אתה מחפש אלפי מילות מפתח שאינן משתנות לעתים קרובות (F5Bot usecase) זה צריך לרוץ לעתים קרובות (חשוב זרמים) מחשבות סגור Aho-Corasick הומצא על ידי מרגרט עם עפר ו נייר לפני 50 שנה, ללא כל AI. מחשבים היום הם מיליוני פעמים מהירים יותר, ואת הבעיה של 600 $ חיפוש יהיה טריוויאלי היום, אבל אם אתה מעבד מיליוני הערות Reddit ליום על VPS קטן, אתה לא יכול פשוט לזרוק חומרה על הבעיה. מזון למחשבה, יש כנראה אלגוריתם בן 50 שנה אשר פותר את הבעיה שלך טוב יותר מכל דבר שאתה עומד ליישם. Footnotes: 
 
 
 
 
 
 המאמר המקורי משנת 1975 Efficient string matching: An aid to bibliographic search הוא קריא באופן מפתיע. דוקטורט של מרגרט ג'יי קוראסיק (1974) היה "בטיחות נתונים בעלים בתוך מערכות פתוחות" - אבטחת מידע מוקדמת. עצוב שהיא לא יש דף ויקיפדיה משלה, למרות האלגוריתם שלה ואלפרד אוהו (הוא 'א' ב AWK - 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 עדיין מכה בכוח ברוטו בחיפוש מילות מפתח מודרניות

About Author

הערות

תלו תגים

מאמר זה הוצג ב

Related Stories

100 Days of AI, Day 13: How Instruction Finetuning Improves a Pre-trained LLM

10 Reasons Why Publishing on HackerNoon Will Skyrocket Your Reach and Impact

The TechBeat: Python's Testing Playbook: Building Bulletproof Code (1/16/2024)

The TechBeat: To Focus or Not Focus: How to Find the Right Product-Market Fit (3/8/2024)

100 Days of AI, Day 13: How Instruction Finetuning Improves a Pre-trained LLM

10 Reasons Why Publishing on HackerNoon Will Skyrocket Your Reach and Impact

The TechBeat: Python's Testing Playbook: Building Bulletproof Code (1/16/2024)

The TechBeat: To Focus or Not Focus: How to Find the Right Product-Market Fit (3/8/2024)

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps