[Algorithm] ما هي بعض الخوارزميات لمقارنة كيف تشبه سلسلتين؟


Answers

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

على سبيل المثال: المسافة ليفنشتين بين night و nigth هو 2 ولكن داميراو ليفنشتين المسافة بين night و nigth سيكون 1 لأنه مجرد مبادلة زوج من الشخصيات.

Question

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

std::string first = "Henry C. Harper v. The Law Offices of Huey & Luey, LLP";

في مقابل:

std::string second = "Harper v. The Law Offices of Huey & Luey, LLP";

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

std::string firstNormalized = "henrycharpervthelawofficesofhueylueyllp";

و:

std::string secondNormalized = "harpervthelawofficesofhueylueyllp";

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

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

في النهاية، أنا بحاجة إلى قرار منطقي حول ما إذا كان ينبغي النظر فيها على نفس أو لا. لا يجب أن يكون مثاليا، ولكن من النادر أن يكون خطأ.

ما هي الخوارزمية التي يمكنني استخدامها والتي من شأنها أن تعطيني نوعا من التحديد الكمي لمدى تشابه السلسلتين إلى بعضهما البعض والتي يمكن أن تتحول بعد ذلك إلى إجابة نعم / لا عن طريق بعض الاستدلال؟