هنا مشكلة: دعونا نقول إنك تتناول حوالي 4 ملايين تعليقات Reddit يوميا، وكنت بحاجة إلى اكتشاف وجود 10،000 كلمة مفتاح محددة في وقت قريب من الواقع. الإجابة غامضة هو واضح - القفز من خلال كل تعليق و كلمات مفتاحية. for comment in reddit_comments:
    for keyword in keywords:
        if keyword in comment:
            # alert user
 هذا هو بسيط جدا ، كما أنها تظهر ببطء. حتى لو انتبهت إلى الرياضيات ، فإنها (بسهولة) تجعل مليارات المقارنة. هذا هو المشكلة التي وقع فيها لويس ونكلي عند بناء F5Bot (خدمة إزالة Reddit المجانية). حل؟ ألغاز من 1975 تسمى يتيح لك البحث عن النماذج في طريق واحد. كوريا مشكلة المكتبة المكتوبة 600 دولار ووجدت المشكلة في Bell Labs (1975) عندما عملت مارجيت كاراسيك على أداة للبحث عن الكلمات الرئيسية على الأقراص التي توفرها الحكومة. شارك كاراسيك في دورة تدريبية حول تصميم الألغاز من قبل ألبيرت أوهو، ووجدوا ما نعرفه باسم ألغاز أوهو كاراسيك. لقد عملت البحث عن المكتبة الآن على 25 دولارًا. لماذا العناية 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" إذا كنت قد بحثت بالفعل عن وكنت تعرف أنه هناك، يمكنك أن تبدأ هناك. بسهولة بناء آلة الحالة المحددة واستغلال المكونات المشتركة. في الأساس، شجرة (من الشريط) حيث كل ناقل يمثل إسم واحد من الكلمات الرئيسية الخاصة بك. عندما تقوم بتحريك شخصية النص الخاص بك من خلال شخصية، أنت تتحرك من خلال هذه الكاميرا. يبدو شبيهًا بـ trie؟ هذا لأنه هو trie! "art" ما هو ذكي هو أن الكمبيوتر يخلق "اتصالات الفشل" بين الأقراص.في اللغة الإنجليزية، وهذا هو - "إذا لم يرتبط الشخص التالي، لا تبدأ من الجذور. أريد أن أشرح لك مثالًا بسيطًا، إذا كنت تبحث عن ، يُمكّن الكمبيوتر من إنشاء ثلاثي (جذور التكلفة) ويضيف الرابطات الإضافية التي ترى بها في الأزرق/ الخضراء: {a, ab, b, bc, bca, c, ca, caa} إذا كنت تعيش مع A وهذا يضيف فقط إلى وهكذا، يمكنك الفارق على الفور إلى أطول التوازن المباشر بدلاً من تسجيل الكلمة من الجذور مرة أخرى. يتم تشخيص النص مرة واحدة فقط - وبالتالي ينتهي بكثافة الوقت من O(n); حيث n هو طوله من النص. trie خطأ الصلة "abccab" من الممكن أن تتحكم في الكلمة مرة أخرى ومرة أخرى؛ O(n * m * k) حيث m هو عدد الكلمات الرئيسية و k هو طولها المتوسط. Aho-Corasick هو O(n + m + z)، حيث z هو عدد المواصفات. حتى لو كنت تبحث عن ملايين الكلمات الرئيسية، Aho-Corasick يتعامل معها بشكل خطير. تنفيذ يمكنك العثور على في مشاريعي الأخيرة، حيث أعدت ذلك لإجراء البحث عن 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 استخدم هذا عندما لا تحتاج إلى إرسال spam عند البحث عن ثلاثة كلمات مفتاحية في الفقرة، استخدمها عندما: ahocorasick 
 
 
 أنت تبحث عن آلاف الكلمات الرئيسية التي لا تتغير في كثير من الأحيان (F5Bot usecase) يجب أن تتحرك في كثير من الأحيان (تفكير النوافذ) التفكير السريع تم اختراع Aho-Corasick من قبل مارغريت مع قلم ورقة منذ 50 عامًا ، دون أي AI. الكمبيوتر اليوم هو أسرع مليار مرة ، وأن مشكلة البحث $ 600 سيكون ضئيلا اليوم. ولكن إذا كنت تتعامل مع ملايين تعليقات Reddit يوميا على VPS صغير ، لا يمكنك فقط هبوط المعدات على المشكلة. أدوية للقلق، هناك احتمالاً ألغاز عمرها 50 عامًا التي تحل مشكلةك أفضل من أي شيء تريد تنفيذها. Footnotes: 
 
 
 
 
 
 المقالة الأصلية في عام 1975 تكيف القصص الفعالة: المساعدة في البحث المكتوب هو قراءة مفاجئة. كان دورة دكتوراه مارغريت كوراسكي (1974) "أمن البيانات المملوكة داخل الأنظمة المفتوحة" - أمن المعلومات المبكرة. هناك مكتبة Python تسمى pyahocorasick التي يتم تنفيذها في C لاستخدام الإنتاج. أنا متأكد من أنها أسرع بكثير من إصداراتي، ولكن المبادئ هي نفسها. KMP (Knuth-Morris-Pratt) يستخدم نهجًا مماثلًا لتجميع النماذج إلى آلة محددة. في الأساس ahocorasick لمشروع واحد. يمكن أن يصبح أوتوماتيك أوتوماتيك - 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

Top Web Development Companies in 2018

Top Industries Which Can Benefit From Augmented Reality App Development

Top 10 Software Consulting Company based on Clutch & Goodfirms Reviews

Top 10 IoT Application Development Companies

Top Web Development Companies in 2018

Top Industries Which Can Benefit From Augmented Reality App Development

Top 10 Software Consulting Company based on Clutch & Goodfirms Reviews

Top 10 IoT Application Development Companies

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps