إبرة في كومة قش: برنامج تعليمي أنيق واسع النطاق للبحث عن نصوص خوارزمية

عند مصادفة مصطلح "بحث نصي" ، عادة ما يفكر المرء في نص كبير من النص تمت فهرسته بطريقة تجعل من الممكن البحث بسرعة عن واحد أو أكثر من مصطلحات البحث عند إدخالها بواسطة المستخدم. هذه مشكلة كلاسيكية لعلماء الكمبيوتر ، حيث توجد العديد من الحلول.

لكن ماذا عن السيناريو العكسي؟ ماذا لو كان المتاح للفهرسة مسبقًا عبارة عن مجموعة من عبارات البحث ، وفقط في وقت التشغيل يتم تقديم نص كبير للبحث؟ هذه الأسئلة هي ما يسعى هذا البرنامج التعليمي لهيكل البيانات الثلاثي إلى معالجته.

التطبيقات

هناك تطبيق حقيقي لهذا السيناريو يطابق عددًا من الأطروحات الطبية مع قائمة من الحالات الطبية ومعرفة الأطروحات التي تناقش أي الحالات. مثال آخر هو اجتياز مجموعة كبيرة من السوابق القضائية واستخراج القوانين التي تشير إليها.

أسلوب مباشر

تتمثل الطريقة الأساسية في تكرار عبارات البحث ، والبحث في النص عن كل عبارة ، واحدة تلو الأخرى. هذا النهج لا مقياس جيد. البحث عن سلسلة داخل أخرى له التعقيد O (n) . يؤدي تكرار ذلك مع عبارات البحث إلى الحرف الفظيع O ( m * n) .

الجانب الصعودي (المحتمل فقط) للنهج المباشر الذي يسهل تنفيذه ، كما هو واضح في مقتطف C # التالي:

 String[] search_phrases = File.ReadAllLines ("terms.txt"); String text_body = File.ReadAllText("body.txt"); int count = 0; foreach (String phrase in search_phrases) if (text_body.IndexOf (phrase) >= 0) ++count;

عند تشغيل هذا الرمز على جهاز التطوير الخاص بي [1] مقابل عينة اختبار [2] ، حصلت على وقت تشغيل مدته ساعة و 14 دقيقة - وهو ما يتجاوز بكثير الوقت الذي تحتاجه لتناول فنجان من القهوة ، أو النهوض والتمدد ، أو أي عذر آخر يستخدمه المطورون لتخطي العمل.

نهج أفضل - Trie

يمكن تحسين السيناريو السابق بطريقتين. على سبيل المثال ، يمكن تقسيم عملية البحث وجعلها متوازية على معالجات / مراكز متعددة. لكن تقليل وقت التشغيل الذي تحققه هذا النهج (إجمالي وقت التشغيل 20 دقيقة بافتراض التقسيم المثالي على 4 معالجات / مراكز) لا يبرر التعقيد الإضافي للترميز / تصحيح الأخطاء.

أفضل حل ممكن هو أن يجتاز نص النص مرة واحدة فقط. يتطلب ذلك فهرسة عبارات البحث في هيكل يمكن عرضه خطيًا ، بالتوازي مع نص النص ، في مسار واحد ، وتحقيق التعقيد النهائي لـ O (n) .

هيكل البيانات المناسب بشكل خاص لهذا السيناريو فقط هو ثلاثي . عادةً ما يتم التغاضي عن بنية البيانات متعددة الاستخدامات هذه وليست مشهورة مثل الهياكل الأخرى ذات الصلة بالأشجار عندما يتعلق الأمر بمشاكل البحث.

يوفر البرنامج التعليمي السابق لـ Toptal حول المحاولات مقدمة ممتازة لكيفية تنظيمها واستخدامها. باختصار ، المثلث عبارة عن شجرة خاصة ، قادرة على تخزين تسلسل من القيم بطريقة تجعل تتبع المسار من الجذر إلى أي عقدة ينتج عنه مجموعة فرعية صالحة من ذلك التسلسل.

لذلك ، إذا تمكنا من دمج جميع عبارات البحث في مثلث واحد ، حيث تحتوي كل عقدة على كلمة ، فسنحصل على العبارات الموضحة في هيكل حيث يؤدي التتبع ببساطة من الجذر إلى الأسفل ، عبر أي مسار ، إلى عبارة بحث صالحة.

تتمثل ميزة Trie في أنها تختصر وقت البحث بشكل كبير. لتسهيل فهم أغراض هذا البرنامج التعليمي الثلاثي ، دعنا نتخيل شجرة ثنائية. عبور شجرة ثنائية له تعقيد O (log 2 n) ، نظرًا لأن كل عقدة تتفرع إلى قسمين ، مما يؤدي إلى قطع الاجتياز المتبقي إلى النصف. على هذا النحو ، فإن الشجرة الثلاثية لها تعقيد اجتياز O (سجل 3 ن) . ومع ذلك ، في الثلاثي ، يتم تحديد عدد العقد الفرعية بالتسلسل الذي تمثله ، وفي حالة النص المقروء / ذي المعنى ، يكون عدد الأطفال مرتفعًا عادةً.

