هل يمكن التغلب على Diff في لعبتها الخاصة؟

Question

أنا أبحث عن الخوارزمية المناسبة لاستخدامها لمقارنة ملفين. أعتقد أنني أستطيع أن أفعل أفضل من diff بسبب بعض القيود المضافة.

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

يمكن أن أستخدم diff لمقارنة هذه الملفات ، لكنني لا أريد ذلك لأن:

1. diff يحاول مجموعة التغييرات معًا ، والعثور على القطع في ملف قد تغير. أنا أبحث فقط عن قائمة بالخطوط التي تغيرت ، ويجب أن تكون هذه مشكلة أبسط بكثير من العثور على أطول متسلسل أو شيء من هذا القبيل.

2. خوارزميات الاختلاف المعممة س (MN) في وقت التشغيل أو الفضاء. أنا أبحث عن شيء أشبه س (م+ن) في الوقت و س (1) في الفضاء.

فيما يلي القيود على المشكلة:

1. قوائم الملفات في نفس الترتيب في كلا الملفين. هم انهم ليس بالضرورة بالترتيب الأبجدي ، لكنهم في نفس الشيء نسبيا ترتيب.

2. معظم الوقت لن يكون هناك اختلافات بين القوائم. إذا كانت هناك اختلافات ، فلن يكون هناك عادة حفنة من الملفات الجديدة/المحذوفة.

3. لست بحاجة إلى تجميع النتائج معًا ، مثل قول "تم حذف هذا الدليل بأكمله" أو "الخطوط 100-200 جديدة". يمكنني إدراج كل سطر مختلف بشكل فردي.

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

لما يستحق ، أنا نشرت مسبقا هذا السؤال على اسأل Metafilter قبل عدة سنوات. اسمح لي بالرد على عدة إجابات محتملة مقدمًا.

إجابه: هذه المشكلة تسمى أطول بعد شائع.

إجابة: أحاول تجنب أطول فترة شائعة لأن الخوارزميات البسيطة تعمل في س (MN) الوقت/الفضاء والأفضل معقدة وأكثر "إرشادي". يخبرني حدسي أن هناك خوارزمية خطي في الوقت المناسب بسبب القيود المضافة.

إجابه: فرزها أبجديًا ثم قارن.

إجابة: ممكن حدوثه o (M log m+n log n), ، وهو أسوأ من س (م+ن).

Answer 1

هذا ليس تماما O(1) الذاكرة ، متطلبات الذاكرة بترتيب عدد التغييرات ، لكنها كذلك O(m+n) مدة العرض.

إنها في الأساس خوارزمية التدفق المخزنة التي تعرف في أي سطر معين الفرق في جميع الخطوط السابقة.

// Pseudo-code:
initialize HashMap<Line, SourceFile> changes = new empty HashMap
while (lines left in A and B) {
    read in lineA from file A
    read in lineB from file B

    if (lineA.equals(lineB)) continue

    if (changes.contains(lineA) && changes.get(lineA).SourceFile != A) {
         changes.remove(lineA)
    } else {
         changes.add(lineA, A)
    }

    if (changes.contains(lineB) && changes.get(lineB).SourceFile != B) {
         changes.remove(lineB)
    } else {
         changes.add(lineB, B)
    }
}

for each (line in longerFile) {
    if (changes.contains(line) && changes.get(line).SourceFile != longerFile) {
         changes.remove(line)
    } else {
         changes.add(line, longerFile)
    }
}

Lines in the HashMap from SourceFile == A have been removed
Lines in the HashMap from SourceFile == B have been added

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

Answer 2

اقرأ ملفًا واحدًا ، ووضع كل اسم ملف في Hashset-مثل بنية البيانات مع O(1) إضافة و O(1) يحتوي على تطبيقات.

ثم اقرأ ملف الثواني ، والتحقق من كل اسم ملف مقابل hashset.

إجمالي الخوارزمية إذا كان ملف واحد لديه طول m والملف الثاني لديه طول n هو O(m+n) كما هو مطلوب.

ملاحظة: تفترض هذه الخوارزمية أن مجموعة البيانات تتناسب بشكل مريح في الذاكرة الفعلية لتكون سريعة.

إذا لم تتمكن مجموعة البيانات من ملائمة الذاكرة بسهولة ، فيمكن تنفيذ البحث باستخدام بعض الاختلافات ب شجرة مع ترحيل القرص. سيكون التعقيد بعد ذلك O(mlog m) لإعداد في البداية و O(n log m) لبعضنا البعض قارن.

Answer 3

من وجهة نظر نظرية ، لا يمكن إجراء مقارنة مسافة التحرير بين سلسلتين (لأنه هنا لديك سلاسل بلغة مضحكة حيث "شخصية" هي اسم ملف) O (M+N). ولكن هنا لدينا تبسيط.

تنفيذ خوارزمية في قضيتك (يجب أن تحتوي على أخطاء):

# i[0], i[1] are undoable iterables; at the end they both return Null

while (a = i[0].next()) && (b = i[1].next()) :    # read one item from each stream
    if a != b:                 # skip if they are identical
        c = [[a],[b]]          # otherwise, prepare two fast arrays to store difference
        for (w = 1; ; w = 1-w) # and read from one stream at a time
             nxi = Null        
             if (nx = i[1-w].next()) in c[w]:  # if we read a new character that matches
                  nxi = c[w].index(nx)          
             if nx is Null: nxi = -1           # or if we read end of stream
             if nxi is not Null:               # then output that we found some diff
                 for cc in c[1-w]: yield cc              # the ones stored 
                 for cc in c[w][0:nxi-1]: yield cc       # and the ones stored before nx
                 for cc in c[w][nxi+1:]: i[w].undo(cc)   # about the remainder - put it back
                 break                         # and return back to normal cycle
 # one of them finished
 if a: yield a
 if b: yield b
 for ci in i: 
     while (cc = ci.next()): yield cc

