¿Hay una función hash circular?

Question

Pensando en esto question on testing string rotation, me pregunté: ¿Existe tal cosa como una función hash circular/cíclica? P.ej.

h(abcdef) = h(bcdefa) = h(cdefab) etc 

usos para esto incluyen algoritmos escalables que pueden comprobar n cuerdas de unos contra otros para ver donde algunos son rotaciones de los demás.

Supongo que la esencia del hash es extraer información que es específica del pedido pero no específica de la posición. ¿Tal vez algo que encuentre una 'primera posición' determinista, gire hacia ella y evalúe el resultado?

Todo parece plausible, pero un poco más allá de mi alcance en este momento; debe estar afuera ya ...

Answer 1

Me gustaría ir con su determinista "primera posición" - encuentre el carácter "menos"; si aparece dos veces, use el siguiente carácter como desempate (etc.). Luego puedes rotar a una posición "canónica", y hash eso de una manera normal. Si los desempates se ejecutan durante todo el curso de la cuerda, entonces tienes una cuerda que es una rotación de sí misma (si ves lo que quiero decir) y no importa cuál elijas para ser "primero".

Así:

"abcdef" => hash("abcdef") 
"defabc" => hash("abcdef") 
"abaac" => hash("aacab") (tie-break between aa, ac and ab) 
"cabcab" => hash("abcabc") (it doesn't matter which "a" comes first!) 

Answer 2

Se puede encontrar una primera posición determinista por siempre a partir de la posición con el "más bajo" (en términos de ordenamiento alfabético) subcadena. Entonces, en su caso, siempre comenzaría en "a". Si hubiera múltiples "a" s, tendría que tomar dos caracteres en cuenta, etc.

Answer 3

Estoy seguro de que podría encontrar una función que pueda generar el mismo hash independientemente de la posición del carácter en la entrada, sin embargo, ¿cómo se asegurará de que h(abc)! = h(efg) para cada entrada concebible? (Se producirán colisiones para todos los algoritmos hash, así que quiero decir, ¿cómo se minimiza este riesgo?)

Necesitará algunas comprobaciones adicionales incluso después de generar el hash para asegurarse de que las cadenas contienen los mismos caracteres.

Answer 4

Actualización: Como señaló Jon, el primer enfoque no maneja las cadenas con la repetición muy bien. Los problemas surgen cuando se encuentran pares duplicados de letras y el XOR resultante es 0. Aquí hay una modificación que creo que corrige el algoritmo original. Utiliza Euclid-Fermat sequences para generar pares enteros coprime para cada ocurrencia adicional de un carácter en la cadena. El resultado es que el XOR para los pares duplicados no es cero.

También he limpiado el algoritmo ligeramente. Tenga en cuenta que la matriz que contiene las secuencias EF solo admite caracteres en el rango de 0x00 a 0xFF. Esta era solo una forma barata de demostrar el algoritmo. Además, el algoritmo todavía tiene el tiempo de ejecución O (n) donde n es la longitud de la cadena.

static int Hash(string s) 
{ 
    int H = 0; 

    if (s.Length > 0) 
    { 
     //any arbitrary coprime numbers 
     int a = s.Length, b = s.Length + 1; 

     //an array of Euclid-Fermat sequences to generate additional coprimes for each duplicate character occurrence 
     int[] c = new int[0xFF]; 

     for (int i = 1; i < c.Length; i++) 
     { 
      c[i] = i + 1; 
     } 

     Func<char, int> NextCoprime = (x) => c[x] = (c[x] - x) * c[x] + x; 
     Func<char, char, int> NextPair = (x, y) => a * NextCoprime(x) * x.GetHashCode() + b * y.GetHashCode(); 

     //for i=0 we need to wrap around to the last character 
     H = NextPair(s[s.Length - 1], s[0]); 

     //for i=1...n we use the previous character 
     for (int i = 1; i < s.Length; i++) 
     { 
      H ^= NextPair(s[i - 1], s[i]); 
     } 
    } 

    return H; 
} 


static void Main(string[] args) 
{ 
    Console.WriteLine("{0:X8}", Hash("abcdef")); 
    Console.WriteLine("{0:X8}", Hash("bcdefa")); 
    Console.WriteLine("{0:X8}", Hash("cdefab")); 
    Console.WriteLine("{0:X8}", Hash("cdfeab")); 
    Console.WriteLine("{0:X8}", Hash("a0a0")); 
    Console.WriteLine("{0:X8}", Hash("1010")); 
    Console.WriteLine("{0:X8}", Hash("0abc0def0ghi")); 
    Console.WriteLine("{0:X8}", Hash("0def0abc0ghi")); 
} 

La salida es ahora:

7F7D7F7F 
7F7D7F7F 
7F7D7F7F 
7F417F4F 
C796C7F0 
E090E0F0 
A909BB71 
A959BB71 

---

primera versión (que no está completo): Uso XOR que es conmutativa (el orden no importa) y otro pequeño truco involucrando coprimes para combinar hashes ordenados de pares de letras en la cadena.Este es un ejemplo en C#:

static int Hash(char[] s) 
{ 
    //any arbitrary coprime numbers 
    const int a = 7, b = 13; 

    int H = 0; 

    if (s.Length > 0) 
    { 
     //for i=0 we need to wrap around to the last character 
     H ^= (a * s[s.Length - 1].GetHashCode()) + (b * s[0].GetHashCode()); 

     //for i=1...n we use the previous character 
     for (int i = 1; i < s.Length; i++) 
     { 
      H ^= (a * s[i - 1].GetHashCode()) + (b * s[i].GetHashCode()); 
     } 
    } 

    return H; 
} 


static void Main(string[] args) 
{ 
    Console.WriteLine(Hash("abcdef".ToCharArray())); 
    Console.WriteLine(Hash("bcdefa".ToCharArray())); 
    Console.WriteLine(Hash("cdefab".ToCharArray())); 
    Console.WriteLine(Hash("cdfeab".ToCharArray())); 
} 

La salida es:

4587590 
4587590 
4587590 
7077996 

Answer 5

he hecho algo como esto para un proyecto en la universidad. Hubo dos enfoques que utilicé para tratar de optimizar un problema de Viajero-Vendedor. Creo que si no se garantiza que los elementos sean únicos, la segunda solución requeriría un poco más de comprobación, pero la primera debería funcionar.

Si puede representar la cadena como una matriz de asociaciones para abcdef se vería como

a b c d e f 
a x 
b  x 
c  x 
d   x 
e   x 
f x 

Pero también lo haría con cualquier combinación de esas asociaciones. Sería trivial comparar esas matrices.

---

Otro truco más rápido sería rotar la cuerda para que la "primera" letra sea la primera. Entonces, si tiene el mismo punto de partida, las mismas cadenas serán idénticas.

Aquí hay un código Ruby:

def normalize_string(string) 
    myarray = string.split(//)   # split into an array 
    index = myarray.index(myarray.min) # find the index of the minimum element 
    index.times do 
    myarray.push(myarray.shift)   # move stuff from the front to the back 
    end 
    return myarray.join 
end 

p normalize_string('abcdef').eql?normalize_string('defabc') # should return true 

Answer 6

Aquí está una implementación usando LINQ

public string ToCanonicalOrder(string input) 
{ 
    char first = input.OrderBy(x => x).First(); 
    string doubledForRotation = input + input; 
    string canonicalOrder 
     = (-1) 
     .GenerateFrom(x => doubledForRotation.IndexOf(first, x + 1)) 
     .Skip(1) // the -1 
     .TakeWhile(x => x < input.Length) 
     .Select(x => doubledForRotation.Substring(x, input.Length)) 
     .OrderBy(x => x) 
     .First(); 

    return canonicalOrder; 
} 

asumiendo genérica método de extensión del generador: el uso

public static class TExtensions 
{ 
    public static IEnumerable<T> GenerateFrom<T>(this T initial, Func<T, T> next) 
    { 
     var current = initial; 
     while (true) 
     { 
      yield return current; 
      current = next(current); 
     } 
    } 
} 

muestra:

var sequences = new[] 
    { 
     "abcdef", "bcdefa", "cdefab", 
     "defabc", "efabcd", "fabcde", 
     "abaac", "cabcab" 
    }; 
foreach (string sequence in sequences) 
{ 
    Console.WriteLine(ToCanonicalOrder(sequence)); 
} 

de salida:

abcdef 
abcdef 
abcdef 
abcdef 
abcdef 
abcdef 
aacab 
abcabc 

luego llamar a .GetHashCode() en el resultado si es necesario.

ejemplos de uso si ToCanonicalOrder() se convierte en un método de extensión:

sequence.ToCanonicalOrder().GetHashCode(); 

Answer 7

Una posibilidad es combinar las funciones de hash de todos los desplazamientos circulares de su entrada en una meta-hash que no depende de la orden de las entradas.

Más formalmente, considere

for(int i=0; i<string.length; i++) { 
    result^=string.rotatedBy(i).hashCode(); 
} 

Dónde podría reemplazar el^= con cualquier otra operación conmutativa.

Más examply, considere la entrada

"ABCD"

para obtener el hash tomamos

almohadilla ("ABCD")^almohadilla ("dabc")^almohadilla ("CDAB")^hash ("bcda").

Como podemos ver, tomar el hash de cualquiera de estas permutaciones solo cambiará el orden en que está evaluando el XOR, lo que no cambiará su valor.

Answer 8

¿Quizás use un hash rodante para cada desplazamiento (como RabinKarp) y devuelva el valor mínimo de hash? Sin embargo, podría haber colisiones.