O Diff pode ser derrotado em seu próprio jogo?

https://stackoverflow.com/questions/1020925

06-07-2019
|

Pergunta

Estou procurando o algoritmo apropriado a ser usado para comparar dois arquivos. Eu acho que posso fazer melhor do que diff Devido a algumas restrições adicionais.

O que eu tenho são dois arquivos de texto, cada um contendo uma lista de arquivos. São instantâneos de todos os arquivos em um sistema tirado em dois momentos diferentes. Quero descobrir quais arquivos foram adicionados ou excluídos entre os dois instantâneos.

eu poderia usar diff Para comparar esses arquivos, mas não quero porque:

diff tenta agrupar mudanças, descobrindo quais pedaços em um arquivo mudaram. Estou procurando apenas uma lista de linhas que mudaram, e esse deve ser um problema muito mais simples do que encontrar a subseqüência mais comum ou algo assim.
Os algoritmos diff generalizados são O (MN) em tempo de execução ou espaço. Estou procurando algo mais como O (M+N) no tempo e O (1) no espaço.

Aqui estão as restrições sobre o problema:

As listagens de arquivos estão na mesma ordem nos dois arquivos. Eles são não necessariamente em ordem alfabética, mas eles estão no mesmo relativo ordem.
Na maioria das vezes, não haverá diferenças entre as listas. Se houver diferenças, geralmente haverá apenas alguns arquivos novos/excluídos.
Não preciso agrupar os resultados, como dizer "todo esse diretório foi excluído" ou "as linhas 100-200 são novas". Eu posso listar individualmente cada linha diferente.

Estou pensando que isso é equivalente ao problema de ter duas listas classificadas e tentar descobrir as diferenças entre as duas listas. O problema é que os itens da lista não são necessariamente classificados em ordem alfabética, então você não sabe se um item é "maior" que outro. Você apenas sabe que os arquivos presentes nas duas listas estarão na mesma ordem.

Pelo que vale a pena, eu Postado anteriormente esta pergunta em Pergunte a Metafilter vários anos atrás. Permita -me responder a várias respostas potenciais antecipadamente.

Responda: Este problema é chamado Subseqüência comum mais longa.

Resposta: Estou tentando evitar a subsequência mais comum mais longa, porque algoritmos simples são executados O (MN) tempo/espaço e melhores são complicados e mais "heurísticos". Minha intuição me diz que há um algoritmo de tempo linear devido às restrições adicionais.

Responda: Classifique -os em ordem alfabética e depois compare.

Resposta: Isso seria O (m log m+n log n), que é pior do que O (M+N).

Solução

Isso não é exatamente O(1) memória, o requisito de memória na ordem do número de alterações, mas é O(m+n) tempo de execução.

É essencialmente um algoritmo de streaming buffer que, em qualquer linha, sabe a diferença de todas as linhas anteriores.

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

Isso depende muito do fato de que os arquivos estão listados na mesma ordem relativa. Caso contrário, o requisito de memória seria muito maior que o número de alterações. No entanto, devido a esse pedido, esse algoritmo não deve usar muito mais memória do que 2 * numchanges.

Outras dicas

Leia um arquivo, colocando cada nome de arquivo em um Hashset-como estrutura de dados com O(1) adicione e O(1) contém implementações.

Em seguida, leia o arquivo segundos, verificando cada nome de arquivo em relação ao hashset.

Algoritmo total se o arquivo um tiver comprimento m e o segundo arquivo tem comprimento n é O(m+n) como requerido.

Nota: Este algoritmo assume que o conjunto de dados se encaixa confortavelmente na memória física para ser rápida.

Se o conjunto de dados não puder se encaixar facilmente na memória, a pesquisa poderá ser implementada usando alguma variação de um B-Tree com paginação em disco. A complexidade seria então O(mlog m) para configurar inicialmente e O(n log m) para um outro arquivo Compare.

Do ponto de vista teórico, comparando a distância de edição entre duas cordas (porque aqui você tem strings em uma linguagem engraçada em que um 'personagem' é um nome de arquivo) não pode ser feito O (M+N). Mas aqui temos simplificações.

Uma implementação de um algoritmo no seu caso (deve conter erros):

# 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

Existem estruturas de dados que eu chamo de matrizes rápidas - elas provavelmente são HashSet coisas, mas as que se lembram de pedir. A adição e a pesquisa neles devem ser O(log N), mas o uso da memória O(N).

Isso não usa memória ou ciclos além O(m+n) Fora de encontrar diferenças. Para cada 'bloco de diferenças' - a operação que pode ser descrita como retirando os itens unidos e adicionando n - isso leva O(M+N) memória e ~~O(MN)~~ O(Mlog N+Nlog M) instruções. A memória é liberada depois que um bloco é feito, então isso não é uma coisa muito se você realmente tiver pequenas alterações. Obviamente, o pior desempenho é tão ruim quanto no método genérico.

Na prática, uma diferença de fator de log no tempo de classificação é provavelmente insignificante - sort pode classificar centenas de milhares de linhas em alguns segundos. Então você realmente não precisa escrever nenhum código:

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

Não estou alegando que esta é necessariamente a solução mais rápida - eu acho Resposta aceita de Ben S estará, pelo menos acima de algum valor de N. Mas é definitivamente o mais simples, ele será escalado para qualquer número de arquivos e (a menos que você seja o cara responsável pela operação de backup do Google), será mais do que rápido o suficiente para o número de arquivos que você tem.

Se você aceitar que os dicionários (mapas de hash) são O (n) espaço e O (1) inserção/pesquisa, esta solução deve ser O (M+N) no tempo e no espaço.

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

Ok, trapaça leve como list.append e list.__delitem__ são apenas O (1) se eles estão vinculados, o que não é realmente verdadeiro ... mas essa é a ideia, de qualquer maneira.

Um refinamento da resposta da Efemient, isso usa apenas memória extra quando há alterações.

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

Comentários? Melhorias?

Eu estive atrás de um programa para diferenciar arquivos grandes sem ficar sem memória, mas não encontrei nada para se adequar aos meus propósitos. Não estou interessado em usar os diffs para corrigir (então eu provavelmente usaria rdiff de Librdiff), mas para inspecionar visualmente as diferenças, talvez transformando-as em dififos de palavras com dwdiff --diff-input (que lê o formato de diff unified) e talvez coletar os dififos de palavras de alguma forma.

(Meu caso de uso típico: eu tenho uma ferramenta de PNL que uso para processar um corpus de texto grande. Eu o executo uma vez, recebo um arquivo com 122760246 linhas de comprimento, faço uma alteração na minha ferramenta, execute -a novamente, obtenha um arquivo que Difere como cada milhão de linhas, talvez duas inserções e uma exclusão, ou apenas uma linha difere, esse tipo de coisa.)

Como não consegui encontrar nada, acabei de fazer um pequeno script https://github.com/unhammer/diff-large-files - Funciona (o DWDIFF o aceita como entrada), é rápido o suficiente (mais rápido que o processo XZ que costuma correr atrás dele no pipeline) e, mais importante, não fica sem memória.

Eu lia as listas de arquivos em dois conjuntos e encontrava os nomes de arquivos exclusivos da lista.

Em Python, algo como:

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

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow