Algoritmo compresion numerica

EnZo #1 Ene '12

Hola Ingenieros informaticos. Me gustaría saber si conoceis algun algoritmo para comprimir largas cadenas de numeros. O si creeis que es posible, porque yo ya creo que no lo es.

Se que hay muchos algoritmos de compresion pero casi todos son en binario. Lo que yo necesito es un algoritmo para que funcione en javascript, ya que este no trabaja con binarios. He estado mirando mucho por google pero no encuentro nada, esto es lo mejor que he encontrado: http://stackoverflow.com/questions/879069/compression-algorithms-for-numbers-only pero no entiendo bien las soluciones que presentan.

HeXaN #2 Ene '12

Mételos en un .rar o un .zip

Deoxys #3 Ene '12

Puedes pasar esos números a binario y luego comprimir la cadena.

Yo lo haría así, coges los números (Decimales supongo), los pasas a binario y luego te limitas a poner los unos y ceros que hay, por ejemplo, en hexadecimal.

Por ejemplo,

54864654654465467548905419811232130498654067213211231 (Puesto a huevo aporreando el teclado)

Lo pasas a binario

100101111000010111110001011110101010100111000111101011010100 (Puesto también de forma aleatoria)

Y luego inicias un contador para cada secuencia de 1 y 0, indicando por qué número se empieza. En el caso anterior,

1|1211441153114111111112334111211112

