Можно ли победить diff в его собственной игре?

https://stackoverflow.com/questions/1020925

06-07-2019
|

Вопрос

Я ищу подходящий алгоритм для сравнения двух файлов.Я думаю, что могу добиться большего, чем diff из-за некоторых дополнительных ограничений.

У меня есть два текстовых файла, каждый из которых содержит список файлов.Это снимки всех файлов в системе, сделанные в два разных момента времени.Я хочу выяснить, какие файлы были добавлены или удалены между двумя снимками.

я мог бы использовать diff сравнивать эти файлы, но я не хочу, потому что:

diff пытается сгруппировать изменения, определяя, какие фрагменты файла изменились.Я ищу только список строк, которые изменились, и это должно быть гораздо более простой задачей, чем поиск самой длинной общей подпоследовательности или чего-то в этом роде.
Обобщенные алгоритмы сравнения: О(мин) во время выполнения или пространстве.Я ищу что-то более похожее О(м+п) вовремя и О(1) в космосе.

Вот ограничения на проблему:

Списки файлов в обоих файлах расположены в одинаковом порядке.Они есть нет обязательно в алфавитном порядке, но они находятся в одном и том же родственник заказ.
В большинстве случаев различий между списками не будет.Если есть различия, обычно будет всего несколько новых/удаленных файлов.
Мне не нужно группировать результаты вместе, например, «весь этот каталог был удален» или «строки 100–200 новые».Я могу отдельно перечислить каждую линию, которая отличается.

Я думаю, что это эквивалентно проблеме наличия двух отсортированных списков и попытки выяснить различия между ними.Проблема в том, что элементы списка не обязательно отсортированы в алфавитном порядке, поэтому вы не знаете, «больше» ли один элемент другого.Вы просто знаете, что файлы, присутствующие в обоих списках, будут находиться в одном и том же порядке.

Чего бы это ни стоило, я ранее опубликовано этот вопрос на Спросите Метафильтр несколько лет назад.Позвольте мне заранее ответить на несколько возможных ответов.

Отвечать: Эта проблема называется Самая длинная общая подпоследовательность.

Ответ: Я пытаюсь избежать самой длинной общей подпоследовательности, потому что в ней выполняются простые алгоритмы. О(мин) время/пространство и лучшие из них сложны и более «эвристичны».Моя интуиция подсказывает мне, что существует алгоритм с линейным временем из-за дополнительных ограничений.

Отвечать: Отсортируйте их по алфавиту и затем сравните.

Ответ: Это было бы O(m log m+n log n), что хуже, чем О(м+п).

Решение

Это не совсем 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.

Другие советы

Прочитайте один файл, поместив каждое имя файла в HashSet -подобная структура данных с O (1) add и O (1) содержит реализации.

Затем прочитайте файл секунд, сверяя каждое имя файла с HashSet.

Общий алгоритм, если длина одного файла m , а длина второго файла n равна O (m + n) , как требуется.

Примечание. Этот алгоритм предполагает, что набор данных удобно размещается в физической памяти, чтобы быть быстрым.

Если набор данных не может легко поместиться в памяти, поиск может быть реализован с использованием некоторого варианта B-Tree с дисковой подкачкой. Тогда сложность будет O (mlog m) для первоначальной настройки и O (n log m) для сравнения каждого файла.

С теоретической точки зрения сравнение расстояния редактирования между двумя строками (потому что здесь у вас есть строки на забавном языке, где «символ» - это имя файла) не может быть сделано 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) за пределами поиска различий. Для каждого «блока различий» - операции, которая может быть описана как удаление M последовательных элементов и добавление N единиц - это занимает O (M + N) памяти и ~~O (MN)~~ O (Mlog N + Nlog M) . Память освобождается после завершения блока, так что это не так уж важно, если у вас действительно есть небольшие изменения. Конечно, производительность в худшем случае такая же плохая, как и при использовании универсального метода.

На практике разница логарифмических значений во времени сортировки, вероятно, незначительна - sort может отсортировать сотни тысяч строк за несколько секунд. Так что на самом деле вам не нужно писать код:

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

Я не утверждаю, что это обязательно самое быстрое решение - я думаю, что Принятый ответ Ben S будет, по крайней мере, выше некоторого значения N. Но это, безусловно, самое простое, оно масштабируется до любого количества файлов, и (если вы не ответственный парень операции резервного копирования Google) это будет более чем достаточно для количества файлов, которые у вас есть.

Если вы согласны с тем, что словари (хеш-карты) являются 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), если они являются связанными списками, что на самом деле не так. но это идея, во всяком случае.

Уточнение ответа эфемиента: дополнительная память используется только при наличии изменений.

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

Комментарии?Улучшения?

Я искал программу для различий больших файлов без исчерпания памяти, но не нашел ничего подходящего для моих целей. Меня не интересует использование различий для исправления (тогда я бы, вероятно, использовал rdiff из librdiff), но для визуальной проверки различий, возможно, превращения их в разностные слова с помощью dwdiff - -diff-input (который читает унифицированный формат diff) и, возможно, каким-то образом собирать слова-diff.

(Мой типичный пример использования: у меня есть какой-то инструмент НЛП, который я использую для обработки большого текстового корпуса. Я запускаю его один раз, получаю файл длиной 122760246 строк, я изменяю свой инструмент, запускаю его снова, получаю файл, который отличается, как каждый миллион строк, может быть две вставки и удаление, или отличается только одна строка, такого рода вещи.)

Поскольку я ничего не мог найти, я просто написал небольшой скрипт https: // github. com / unhammer / diff-large-files & # 8211; он работает (dwdiff принимает его в качестве входных данных), он достаточно быстрый (быстрее, чем процесс xz, который часто запускается после него в конвейере), и, что наиболее важно, он не исчерпывает память.

Я прочитал бы списки файлов в два набора и нашел бы имена файлов, которые являются уникальными для любого списка.

В Python что-то вроде:

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)))

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow