خوارزمية اختلاف النص
https://stackoverflow.com/questions/145607
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أحتاج إلى خوارزمية يمكنها مقارنة ملفين نصيين وإبراز الفرق بينهما، ويمكنها (والأفضل من ذلك!) حساب الفرق بينهما بطريقة ذات معنى (مثل ملفين متشابهين يجب أن يكون لهما درجة تشابه أعلى من ملفين مختلفين، مع كلمة "مشابه" محددة في المصطلحات العادية).يبدو الأمر سهل التنفيذ، لكنه ليس كذلك.
يمكن أن يكون التنفيذ بلغة c# أو python.
شكرًا.
المحلول
في بايثون، هناك difflib, ، كما اقترح آخرون أيضًا.
difflib يقدم SequenceMatcher class، والتي يمكن استخدامها لتعطيك نسبة التشابه.وظيفة المثال:
def text_compare(text1, text2, isjunk=None):
return difflib.SequenceMatcher(isjunk, text1, text2).ratio()
نصائح أخرى
يمكنني أن أوصي بإلقاء نظرة على كود ومقالات نيل فريزر:
متوفر حاليًا في Java و JavaScript و C ++ و Python.بغض النظر عن اللغة ، تتميز كل مكتبة بموجب واجهة برمجة التطبيقات نفسها ونفس الوظيفة.جميع الإصدارات لديها أيضا تسخير اختبار شامل.
نيل فريزر:استراتيجيات الفرق - للملاحظات النظرية والتنفيذية
ينظر الى difflib.(بايثون)
سيؤدي ذلك إلى حساب الفروق في أشكال مختلفة.يمكنك بعد ذلك استخدام حجم اختلاف السياق كمقياس لمدى اختلاف الوثيقتين؟
ما أفهمه حاليًا هو أن أفضل حل لمشكلة أقصر نص تحريري (SES) هو طريقة مايرز "الثعبان الأوسط" مع تحسين مساحة هيرشبيرج الخطية.
تم وصف خوارزمية مايرز في:
ه.مايرز ، "خوارزمية الفرق"
الخوارزمية 1، 2 (1986)، 251-266.
تستخدم الأداة المساعدة GNU diff خوارزمية مايرز.
تسمى "درجة التشابه" التي تتحدث عنها "مسافة التحرير" في الأدبيات وهي عدد عمليات الإدخال أو الحذف اللازمة لتحويل تسلسل واحد إلى الآخر.
لاحظ أن عددًا من الأشخاص قد استشهدوا بخوارزمية المسافة Levenshtein ولكن هذا، على الرغم من سهولة تنفيذه، ليس الحل الأمثل لأنه غير فعال (يتطلب استخدام مصفوفة ربما ضخمة n*m) ولا يوفر "نص التحرير" " وهو تسلسل التعديلات التي يمكن استخدامها لتحويل تسلسل إلى آخر والعكس صحيح.
للحصول على تنفيذ جيد لـ Myers/Hirschberg، انظر إلى:
http://www.ioplex.com/~miallen/libmba/dl/src/diff.c
لم تعد المكتبة الموجودة بداخلها تتم صيانتها ولكن على حد علمي فإن وحدة diff.c نفسها لا تزال صحيحة.
مايك
إذا كنت تريد تفصيلًا أدق من الخطوط، فيمكنك استخدام مسافة Levenshtein.تعد مسافة Levenshtein مقياسًا مباشرًا لكيفية التشابه بين النصين.
يمكنك أيضًا استخدامه لاستخراج سجلات التحرير وإجراء فروق دقيقة للغاية، مماثلة لتلك الموجودة في صفحات سجل التحرير في SO.كن حذرًا من أن حساب مسافة Levenshtein يمكن أن يستهلك الكثير من وحدة المعالجة المركزية والذاكرة، لذا فإن استخدام difflib، كما اقترح Douglas Leder، سيكون على الأرجح أسرع.
راجع.أيضًا هذه الإجابة.
هناك عدد من مقاييس المسافة، كما ذكر بارادوجا هناك مسافة ليفنشتاين، ولكن هناك أيضًا NYSIIS و Soundex.فيما يتعلق بتطبيقات بايثون، لقد استخدمت py-editdist و أدفاس قبل.كلاهما جميل بمعنى أنك تحصل على رقم واحد كنتيجة.تحقق من ADVAS أولاً، فهو ينفذ مجموعة من الخوارزميات.
كما ذكرنا، استخدم difflib.بمجرد حصولك على الناتج المختلف، قد تجد ملف مسافة ليفنشتاين من السلاسل المختلفة لإعطاء "قيمة" لمدى اختلافها.
يمكنك استخدام حل مشكلة التبعية المشتركة الأطول (LCS)..راجع أيضًا المناقشة حول الطرق الممكنة لتحسين هذا الحل.
إحدى الطرق التي استخدمتها لوظيفة مختلفة، وهي حساب مقدار البيانات الجديدة في ملف معدل، ربما تكون مناسبة لك أيضًا.
لدي تطبيق diff/patch C# الذي يسمح لي بأخذ ملفين، الإصدار القديم والجديد من نفس الملف، وحساب "الفرق"، ولكن ليس بالمعنى المعتاد للكلمة.أقوم بشكل أساسي بحساب مجموعة من العمليات التي يمكنني إجراؤها على الإصدار القديم لتحديثه ليحتوي على نفس محتويات الإصدار الجديد.
لاستخدام هذا للوظيفة الموصوفة في البداية، لمعرفة مقدار البيانات الجديدة، قمت ببساطة بإجراء العمليات، ولكل عملية تم نسخها حرفيًا من الملف القديم، وكان لها عامل 0، وكل عملية أدرجت نصًا جديدًا (تم توزيعه كجزء من التصحيح، نظرًا لأنه لم يحدث في الملف القديم) كان له عامل واحد.تم منح جميع الشخصيات هذا المصنع، والذي أعطاني بشكل أساسي قائمة طويلة من 0 و1.
كل ما كان علي فعله بعد ذلك هو جمع الصفر والواحد.في حالتك، مع تطبيقي، فإن العدد المنخفض من 1 مقارنة بـ 0 يعني أن الملفات متشابهة جدًا.
سيتعامل هذا التنفيذ أيضًا مع الحالات التي يقوم فيها الملف المعدل بإدراج نسخ من الملف القديم خارج الترتيب، أو حتى نسخ مكررة (على سبيل المثال.تقوم بنسخ جزء من بداية الملف ولصقه بالقرب من الأسفل)، حيث سيكون كلاهما نسخًا من نفس الجزء الأصلي من الملف القديم.
لقد جربت وزن النسخ، بحيث تم حساب النسخة الأولى على أنها 0، والنسخ اللاحقة من نفس الأحرف لها عوامل أعلى تدريجيًا، من أجل إعطاء عملية النسخ/اللصق بعض "العامل الجديد"، لكنني لم أنهيها أبدًا كعملية نسخ/لصق. تم إلغاء المشروع.
إذا كنت مهتمًا، فإن رمز الفرق/التصحيح الخاص بي متاح من مستودع Subversion الخاص بي.
نلقي نظرة على أجعد وحدة.يحتوي على خوارزميات سريعة (مكتوبة بلغة C) لـ soundex و NYSIIS و double metaphone.
مقدمة جيدة يمكن العثور عليها في: http://www.informit.com/articles/article.aspx?p=1848528
