خوارزمية الفرق؟[مغلق]

Question

لقد كنت أبحث بجنون عن شرح لخوارزمية مختلفة تعمل وفعالة.

الأقرب عندي هو هذا الرابط إلى RFC 3284 (من العديد من منشورات مدونة Eric Sink)، والتي تصف بعبارات مفهومة تمامًا تنسيق البيانات حيث يتم تخزين نتائج الفرق.ومع ذلك، فإنه لم يذكر على الإطلاق كيفية وصول البرنامج إلى هذه النتائج أثناء إجراء الفرق.

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

أين يمكنني العثور على وصف لخوارزمية فعالة تؤدي في النهاية إلى إخراج VCDIFF؟
بالمناسبة، إذا وجدت وصفًا للخوارزمية الفعلية المستخدمة بواسطة DiffMerge من SourceGear، فسيكون ذلك أفضل.

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

Answer 1

خوارزمية الفرق O(ND) وتغيراتها إنها ورقة رائعة وقد ترغب في البدء بها.يتضمن رمزًا زائفًا وتصورًا رائعًا لاجتياز الرسم البياني المتضمن في إجراء الفرق.

القسم 4 تقدم هذه الورقة بعض التحسينات على الخوارزمية التي تجعلها فعالة للغاية.

إن تنفيذ ذلك بنجاح سيترك لك أداة مفيدة جدًا في صندوق الأدوات الخاص بك (وربما بعض الخبرة الممتازة أيضًا).

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

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

ال مصدر الرمز يبدو أنه يتبع الخوارزمية الأساسية عن كثب ويسهل قراءتها.

هناك أيضًا القليل من المعلومات حول إعداد المدخلات، والتي قد تجدها مفيدة.هناك فرق كبير في الإخراج عندما تختلف حسب الحرف أو الرمز المميز (الكلمة).

حظ سعيد!

Answer 2

وأود أن أبدأ بالنظر إلى الفعلية <م> شفرة المصدر للفرق، مما يجعل GNU <لأ href = "http://ftp.gnu.org/gnu/diffutils/" يختلط = "noreferrer "> متاحة .

لعلامة <م> التفاهم كيف يعمل هذا الكود في الواقع، مستندات في ذلك حزمة مرجع الأوراق التي أوحت بها:

<اقتباس فقرة>   

ويوصف الخوارزمية الأساسية في "O (ND) الفرق خوارزمية وتنوعاتها"، يوجين دبليو مايرز، "Algorithmica" المجلد. 1 رقم 2، 1986، ص 251-266؛ وفي "ملف   برنامج المقارنات "، ويب ميلر ويوجين دبليو مايرز، 'البرمجيات - الممارسة والخبرة.. المجلد 15 رقم 11، 1985، ص 1025-1040 الخوارزمية اكتشف بشكل مستقل كما هو موضح في" الخوارزميات لمطابقة سلسلة التقريبية " ، E. Ukkonen، `المعلومات والمجلد تحكم. 64، 1985، ص. 100-118.

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

Answer 3

https://github.com/google/diff-match-patch

<اقتباس فقرة>   

و"إن الفرق المباراة والمكتبات التصحيح   تقدم خوارزميات قوية لأداء   العمليات المطلوبة لمزامنة   نص عادي. ... متاح حاليا   في جافا، جافا سكريبت، C ++، C # و   بيثون "

وانظر أيضا wikipedia.org الفرق الصفحة و- "<أ href = على" HTTP : //bramcohen.livejournal.com/37690.html "يختلط =" نوفولو noreferrer "> برام كوهين: تم حل المشكلة فرق"

Answer 4

وجئت الى هنا بحثا عن خوارزمية فرق وجعل بعد ذلك تنفيذ بلدي. عذرا أنا لا أعرف عن vcdiff.

ويكيبيديا : من متتالية جزئية أطول مشترك انها ليست سوى خطوة صغيرة للحصول على diff- مثل الإخراج: إذا كان عنصر غائب في متتالية جزئية ولكن موجودة في النص الأصلي، فإنه يجب أن يكون تم حذفه. (و'-'. علامات أدناه) إذا كان غائبا في متتالية جزئية ولكن موجودة في تسلسل الثاني، فإنه يجب أن يكون قد أضاف في (. وعلامات '+')

ونيس الرسوم المتحركة من LCS خوارزمية هنا .

وصلة إلى تنفيذ LCS روبي هنا .

وبلدي بطيئة وبسيطة روبي التكيف أدناه.

def lcs(xs, ys)
  if xs.count > 0 and ys.count > 0
    xe, *xb = xs
    ye, *yb = ys
    if xe == ye
      return [xe] + lcs(xb, yb)
    end
    a = lcs(xs, yb)
    b = lcs(xb, ys)
    return (a.length > b.length) ? a : b
  end
  return []
end

def find_diffs(original, modified, subsequence)
  result = []
  while subsequence.length > 0
    sfirst, *subsequence = subsequence
    while modified.length > 0
      mfirst, *modified = modified
      break if mfirst == sfirst
      result << "+#{mfirst}"
    end
    while original.length > 0
      ofirst, *original = original
      break if ofirst == sfirst
      result << "-#{ofirst}"
    end
    result << "#{sfirst}"
  end
  while modified.length > 0
    mfirst, *modified = modified
    result << "+#{mfirst}"
  end
  while original.length > 0
    ofirst, *original = original
    result << "-#{ofirst}"
  end
  return result
end

def pretty_diff(original, modified)
  subsequence = lcs(modified, original)
  diffs = find_diffs(original, modified, subsequence)

  puts 'ORIG      [' + original.join(', ') + ']'
  puts 'MODIFIED  [' + modified.join(', ') + ']'
  puts 'LCS       [' + subsequence.join(', ') + ']'
  puts 'DIFFS     [' + diffs.join(', ') + ']'
end

pretty_diff("human".scan(/./), "chimpanzee".scan(/./))
# ORIG      [h, u, m, a, n]
# MODIFIED  [c, h, i, m, p, a, n, z, e, e]
# LCS       [h, m, a, n]
# DIFFS     [+c, h, +i, -u, m, +p, a, n, +z, +e, +e]

Answer 5

واستنادا إلى الارتباط أعطى Emmelaich، وهناك أيضا تشغيل كبيرة أسفل الاستراتيجيات الفرق على موقع نيل فريزر (واحد من الكتاب من المكتبة) .

ويغطي الاستراتيجيات الأساسية ونحو نهاية المقال تقدم إلى خوارزمية ماير وبعض نظرية الرسم البياني.