¿Reordenar datos (conjunto de cadenas) para optimizar la compresión?

12

¿Hay algún algoritmo para reordenar datos para optimizar la compresión? Entiendo que esto es específico para los datos y el algoritmo de compresión, pero ¿hay alguna palabra para este tema? ¿Dónde puedo encontrar investigación en esta área?

Específicamente, tengo una lista json de 1,5 millones de cadenas, y quiero reordenar las cadenas para que se optimice la compresión gzip (para HTTP). Ordenar las cadenas funciona bastante bien, pero realmente no sé si eso es óptimo.

optimization permutations Jayen
fuente
1
El reordenamiento óptimo de las cadenas para la compresión gzip (LZ77 con una pequeña ventana deslizante) suena como un problema NP-difícil. Probablemente pueda llegar a una reducción del problema de supercuerda común más corto.
Jouni Sirén
@ JouniSirén Creo que la subcadena común más larga es un mejor enfoque, ya que la supercadena común más corta me limita a tener la parte común consecutiva, ¿verdad? No me importa NP-hard siempre que sea manejable (como lleva un día en una máquina moderna).
Jayen

Respuestas:

6

Esta es una adición a la respuesta de Navin Goyal.

Dado que un archivo JSON puede considerarse como una estructura de datos de árbol, puede usar la transformación XBW para árboles, que es una extensión de la transformación Burrows-Wheeler para cadenas.

Hiroki Yanagisawa
fuente
1
Gracias por eso. Solo tengo una lista / matriz JSON, no ningún objeto JSON, por lo que no veo cómo se puede considerar como un árbol. Podría convertir las cadenas en un trie, pero luego no veo cómo esto se relaciona con la transformación XBW.
Jayen
4

Burrows - Wheeler transform es un conocido algoritmo de compresión que funciona reordenando los caracteres de la cadena que se van a comprimir.

Navin Goyal
fuente
1
Gracias por eso, pero no estoy seguro de cómo puedo usar esta información. Quiero reordenar las cadenas de la lista para comprimirlas, pero no me importa si puedo recuperar el orden original.
Jayen
1

Para mejorar la compresión gzip, desea que las cadenas "similares" estén cerca de la lista. Hay varias formas de definir tal similitud; permítanme describir una razonable que funciona bien en la práctica. Recuerde que el tamaño de bloque de gzip es 64K. Por lo tanto, sus datos se dividirán en bloques de 64K bytes y cada bloque se comprimirá de forma independiente. Para optimizar la compresión, sería necesario minimizar el número de k-mers distintos (subcadenas de tamaño k) en cada bloque. La motivación es que todas esas subcadenas serán reemplazadas por un identificador.

Si bien el problema anterior es difícil en teoría (es una variante de la partición de hipergrafía), existen algoritmos prácticos rápidos. Recomendaría la agrupación tipo LSH que se puede implementar con un solo paso sobre sus datos. Observe que la ordenación (alfabéticamente) es otra forma de "agrupar" cadenas similares juntas. Sin embargo, los algoritmos de agrupamiento especializados pueden funcionar mejor.

Una alternativa es usar zstd , que es (i) más rápido, (ii) obtiene relaciones de compresión más altas y (iii) no tiene limitaciones en el tamaño del bloque (y, por lo tanto, comprime las cadenas igualmente bien, independientemente del orden de entrada).

Sergey Pupyrev
fuente
0

Hace un tiempo vi un algoritmo que quizás puede ser útil. Utiliza un algoritmo de edición de distancia para calcular la distancia entre cada palabra. Por lo tanto, construye un gráfico cuyo peso de cada borde es esta distancia. Finalmente, obtiene una orden que elige una ruta que tiene la suma más baja de pesos. Tal vez pueda mejorar gzip.

Rafael Ribeiro
fuente
eso no suena manejable, pero si alguien lo intenta, publique un comentario con sus resultados
Jayen
Intentaré probarlo. Tengo curiosidad por este problema. Además de eso, ¿por qué crees que no es manejable?
Rafael Ribeiro
que yo sepa, la distancia de edición es O (nm), donde n y m son el número de letras en el par de cadenas y debe hacer esto para cada par de cadenas O (s ^ 2), entonces si n = m, eso es O (s ^ 2 * n ^ 2) que me suena intratable para 1.5 millones de cadenas.
Jayen
Oh, no me preocupaba tanto la complejidad porque pensaba que su problema es disminuir solo el tamaño binario. Entonces esta operación ocurrirá con más frecuencia, ¿verdad?
Rafael Ribeiro
Estaba buscando aquí y tal vez el costo de la distancia de edición se puede reducir usando autómatas levenshtein
Rafael Ribeiro