Conseguir una representación de una cadena int

Question

Busco una forma de crear una representación larga \ int de una cadena alfanumérica arbitraria. Los códigos Hash no lo harán, porque no puedo permitir colisiones hash, es decir, la representación debe ser única y repetible.

La representación numérica se usará para realizar comparaciones eficientes (con suerte). La creación de la clave numérica llevará algún tiempo, pero solo tiene que ocurrir una vez, mientras que necesito realizar un gran número de comparaciones con ella, lo que con suerte será mucho más rápido que comparar las cadenas sin procesar.

Cualquier otra idea de comparación de cadenas de más rápido serán los más apreciados también ...

Answer 1

¿Por cuánto tiempo son sus cadenas? A menos que elija una representación int que sea más larga que la cadena, las colisiones siempre serán posibles independientemente de la conversión que esté utilizando. Entonces, si está utilizando un entero de 32 bits, solo puede representar cadenas de hasta 4 bytes de manera única.

Answer 2

¿No puede simplemente comenzar con un código hash, y si los códigos hash coinciden, hacer una comparación carácter por personaje?

Answer 3

¿Cuán grandes son sus cadenas? Las cadenas arbitrariamente largas no se pueden comprimir en formato de 32/64 bits.

Answer 4

Si no desea que las colisiones, probar algo loco como SHA-512. No puedo garantizar que no habrá colisiones, pero no creo que hayan encontrado ninguna.

Answer 5

Suponiendo que "alfanumérico" significa letras y números, podría tratar cada letra/número como un dígito de base 36. Desafortunadamente, las cadenas grandes harán que el número crezca rápidamente y tendrías que recurrir a enteros grandes, que son poco eficientes.

Si sus cadenas son generalmente diferentes cuando realiza la comparación (es decir, busca una cadena específica), el hash podría ser su mejor opción. Una vez que obtenga un golpe potencial, puede hacer la comparación de cuerdas para estar seguro. Un hash bien diseñado hará que las colisiones sean extremadamente raras.

Answer 6

Parecería que un hash MD5 funcionaría bien. El riesgo de una colisión hash sería extremadamente improbable. Dependiendo de la longitud de su cadena, un hash que genera un int/largo se ejecutaría en problemas de valor máximo muy rápidamente.

Answer 7

¿Por qué no haces algo como 1stChar + (10 x 2ndChar) + 100 x (3rdChar) ...., donde usas el valor entero simple de cada carácter, es decir, a = 1, b = 2, etc. , o solo el valor entero si no es una letra. Esto le dará un valor único para cada cadena, incluso para 2 cadenas que son exactamente las mismas letras en un orden diferente.

Por supuesto, si se vuelve más complicado si necesita preocuparse por Unicode en lugar de ASCII y los números podrían agrandarse si necesita usar una cadena larga.

son las funciones de comparación de cadenas estándar de Java definitivamente no es lo suficientemente eficiente?

Answer 8

¿Por cuánto tiempo son los hilos? Si son muy cortos, se puede generar un ID único al considerar los caracteres como dígitos en la base 36 (26 + 10) que forman un n -dígitos donde n es la longitud de la cadena. Por otro lado, si las cadenas son lo suficientemente cortas como para permitir esto, la comparación directa no será un problema de todos modos.

De lo contrario, tendrá que generar un hash libre de colisiones y esto solo se puede hacer cuando se conoce por adelantado el espacio problemático completo (es decir, si conoce todas las cadenas posibles).Querrá echarle un vistazo al perfect hashing, aunque el único algoritmo factible para encontrar una función hash perfecta que conozco es probabilística, por lo que las colisiones aún son teóricamente posibles.

Puede haber otras formas de encontrar dicha función. Knuth llamó a esto un "rompecabezas bastante divertido ..." en TAoCP pero tampoco da un algoritmo.

En general, da muy poca información para encontrar un algoritmo que no requiera investigar todo el espacio problemático de alguna manera. Esto significa invariablemente que el problema tiene un tiempo de ejecución exponencial, pero podría resolverse usando heurística de aprendizaje automático. No estoy seguro de si esto es aconsejable en su caso.

Answer 9

Tal vez:

String y = "oiu291981u39u192u3198u389u28u389u"; 
BigInteger bi = new BigInteger(y, 36); 
System.out.println(bi); 

Answer 10

Algunas preguntas en el principio:

1. ¿Se han probado así de simple comparación de cadenas es demasiado lento?
2. ¿Cómo se ve la comparación ('ABC' == 'abc' o 'ABC'! = 'Abc')?
3. ¿Cuántas cadenas tiene que comparar?
4. ¿Cuántas comparaciones tienes que hacer?
5. ¿Cómo se ven sus cadenas (la longitud, la caja de la letra)?

