سلسلة تقريبية مطابقة

Question

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

التطبيق مخصص لمطابقة اسم الشركة فقط ولا شيء آخر.

من المحتمل أن يكون التحدي الأكبر هو جزء الاسم النهائي للشركة وجزء قصير مسمى مثال: 1. Companya Pty Ltd vs Companya Pty. المحدودة. VS Companya 2. Wes Engineering Vs Wes Engineering (حدث نادر للغاية)

هل تعتقد أن مسافة تحرير Levenshtein كافية؟

أنا أستخدم C#

التحيات ، ماكس

Answer 1

هناك العديد من مقاييس مسافة السلسلة التي يمكنك استخدامها.

أوصي Jaro-Winkler. على عكس التحرير حيث تكون نتيجة المقارنة في وحدات منفصلة من التعديلات ، يمنحك JW درجة 0-1. إنه مناسب بشكل خاص للأسماء المناسبة. انظر أيضا هذا البرنامج التعليمي الجميل و هذا السؤال جدا.

لم أعمل مع C# ولكن إليك بعض تطبيقات JW التي وجدتها عبر الإنترنت:

ضحية 1 (لديهم إصدار Net Dot أيضًا إذا نظرت إلى قائمة الملفات)

ضحية 2

---

إذا كنت ترغب في القيام بمطابقة أكثر تطوراً قليلاً ، فيمكنك محاولة القيام ببعض التطبيع المخصص لنماذج الكلمات التي تحدث عادة في أسماء الشركات مثل ltd/limited, inc/incorporated, corp/corporation لحساب عدم حساسية الحالة ، الاختصارات وما إلى ذلك. بهذه الطريقة إذا قمت بحساب

distance (normalize("foo corp."), normalize("FOO CORPORATION") )

يجب أن تحصل على النتيجة لتكون 0 بدلاً من 14 (وهو ما ستحصل عليه إذا قمت بحساب مسافة تحرير Levenshtein).

Answer 2

نعم ، مسافة Levenshtein مناسبة لهذا. سوف يعمل مع كل من أدرجت على الأقل.

يمكنك أيضا استخدام Soundex, ، لكنني لا أعتقد أنك ستحتاج إليها.

Answer 3

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

Answer 4

لقد قدمت إجابتي بالفعل في سؤال آخر.

https://stackoverflow.com/a/30120166/2282794

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

إذا كنا نريد فقط التحدث عن خوارزميات مطابقة السلسلة التقريبية ، فهناك الكثير. قليلون منهم هم: Jaro-Winkler ، Edit Cayment (Levenshtein) ، تشابه Jaccard ، خوارزميات Soundex/Phonetics وما إلى ذلك. يمكنك تنفيذ كل منهم في C#

المفارقة هي أنها تعمل أثناء محاولتك مطابقة سلاسل إدخال معينة. حسنًا من الناحية النظرية ولإظهار الطريقة التي تتطابق بها سلسلة غامضة أو تقريبية.

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

ربما تحدثت للتو عن لوسين وهو خاص بجافا ولكن هناك لوكين لـ .NET أيضًا.

https://lucenenet.apache.org/