Esiste una funzione di hash circolare?

Question

Pensando a questo question on testing string rotation, mi chiedevo: esiste una funzione di hash circolare/ciclica? Per esempio.

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

usi per questo includono algoritmi scalabili in grado di controllare n stringhe contro l'altro per vedere dove alcuni sono rotazioni degli altri.

Suppongo che l'essenza dell'hash sia estrarre informazioni specifiche per l'ordine ma non specifiche della posizione. Forse qualcosa che trova una "prima posizione" deterministica, ruota ad esso e blocca il risultato?

Tutto sembra plausibile, ma leggermente al di là della mia presa in questo momento; deve essere già là fuori ...

Answer 1

Vorrei andare con la tua "prima posizione" deterministica - trovare il carattere "minimo"; se appare due volte, usa il prossimo carattere come tie breaker (etc). È quindi possibile ruotare su una posizione "canonica" e cancellarlo in un modo normale. Se i tie breaker corrono per l'intero corso della stringa, allora hai una stringa che è una rotazione di se stessa (se vedi cosa intendo) e non importa quale scegli di essere "primo".

Quindi:

"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

Si potrebbe trovare una prima posizione deterministico da sempre a partire dalla posizione con il "più basso" (in termini di ordine alfabetico) stringa. Quindi nel tuo caso, inizi sempre da "a". Se ci fossero più "a", dovresti tenere conto di due caratteri.

Answer 3

Sono sicuro che potresti trovare una funzione che può generare lo stesso hash indipendentemente dalla posizione dei caratteri nell'input, tuttavia, come farai a garantire che h(abc)! = h(efg) per ogni input immaginabile? (Si verificheranno collisioni per tutti gli algoritmi hash, quindi, come si riduce questo rischio.)

Avresti bisogno di alcuni controlli aggiuntivi anche dopo aver generato l'hash per assicurarti che le stringhe contengano gli stessi caratteri.

Answer 4

Aggiornamento: Come ha sottolineato Jon, il primo approccio non gestisce molto bene le stringhe con ripetizione. I problemi sorgono quando si incontrano coppie di lettere duplicate e lo XOR risultante è 0. Ecco una modifica che credo corregge l'algoritmo originale. Utilizza Euclid-Fermat sequences per generare interi coprimi paralleli per ogni occorrenza aggiuntiva di un carattere nella stringa. Il risultato è che lo XOR per coppie duplicate è diverso da zero.

Ho anche ripulito leggermente l'algoritmo. Si noti che l'array contenente le sequenze EF supporta solo caratteri nell'intervallo da 0x00 a 0xFF. Questo era solo un modo economico per dimostrare l'algoritmo. Inoltre, l'algoritmo ha ancora il tempo di esecuzione O (n) dove n è la lunghezza della stringa.

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")); 
} 

L'uscita è ora:

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

---

Prima versione (che non è completa): Usare XOR che è commutativa (ordine non importa) e un altro piccolo trucco coinvolgere coprimi per combinare gli hash ordinati di coppie di lettere nella stringa.Ecco un esempio in 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())); 
} 

L'output è:

4587590 
4587590 
4587590 
7077996 

Answer 5

ho fatto qualcosa di simile per un progetto in un college. C'erano 2 approcci che ho usato per cercare di ottimizzare un problema Travelling-Salesman. Penso che se gli elementi NON sono garantiti come unici, la seconda soluzione richiederebbe un po 'più di controllo, ma il primo dovrebbe funzionare.

Se si riesce a rappresentare la stringa come una matrice di associazioni in modo abcdef sarebbe simile

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

Ma lo farebbe con qualsiasi combinazione di tali associazioni. Sarebbe banale confrontare quelle matrici.

---

Un altro trucco più rapido sarebbe quello di ruotare la stringa in modo che la "prima" lettera sia la prima. Quindi se hai lo stesso punto di partenza, le stesse stringhe saranno identiche.

Ecco del codice vermiglio:

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

Ecco un'implementazione utilizzando 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; 
} 

assumendo generico metodo di estensione generatore: Utilizzo

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); 
     } 
    } 
} 

campione:

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

uscita:

abcdef 
abcdef 
abcdef 
abcdef 
abcdef 
abcdef 
aacab 
abcabc 

quindi richiamate .GetHashCode() sul risultato se necessario.

esempio dell'uso se ToCanonicalOrder() viene convertito in un metodo di estensione:

sequence.ToCanonicalOrder().GetHashCode(); 

Answer 7

Una possibilità è quella di combinare le funzioni di hash di tutti i turni circolari del vostro ingresso in una meta-hash, che non dipende dalla ordine degli input.

Più formalmente, considerano

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

Dove si potrebbe sostituire il^= con qualsiasi altra operazione commutativa.

Più examply, prendere in considerazione l'ingresso

"ABCD"

per ottenere l'hash prendiamo

hash ("ABCD")^hash ("DABC")^hash ("CDAB")^hash ("bcda").

Come possiamo vedere, prendere l'hash di una qualsiasi di queste permutazioni cambierà solo l'ordine in cui si sta valutando lo XOR, che non cambierà il suo valore.

Answer 8

Forse utilizzare un hash rolling per ogni offset (come RabinKarp) e restituire il valore hash minimo? Ci potrebbero essere collisioni però.