Acortador de cadena alfanumérica (simil URL Shortener)
 

Hola gente de Club Delphi.

Les escribo para consultarle alguna idea/código para "acortar" una cadena alfanumérica en una cadena del mismo tipo pero de menor tamaño.
Concretamente, tengo una cadena de 28 caracteres y necesito generar una nueva cadena pero de 8 o 10 caracteres con las siguientes características:

- Debe contar con la menor cantidad de colisiones posibles. Es para generar un código unívoco.
- Debe poder ser reversible. Cod28 --> CODIFICA --> Cod8, Cod8 --> DECODIFICA --> Cod28.

He estado investigando un poco y encontré algoritmos hash como ADLER32, CRC32, etc que te generan cadenas cortas pero no se muy bien como se comporta en cuestión de colisiones.
Les agradecería si me pueden orientar sobre alguna forma de resolver esto.
Desde ya, muchas gracias.
Saludos.

No es que vaya a aportar algo pero diré una cosa: si es reversible entonces es seguro que no hay colisiones.

// Saludos

Hola,

Ay, si no fuese por los matemáticos... ¡en las cavernas andábamos todavía! :)

Cuanta sabiduría veo por aquí :rolleyes:

Ustedes sabrán disculpar el destello luminoso en sus monitores ;)

// Saludos

Buscando en google con "hash collisions short string" parece que hay buen material.

Spoiler: Una funcion de hash moderna es suficientemente buena.

Lo de las colisiones es algo que te ha pasado con las funciones que usaste? Aqui hay un codigo que chequea colisiones:

https://stackoverflow.com/questions/...oid-collisions

Asi que puedes hacer la prueba...

Menos mal que tengo puesta las gafas de sol :cool:

Tal vez se me ha escapado algo (es posible con la edad), pero creo que estás mezclando cosas distintas. Totalmente distintas.

* Un "URL Shortener" se basa en que convierte una cadena de 30 caracteres en otra de 5 caracteres (por decir algo), pero usando una tabla auxiliar donde están ambas. De forma, que la forma de obtener "la cadena larga" es ir a la tabla auxiliar y buscar es registro con la pareja:
CADENA_CORTA = CADENA_LARGA.

* Otra cosa totalmente distinta es "codificar" una CADENA_LARGA de 30 caracteres y obtener una CADENA_CORTA de 5 CARACTERES, teniendo en cuenta además que:
a) Eso sea reversible
b) Que no existan colosiones.

No se si eso es posible, y se acerca más a la teoría de un compresor, que de un codificador.

Lo dicho, seguramente se me está escapando algo...

También hablas de un algoritmo de CRC (o similares de checksum). También es otra cosa.
Un algoritmo de CRC cumple alguna caracteristica de las que comentas, pero no todas. Con un CRC:
a) Puedes convertir una CADENA_LARGA (1234567890qwertyuiopadsfg) en una CADENA_CORTA (34253).
b) Pero a partir de la CADENA_CORTA (34253), nunca podrás obtener la CADENA_LARGA (1234567890qwertyuiopadsfg). ¿De otra forma para qué serviría tener la larga?


Un Saludo.

Por otro lado lo que ha dicho Román. Estas dos premisas son excluyentes, por lógica:

- Debe contar con la menor cantidad de colisiones posibles. Es para generar un código unívoco.
- Debe poder ser reversible. Cod28 --> CODIFICA --> Cod8, Cod8 --> DECODIFICA --> Cod28.

Es decir, con una única posible colisión, el código ya no será reversible.

Aunque si el rango de posibles valores es finito, y se puede calcular, es posible crear una tabla como dice Neftali.

Supongo que importa mas:

Asi que un algoritmo de compresion es la solucion.

Este es un ejemplo especializado para cadenas cortas:

https://ed-von-schleck.github.io/shoco/

Ahora, si como parece, esto es para generar IDs, y pa' rematar son ascendentes -sea que tengan letras o no, lo importante es que tenga un metodo calculable para "ascender al siguiente"- ? Pues la cosa se pone mucho mas facil aun.

