Algoritmo de compactação sem perdas de Broo e codificação delta, comparação com o Xdelta3. Desenvolvimento de projetos residenciais

Fico feliz em recebê-lo. Quase um ano se passou desde que o último artigo foi publicado e estamos prontos para contar o que aconteceu com o próprio algoritmo e como a codificação delta está envolvida.

Entrada

Após o lançamento do artigo sobre melhorias no algoritmo Broo, enfrentamos um obstáculo na melhoria do nível de compactação e desempenho, ou seja, era impossível melhorar o nível de compactação sem afetar a velocidade de descompressão e vice-versa. Farei uma reserva imediatamente, as melhorias foram feitas sem prejuízo de outras características do algoritmo, mas essas alterações são insignificantes; escreveremos sobre essas alterações posteriormente. Então, depois, pensamos sobre onde podemos aplicar nossa experiência e conhecimento acumulados em uma direção semelhante. E a escolha caiu codificação delta .

O que é codificação delta?

Codificação delta ( codificação delta da Eng. Delta) - uma maneira de representar dados na forma da diferença ( delta ) entre os dados seriais em vez dos próprios dados.

Na prática, se os algoritmos de compactação permitirem reduzir o tamanho do arquivo e armazená-lo ou encaminhá-lo sem nenhuma dependência de outros arquivos, os algoritmos de codificação delta permitem criar um patch (diferença) de tamanho menor com base em dois arquivos (conjunto de dados) e aplicar o patch ao arquivo ( conjunto de dados) 1 - obtenha um arquivo (conjunto de dados) 2 .

O aplicativo mais comum para codificação delta é atualizar aplicativos em seus telefones e PCs. Em vez de baixar o aplicativo completamente e substituir os arquivos, um patch muito menor é criado (dependendo do número de alterações), que permite baixar a atualização muito mais rapidamente, e a velocidade de aplicar o patch afeta diretamente a velocidade de atualização do próprio aplicativo.

Se você souber onde mais a codificação delta é usada, escreva nos comentários.

Sobre mudanças no algoritmo Broo

Como dissemos, existem alguns deles:

• Adicionado suporte para arquivos de tamanho 2 ^ 64 para x64 e 2 ^ 32 para x32.
• Taxa de compressão aprimorada.

Essas mudanças ainda estão no estágio de experimentação e depuração. O principal problema - depois de adicionar suporte para arquivos grandes, a velocidade de descompressão caiu 20%, o que é inaceitável para nós. Por isso, ainda estamos procurando uma solução.

Abaixo, fornecemos apenas uma tabela de comparações da versão antiga do algoritmo, a experimental e alguns níveis de zstd. O arquivo xml do artigo anterior .

Processador: Intel i7-7700HQ

Memória: DDR4-2400

Como muitos algoritmos, a velocidade depende do processador, como podemos ver na tabela, a velocidade de descompressão é 1,5 vezes mais rápida que a do primeiro nível zstd, no processador Intel i7-7700HQ. Enquanto no antigo Intel i3-550, a velocidade de descompressão era aproximadamente igual à velocidade de descompressão zstd, você pode ver as tabelas de comparação aqui .

Isso sugere que você pode realizar uma integração mais rígida com processadores individuais. Depende das especificidades da tarefa.

Codificação Delta e Broo

Como você deve ter adivinhado, desenvolvemos nosso próprio algoritmo de codificação delta e denominamos DBroo (Delta Broo).

Principais características e características:

• Suporte para tamanhos de arquivo 2 ^ 64 para x64 e 2 ^ 32 para x32.
• Trabalhe com dados binários.
• É permitida a modificação parcial do arquivo de referência ao qual o patch será aplicado.

Existem soluções prontas, como diff, bsdiff, xdelta e outras. O objetivo era encontrar o melhor (além de acessível) nessa direção e competir com ele. O Xdelta3 acabou por ser o principal concorrente de uma maneira puramente experimental. Proporciona boa compactação e uma velocidade de aplicação de patches bastante rápida. O Xdelta3 também é usado para atualizações do CyanogenMod (agora LineageOS ).

Agora, vejamos a tabela de comparação do DBroo e do Xdelta3. Como arquivo de referência, "xml" é usado e, como um novo arquivo, o mesmo, mas modificado aleatoriamente.

PS

O desenvolvimento é dado apenas aos produtos que têm demanda no mercado. Portanto, agradecemos seus comentários. Também criamos um canal de telegrama .

Obrigada