Metodos de compresion para pocos datos

[Darukur]

Hola gente, queria abusar un poco de su predisposicion a ayudar y de su conocimiento...
Estuve analizando los metodos de compresion, entre ellos:

*La compresion Huffman que optimiza dandole menos longitud de palabra al dato mas frecuente y mas longitud de palabra al menos frecuente.
*La compresion LZ77 que optimiza realizando diccionarios.
*RLE
*Otros

Todos estan pensados para grandes cantidades de datos, como el Huffman, que requiere guardar en la cabecera la tabla que da la relacion inequivoca con el arbol Huffman o el LZ77 que necesita realizar el diccionario.

No he visto nada para realizar compresion a cantidades de datos que rondan los 200 bytes maximo, ya que para transmisiones radiales en VHF como se utiliza 1200 / 2400 baudios, 200 bytes representan 2 segundos y puede significar que el dato no llegue por ruidos interferentes.

Si saben de algun metodo les agradecere. 

Agrego unos link interesantes, hablan de compresion de pocos datos:
http://www.rdrop.com/~cary/html/data_compression.html
http://ciir.cs.umass.edu/cmpsci646/Slides/ir07%20compression.pdf

[Zaphyrus]

Darukur:

Veo que estas a full con la compresión y de pasada investigando para el reproductor de MP3. Cuando me desocupe de los "urgentes" me pongo a investigar así te doy una mano.

Salutes

[Darukur]

Nadie tiene una sugerencia o alguna info que aportar? 

[aitopes]

Contanos un poco en que consisten los datos,por ahi surge alguna idea.

Por ejemplo: Si tus datos son 15005, 15000, 15008, 15003, 15000  , etc, es sencillo transitir al comienzo "15000" y luego la diferencia con ese numero, en lugar de "15005, 15000, 15008, 15003, 15000" transmitirias "15000,5,0,8,3,0" que es mucho mas compacto....

Pero ese tipo de metodos "caseros" dependen del tipo de datos, por eso si amplias un poco el post, por ahi a alguien se le ocurre algo mas puntual.

Saludos!

[Darukur]

Estoy buscando un metodo de compresion generalista (que no dependa del tipo de dato) para cantidades de datos muy bajos (menos de 200 bytes).
Aitopes el metodo que comentas seria parecido al metodo de compresion IMA de audio, que gasta solo 4 bits cada 16 bits, que mira la diferencia en valor con respecto al anterior.
Estuve analizando alterar metodo Huffman en vez de trabajar en palabras de 8 bits que trabaje con palabras de 4 bits, asi solo transmito 16 bytes al principio con la tabla para los 16 diferentes valores.
De aca se analiza la entropia en 16 elementos solamente.

[manwenwe]

Hola, la compresión a la que se refiere aitopes se llama codificacción relativa. El problema que puedes tener con esta codificación es que sólo es eficiente en sucesiones de datos que tengan poca diferncia entre 2 datos consecutivos; en tu caso si quieres enviar bytes creo que que no te va a valer la pena pues el máximo valor a enviar y la distancia máxima coinciden : 255. Además deberias implementar algún método para representar numeros negativos, como por ejemplo complemento a 2 con lo que perderías como mínimo un bit por byte.

En cuanto a lo que comentas sobre Huffman... en realidad la eficiencia de este algorítmo(como la del resto de códigos no adaptativos: Huffman modificado, Shannon-Fano, Comma,etc) depende más del número de simbolos distintos que de la cantidad de información a enviar... además tienes el inconveniente de que debes saber de antemano las probabilidades de todos los símbolos...

Después tienes los códigos adaptativos, donde no necesitas conocer las probabilidades de los mensajes de la fuente pues la tabla de codificación cambia en función de la evolución de la fuente. El funcionamiento es más o menos el siguiente: cada mensaje tiene asociado un contador que se incrementa con cada emisión del mensaje; cada instante de tiempo prefijado se calculan las probabilidades y cada cierto numero de mensajes se reasignan las palabras código en función de las nuevas probabilidades. El único problemas es que el receptor debe hacer lo mismo, con lo que RX y TX deben estar coordinados....