Hola, ante todo agradezco sus respuestas y pido disculpas si mezclé conceptos en mi intento por explicar el problema que necesito resolver. No soy un experto en el tema.

Básicamente, el problema es que tengo una cadena de 28 caracteres que me identifica un proceso y debo convertirla (o comprimirla o codificarla) en otra cadena de menor longitud (8 o 10 caract. aprox.) que tiene que ser impresa en una etiqueta y posteriormente leída e ingresada manualmente por un usuario (sin posib. de utilizar cód. de barra). Imagínense un usuario con la etiqueta en la mano tratando de leer en un espacio reducido y tipeando 28 caracteres. :confused:

Por esta razón, les consultaba algún algoritmo en Delphi que simule lo que realiza un "acortador de URL's" para que a partir una dirección genera una nueva mas pequeña.
Investigando un poco antes de realizar esta consulta, encontré que existen funciones para realizar checksum como ADLER32 o CRC32 que acortan estas cadenas pero que (a mi entender) no son reversibles por lo tanto no puede utilizarse como clave única.

Tomando el comentario de Neftali sobre el principio de funcionamiento de los "acortadores de URL's", como puedo generar un código que identifique una entrada única en esta tabla auxiliar con el código de la nueva URL? Existe algún algoritmo para generar este código?
Pensando rápido se me ocurre, por ejemplo utilizando ADLER32, que a partir de una cadena generar el código y verificar que no existe ingresado en esta tabla auxiliar. Si existe, volver a aplicar el algoritmo sobre este código generado y volver a chequear que no exista. Este proceso se repetiría hasta tanto se sigan encontrando coincidencias y llevaríamos un contador de nivel para utilizar en la decodificación.
Para decodificar, en teoría, deberíamos aplicar el proceso inverso tantas veces como niveles hayamos registrado.
Lo estoy pensando a medida que escribo estas líneas. Voy a intentar implementarlo y les cuento.

Nuevamente les agradezco por su tiempo y si tienen alguna otra idea o forma, bienvenida!
Saludos.

Segun tu caso de uso, puedes reusar un acortador de URLS. Solo tienes que crear una tabla que diga HasId=FullId y eso es todo. Si generaste un HashId es porque tienes el FullId, asi que si pasar un valor y no lo encuentras, es porque obviamente nunca fue generado.

mamcx, gracias por tu respuesta.

Conoces alguna implementación de un acortador de URL's para Delphi? Estuve buscando en Google pero no pude encontrar nada todavía.

Gracias.
Saludos

Estuve investigando un poco y en algunos sitios sugieren usar Base62.
Alguno conoce alguna implementación para Delphi que se pueda utilizar?

No sabría por donde irá una solución a tu caso, pero al leer en este hilo sobre hash y colisiones recordé algo que me comentó un especialista de seguridad en Twitter: "las colisiones uno las puede evitar... a menos que sea eso lo que busca" y adjuntaba a sus palabras el siguiente enlace.

El paper en cuestión expone justamente eso, demostrando algunas vulnerabilidades (entre otras que se dieron a conocer) de MD5.

Así que... hay que pensarlo bien.

Saludos,

Pero en el caso que se plantea, no hay que preocuparse mucho por las colisiones

Entonces, si no hay que preocuparse por las colisiones es porque no se trata de un algoritmo que tenga como base un hash.
Si es el caso, ¿porqué tu mismo has vuelto a meterlo en la bolsa en uno de tus últimos comentarios?:

Si al final le estás mareando al usuario.
Roman tiró la indirecta al comienzo y Neftali apuntó con la linterna. ¡Si no debe haber colisión, y debe ser reversible, entonces no se trata de un algoritmo de reducción hash!

Una reversibilidad apunta más hacia un cifrado que otra cosa.
El asunto acá es que no hay tal reversibilidad... pasa por tener una forma de referenciar una cadena de menor longitud por otra de mayor. Necesariamente debe intervernir una tabla que haga esa asociación. Generada alguna cadena corta esta se marca como usada. Listo. No más. ¿Que tiene que intervernir acá un "Hashid"?