خوارزمية البحث عن النص

كمثال بسيط ، لنفترض عبارات البحث التالية:

• "عائلة واحدة"
• "عائلة مختلفة"
• "وجود منفصل"
• "أعضاء العصبة"

تذكر أننا نعرف عبارات البحث لدينا مسبقًا. لذلك ، نبدأ ببناء فهرس على شكل ثلاثي:

لاحقًا ، يقدمه مستخدم برنامجنا مع ملف يحتوي على النص التالي:

اللغات الأوروبية أعضاء في نفس العائلة. وجودهم المفصول هو اسطورة.

الباقي بسيط للغاية. ستحتوي الخوارزمية لدينا على مؤشرين (مؤشرات ، إذا كنت ترغب في ذلك) ، أحدهما يبدأ من الجذر ، أو عقدة "البداية" في بنية ثلاثية ، والآخر عند الكلمة الأولى في نص النص. يتحرك المؤشران معًا ، كلمةً بعد كلمة. يتحرك مؤشر النص ببساطة إلى الأمام ، بينما يتجاوز مؤشر trie ثلاثي العمق ، متتبعًا سلسلة من الكلمات المطابقة.

يعود مؤشر trie ليبدأ في حالتين: عندما يصل إلى نهاية الفرع ، مما يعني أنه تم العثور على عبارة بحث ، أو عندما يصادف كلمة غير متطابقة ، وفي هذه الحالة لم يتم العثور على تطابق.

أحد الاستثناءات لحركة مؤشر النص هو عندما يتم العثور على تطابق جزئي ، أي بعد سلسلة من التطابقات تتم مصادفة عدم تطابق قبل انتهاء الفرع. في هذه الحالة ، لا يتحرك مؤشر النص للأمام ، لأن الكلمة الأخيرة يمكن أن تكون بداية فرع جديد.

دعنا نطبق هذه الخوارزمية على مثال بنية بيانات Trie ونرى كيف تسير الأمور:

كما نرى ، نجح النظام في العثور على العبارتين المطابقتين ، "نفس العائلة" و "الوجود المنفصل" .

مثال من العالم الحقيقي

بالنسبة لمشروع حديث ، واجهت المشكلة التالية: لدى العميل عدد كبير من المقالات وأطروحات الدكتوراه المتعلقة بمجال عملها ، وقد أنشأت قائمة خاصة بها من العبارات التي تمثل عناوين وقواعد محددة تتعلق بنفس مجال الشغل.

كانت معضلتها كالتالي: بالنظر إلى قائمة العبارات لديها ، كيف تربط المقالات / الأطروحات بتلك العبارات؟ الهدف النهائي هو أن تكون قادرًا على اختيار مجموعة من العبارات بشكل عشوائي ولديك على الفور قائمة بالمقالات / الأطروحات التي تذكر تلك العبارات المحددة الجاهزة للاستيلاء عليها.

كما تمت مناقشته سابقًا ، هناك جزأين لحل هذه المشكلة: فهرسة العبارات في ثلاثي ، والبحث الفعلي. توفر الأقسام التالية تنفيذًا بسيطًا في C #. يرجى ملاحظة أنه لا يتم التعامل مع معالجة الملفات ومشكلات الترميز وتنظيف النص والمشكلات المماثلة في هذه المقتطفات ، نظرًا لأنها خارج نطاق هذه المقالة.

الفهرسة

تقوم عملية الفهرسة ببساطة باجتياز العبارات واحدة تلو الأخرى وإدراجها في المثلث ، كلمة واحدة لكل عقدة / مستوى. يتم تمثيل العقد بالفئة التالية:

 class Node { int PhraseId = -1; Dictionary<String, Node> Children = new Dictionary<String, Node>(); public Node() { } public Node(int id) { PhraseId = id; } }