También puedes reducir la cadena anterior indicando las cadenas de '1010101' '11001100' o similares que se repiten. Sólo tienes que indicar por qué número empiezan y cuánto duran. Por ejemplo, [Nx (N=cantidad de bits iguales consecutivos, x=longitud)

1211441153114[1823341112[142

spoiler

EnZo #4 Ene '12

Gracias Deoxys. Se ve que no lo he dejado claro, pero me referia comprimir un numero de decimal a decimal.

Es decir:
54864654654465467548905419811232130498654067213211231

a:
54213486465465446546314890541981123123

Es que creo que no es posible tal cosa.

1 respuesta

BLZKZ #5 Ene '12

#4 y que más te da que uses por medio binarios si eres tú quien va a tratar por medio con ellos. quiero decir, tu te haces tu funcion "comprimir" y tu funcion "descomprimir" y las llamas según lo necesites y te da igual que js no trate con binario :/

1

EnZo #6 Ene '12

Por que es algo que no existe y lo que tu dices si. Sin ir mas lejos la familia LZ http://es.wikipedia.org/wiki/LZ77

1 respuesta

BLZKZ #7 Ene '12

#6 el problema es que la mayoria de algoritmos de este tipo guardan patrones siguendo un patrón (aunque suene redundante), que me imagino que ya lo sabes. Encontrar dichos patrones es mucho más sencillo cuando solo tienes 2 valores posibles, tu lo quieres para 10, que además de tener una complejidad temporal mucho mayor, obtendrás una complejidad espacial más grande.

Si no existen posiblemente es porque no son convenientes usarlos, o hay opciones mucho más optimas :/

Pero vamos, esto se escapa un poco de mis conocimientos en el campo

EnZo #8 Ene '12

Si, entiendo que para comprimir en el dia a dia no es optimo y que si no hay nada hecho es porque no merece la pena desarrollarlo, sabiendo que en otro caso puedes usar todos los caracteres y en binario o hex.

Pero te explico por que viene toda esta rallada y así lo entenderás mejor (Sigue siendo una gilipollez que no tiene futuro).

Cuando llamas a tu operador movil un contestador te pregunta sobre que quieres que te atiendan, entonces te ofrece opciones y te va encauzando hacia un operador personal o hacia otros resultados (todos los hemos sufrido xD). Cuando tu pulsas una tecla del teclado es donde le estas pasando informacion al operador para luego gestionarla.

Ahora bien, teniendo en cuenta que tu operador puede recibir esas teclas que pulsas y que puede gestionarlas. Entonces mi pregunta es. Se podria mejorar esa tarea con instrucciones mas directas?

Por ejemplo: ir a soporte directamente.

Entonces es aqui donde entra la parte tecnica que seria algo asi:

Pasamos la palabra "soporte" a ascii decimal:
115 111 112 111 114 116 101
115111112111114116101

Tenemos esa secuencia de numeros que se puede introducir por teclado. Y cuando llamamos al teleoperador conforme suena la señal para introducir la secuencia de numeros
introducimos esa secuencia.

De ahí que quiera comprimir un numero a otro mas pequeño, para ahorrar introduccion de digitos.
Logicamente toda esta tarea la haria un software instalado en el movil y otro en el operador.

Sabiendo todo eso tambien estaria la almohadilla y el asterisco como caracteres auxiliares para hacer la compresion.

Pero ya te digo, creo que es imposible comprimir esos numeros.

En cualquier caso gracias por la ayuda

1 respuesta

Tunnecino #9 Ene '12

Y, esto te lo digo desde la iluminación que me ha dado leer tu texto, si por ejemplo Hola es:

446665552 haces, 4263532, o soporte: 746376373832.

No se, supongo que de ahí se podría comprimir un poco más... pero con solo números enteros...

EnZo #10 Ene '12

Y como lo descomprimes si no aplicas banderas?

1 respuesta

Tunnecino #11 Ene '12

#10 Pues, como lo que estamos haciendo es poner las veces que se repite, y no cada una, teniendo en cuenta que no vamos a usar caracteres especiales como tildes y tal, y partiendo del ejemplo simple que te he puesto (que técnico todo xD):

Dividimos la cadena en parejas de 2, siendo el primer número la tecla, y el segundo las veces que se repite. En el ejemplo la he liado por que en el caso de que no se repitiese tendríamos que poner un 0, si no se va al traste todo.

1 respuesta

XenomorpH #12 Ene '12

#11 pero eso tiene doble filo, con 123456 se te queda 102030405060... que es el doble de largo.. no?

2 respuestas

Tunnecino #13 Ene '12

#12 Ya... a no ser que el que recibe o envíe lo separe por rangos de tiempo, como el propio teclado que tienes x segundos para continuar con la misma o se resetea, en ese caso sería 1 2 3 4 5 6.

Igneus #14 Ene '12

No le veo ningun sentido (tampoco entiendo mucho del tema). Seria mucho mas lento trabajar en decimal porque la electronica de los computadores esta hecha para trabajar en binario.

1 respuesta

EnZo #15 Ene '12

#14 En #8 explico un poco el porqué, aunque sea una paja mental

1 respuesta

catalon #16 Ene '12 Inocente

cojes el numero, le restas diecmil <-- compresion
cojes el numero, le sumas diecmil <-- descompresion

TOMA!!

Igneus #17 Ene '12

#15 si, precisamente por #8 lo digo

El que tu pulses una tecla es una abstraccion de lo verdaderamente importante, que es el codigo binario. El movil (que no se como funciona xD) envia señales en codigo binario, ponte que cuando tu pulsas 7 el movil envia:

1010100001110101010111

donde el 0111 final correspondera a la tecla/s pulsadas y el resto dependera del protocolo del pais, la operadora o lo que sea. Entonces el operador tendra un circuito X, que en funcion del codigo k tu le mandes y el estado en el que estes, te envia a un estado u otro.

Si el contestador tiene 3 opciones, tiene 3 estados, que pueden ser:
00 - Escuchar mensajes
01 - Borrar mensajes
10 - Salir

y eso se traduce en que te va a pedir pulsar el 1 para escuchar mensajes, el 2 para borrar y el 3 para salir, esa es la minima codificacion que puedes hacer.

1 respuesta

EnZo #18 Ene '12

#17 No soy teleco pero hasta donde yo se, es que cuando estableces una conexion telefonica el operador es capaz de detectar las teclas que tu pulsas gracias al sonido que emiten. Interpreta ese sonido y sabe a que numero le has pulsado. No hay ningun tipo de comunicacion binaria ahí.

Igneus #19 Ene '12

Vale, sonido o lo que sea, esque tampoco es el tema xDD (ni se como funciona). Habra X componente de por medio que te transforme la señal binaria a otra señal, otro componente que la envie y algo a la inversa para el operador, pero el circuito de control que es el que te dice pulse tal, pulse cual y en funcion de esto hace aquello o lo otro, trabaja en binario que es lo importante.

EnZo #20 Ene '12

Que componente? No existe tal componente que yo sepa.

Piensalo de forma real, cuando llamas a Orange y te sale el contestador para las diferentes opciones tienes que pulsar una tecla. Esa tecla tienes que pulsarla si o si, porque es el unico metodo de comunicacion en ese momento (junto con el de la voz que es lo mismo).

En ese momento tienes que enviar el sonido para decir que has pulsado X tecla. El sonido lo genera tu telefono. No pienses que al pulsar el 1 se trasmiten datos binarios...

LOc0 #21 Ene '12

¿ http://jszip.stuartk.co.uk/ ?

Salu2

1 respuesta

Igneus #22 Ene '12

No pienso que se transmite nada, a mi la parte de transmision de datos me da igual como se haga, no es mi campo, de eso se encargara otra persona el teleco o quien sea. Se hará por tono o como sea esque me da igual xD

#23 pues explicate xD

2 respuestas

EnZo #23 Ene '12

#21 Que guapada no? Y no tira servidor en ningun momento O_o
No sirve para el problema pero se agradece, a marcadores vá xD

#22 Como te va a dar igual la parte de trasmision de datos si es el quid xD
Es que creo que no lo has entendido.

2 respuestas

elkaoD #24 Ene '12

#23 creo que eres tú quien no le entiende a él. Qué más te dará la representación numérica si puedes cambiarla a gusto del consumidor cuando te de la gana. La representación no es más que eso: representación. Un número no vale nada de por sí.

Tu problema no es de compresión sino de representación. Tú lo que quieres es un compresor que devuelva el resultado en base 10. Comprime, pasa tu cadena comprimida (en la base que sea, da igual binario, decimal... da lo mismo) a base 10 y ya tienes tu bonito número comprimido y tecleable en el móvil.

Incluso si usas * y # puedes usar base 12 y comprime un poquito más.

Aún así, se pierde mucha compresión en el cambio de base (si vienes de "bytes"), así que no sé si te resultará rentable. Haz pruebas.

De todas formas creo que estás dando palos de ciego. Comprimir cadenas TAN pequeñas es imposible. Normalmente los compresor se aprovechan de patrones porque, aún añadiéndole datos de control, gracias a la repetición de patrones acabas ahorrando espacio. Este no es tu caso: tus cadenas apenas van a tener patrones repetidos, por lo que la compresión NO es el camino a seguir. Siempre vas a tener el problema de cadenas que "comprimen" a mayor tamaño como comentas en #12. Es el precio a pagar por comprimir cosas sin apenas repeticiones: no sólo no comprimen sino que aumentan de tamaño por los caracteres de control.

Lo máximo que creo puedes hacer es, si la entrada al "compresor" son sólo números, coger tu cadena en base 10 y pasarla a base 12 para aprovechar * y # también como caracteres de salida.

EDIT:

En Java:

public static String compress(long integer) {
    return Long.toString(integer, 12)
            .replace('a', '*')
            .replace('b', '#');
}

compress(1234567890) = "2*5555016"; // Ahorro de un carácter

El ahorro medio es de un carácter. No vas a sacar mucho más si no juegas con duración de las pulsaciones o algo de eso.

EDIT2:
Huffman coding es otro algoritmo que te podría interesar, pero estamos en las mismas: la mayoría de algoritmos de compresión se aprovechan de "casos específicos". Este sólo te conviene si hay diferencias de probabilidad de aparición de los símbolos.

EnZo #25 Ene '12

#23 La representacion es el numero que necesito para poder teclear en el telefono. "ya tienes tu bonito número comprimido y tecleable en el móvil"
Al final necesitas el numero en decimal o en base 12 como mucho para poder teclearlo verdad? Da igual que el algoritmo luego haga los procedimientos que tenga que hacer para comprimir y descomprimir. Cuando lo comprimes debe devolverte un numero decimal, ni mas ni menos. Y cuando quieras descomprimirlo tendras que pasarle como parametro un decimal de igual manera...

Luego ya viene el problema del algoritmo de compresion que estas en lo cierto. Al ser cadenas tan pequeñas no tendras manera de conseguir reducir el tamaño encontrando patrones.

1 respuesta

elkaoD #26 Ene '12

#25 pues sí, pero #22 creo que se refería a que pensaras menos en la representación externa, dado que al fin y al cabo el paso a representación "tecleable" se puede hacer en la etapa final (la salida del compresor) y mientras tanto trabajar para comprimir sobre la codificación en binario.

Otra opción que se me ha ocurrido, algo chorra pero podría funcionar. * y # podrían servir como caracteres de control de repetición. * = el número está repetido 3 veces, # = 4 veces, ausencia de carácter = no se repite

123412244441244444444 pasaría a ser 12341224#24##

Como ves, cuando la repetición es 2 o menos no añade ningún carácter, mientras que 3 o 4 repeticiones las comprime a 2 caracteres.

3 -> 3
33 -> 33
333 -> 3*
3333 -> 3#
33333 -> 3#3
333333 -> 3#33 o mejor 3**
3333333 -> 33 o mejor 3#*
33333333 -> 3##
333333333 -> 3##3 o 3*

¡OJO! No confundir con representar en lugar de * y # como caracteres de control de tamaño, sólo caracteres de repetición. * = repetir 2 veces el último leído, # = repetir 3 veces:

3 -> 3
33 -> 33
333 -> 3*
3333 -> 3#
33333 -> 3** o 3#3 (como el anterior)
333333 -> 3#*
3333333 -> 3##
33333333 -> 3##3 <- ESTA CADENA ES MÁS LARGA QUE CON LA CODIFICACIÓN ANTERIOR
333333333 -> 3##*

De hecho, podrías darte cuenta de que combinaciones como #* y # dan completamente igual, por lo que podrías asignarles significados diferentes: # = 7 veces, *# = cualquier otra combinación. Si la combinación por la que sustuyes *# es de más de 2 caracteres (por ejemplo *# = 9 repeticiones, sustituyendo a ***) ahorras más espacio. La manera de trabajar se complica de todas formas, tendrías problemas parecidos a cuando tienes que tratar con números romanos, pero si haces BIEN el algoritmo comprimirá bastante mejor.

¡No sé cómo se me ha ocurrido el método pero es COJONUDO! Creo que es tu solución.

1 respuesta

Kiroushi #27 Ene '12

¿En serio estás planteando que en vez de recordar un número de asistencia telefónica (digamos, 1400)... tengas que recordar números que resultan de una "transcripción-compresión" de ascii (además, una palabra española) a decimal?

Tío, búscate otro proyecto porque esto no tiene ni pies ni cabeza.

General: 1400
Soporte: 1401 (Por decir algo)
Bajas: 1410 (Por decir algo)

De nada.

2 respuestas

Tunnecino #28 Ene '12

#27 Yo creo que mas que eso, es cuando te piden, Pulsa X para Soporte Técnico.

1 respuesta

EnZo #29 Ene '12

#26 No está nada mal elkaoD puede ser una buena solucion. Me pregunto si sera mas eficiente pasarlo a binario que a decimal ya que hay mas repeticiones y tu algoritmo puede ser mas eficiente, tendria que probar, aunque no creo...

3 -> 3
33 -> 33
333 -> 3#
3333 -> 33
33333 -> 34
333333 -> 35
3333333 -> 36
33333333 -> 37
333333333 -> 38

El problema de esta opcion es que en la linea 3333 -> 3*3 tengo un caracter mas que tu y es mas probable que se repitan numeros cortos que largos.

#27 Aprende a leer. De nada.

2 respuestas

elkaoD #30 Ene '12

#29 con mi método sólo usas 3 caracteres a partir de 10 repeticiones:

"*",    // 3
"#",    // 4
"#X",   // 5
"**",   // 6
"*#",   // 7
"##",   // 8
"#*",   // 9
"**#",  // 10
"*##",  // 11
"###",  // 12
"***",  // 13
"*#*",  // 14
"#**",  // 15
"##*",  // 16

Usuarios habituales