algorithm - turing - size of the output produced by hash functions

Mapeando dos enteros a uno, de una manera única y determinística.

Question

Imagine dos enteros positivos A y B. Quiero combinar estos dos en un solo entero C.

No puede haber otros enteros D y E que se combinen con C. Así que combinarlos con el operador de suma no funciona. Por ejemplo, 30 + 10 = 40 = 40 + 0 = 39 + 1 Tampoco funciona la concatinación. Por ejemplo, "31" + "2" = 312 = "3" + "12"

Esta operación de combinación también debe ser determinista (siempre produce el mismo resultado con las mismas entradas) y siempre debe producir un número entero en el lado positivo o negativo de los números enteros.

Answer 1

¿Es esto posible?
Estás combinando dos enteros. Ambos tienen el rango de -2,147,483,648 a 2,147,483,647 pero solo tomará los positivos. Eso hace 2147483647 ^ 2 = 4,61169E + 18 combinaciones. Como cada combinación tiene que ser única Y dar como resultado un entero, necesitará algún tipo de entero mágico que pueda contener esta cantidad de números.

¿O es mi lógica defectuosa?

Answer 2

¿Qué tal algo mucho más simple? Dados dos números, A y B dejan que str sea la concatenación: ''A'' + '';'' + ''B''. Entonces deja que la salida sea hash (str). Sé que esta no es una respuesta matemática, pero una simple secuencia de comandos de python (que tiene una función hash incorporada) debería hacer el trabajo.

Answer 3

Aquí hay una extensión del código de @DoctorJ a enteros ilimitados basado en el método dado por @nawfal. Puede codificar y decodificar. Funciona con matrices normales y matrices numpy.

#!/usr/bin/env python
from numbers import Integral    

def tuple_to_int(tup):
    """:Return: the unique non-negative integer encoding of a tuple of non-negative integers."""
    if len(tup) == 0:  # normally do if not tup, but doesn''t work with np
        raise ValueError(''Cannot encode empty tuple'')
    if len(tup) == 1:
        x = tup[0]
        if not isinstance(x, Integral):
            raise ValueError(''Can only encode integers'')
        return x
    elif len(tup) == 2:
        # print("len=2")
        x, y = tuple_to_int(tup[0:1]), tuple_to_int(tup[1:2])  # Just to validate x and y

        X = 2 * x if x >= 0 else -2 * x - 1  # map x to positive integers
        Y = 2 * y if y >= 0 else -2 * y - 1  # map y to positive integers
        Z = (X * X + X + Y) if X >= Y else (X + Y * Y)  # encode

        # Map evens onto positives
        if (x >= 0 and y >= 0):
            return Z // 2
        elif (x < 0 and y >= 0 and X >= Y):
            return Z // 2
        elif (x < 0 and y < 0 and X < Y):
            return Z // 2
        # Map odds onto negative
        else:
            return (-Z - 1) // 2
    else:
        return tuple_to_int((tuple_to_int(tup[:2]),) + tuple(tup[2:]))  # ***speed up tuple(tup[2:])?***


def int_to_tuple(num, size=2):
    """:Return: the unique tuple of length `size` that encodes to `num`."""
    if not isinstance(num, Integral):
        raise ValueError(''Can only encode integers (got {})''.format(num))
    if not isinstance(size, Integral) or size < 1:
        raise ValueError(''Tuple is the wrong size ({})''.format(size))
    if size == 1:
        return (num,)
    elif size == 2:

        # Mapping onto positive integers
        Z = -2 * num - 1 if num < 0 else 2 * num

        # Reversing Pairing
        s = isqrt(Z)
        if Z - s * s < s:
            X, Y = Z - s * s, s
        else:
            X, Y = s, Z - s * s - s

        # Undoing mappint to positive integers
        x = (X + 1) // -2 if X % 2 else X // 2  # True if X not divisible by 2
        y = (Y + 1) // -2 if Y % 2 else Y // 2  # True if Y not divisible by 2

        return x, y

    else:
        x, y = int_to_tuple(num, 2)
        return int_to_tuple(x, size - 1) + (y,)