Saludos,

[delphius], muchas gracias por tu respuesta.

Podrías sugerirme algún generador hecho en Delphi para resolver esto que me transforme una cadena de 28 caracteres en 8 o 10 caracteres? En el inicio de esta discusión (incluidas las fallas teóricas de mi parte) yo consultaba por algún algoritmo que me acorte justamente una cadena. También considero conveniente tomar como referencia el consejo de Neftali sobre implementar una tabla para relacionar estas cadenas.

Nuevamente, muchas gracias.
Saludos.

Por que necesitas 8 o 10 caracteres? No te bastaria con tener un Id que identifique a cada string? Con un sencillo diccionario<integer, string> de delphi lo solucionarias

Porque el origen es un código de 28 caracteres y tengo que convertirlo en algo mas corto que tiene que ser leído e ingresado manualmente por un usuario desde una etiqueta. El objetivo de ser 8/10 caracteres es para establecer algún formato (estilo serial number) donde los dígitos no son correlativos sino que es un código alfanumérico conformado por letras y números.

¿De qué volumen estamos hablando?
Pensando en 1 día o en un año.

Por fin vas hilando más fino y al verdadero dilema.
Nos pusiste un bosque enfrente del árbol.

Aún empleando ese "id" alfanumérico restringido a cierta longitud va a ser tarde o temprano una limitación.

Empleando las 27 letras y los 10 números tienes para un ID de longitud de 10, un máximo de 37^10 posibles ids.

Saludos,

[delphius], en una respuesta anterior había detallado para que lo necesitaba exactamente. Te copio el mensaje:

En este momento estoy haciendo pruebas con un generador de cadenas aleatorias alfanuméricas para estos IDs. Lo saqué una respuesta de [Casimiro Notevi] y [Antoniov]
Después les cuento que tal fue.
Nuevamente, muchas gracias por su tiempo.
Saludos.

Mira. A ti solo te importa que la cadena sea corta. Puedes usar cualquier libreria de hash/encoding que te cumpla con el largo, pero si nos atenemos a lo que dices, puedes pre-generar las cadenas superfacil.

Código Delphi [-]
Largo1= C1
Largo2= C2
Largo3= C3

Yo voy con mamcx. Para este problema específico creo que le estás dando demasiadas vueltas. Si dispones de una tabla en la bd donde almacenar la correspondencia entre las cadenas largas y cortas, lo único que necesitas es un autonumérico/generador que puedes prefijar con una cadena al gusto o simplemente rellenar con ceros iniciales:

// Saludos

El problema es que estuve buscando alguna librería o función de hash/encoding y no pude encontrar ninguna. Podrías recomendarme alguna?
[roman], estoy probando justo eso, cuando lo tenga resuelto les cuento.

Muchas gracias.

Con lo que dice roman, ni falta hace emplear una biblioteca que te lo haga. No es algo taan complicado en diseñar un algoritmo que haga esto:

AAAA, AAAB, AAAC ... AAAZ, AAA0, AAA1, ... AAA9, AABA, AABB, ... AABZ, AAB0, ... AAB9, ... ZZZZ, ... 9999

Y disponer en una tabla algo como:
ID - CadenaCorta - CadenaLarga
1 - AAAA - etc
2 - AAAB - etc
...

Y aquí es donde entra lo que yo dije: dependiendo de la longitud que se establezca a la cadena, y el juego de carácteres definido, tendrás la cantidad máxima de registros que puede soportar. Que para el caso de 27 letras más 10 números y una cadena de longitud de 10 será posible tener 37^10 = 4808584372417849 registros. Esto puede ser mucho o poco según el volumen de datos.

¡Y nota en como el tema de la cadena corta en realidad no hace más que hacer un intermediario más! Ya existe una relación 1-1 en un ID autonumérico y la correspondiente cadena larga. Proceder a generar una cadena corta que "identifique" o que haga de alias para cada cadena larga no deja de ser otra relación 1-1 ya existente, ya que actúa como una clave artificial más.