Por último(de los que yo conozco, claro  ) los algoritmos de compresión orientada a caracter. Son menos eficientes que los anteriores pero están más implantados. En estos no se sustituyen todos los caracteres por por palabras código sino cierta parte del texto; también se utilizan caracteres especiales que indican inicio/fin/tipo de compresión, etc. Estos codigos tienen el problema de que es posible que la fuente no tenga caracteres especiales(algo que creo que puede ocurrir en tu caso, a no ser que estes dipuesto a sacrificar alguna de las 256 representaciones que puedes obtener con un byte o de la 16 de un nibble..); pero se puede solucionar utilizando una técnica que se llama "bordado e insercción": eliges un caracter poco frecuente como indicador de compresión, cuando aparece este una vez en el texto se interpreta como indicador de inicio de compresión y si aparece realmente se expresa de forma duplicada para que no se confunda con el indicador(caracter stuffing). Bueno algunos de estos códigos son(supongo que los encontras en google): "supresión de nulos", "mapeo de bits", "longitud de recorrido", "empaquetado en medios octetos", "sustitución diatómica", "supresión de patrones", "MNP clase 5", "MNP clase 7"....

Bueno resumiendo, si tu intención es trabajar con bytes en vez de con cadenas más largas de bits, te recomiendo estos último pues no son demasiado complejos de implementar y no te tendrás que comer la cabeza ni con calcular probabilidades ni con sincronizar RX y TX(eso sí perderas algo de eficiencia en la compresión). Si tienes alguna duda al respecto.... a mandar. Saludos a todos!

[Darukur]

manwenwe, mientras lo estoy leyendo te estoy agradeciendo.....
.
.
Listo, como charlamos, los metodos LZ77 o Huffman no estan pensados para poca cantidad de datos...
Estudiare los metodos:
-supresión de nulos
-mapeo de bits
-longitud de recorrido
-empaquetado en medios octetos
-sustitución diatómica
-supresión de patrones
-MNP clase 5
MNP clase 7

Con respecto a la compresion con caracter de inicio y fin (perdiendo un caracter) creo que lo utiliza el RLE (run lenght enconding) que lo implemente y tiene el problema nombrado por vos con lo que tenes que hacer un simbolo especial de mas longitud de palabra que el resto.

Estuve viendo lo que comentabas compresion adaptativa y me podria servir tambien ya que no se transmite la tabla al principio y ademas no se debe leer el mensaje dos veces (se hace al vuelo).

Repito, gracias manwenwe
EOF.......Ruido

[manwenwe]

Hola, el metodo RLE que mencionas es justamente el de longitud de recorrido... He estado mirando un poco como funciona el LZ77 y es en parte parecido a los MNP clase5 y clase 7 que te comenté; creo que hay unas 10 versiones del MNP y si no recuerdo mal todas están especificadas en el estandar CCITT v.42, además son híbrido entre codificación orientada a caracter y adaptativa...

En realidad todos estos métodos que te he comentado se utilizan para compresión de datos orientada a transmisión digital(p.e.: los MNP se utilizan en modems) y realmente, creo que no los has especificado, no se con que motivos quieres realizar la compresión. Si es para almacenamiento masivo de datos la verdad es que no se si te puedo ayudar porque no se demasiado del funcionamieno de estos. Lo único que tengo claro es que al menos los de video y audio están basados en perdida de calidad; en cuanto a los tipos zip, rar, arj, etc. ¿?¿?¿?... en fin creo que todos(video, datos y audio) son , en parte, "hijos" del Huffman(creo que este hombre debió ser en su época el Von Neumman de la compresión )...

Creo que si especificas más el motivo de la compresión te podremos ayudar todos mejor, puesto que la eficiencia de los métodos de compresión tambien depende del nivel físico y del origen de la información. Si intentas comprimir orientado a transmisión digital, banda base o radiofrecuencia puede que pueda ayudarte... Saludos

[Darukur]

Bueno, hare un esfuerzo de explicarme claramente....
Trabajo mucho con la transmision digital de datos por radio en VHF-UHF en velocidades que no superan los 2400 baudios (en realidad usamos 1200 baudios ya que es muy dependiente de las radios).
Como te daras cuenta la compresion es importante porque significa tiempo (y mucho) donde una trama puede llegar a tener 2 segundos en el aire y como los sistemas se instalan en coches los ruidos del mismo complican las transmisiones y mas si son muchos datos.
Se producen muchos reenvios y se aumenta el uso del canal, ademas con las radios esta el problema de los tiempos de establecimiento de la transmision (de 150 a 300ms con lo que ya se tiene perdido un buen tiempo del canal sin dato util)
Otra cosa es que el canal de aire esta SIEMPRE utilizado, hay una central que encuesta a todos los moviles (vuelta de encuesta) y a medida que aumenta la cantidad de moviles se aumenta dicha vuelta (150 moviles = 2 minutos)
Por eso buscaba la manera de aumentar la efectividad del canal con un poco de compresion que no sea muy "cableada" por uno mismo.
Me parece que me decidi por el Huffman adaptativo que no requiere el envio de la tabla, ambos lados van armandola.
.
Y si como comentas estuve leyendo un monton de "Don Huffman" y la verdad aplaudo a los tipos como el ya que sacan cosas de la nada antes de que nadie se le hubiese ocurrido un uso o que haya al menos un sistema que lo pueda usar (imaginate las maquinas de esa epoca).
En fin me saco el sombrero......