هناك هياكل بيانات أسميها صفائف سريعة - ربما تكون HashSet الأشياء ، ولكن تلك التي تتذكر الطلب. يجب أن تكون الإضافة والبحث فيها O(log N), ، لكن استخدام الذاكرة O(N).

هذا لا يستخدم أي ذاكرة أو دورات خارج O(m+n) خارج العثور على الاختلافات. لكل "كتلة الاختلاف" - العملية التي يمكن وصفها بأنها تسلب العناصر consequTive وإضافة N - O(M+N) الذاكرة و O(MN) O(Mlog N+Nlog M) تعليمات. يتم إصدار الذاكرة بعد الانتهاء من الكتلة ، لذلك ليس هذا شيءًا كبيرًا إذا كان لديك بالفعل تغييرات صغيرة فقط. بالطبع ، أسوأ أداء سيء كما هو الحال مع الطريقة العامة.

Answer 4

في الممارسة العملية ، ربما يكون اختلاف عامل السجل في أوقات الفرز ضئيلة - sort يمكن فرز مئات الآلاف من الخطوط في بضع ثوان. لذلك لا تحتاج فعليًا إلى كتابة أي رمز:

sort filelist1 > filelist1.sorted
sort filelist2 > filelist2.sorted
comm -3 filelist1.sorted filelist2.sorted > changes

أنا لا أدعي أن هذا هو بالضرورة أسرع حل - أعتقد إجابة بن إس مقبولة سيكون ، على الأقل أعلى من قيمة N. ، لكنها بالتأكيد أبسط ، وسوف تتوسع في أي عدد من الملفات ، و (ما لم تكن الشخص المسؤول عن عملية النسخ الاحتياطي من Google) سيكون أكثر من سرعة بما يكفي للرقم من الملفات التي لديك.

Answer 5

إذا قبلت أن القواميس (خرائط التجزئة) هي مساحة O (n) و O (1) إدراج/بحث ، فيجب أن يكون هذا الحل O (M+N) في كل من الزمان والمكان.

from collections import defaultdict
def diff(left, right):
    left_map, right_map = defaultdict(list), defaultdict(list)
    for index, object in enumerate(left): left_map[object] += [index]
    for index, object in enumerate(right): right_map[object] += [index]
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left_map[right[j]]:
            i2 = left_map[right[j]].pop(0)
            if i2 < i: continue
            del right_map[right[j]][0]
            for i in range(i, i2): print '<', left[i]
            print '=', left[i2], right[j]
            i, j = i2 + 1, j + 1
        elif right_map[left[i]]:
            j2 = right_map[left[i]].pop(0)
            if j2 < j: continue
            del left_map[left[i]][0]
            for j in range(j, j2): print '>', right[j]
            print '=', left[i], right[j2]
            i, j = i + 1, j2 + 1
        else:
            print '<', left[i]
            i = i + 1
    for j in range(j, len(right)): print '>', right[j]

>>> diff([1, 2, 1, 1, 3,    5, 2,    9],
...      [   2, 1,    3, 6, 5, 2, 8, 9])
< 1
= 2 2
= 1 1
< 1
= 3 3
> 6
= 5 5
= 2 2
> 8
= 9 9

حسنًا ، غش طفيف مثل list.append و list.__delitem__ هي فقط O (1) إذا كانت قوائم مرتبطة ، فهذا ليس صحيحًا حقًا ... ولكن هذه هي الفكرة ، على أي حال.

Answer 6

صقل إجابة الزوارق ، وهذا يستخدم فقط ذاكرة إضافية عندما تكون هناك تغييرات.

def diff(left, right):
    i, j = 0, 0

    while i < len(left) and j < len(right):
        if left[i] == right[j]:
            print '=', left[i], right[j]
            i, j = i+1, j+1
            continue

        old_i, old_j = i, j
        left_set, right_set = set(), set()

        while i < len(left) or j < len(right):
            if i < len(left) and left[i] in right_set:
                for i2 in range(old_i, i): print '<', left[i2]
                j = old_j
                break

            elif j < len(right) and right[j] in left_set:
                for j2 in range(old_j, j): print '>', right[j2]
                i = old_i
                break

            else:
                left_set .add(left [i])
                right_set.add(right[j])
                i, j = i+1, j+1

    while i < len(left):
        print '<', left[i]
        i = i+1

    while j < len(right):
        print '>', right[j]
        j = j+1

تعليقات؟ تحسينات؟

Answer 7

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

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

بما أنني لم أتمكن من العثور على أي شيء ، فقد صنعت نصًا صغيرًا https://github.com/unhammer/diff-large-files - إنه يعمل (يقبله DWDIFF كمدخلات) ، إنه سريع بما فيه الكفاية (أسرع من عملية XZ التي غالباً ما يتم تشغيلها بعدها في خط الأنابيب) ، والأهم من ذلك أنها لا تنفد من الذاكرة.

Answer 8

أود أن أقرأ قوائم الملفات في مجموعتين وأجد أسماء الملفات هذه الفريدة لأي من القائمة.

في بيثون ، شيء مثل:

files1 = set(line.strip() for line in open('list1.txt'))
files2 = set(line.strip() for line in open('list2.txt'))
print('\n'.join(files1.symmetric_difference(files2)))