خوارزمية جيدة للعثور على جميع أزواج السلاسل بين مجموعتين بحيث يتم تضمين جميع الكلمات من السلسلة الأولى في السلسلة الثانية؟

Question

لدي مجموعتان كبيرتان من السلاسل (في الواقع هما أسماء منتجات)."كبير" يعني بضعة ملايين من السلاسل.

مثال:

مجموعة 1:

Some good product
Another product
Some name
Blah

المجموعة 2:

Very long some product name with words blah
Another very long product name
asd asd sad sad asdsa
Blah blah blah

تحتوي المجموعة 1 على أسماء "جيدة".تحتوي المجموعة 2 على أسماء "قذرة".

أريد: لكل عنصر من المجموعة 2 (بالإضافة إلى ذلك:item2) ابحث عن العنصر الأطول من المجموعة 1 (بالإضافة إلى ذلك:item1) بحيث يتم تضمين كافة الكلمات من item1 في item2.

في المثال الموضح، ستكون الأزواج كما يلي:

Very long SOME product NAME with words blah => Some name
ANOTHER very long PRODUCT name              => Another product
asd asd sad sad asdsa                       => none
BLAH blah blah                              => blah

حتى الآن لم أستطع التفكير في أي شيء أفضل من خوارزمية القوة الغاشمة:

1. قسّم كل سلسلة من المجموعة 1 إلى كلمات = نحصل على مجموعة من قوائم الكلمات، فليكن المجموعة 3
2. قسّم كل سلسلة من المجموعة 2 إلى كلمات = نحصل على مجموعة من قوائم الكلمات، فليكن المجموعة 4
3. التقط قائمة بالكلمات من المجموعة 3 (المزيد:list3)، قارنها بجميع قوائم الكلمات من المجموعة 4 حتى تجد بعض القائمة المضمنة بالكامل في القائمة3.

ومع ذلك، فهو يتمتع بدرجة عالية من التعقيد ويعمل ببطء شديد.يستغرق تنفيذي البسيط حوالي 1.8 ثانية للعثور على زوج واحد (المجموعة 1 تحتوي على 3 ملايين عنصر، والمجموعة 2 تحتوي على 4 ملايين عنصر).إذا قمت بتنفيذ نفس المهمة باستخدام فهارس MySQL-fulltext (فهي تسمح بالبحث عن السلاسل التي تحتوي على جميع الكلمات المحددة)، فإن البحث الواحد يستغرق حوالي 0.4 ثانية.لذلك أتساءل عما إذا كانت هناك بعض الأساليب الجيدة التي يمكن تطبيقها هنا بدم صغير :)

لغة البرمجة الخاصة بي هي PHP7.يتم تخزين البيانات في MySQL DB.

Answer 1

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

المؤشرات

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

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

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

يحاول

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

بعد ذلك، قم ببناء محاولة لتمثيل مجموعة الأسماء الجيدة (Set1).على سبيل المثال، في المثال الخاص بك سوف يكون المحاولة

+-- another --+-- product --+
|`-- blah --+
|`-- good --+-- product --+-- some --+
 `-- name --+-- some --+

الآن، اختر اسمًا قذرًا.نريد العثور على تطابق لها من المحاولة.أقترح عليك استخدام خوارزمية متكررة للعثور على جميع التطابقات:للعثور على تطابق للاسم $w_1 \cdots w_n$ في المحاولة $T$, ، تحقق مما إذا كانت هناك حافة خارج جذر $T$ المسمى $w_1$, ، وإذا كان الأمر كذلك، ابحث بشكل متكرر عن جميع التطابقات لـ $w_2 \cdots w_n$ في الجزء الفرعي المشار إليه بتلك الحافة؛يمكنك أيضًا العثور بشكل متكرر على جميع التطابقات لـ $w_2 \cdots w_n$ في $T$.بمجرد العثور على جميع التطابقات، احتفظ بأطولها.

على سبيل المثال، بالنسبة لـ "اسم منتج آخر طويل جدًا"، بعد الفرز يصبح هذا "منتج آخر ذو اسم طويل جدًا".يمكنك البحث عن ذلك في المجموعة الفرعية من خلال البحث بشكل متكرر عن جميع التطابقات لـ "منتج ذو اسم طويل جدًا" في المجموعة الفرعية +-- product --+, ، ومن خلال العثور على جميع المطابقات لـ "منتج ذو اسم طويل جدًا" في التجربة الرئيسية.

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

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