Pergunta

Alguém tem, ou sabe de um patch binário de geração a implementação do algoritmo em C#?

Basicamente, comparar dois arquivos (designado idade e novo), e produzir um arquivo de patch que pode ser usado para atualizar o idade arquivo para ter o mesmo conteúdo que o novo arquivo.

A execução teria que ser relativamente rápido, e trabalhar com arquivos grandes.Ele deve apresentar O(n) ou O(logn) tempos de execução.

Meus próprios algoritmos tendem a ser péssimo (rápido, mas produzem enormes manchas) ou lenta (produzir pequenas manchas, mas têm de O(n^2) tempo de execução).

Qualquer conselho, ou ponteiros para a implementação seria bom.

Especificamente, a implementação vai ser usado para manter os servidores de sincronização de vários grandes datafiles que temos um servidor mestre para.Quando o servidor mestre datafiles mudar, nós precisamos atualizar várias off-servidores de site bem.

O mais ingênuo algoritmo de eu ter feito, que funciona apenas para arquivos que podem ser guardados na memória, é como segue:

  1. Pegue os primeiros quatro bytes do idade arquivo, chamamos de chave
  2. Adicione esses bytes para um dicionário, onde tecla -> posição, onde posição é a posição de onde eu peguei os 4 bytes, 0, para começar
  3. Pular o primeiro desses quatro bytes, pegue outro 4 (3 sobreposição, 1), e adicionar ao dicionário da mesma forma
  4. Repita os passos 1 a 3 para todos os 4 blocos de bytes no idade arquivo
  5. Desde o início do novo arquivo, pegue 4 bytes, e a tentativa de olhar no dicionário
  6. Se encontrado, localizar o jogo há mais tempo se houver vários, comparando bytes a partir de dois ficheiros
  7. Codificar uma referência para a localização na caixa idade arquivo, e ignorar a correspondência do bloco no novo arquivo
  8. Se não for encontrado, codificação de 1 byte da novo arquivo, e ignorá-lo
  9. Repita os passos 5 a 8 para o resto da novo arquivo

Este é um pouco como compressão, sem janelas, de modo que ele utilize muita memória.É, no entanto, bastante rápido, e produz pequenas manchas, enquanto eu tento fazer com que os códigos de saída mínima.

Uma memória mais eficiente algoritmo utiliza janelas, mas produz muito maior arquivos de patch.

Há mais nuances para o algoritmo acima que eu pulei neste post, mas eu posso postar mais detalhes, se necessário.Eu, no entanto, sinto que eu preciso de um algoritmo diferente completamente, de modo a melhorar o algoritmo acima é, provavelmente, não vai me levar para longe o suficiente.


Edição #1:Aqui está uma descrição mais detalhada do algoritmo acima.

Primeiro, misture os dois arquivos, de modo que você tem um grande arquivo.Lembre-se que o corte de ponto entre os dois arquivos.

Em segundo lugar, fazer o que pegue 4 bytes e adicionar a sua posição para o dicionário passo para tudo, em todo o arquivo.

Em terceiro lugar, a partir de onde o novo o arquivo é iniciado, faça o laço com a tentativa de localizar uma combinação existente de 4 bytes, e encontrar o maior correspondência.Certifique-se de que nós apenas considerar as posições do arquivo antigo, ou a partir de anteriores no arquivo novo que estamos atualmente no.Isso garante que podemos reutilizar o material antigo e o novo ficheiro durante a aplicação do adesivo.


Edição #2: Código-fonte para o algoritmo acima

Você pode receber um aviso sobre o certificado de ter alguns problemas.Eu não sei como resolver isso então para o momento, basta aceitar o certificado.

A fonte usa muitos outros tipos de resto de minha biblioteca, de modo que o arquivo não é tudo o que preciso, mas que é a implementação do algoritmo.


@lomaxx, eu tenho tentado encontrar uma boa documentação para o algoritmo utilizado no subversion, chamado xdelta, mas a menos que você já sabe como o algoritmo funciona, os documentos que eu encontrei não contar-me o que eu preciso saber.

Ou talvez eu só estou densa...:)

Eu levei uma espiada rápida no algoritmo do site que você deu, e infelizmente não é utilizável.Um comentário do binário do arquivo diff diz:

Encontrar um conjunto ótimo de diferenças requer quadrática tempo em relação ao tamanho da entrada, e assim torna-se inutilizável muito rapidamente.

Minhas necessidades não são ideais, embora, por isso eu estou procurando uma solução mais prática.

Obrigado pela resposta, porém, adicionado um marcador para seus utilitários, se eu precisar deles.

Edição #1:Nota, eu vou olhar para o seu código para ver se eu posso encontrar algumas ideias, e eu vou também enviar-lhe um e-mail mais tarde com perguntas, mas eu já li o livro que ele referencia e que a solução é boa para encontrar soluções ótimas, é impraticável em uso devido aos requisitos de tempo.

Edição #2:Eu definitivamente vou caçar o python xdelta implementação.

Foi útil?

Solução

Desculpe, eu não poderia ser de mais ajuda.Eu seria, definitivamente, ficar olhando para xdelta porque eu tenho usado um número de vezes para produzir qualidade de diffs em 600 MB+ arquivos ISO que temos gerado para a distribuição de nossos produtos e executa muito bem.

Outras dicas

bsdiff foi projetado para criar muito pequenas manchas de arquivos binários.Como afirmou em sua página, ele requer max(17*n,9*n+m)+O(1) bytes de memória e executado em O((n+m) log n) tempo (em que n é o tamanho do arquivo antigo e m é o tamanho do novo arquivo).

A implementação original é em C, mas C# porto é descrito aqui e disponível aqui.

Você tem visto VCDiff?Ele é parte de uma biblioteca de mobiliário e acessorios que parece ser bastante ativo (último lançamento r259, 23 de abril de 2008).Eu ainda não usei, mas achei que valia a pena mencionar.

Ele pode ser vale a pena conferir o que os caras estão fazendo neste espaço, não necessariamente na C# arena quer.

Esta é uma biblioteca escrita em c#

SVN também tenha um diff binário algoritmo e eu sei que há uma implementação em python, apesar de eu não poderia encontrá-lo com uma rápida pesquisa.Eles pode dar-lhe algumas ideias sobre onde melhorar o seu próprio algoritmo de

Se isso é para instalação ou distribuição, você já pensou em usar o SDK do Windows Installer?Ele tem a capacidade de patch arquivos binários.

http://msdn.microsoft.com/en-us/library/aa370578(VS.85).aspx

Este é um indicativos, mas o seguinte é para o rsync algoritmo que pode ser usado para criar o binário de patches.

http://rsync.samba.org/tech_report/tech_report.html

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top