def isqrt(n):
    """":Return: the largest integer x for which x * x does not exceed n."""
    # Newton''s method, via http://.com/a/15391420
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

Answer 4

Aunque la respuesta de Stephan202 es la única realmente general, para los enteros en un rango acotado puedes hacerlo mejor. Por ejemplo, si su rango es 0..10,000, entonces puede hacer:

#define RANGE_MIN 0
#define RANGE_MAX 10000

unsigned int merge(unsigned int x, unsigned int y)
{
    return (x * (RANGE_MAX - RANGE_MIN + 1)) + y;
}

void split(unsigned int v, unsigned int &x, unsigned int &y)
{
    x = RANGE_MIN + (v / (RANGE_MAX - RANGE_MIN + 1));
    y = RANGE_MIN + (v % (RANGE_MAX - RANGE_MIN + 1));
}

Los resultados pueden caber en un solo entero para un rango hasta la raíz cuadrada de la cardinalidad del tipo entero. Esto es un poco más eficiente que el método más general de Stephan202. También es considerablemente más fácil de decodificar; No requiere raíces cuadradas, para empezar :)

Answer 5

Compruebe esto: http://en.wikipedia.org/wiki/Pigeonhole_principle . Si A, B y C son del mismo tipo, no se puede hacer. Si A y B son enteros de 16 bits, y C es de 32 bits, simplemente puede usar el desplazamiento.

La naturaleza misma de los algoritmos de hash es que no pueden proporcionar un hash único para cada entrada diferente.

Answer 6

Estás buscando un biyectivo NxN -> N mapeo. Estos se utilizan para, por ejemplo, dovetailing . Eche un vistazo a este PDF para ver una introducción a las llamadas funciones de emparejamiento . Wikipedia introduce una función de emparejamiento específica, a saber, la función de emparejamiento de Cantor :

Tres observaciones:

• Como han dejado claro otros, si planea implementar una función de emparejamiento, pronto encontrará que necesita enteros arbitrariamente grandes (bignums).
• Si no desea hacer una distinción entre los pares (a, b) y (b, a), clasifique a y b antes de aplicar la función de emparejamiento.
• En realidad mentí. Usted está buscando un bijective ZxZ -> N mapeo. La función de Cantor solo funciona en números no negativos. Sin embargo, esto no es un problema, porque es fácil definir una bijection f : Z -> N , así:
  • f (n) = n * 2 si n> = 0
  • f (n) = -n * 2 - 1 si n <0

Answer 7

La forma matemática estándar para los enteros positivos es utilizar la singularidad de la factorización prima.

f( x, y ) -> 2^x * 3^y

El inconveniente es que la imagen tiende a abarcar una gran variedad de enteros, por lo que, cuando se trata de expresar el mapeo en un algoritmo de computadora, es posible que tenga problemas para elegir el tipo adecuado para el resultado.

Puede modificar esto para lidiar con los x negativos de x e y codificando las banderas con potencias de 5 y 7 términos.

p.ej

f( x, y ) -> 2^|x| * 3^|y| * 5^(x<0) * 7^(y<0)

Answer 8

Lo que sugieres es imposible. Siempre tendrás colisiones.

Para asignar dos objetos a otro conjunto único, el conjunto asignado debe tener un tamaño mínimo del número de combinaciones esperadas:

Suponiendo un entero de 32 bits, tiene 2147483647 enteros positivos. Elegir dos de estos donde el orden no importa y con repetición produce 2305843008139952128 combinaciones. Esto no encaja bien en el conjunto de enteros de 32 bits.

Sin embargo, puede ajustar esta asignación en 61 bits. El uso de un entero de 64 bits es probablemente el más fácil. Establezca la palabra alta en el entero más pequeño y la palabra baja en el más grande.

Answer 9

No es tan difícil construir un mapeo:

1 2 3 4 5 use this mapping if (a,b) != (b,a) 1 0 1 3 6 10 2 2 4 7 11 16 3 5 8 12 17 23 4 9 13 18 24 31 5 14 19 25 32 40 1 2 3 4 5 use this mapping if (a,b) == (b,a) (mirror) 1 0 1 2 4 6 2 1 3 5 7 10 3 2 5 8 11 14 4 4 8 11 15 19 5 6 10 14 19 24 0 1 -1 2 -2 use this if you need negative/positive 0 0 1 2 4 6 1 1 3 5 7 10 -1 2 5 8 11 14 2 4 8 11 15 19 -2 6 10 14 19 24

Averiguar cómo obtener el valor para un arbitrario a, b es un poco más difícil.

Answer 10

Para enteros positivos como argumentos y donde el orden de los argumentos no importa:

1. Aquí hay una función de emparejamiento desordenada :

   <x, y> = x * y + trunc((|x - y| - 1)^2 / 4) = <y, x>

2. Para x ≠ y, aquí hay una función de emparejamiento desordenada única :

   <x, y> = if x < y:
              x * (y - 1) + trunc((y - x - 2)^2 / 4)
            if x > y:
              (x - 1) * y + trunc((x - y - 2)^2 / 4)
          = <y, x>

Answer 11

Que el número a sea ​​el primero, b el segundo. Sea p el número primo a a+1 , q sea ​​el número primo b+1

Entonces, el resultado es pq , si a<b, o 2pq si a>b . Si a=b , sea p^2 .

Answer 12

Si A y B se pueden expresar con 2 bytes, puede combinarlos en 4 bytes. Ponga A en la mitad más significativa y B en la mitad menos significativa.

En lenguaje C esto da (asumiendo sizeof (short) = 2 y sizeof (int) = 4):

int combine(short A, short B)
{
    return A<<16 | B;
}

short getA(int C)
{
    return C>>16;
}

short getB(int C)
{
    return C & 0xFFFF;
}

Answer 13

tengamos dos números B y C, codificándolos en un solo número A

A = B + C * N

dónde

B = A% N = B

C = A / N = C

Answer 14

La función de emparejamiento de Cantor es realmente una de las mejores que existen, ya que es sencilla, rápida y eficiente en cuanto al espacio, pero hay algo incluso mejor publicado en Wolfram por Matthew Szudzik, aquí . La limitación de la función de emparejamiento de Cantor (relativamente) es que el rango de resultados codificados no siempre se mantiene dentro de los límites de un entero de 2N bits si las entradas son dos enteros de N bits. Es decir, si mis entradas son dos enteros de 16 bits que van de 0 to 2^16 -1 , entonces hay 2^16 * (2^16 -1) combinaciones de entradas posibles, por lo que, por el obvio principio del casillero , necesitamos un salida de tamaño al menos 2^16 * (2^16 -1) , que es igual a 2^32 - 2^16 , o en otras palabras, un mapa de 32 bits debería ser idealmente viable. Esto puede no ser de poca importancia práctica en el mundo de la programación.

Función de emparejamiento de Cantor :

(a + b) * (a + b + 1) / 2 + a; where a, b >= 0

El mapeo para dos enteros máximos de la mayoría de los 16 bits (65535, 65535) será 8589803520 que, como puede ver, no puede ajustarse en 32 bits.

Entra en la función de Szudzik :

a >= b ? a * a + a + b : a + b * b;  where a, b >= 0

La asignación para (65535, 65535) ahora será 4294967295, que como puede ver es un entero de 32 bits (0 a 2 ^ 32 -1). Aquí es donde esta solución es ideal, simplemente utiliza cada punto en ese espacio, por lo que nada puede tener más espacio.

Ahora, considerando el hecho de que normalmente tratamos con implementaciones firmadas de números de varios tamaños en lenguajes / marcos, consideremos enteros de signed 16 bits signed 16 van desde -(2^15) to 2^15 -1 (más adelante veremos cómo extienda incluso la salida para abarcar sobre el rango firmado). Como a y b tienen que ser positivos, van de 0 to 2^15 - 1 .

