Qual é a melhor maneira de compactar uma lista de strings semelhantes, mas não idênticas?

Question

Digamos que tenho várias strings bastante semelhantes, mas não absolutamente idênticas.

Eles podem diferir mais ou menos, mas a semelhança pode ser vista a olho nu.

Todos os comprimentos são iguais, cada um com 256 bytes.O número total de strings é menor que 2 ^ 16.

Qual seria o melhor método de compactação para esse caso?

ATUALIZAR (formato de dados):

Não posso compartilhar os dados, mas posso descrevê-los bem próximos da realidade:

Imagine a notação (como a linguagem LOGO) que é a sequência de comandos de algum dispositivo para mover e desenhar no plano.Como:

U12 - move up 12 steps
D64 - move down 64 steps
C78 - change drawing color to 78
P1  - pen down (start drawing)

e assim por diante.

Todo o vocabulário desta língua não excede o tamanho do alfabeto inglês.

A string então descreve uma imagem completa:"U12C6P1L74D74R74U74P0....".

Imagine agora a turma de dez mil crianças que foram orientadas a desenhar alguma imagem bem específica com a ajuda desta linguagem:como a bandeira do seu país.Obteremos 10K de strings, todas diferentes e iguais ao mesmo tempo.

Nossa tarefa é compactar todo o conjunto de strings da melhor maneira possível.

Minha suspeita aqui é que existe uma maneira de explorar essa semelhança e comprimento comum das cordas, enquanto Huffman, por exemplo.não o usarei explicitamente.

Answer 1

Você poderia nos dizer quais são os dados?Talvez como uma sequência de DNA?Como

AGCTGTGCGAGAGAGAGCGGTGGG...

GGCTGTGCGAGCGAGAGCGGTGGG...

CGCTGTGAGAGNGAGAGCGGTGGG...

NGCTGTGCGAGAGAGAGCGGTGGG...

GGCTGTGCGAGTGAGAGCGGTGGG...

... ...

?Talvez ou não.De qualquer forma, aqui estão dois níveis ou duas maneiras de pensar:

1. Codificação de Huffman:ref.Wikipédia por conta própria

2. Stringologia:ref. http://books.google.com.hk/books/about/Jewels_of_stringology.html?id=9NdohJXtIyYC

Acho que é fácil resolver o seu problema, mas difícil escolher o melhor caminho.Você pode projetar vários métodos para comparar usando http://en.wikipedia.org/wiki/Data_compression e mais ferramentas.

Answer 2

Como você tem uma largura fixa de 256 bytes e uma potência de 2, eu tentaria uma transformação de roda de toca ou um algoritmo de movimento para frente com esse tamanho ou talvez o dobro desse tamanho.Então você pode tentar um código huffman.Talvez você possa tentar uma curva de Hilbert em 256 bytes e depois um BWT e MFT?

Answer 3

"O número total de cordas é menor que 2^16." Este é um número pequeno e limitado, que facilita o seu trabalho:Por que você não mantém uma tabela de pesquisa (tabela hash) de todas as strings vistas anteriormente.Você pode então converter cada linha de 256 bytes em um índice de dois bytes nesta tabela de pesquisa.

Você então tem uma sequência de números inteiros de 16 bits.Esses números inteiros conterão padrões como "depois que a caneta caiu, há 90% de chance de o próximo comando começar a desenhar".Se os dados contiverem padrões como este, o PPM é sua escolha.7-zip possui uma implementação PPM de alta qualidade.Você pode escolhê-lo usando a GUI ou a linha cmd.