algoritmo para generar un código único (constante) de una cadena que debe ser reversible

El requisito:algoritmo para generar un código único (constante) de una cadena que debe ser reversible

Tenemos valores en el PP como

Chennai 
Baroda 
Bangalore 
New Delhi 
São Paulo, Lisboa 
San Jose

etc ...

por lo que quiero para convertir estas cadenas en una cadena corta única. Por ejemplo

Chennai –> xy67kr 

San Jose –> iuj73d

básicamente algo similar al URL shortner.

Y el algoritmo para convertir esto debería ser reversible ... es decir, cuando pase "xy67kr" a una función de decodificación, debería devolverme "Chennai".

Esperamos su ayuda.

Fuente

2012-03-30 Taher

¿Las cadenas deben tener una longitud fija? –

Si tiene una base de datos, entonces el proceso de reversión debería ser bastante fácil ... –

1 - Las cadenas no son de longitud fija. Longitud máxima = 200 caracteres 2 - Deseo evitar la llamada a la base de datos. Esa es la razón por la que quiero generar un algoritmo. Que se puede usar en DB para codificar las cadenas. Se puede usar el mismo algoritmo para decodificar y obtener valor real en mi aplicación web – Taher

Como han indicado otros carteles, no se puede tener una función que acorte cadenas arbitrarias, eso es matemáticamente imposible. Pero puede crear una función personalizada que funcione bien con su conjunto particular de cadenas.

Un enfoque ejemplo sería para calcular la frecuencia de carácter en el conjunto, a continuación, sólo codificar los caracteres con un prefix code de tal manera que las letras más frecuentes están codificados con prefijos cortos (es decir Huffman coding.)

El enfoque anterior hace no aproveche el hecho de que en lenguaje natural el siguiente carácter puede predecirse con bastante precisión de los anteriores, por lo que puede extender el algoritmo anterior para que, en lugar de codificar los caracteres de forma independiente, codifique el siguiente carácter en un n-gram. Esto, por supuesto, requiere una tabla de compresión más grande que el enfoque simple, ya que efectivamente tiene un código separado dependiendo del prefijo. Por ejemplo, si 'e' es muy frecuente después de 'th', 'e' después de 'th' está codificado con un prefijo muy corto. Si 'e' es muy poco frecuente después de 'ee', entonces puede codificarse con un prefijo muy largo en este caso. El algoritmo de decodificación obviamente necesita ver el prefijo descomprimido actualmente para verificar cómo decodificar el siguiente carácter.

Este enfoque general asume que las frecuencias no cambian, o al menos cambian lentamente. Si su conjunto de datos cambia, tendrá que volver a calcular las estadísticas y volver a codificar las cadenas.

Fuente

2012-03-30 13:13:55

Dudo que esto funcione bien para datos de entrada cortos. También parece que el OP quiere una codificación de longitud fija, lo que claramente es imposible. –

@OliCharlesworth Por el contrario, este tipo de codificación estadística funciona bien incluso para cadenas de caracteres individuales, salvo por el hecho de que incluso si el código resultante es, por ejemplo, 6 bits, entonces todavía tiene que enviar (o guardar) al menos un byte . Estoy de acuerdo en que la codificación de longitud fija es imposible. –

Ok, en mi pregunta original, pregunté que mis cadenas de entrada pueden ser de longitud variable. Entonces, supongamos que los hago de longitud fija mediante la aplicación de relleno, es decir -> Nueva York [se convierte] -> Nueva York! @ !! @! o algo así. ¿Es posible acortarlos después de la codificación? – Taher

Ver my answer a la pregunta similar y simplemente volver a escribir a PHP:

Codificación:

$encoded = base64_encode(gzdeflate("São Paulo, Lisboa"))

Decodificación:

$decoded = gzinflate(base64_decode($encoded))

Tenga en cuenta que gzdeflate se comporta mejor que gzcompress en cadenas cortas.

Pero de todos modos el problema con esto es que para cuerdas cortas alarga la cuerda. Esto funciona mejor en textos más largos. Sería, por supuesto, mejor utilizar algún algoritmo de compresión con información a priori, como el método de ppm o sufijo con el árbol de sufijo inicial ... entonces también funcionaría perfectamente en cadenas cortas.

Fuente

2012-03-30 08:39:26 TMS

Sí, creo que el punto es que esto no ayudará al OP. –

Sería por supuesto mejor usar un ** algoritmo de compresión con información a priori **, como el método de ppm o sufijo con el sufijo inicial ... entonces funcionaría perfectamente en cadenas cortas también. Pero entonces la pregunta es si estos métodos son accesibles dentro de PHP. – TMS

Estoy trabajando con C#, no PHP :) – Taher

No puede acortar cadenas de longitud arbitrarias a una longitud fija.

Lo que puede hacer es crear esas cadenas cortas para el único ID de la fila de esa cadena específica en la base de datos. Aquí hay algunos consejos: How to design a sequential hash-like function.

Fuente

2012-03-30 08:47:18

Esto no es necesariamente determinista, pero obviamente podría usar una tabla de búsqueda. El servicio sería similar a goo.gl o imgur

Fuente

2014-03-12 23:38:47

algoritmo para generar un código único (constante) de una cadena que debe ser reversible

Respuesta

Cuestiones relacionadas