Saludos,

Pues justo mi pregunta iba por ahí.
Aquí para otros temas se usa un código que se genera como: AAAA-XXXX-NN. Un ejemplo sería este: 2015-TFGR-01

En este caso es relevante el año (los 4 primeros). Tal vez en el tuyo no lo sea, pero la idea es la misma.
Además facilita el trabajo de entrada al operario y sirve de comprobación.

Sea cual fuese el diseño que se utilice para generar el código alfanumérico tiene su límite. Por eso yo hice los cálculos de cuantos IDs/códigos se pueden conseguir para que agustibaldo se diera cuenta de lo que esto representa. En tu ejemplo hay 10000 x 27^4 x 100 = 531441000000 combinaciones. ¿Mucho, poco? no lo se pero debe hacerse un adecuado análisis... no vaya a ser cosa que la mediciona sea peor que el remedio.

Un código alfanumérico debe ser lo suficiente extenso como para permitir la entrada de una buena cantidad de nuevos items, pero a su vez debe ser lo más corto y fácil de memorizar. Por ejemplo, algo como NNN-XXX siendo N: número, X:letra es un código bastante simple y fácil de recordar. A su vez permitirá exactamente 1000 combinaciones numéricas, y por cada una de ellas 27^3 = 19683 alfanuméricas. Siendo un total de: 19683000. Las patentes de los autos en Argentina sigue este diseño, y ya estamos a punto de quebrarlo... y eso que las ventas de autos nuevos y usados viene en picada.

Acá sucede lo mismo, si agustibaldo no tiene cuidado o se queda chico, bastante pronto, o termina haciendo un sistema de "codificación" bastante amplio, que no se termina de llenar y que no sea fácil de llevar ni de recordar.

Por lo general estos tipos de códigos alfanuméricos se emplea cuando la cantidad de elementos es relativamente manejable. Lo suficiente como para permitir deducir con poco esfuerzo mental a que items hace referencia. Ni muchos, ni pocos. A su vez, se espera además que esta cantidad sea más o menos estable o previsible y no varíe. Son muy útiles en los ambientes industriales en donde ya se conocen la cantidad total de posibles productos o materias primas que se utilizarán o se pueden producir.

Saludos,

Creo que todo esto es divagar, lo que de verdad se necesita es saber exactamente qué quiere hacer y qué necesita agustibaldo :)

Te equivocas amigo. Muchas veces no saben lo que quieren hacer y tampoco saben para que lo necesita. Lo que si saben, es que lo quieren para ayer.
Por donde debió empezarse el hilo es hacerse las siguientes preguntas:
¿Que se pretende seriamente "ganar" con todo esto? ¿En verdad aporta un valor de negocio y le da un valor agregado? ¿Cuántas veces o con que frecuencia se usará esta funcionalidad? ¿Resuelve un problema o más bien lo sustituye o esconde por otro?

Las veces que se ha visto por los foros preguntas del estilo "necesito X cosa", pensaban en Y y la solución pasaba por Z.
Este hilo no es la excepción. Y me extraña de todos ustedes que no se hayan cuestionado... al menos un "ummm, ¿y no será que estás usando un cañón cuando una .22 basta?"

Vengo yo y digo que el bosque tapa el árbol, y recién esto toma color. Lo digo de nuevo...lo veo verde....

Saludos,

Seguro que sabe para qué lo quiere. Otra cosa distinta es que sea lo más adecuado, o no, para lo que necesita.

No. CREE saber lo que quiere.
Ante la evidencia de que ha averiguado (y se le ofrecieron opciones) tan dispares yo lo pongo en duda. Lo único puntual es que quiere acortar, para "ahorrarse" un algo para hacer otro algo no concretado ni definido.
No sería mejor preguntar en lugar de los diferentes cuchillos que hay para cortar, ¿porqué, para que, con fin, y que se espera hacer con los trozos cortados?

Veo un bosque, el árbol sigue ahí escondido.

Saludos,

Pues eso es lo que he dicho ;)