Por lo que recuerdo, String en Java es un objeto y dos cadenas idénticas apuntan al mismo objeto.

Por lo tanto, tal vez sería suficiente para comparar objetos (probablemente la comparación de cadenas ya está implementada de esta manera).

Si no ayuda, puede intentar utilizar la implementación de Pascal del objeto de cadena cuando el primer elemento es de longitud y si sus cadenas tienen varias longitudes, esto debería ahorrar algo de tiempo de CPU.

Answer 11

A menos que su cuerda tenga una longitud limitada, no puede evitar colisiones.

Hay 4294967296 valores posibles para un número entero (2^32). Si tiene una cadena de más de 4 caracteres ASCII, o más de dos caracteres Unicode, entonces hay más valores de cadena posibles que valores enteros posibles. No puede tener un valor entero único para cada cadena de 5 caracteres posibles. Los valores largos tienen más valores posibles, pero solo proporcionarían un valor único para cada cadena posible de 8 caracteres ASCII.

Los códigos Hash son útiles como un proceso de dos pasos: primero verifique si el código hash coincide, luego verifique toda la cadena. Para la mayoría de las cadenas que no coinciden, solo necesita hacer el primer paso, y es realmente rápido.

Answer 12

La longitud de la secuencia puede variar, pero digamos 10 caracteres por ahora.

En ese caso, para garantizar la exclusividad, debe usar algún tipo de representación de entero grande. Dudo que hacer comparaciones en enteros grandes sea mucho más rápido que hacer comparaciones de cadenas en primer lugar. Voy a decir lo que otros han dicho aquí, usar algún tipo de hash, luego, en el caso de una coincidencia de hash, verificar las cadenas originales para eliminar cualquier colisión.

En cualquier caso, si sus cadenas tienen alrededor de 10 caracteres, dudo que comparar, por ejemplo, un grupo de hashes de 32 bits sea mucho más rápido que las comparaciones directas de cadenas. Creo que debes preguntarte si realmente vale la pena la complejidad adicional.

Answer 13

Al final del día, un solo carácter alfanumérico tiene al menos 36 valores posibles. Si incluye signos de puntuación, minúsculas, etc., puede pasar fácilmente 72 valores posibles.

Un número que no colisiona y que le permite comparar rápidamente cadenas necesariamente crecerá exponencialmente con la longitud de la cadena.

Así que usted primero debe decidir sobre la cadena más larga que está esperando para comparar. Suponiendo que tiene N caracteres de longitud, y suponiendo que SÓLO necesita letras mayúsculas y los números 0-9, debe tener una representación entera que puede ser tan alta como 36^N

Para una cadena de longitud 25 (común nombre del campo) luego terminas necesitando un número binario con 130 bits.

Si lo compone en números de 32 bits, necesitará 4. Luego puede comparar cada número (cuatro comparaciones enteras no deberían tomarse en ningún momento, en comparación con caminar la cadena). Recomendaría una gran biblioteca de números, pero para este caso especializado estoy bastante seguro de que puede escribir el suyo propio y obtener un mejor rendimiento.

Si desea manejar 72 valores posibles por carácter (mayúsculas, minúsculas, números, puntuación ...) y necesita 10 caracteres, necesitará 62 bits, dos enteros de 32 bits (o uno de 64 bits si está en un sistema compatible con la informática de 64 bits)

Sin embargo, si no puede restringir los números en la cadena (es decir, podría ser cualquiera de las 256 letras/números/caracteres/etc.) y usted no puede definir el tamaño de la cadena, luego comparar las cadenas directamente es la única manera de hacerlo, pero hay un atajo.

Emite el puntero de la cadena a una matriz de enteros sin signo de 32 bits y compara la cadena 4 bytes a la vez (o 64 bits/8 bytes por vez en un procesador de 64 bits). Esto significa que una cadena de 100 caracteres solo requiere 25 comparaciones como máximo para encontrar cuál es mayor.

Puede necesitar redefinir el conjunto de caracteres (y convertir las cadenas) para que los caracteres con mayor precedencia tengan valores más cercanos a 0, y valores de precedencia más bajos cerca de 255 (o viceversa, dependiendo de cómo los están comparando).

¡Buena suerte!

-Adam

Answer 14

Mientras que es una función hash, ya sea String.hashCode(), MD5 o SHA1, la colisión es inevitable a menos que tenga un límite fijo de la longitud de la cadena. Es matemáticamente imposible tener un mapeo uno-a-uno desde un grupo infinito a un grupo finito.

Retroceder, ¿es posible evitar colisiones absolutamente?