تسريع levenshtein / similar_text في PHP

Question

وأنا حاليا باستخدام similar_text لمقارنة سلسلة ضد قائمة ~ 50000 الذي يعمل على الرغم من أن يرجع ذلك إلى عدد من المقارنات انها بطيئة جدا. يستغرق حوالي 11 دقيقة لمقارنة ~ 500 سلاسل فريدة من نوعها.

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

وأنا متأكد من استخدام levenshtein سيكون أسرع وقليلا وظيفة LevenshteinDistance شخص شارك في دليل تبدو مثيرة للاهتمام. أنا في عداد المفقودين شيء يمكن أن تجعل من هذا أسرع بكثير؟

Answer 1

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

وعلى سبيل التجربة، وأنا استدار بعض الرمز إلى C # لنرى كيف أسرع بكثير سيكون على كود interperated. وتجلى ذلك في حوالي 3 دقائق مع نفس البيانات.

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

في النهاية أنا اختار نهج أبسط، MySQLs النص الكامل التي عملت بشكل جيد جدا. أحيانا هناك اخطاء على الرغم من أنها سهلة للكشف عن والصحيح. أيضا تشغيله سريع جدا، في حوالي 3-4 ثواني.

Answer 2

وربما كنت قد "ماس كهربائي" بعض الشيكات من خلال مقارنة لأول مرة سلسلة الخاص بك عن تطابق تام (وبمقارنة أولا إذا طول متطابقة)، وإذا كان من تخطي الدعوة similar_text أكثر تكلفة.

وكما لوحظjason، وهو O (N ^ 3) الخوارزمية لن تكون خيارا جيدا.

Answer 3

عند استخدام إنسان levenshtein (إنسان يطابق سلسلة مع k بعد) يمكنك القيام الاختيار مطابقة في O(n)، حيث n هو طول السلسلة التي يتم التحقق. وبناء على إنسان اتخاذ O(kn)، حيث k هو المسافة وn أقصى طول السلسلة القاعدة.