Reordenando dados (conjunto de cadeias) para otimizar a compactação?

12

Existem algoritmos para reordenar dados para otimizar a compactação? Entendo que isso seja específico dos dados e do algoritmo de compactação, mas existe uma palavra para este tópico? Onde posso encontrar pesquisas nessa área?

Especificamente, tenho uma lista json de 1,5 milhão de strings e quero reordená-las para que a compactação gzip (para HTTP) seja otimizada. Classificar as strings funciona muito bem, mas eu realmente não sei se isso é ótimo.

optimization permutations Jayen
fonte
1
Reordenar de maneira ideal as seqüências de caracteres para compactação gzip (LZ77 com uma pequena janela deslizante) parece um problema difícil de NP. Você provavelmente pode ter uma redução do menor problema comum de supercorda.
Jouni Sirén
@ JouniSirén Acho que a substring comum mais longa é uma abordagem melhor, já que a menor supercorda comum me limita a ter a parte comum consecutiva, certo? Eu não me importo com NP desde que seja tratável (como leva um dia para funcionar em uma máquina moderna).
Jayen

Respostas:

6

Esta é uma adição à resposta do Navin Goyal.

Como um arquivo JSON pode ser considerado como uma estrutura de dados em árvore, é possível usar a transformação XBW para árvores, que é uma extensão da transformação Burrows-Wheeler para cadeias.

Hiroki Yanagisawa
fonte
1
Obrigado por isso. Eu só tenho uma lista / matriz JSON, não objetos JSON, portanto não vejo como ela pode ser considerada uma árvore. Eu poderia converter as strings em um trie, mas não vejo como isso se relaciona com a transformação XBW.
Jayen
4

A conversão Burrows - Wheeler é um algoritmo de compactação conhecido que funciona reordenando os caracteres na sequência a ser compactada.

Navin Goyal
fonte
1
Obrigado por isso, mas não tenho certeza de como posso usar essas informações. Quero reordenar as seqüências de caracteres da lista a serem compactadas, mas não me importo se posso recuperar o pedido original.
Jayen
1

Para melhorar a compactação gzip, você deseja que as seqüências "semelhantes" sejam fechadas na lista. Existem várias maneiras de definir essa semelhança; deixe-me descrever um razoável que funcione bem na prática. Lembre-se de que o tamanho do bloco do gzip é de 64K. Assim, seus dados serão divididos em blocos de 64K bytes e cada bloco será compactado independentemente. Para otimizar a compactação, seria necessário minimizar o número de k-mers distintos (substrings de tamanho k) em cada bloco. A motivação é que todos esses substrings sejam substituídos por um identificador.

Embora o problema acima seja difícil em teoria (é uma variante do particionamento de hipergráficos), existem algoritmos práticos rápidos. Eu recomendaria o cluster do tipo LSH que pode ser implementado com uma única passagem nos seus dados. Observe que a classificação (alfabética) é outra maneira de "agrupar" cadeias semelhantes. No entanto, algoritmos de clustering especializados podem ter um desempenho melhor.

Uma alternativa é usar o zstd , que é (i) mais rápido, (ii) obtém taxas de compressão mais altas e (iii) não possui limitações no tamanho do bloco (e, assim, compacta as seqüências igualmente bem, independentemente da ordem de entrada).

Sergey Pupyrev
fonte
0

Eu vi um algoritmo há algum tempo atrás, que talvez possa ser útil. Ele usa um algoritmo de distância de edição para calcular a distância entre cada palavra. Assim, ele cria um gráfico em que cada peso da aresta é essa distância. Por fim, ele recebe uma ordem escolhendo um caminho com a menor soma de pesos. Talvez possa melhorar o gzip.

Rafael Ribeiro
fonte
que não soa tratável, mas se alguém faz experimentá-lo, por favor postar um comentário com seus resultados
Jayen
Vou tentar testá-lo. Estou curioso sobre este problema. Além disso, por que você acha que não é tratável?
Rafael Ribeiro
Até onde eu sei, a distância de edição é O (nm), onde n e m são o número de letras no par de strings e você deve fazer isso para cada par de strings O (s ^ 2), portanto, se n = m, é O (s ^ 2 * n ^ 2) que me parece intratável por 1,5 milhão de strings.
Jayen
Ah, não me preocupei muito com a complexidade, porque pensei que seu problema é diminuir apenas o tamanho binário. Então essa operação ocorrerá com mais frequência, certo?
Rafael Ribeiro
Eu estava procurando aqui e talvez custo editdistance pode ser reduzida usando levenshtein autômatos
Rafael Ribeiro