[manwenwe]

Hola Darukur... creo que ahora vemos todos las cosas más claras jejee... De lo que me comentas extraigo algunas conclusiones y tambien tengo alguna duda... Veo que trabajas con modulación paso banda... hay algo que no acabo de entender...¿que quieres decir con que la señal(las tramas en rafagas...) permanece 2 segundos en el aire? ¿te refieres pasando por por estaciones base, repetidores, etc...(incluyendo modulaciones/demodulaciones)? Es porque sino esto que dices no tiene mucho sentido porque en 2 seg. una señal de radio en propagación por espacio libre llega a la Luna...

Realmente el Huffman adaptativo es una buena opción aunque creo que el problema de la eficiencia de transmisión podria sulicionarse de mejor forma adaptando  el sistema a las características que necesitas... utilizando filtros en los transmisores de los coches, multiplexación en las estaciones base, una codificación de canal más resistente al ruido, etc. Aunque por lo que comentas supongo que tu trabajo es montar todo el sistema no diseñar los componentes por lo que no tienes otra que trabajar con los datos e intentar reducir su tamaño...

Bueno espero que mis comentarios te hayan servido de algo... por como veo que es tu trabajo seguro que sabes solucionar tu problema mucho mejor que lo haría yo pues lo que se es de mis estudios de telecomunicaciones, apenas tengo experiencia montando sistemas de radiocomunicaciones.

En fin, suerte y al toro... jejeje saludos!

[Darukur]

Lo de los 2 segundos es asi:
A 1200 baudios un bit dura aproximadamente 0.9 msegundos, multiplicado por 10 para un byte clasico de USART (START+DATO+STOP) hacen 9 mseg por byte.
Para transmitir 200 bytes de datos se requieren 1,8 segundos y como explique la radio tiene un tiempo de establecimiento (PTT) de aprox 200mSeg -> 2 segundos.
Tratar de transmitir una rafaga de mas de 2 segundos es directamente desperdiciar el canal ya que cualquier ruido (gausiano, impulsivo, etc etc etc ect ) se mete en el medio de la trama y arruina el paquete.
Esto obviamente no pensando en un solo equipo sino en un canal compartido por 200 equipos con diferente nro de identificacion, es por esto que cada byte cuenta 

No es modulacion de BLU es FM en VHF, los modems que usamos son norma V.23 (FSK 2 niveles).
Los equipos son estandarizados de VHF en FM (Motorola, Vertex, YAESU, etc), el tema de la velocidad es directamente un problema del equipo de radio (se ajusta todo para el del peor caso) ya que nosotros no ponemos dichos equipos, los pone el cliente.

Repito, gracias por la ayuda y el tiempo.

[Darukur]

Una consulta manwenwe...
Esuve viendo Huffman adaptativo y aunque entiendo como se realiza la compresion, se me escapa como realizarlo en C para un PIC, estoy haciendo estructuras y manejo de punteros a dichas estructuras pero se me complica...
En esta pag hay un ejemplo con un Applet de Java muy bueno http://www.cs.sfu.ca/cs/CC/365/li/squeeze/
Si tenes algo se agradece.

[manwenwe]

Hola Darukur, yo lo que he visto sobre este código es teoría, no lo he implementado nunca en lenguaje de programación(sólo he hecho los tipicos arbolitos para codificar/decodificar palabras... ). Lo unico que acabo de echar un vistazo por google y... si buscas en castellano parece que no hay nada pero en inglés si... intenta buscar por:     

 "adaptive huffman" " code in c"

...he visto varias entradas interesantes pero la que me parece que tiene mejor pinta es esta:

http://www.xcf.berkeley.edu/~ali/K0D/Algorithms/huff/

Lo bueno es que parece que está en ANSI C, lo no tan bueno es que por lo extenso del código parece que necesitaras un PIC con bastante memoria de programa... no creo que te valga con menos de 16kb pues incluye unas cuantas librerias...

Bueno espero que te valga de algo saludos y animo con tu proyecto!