Función de emparejamiento de Cantor :

La asignación para dos enteros con signo máximo de 16 bits máximo (32767, 32767) será 2147418112, que es poco más que el valor máximo para el entero de 32 bits con signo.

Ahora la función de Szudzik :

(32767, 32767) => 1073741823, mucho más pequeño ..

Vamos a tener en cuenta los enteros negativos. Eso está más allá de la pregunta original que conozco, pero solo estoy elaborando para ayudar a los futuros visitantes.

Función de emparejamiento de Cantor :

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
(A + B) * (A + B + 1) / 2 + A;

(-32768, -32768) => 8589803520 que es Int64. ¡La salida de 64 bits para entradas de 16 bits puede ser tan imperdonable!

La función de Szudzik :

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
A >= B ? A * A + A + B : A + B * B;

(-32768, -32768) => 4294967295 que es de 32 bits para el rango sin signo o de 64 bits para el rango firmado, pero aún mejor.

Ahora todo esto mientras que la salida siempre ha sido positiva. En el mundo firmado, se ahorrará aún más espacio si pudiéramos transferir la mitad de la salida al eje negativo . Podrías hacerlo así para Szudzik''s:

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
C = (A >= B ? A * A + A + B : A + B * B) / 2;
a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;

(-32768, 32767) => -2147483648

(32767, -32768) => -2147450880

(0, 0) => 0 

(32767, 32767) => 2147418112

(-32768, -32768) => 2147483647

Qué hago: después de aplicar un peso de 2 a las entradas y pasar por la función, luego divido la salida por dos y llevo algunas de ellas al eje negativo multiplicando por -1 .

Vea los resultados, para cualquier entrada en el rango de un número de 16 bits con signo, la salida se encuentra dentro de los límites de un entero de 32 bits con signo que es genial. No estoy seguro de cómo hacerlo de la misma manera para la función de emparejamiento de Cantor, pero no probé tanto como no es tan eficiente. Además, más cálculos involucrados en la función de emparejamiento de Cantor significa que también es más lento .

Aquí hay una implementación de C #.

public static long PerfectlyHashThem(int a, int b)
{
    var A = (ulong)(a >= 0 ? 2 * (long)a : -2 * (long)a - 1);
    var B = (ulong)(b >= 0 ? 2 * (long)b : -2 * (long)b - 1);
    var C = (long)((A >= B ? A * A + A + B : A + B * B) / 2);
    return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}

public static int PerfectlyHashThem(short a, short b)
{
    var A = (uint)(a >= 0 ? 2 * a : -2 * a - 1);
    var B = (uint)(b >= 0 ? 2 * b : -2 * b - 1);
    var C = (int)((A >= B ? A * A + A + B : A + B * B) / 2);
    return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}

Dado que los cálculos intermedios pueden exceder los límites del entero con signo 2N , he usado el tipo entero 4N (la última división por 2 devuelve el resultado a 2N ).

El enlace que he proporcionado en una solución alternativa describe muy bien un gráfico de la función que utiliza cada punto en el espacio. ¡Es sorprendente ver que puede codificar de forma única un par de coordenadas en un solo número de manera reversible! ¡¡El mundo mágico de los números !!

Answer 15

f(a, b) = s(a+b) + a , donde s(n) = n*(n+1)/2

• Esta es una función, es determinista.
• También es inyectivo: f asigna diferentes valores para diferentes pares (a, b). Puede probar esto usando el hecho: s(a+b+1)-s(a+b) = a+b+1 < a .
• Devuelve valores bastante pequeños; es bueno si lo va a utilizar para la indexación de matrices, ya que la matriz no tiene que ser grande.
• Es fácil de almacenar en caché: si dos (a, b) pares están cerca uno del otro, entonces f asigna números que están cerca uno del otro (en comparación con otros métodos).

No entendí lo que quieres decir con:

Siempre debe producir un número entero en el lado positivo o negativo de los números enteros

¿Cómo puedo escribir (mayor que), (menor que) caracteres en este foro?