مقارنة مسافة السلسلة بناءً على تجزئة مسبقة

Question

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

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

سؤالي هو ، هل هناك شيء كهذا موجود بالفعل؟ بالتأكيد سيكون هناك شيء يتيح لي تجنب الجري مسافة Levenshtein على كل سلسلة في القائمة؟

أو ربما هناك خيار ثالث لم أفكر فيه بعد؟

Answer 1

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

فكر آخر - إذا كنت تقدر أن احتمال إدخال غير صحيح منخفض ، فقد تكون على ما يرام في الواقع الحصول على ضرب 99.9 ٪ من الوقت ، والتراجع إلى Soundex الذي قد يلتقط 90 ٪ من الحالات المتبقية ثم البحث عن الكل قائمة ل 0.01 ٪ المتبقية من الوقت.

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