¿Cuál es la mejor manera de comprimir una lista de cadenas similares pero no idénticas?

Question

Di, tengo una serie de cuerdas que son bastante similares pero no son absolutamente idénticas.

Pueden diferir más o menos, pero el ojo desnudo puede verse.

Todas las longitudes son iguales, cada una es 256 bytes. El número total de cadenas es inferior a 2 ^ 16.

¿Cuál sería el mejor método de compresión para tal caso?

Actualización ( Formato de datos ):

No puedo compartir los datos, pero puedo describirlo bastante cerca de la realidad:

Imagina la notación (como lenguaje logo) que es la secuencia de comandos para un dispositivo para moverse y dibujar en plano. Tales como:

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

y así sucesivamente.

Todo el vocabulario de este idioma no excede el tamaño del alfabeto inglés.

La cadena luego describe una imagen completa: "u12c6p1l74d74r74u74p0 ...".

Imagine ahora la clase de diez mil niños a quienes se les dijo que dibujara una imagen muy específica con la ayuda de este idioma: como la bandera de su país. Obtendremos 10k de cuerdas que son diferentes y todas iguales al mismo tiempo.

Nuestra tarea es comprimir todo el montón de cuerdas lo mejor posible.

Mi sospecha aquí es que hay una manera de explotar esta similitud y la longitud común de las cuerdas, mientras que, Huffman, por ejemplo. No lo usará explícitamente.

Answer 1

¿Podrías decirnos cuáles son los datos?Tal vez como una secuencia de ADN?Como

agctgtgcgagagagagaggggggggg ...

ggctgtgcgggcgagagggggggg ...

cgctgtgagaggnggagagggggggg ...

ngctgtgcggagagagagggggggg ...

ggctgtgcgggtgagagggggggg ...

... ...

? Tal vez o no.De todos modos, aquí hay dos niveles o dos formas de pensar:

1. Huffman Coding: Ref.Wikipedia por usted mismo

2. stringology: ref. http://books.google.com.hk/books/about/Jowels_of_stringology.html?id=9NDOHJXTIYYYC

   Creo que es fácil resolver su problema, pero difícil de elegir la mejor manera.Puede diseñar varios métodos para comparar mediante el uso de http://en.wikipedia.org/wiki/data_compripsion y más herramientas.

Answer 2

Dado que tiene un ancho fijo de 256 bytes y es una potencia de 2, probaría una transformación de madriguera o un algoritmo de movimiento a frente con ese tamaño o tal vez el doble de ese tamaño.Entonces puedes probar un código Huffman.Tal vez usted puede probar una curva de Hilbert en 256 bytes y luego un BWT y MFT?

Answer 3

"El número total de cadenas es inferior a 2 ^ 16".Este es un número pequeño, limitado, lo que hace que su trabajo sea muy fácil: ¿por qué no mantiene una tabla de búsqueda (tabla hash) de todas las cadenas previamente vista?Luego puede convertir cada línea de 256 bytes en un índice de dos bytes en esta tabla de búsqueda.

Tienes una secuencia de enteros de 16 bits.Estos enteros contengan patrones como "Después de que la pluma se apagó, hay una probabilidad del 90% de que el siguiente comando es comenzar a dibujar".Si los datos contienen patrones como este, PPM es su elección.7-ZIP tiene una implementación de PPM de alta calidad.Puede elegirlo usando la línea GUI o CMD.