خصم غامض: الاقتراض الغامض

الاقتراض غير القانوني هو هيدرا متعددة الرؤوس ، عدو يقوم بتغيير وجهه باستمرار. أفضل محققينا الخاصين مستعدون للتشبث بأي جريمة يرتكبها هذا العدو. ومع ذلك ، فإن العدو لا ينام ، إنه ماكر وغادر: من الواضح أنه يستبدل بشيء واحد ، وهو يكتسح آثار الآخرين بشكل لا يصدق. في بعض الأحيان يتمكن من اللحاق بالركب بمساعدة موظفنا الأكثر ذكاءً - Suffix Massiv . في بعض الأحيان يتردد العدو ، ويدير البحث الدقيق وغير المجيد حساب موقعه. لكن الشر غدرا ، ونحن نحتاج باستمرار إلى قوى جديدة لمحاربته .

اليوم سوف نتحدث عن المخبر الخاص الجديد المسمى Fuzzy Search ، وكذلك عن أول لقاء له مع الاقتراض الغامض.

مع وكالة المباحث المناهضة للاكتئاب ، استعد لقضية الخصم الغامضة

المشهد

عند التحقق من المنطقة (المستند) ، تتحقق مكافحة الانتحال من وجود أي مكالمات حول جريمة محتملة في المنطقة. شهود العيان الذين سوف إشارة لنا حول الجريمة هي مؤشر القوباء المنطقية .

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

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

الفكرة الأولى

أنت الآن مخبر يا بني.
من الآن فصاعدًا ، يُحظر عليك الإيمان بالصدفة.

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

مذكرات المباحث عن طريقة العمل. المرحلة الاولى

سوف نستخدم ميزتين للمهمة:

1. نحن مهتمون بتكرارات واضحة ذات طول ثابت.
2. في مستند جيد ، لا يتم تكرار نفس القوباء المنطقية عدة مرات.

الشرط الثاني ضروري للحد من عدد التكرارات الواضحة الموجودة. في الواقع ، فإن المفردة التي تحدث 1000 مرة في المستند وفي المصدر ستمنح 1،000،000 زوج من التطابقات. لا يمكن رؤية مثل هذه القوباء المنطقية المتكررة بشكل متكرر إلا في مستندات غير نظيفة مع محاولات الزحف.

يتم تقديم مستند تم مسحه من عمليات الزحف كسلسلة من الكلمات. نأتي الكلمات إلى شكل الكلمة العادية ، ثم تجزئة لهم. نحصل على سلسلة من الأعداد الصحيحة (على gif - سلسلة من الحروف). يتم تجزئة جميع القوباء المنطقية لهذا التسلسل وإدخالها في جدول التجزئة مع قيمة موضع بداية السلسلة الفرعية. ثم ، لكل لوحة خشبية في وثيقة المرشح ، يتم العثور على التطابقات في جدول التجزئة. هذا يخلق التكرارات واضحة من طول ثابت. تُظهر الاختبارات تسارعًا ثلاثيًا عند استخدام الطريقة الجديدة مقارنةً بالصفيف اللاحق.

نحسب الجنائية

- هل هناك أي نقاط أخرى تنصحني أن أنتبه إليها؟
"سلوك الكلب الغريب في ليلة الجريمة".
- الكلاب؟ لكنها لم تتصرف بأي شكل من الأشكال!
"هذا غريب" ، قال هولمز.

_{© آرثر كونان دويل ، "فضي" (من سلسلة "ملاحظات على شرلوك هولمز")}

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

مذكرات المباحث عن طريقة العمل. المرحلة الثانية

_{مصدر الصورة: pixabay.com}

توزع المرحلة الثانية التكرارات إلى اليسار واليمين عبر المستند. التوزيع يأتي من "المراكز" - وجدت التكرارات واضحة. لمقارنة اللواحق ، نستخدم مسافة Levenshtein - الحد الأدنى لعدد عمليات الحذف / الاستبدال / الإدخالات للكلمات اللازمة لجلب سطر إلى آخر. يمكن حساب المسافة ديناميكيًا للواحق المكررة باستخدام خوارزمية فاغنر فيشر ، استنادًا إلى التحديد التكراري لمسافة ليفنشتاين. ومع ذلك ، فإن هذه الخوارزمية تربيعية في التعقيد ولا تسمح بالتحكم في نسبة الأخطاء. مشكلة أخرى هي التعريف الدقيق لحدود التكرارات. لمعالجة هذه المشكلات ، نستخدم العديد من الإجراءات الواضحة ، ولكن مع ذلك.

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

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

عصابة من المجرمين

- غدا نخطط للالتقاء مع زملاء الدراسة!
- في زميل واحد كبير؟
- ماذا؟

_{© بشورج}

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

_{مصدر الصورة: pixabay.com}

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

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

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

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

تدريب المبتدئين

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

نموذج حدودي اللازمة لتحسين. لتحديد المعلمات النموذج الأمثل ، تم استخدام عينة PlagEvalRus .

تنقسم العينة إلى 4 مجموعات:

• Generated_Copypast (4250 زوجًا) - القروض الحرفية الناتجة
• Generated_Paraphrased (4250 زوجًا) - قروض ضعيفة ومتوسطة الدخل تم إنشاؤها بواسطة الجهاز باستخدام ضوضاء الممرات الأصلية (بدائل تعسفية / عمليات حذف / إدراج)
• يدويا (713 أزواج) نصوص مكتوبة بخط اليد مع أنواع مختلفة من القروض ، معظمها قروض ضعيفة ومتوسطة التعديل (يستعاض عنها بما لا يزيد عن 30 ٪ من الكلمات في نسختين)
• يدويا - صياغة 2 (198 أزواج) نصوص مكتوبة بخط اليد مع قروض متوسطة وتعديل عالي (أكثر من 30 ٪ كلمات)

تم البحث عن معلمات النموذج الأمثل باستخدام طريقة النسب متعدد البدء. تعظيم $$$F_ \ beta$قياس مع $$$\ beta ^ 2 = \ frac {1} {4}$(التركيز على الدقة). فيما يلي أهم المعلمات المثلى.

تاريخ القضية

انتهت الفترة التجريبية للبحث Fuzzy الخاصة بنا. دعنا نقارن إنتاجيته بإنتاج المباحث الأخرى ، مجموعة لاحقة. الدورة التدريبية Fuzzy Search تمت في البرنامج Manually_Paraphrased.

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

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

عند اختبار المستندات التي يصل حجمها إلى 10 ⁷ كلمات ، فإننا نتحقق من الخطية لكلتا الخوارزميات. على المعالج i5-4460 ، يعالج البرنامج زوجًا من "مصدر المستند" يبلغ طوله مليون كلمة في أقل من ثانية.

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

الأمثلة على ذلك:

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

خاتمة

يعمل Fuzzy Search في فريق مع أدواتنا الأخرى: البحث السريع عن مستندات المرشح ، واستخراج تنسيق المستندات ، ومحاولات الالتفافية على نطاق واسع. يتيح لك هذا الأمر العثور بسرعة على الانتحال المحتمل. بحث Fuzzy Search في هذا الفريق ويقوم بأداء وظائفه البحثية بشكل أكثر جودة ، والأهم من ذلك ، أن يكون أسرع من Suffix Array. سوف تتعامل وكالتنا بشكل أفضل مع مهامها ، وسيواجه المؤلفون عديمي الضمير مشاكل جديدة عند استخدام نص غير أصلي .

خلق مع عقلك الخاص!