بحاجة إلى طريقة فعالة للبحث عن متطلبات المواصفات التالية

Question

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

1. استخدام التجزئة (ولكن ليس من الواضح كيفية تصميمه)

2. استخدام مرشحات إزهار للبحث (يرجى google، إذا كنت لا تعرف عن ذلك، عملها مثير جدا للاهتمام!): المشكلة في استخدام مرشحات إزهار هي "الإيجابيات الخاطئة ممكنة، ولكن السلبيات الخاطئة ليست". قد أفتقد بعض النتائج ....

Answer 1

قبل البحث، قم بإنشاء تري كل مباريات إيجابية.

سيأخذ إنشاء Trie O (n) حيث n هو عدد الكلمات.

إلى البحث، حاول أن تتطابق مع الكلمة ضد Trie. يتم البحث عن UPS في O (م) حيث م هو الطول من الكلمة للبحث.

إجمالي وقت التشغيل: O (N + NM) => O (NM) للعثور على كل الكلمات.