يتم تمثيل كل عبارة بواسطة معرف ، والذي يمكن أن يكون بسيطًا مثل رقم تزايدي ، ويتم تمريره إلى وظيفة الفهرسة التالية (الجذر المتغير هو الجذر الفعلي للمثلث):

 void addPhrase(ref Node root, String phrase, int phraseId) { // a pointer to traverse the trie without damaging // the original reference Node node = root; // break phrase into words String[] words = phrase.Split (); // start traversal at root for (int i = 0; i < words.Length; ++i) { // if the current word does not exist as a child // to current node, add it if (node.Children.ContainsKey(words[i]) == false) node.Children.Add(words[i], new Node()); // move traversal pointer to current word node = node.Children[words[i]]; // if current word is the last one, mark it with // phrase Id if (i == words.Length - 1) node.PhraseId = phraseId; } }

يبحث

عملية البحث هي تنفيذ مباشر للخوارزمية الثلاثية التي تمت مناقشتها في البرنامج التعليمي أعلاه:

 void findPhrases(ref Node root, String textBody) { // a pointer to traverse the trie without damaging // the original reference Node node = root; // a list of found ids List<int> foundPhrases = new List<int>(); // break text body into words String[] words = textBody.Split (); // starting traversal at trie root and first // word in text body for (int i = 0; i < words.Length;) { // if current node has current word as a child // move both node and words pointer forward if (node.Children.ContainsKey(words[i])) { // move trie pointer forward node = node.Children[words[i]]; // move words pointer forward ++i; } else { // current node does not have current // word in its children // if there is a phrase Id, then the previous // sequence of words matched a phrase, add Id to // found list if (node.PhraseId != -1) foundPhrases.Add(node.PhraseId); if (node == root) { // if trie pointer is already at root, increment // words pointer ++i; } else { // if not, leave words pointer at current word // and return trie pointer to root node = root; } } } // one case remains, word pointer as reached the end // and the loop is over but the trie pointer is pointing to // a phrase Id if (node.PhraseId != -1) foundPhrases.Add(node.PhraseId); }

أداء

الكود المقدم هنا مستخرج من المشروع الفعلي وقد تم تبسيطه لغرض هذه الوثيقة. أدى تشغيل هذا الكود مرة أخرى على نفس الجهاز [1] وعلى نفس عينة الاختبار [2] إلى وقت تشغيل يبلغ 2.5 ثانية لبناء ثلاثي و 0.3 ثانية للبحث. الكثير لوقت الراحة ، إيه؟

الاختلافات

من المهم أن ندرك أن الخوارزمية كما هو موضح في هذا البرنامج التعليمي الثلاثي يمكن أن تفشل في حالات حافة معينة ، وبالتالي فهي مصممة مع مصطلحات بحث محددة مسبقًا في الاعتبار بالفعل.

على سبيل المثال ، إذا كانت بداية أحد مصطلحات البحث مطابقة لجزء ما من مصطلح بحث آخر ، كما في:

• " للمشاركة والاستمتاع مع الأصدقاء"
• "لدي تذكرتان لمشاركتهما مع شخص ما"

ويحتوي نص النص على عبارة تجعل مؤشر trie يبدأ في المسار الخطأ ، مثل:

لدي تذكرتان للمشاركة والاستمتاع مع الأصدقاء.

ثم ستفشل الخوارزمية في مطابقة أي مصطلح ، لأن مؤشر trie لن يعود إلى عقدة البداية حتى يمر مؤشر النص بالفعل ببداية مصطلح المطابقة في نص النص.

من المهم النظر فيما إذا كان هذا النوع من حالة الحافة هو احتمال لتطبيقك قبل تنفيذ الخوارزمية. إذا كان الأمر كذلك ، يمكن تعديل الخوارزمية بمؤشرات ثلاثية إضافية لتتبع جميع المباريات في أي وقت ، بدلاً من مطابقة واحدة فقط في كل مرة.

خاتمة

البحث عن النص هو مجال عميق في علوم الكمبيوتر ؛ حقل غني بالمشاكل والحلول على حد سواء. قد يبدو نوع البيانات التي اضطررت للتعامل معها (23 ميغابايت من النص هو عدد كبير من الكتب في الحياة الواقعية) حدث نادر أو مشكلة متخصصة ، لكن المطورين الذين يعملون في مجال البحث اللغوي أو الأرشفة أو أي نوع آخر من التلاعب بالبيانات ، تأتي عبر كميات أكبر من البيانات بشكل منتظم.

كما هو واضح في البرنامج التعليمي ثلاثي بنية البيانات أعلاه ، من الأهمية بمكان أن تختار بعناية الخوارزمية الصحيحة للمشكلة المطروحة. في هذه الحالة بالذات ، خفض نهج trie وقت التشغيل بنسبة مذهلة بلغت 99.93٪ ، من أكثر من ساعة إلى أقل من 3 ثوانٍ.

لا يعتبر هذا بأي حال هو النهج الفعال الوحيد المتاح ، ولكنه بسيط بما فيه الكفاية ، وهو ناجح. أتمنى أن تكون قد وجدت هذه الخوارزمية مثيرة للاهتمام ، وأتمنى لك حظًا سعيدًا في مساعيك في الترميز.

[1] الآلة المستخدمة في هذا الاختبار لها المواصفات التالية:

• انتل i7 4700HQ
• 16 جيجا رام

تم إجراء الاختبار على Windows 8.1 باستخدام .NET 4.5.1 وأيضًا Kubuntu 14.04 باستخدام أحدث إصدار من mono وكانت النتائج متشابهة جدًا.

[2] تتكون عينة الاختبار من 280 كيلو عبارة بحث بحجم إجمالي 23.5 ميجا بايت ، ونص نصي يبلغ 1.5 ميجا بايت.