Gibt es eine zirkuläre Hash-Funktion?

Question

Nachdenken über diese question on testing string rotation, fragte ich mich: Gab es so etwas wie eine zirkuläre/zyklische Hash-Funktion? Z.B.

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

Verwendungen für diese skalierbare Algorithmen enthalten, die n Saiten gegeneinander überprüfen, um zu sehen, wo einige Drehungen andere.

Ich nehme an, die Essenz des Hash ist, um Informationen zu extrahieren, die auftragsspezifisch, aber nicht positionsspezifisch sind. Vielleicht dreht sich etwas, das eine deterministische "erste Position" findet, darauf und hasht das Ergebnis?

Es scheint alles plausibel, aber im Moment etwas außer Reichweite; es muss schon da draußen sein ...

Answer 1

Ich würde mit deiner deterministischen "ersten Position" gehen - finde das "kleinste" Zeichen; Wenn es zweimal angezeigt wird, verwenden Sie das nächste Zeichen als Tieferbrecher (usw.). Sie können dann zu einer "kanonischen" Position rotieren und diese normal hashen. Wenn die Tie Breaker für den gesamten Verlauf der Saite laufen, dann haben Sie eine Saite, die eine Rotation von sich selbst ist (wenn Sie sehen, was ich meine) und es ist egal, welche Sie wählen, um "zuerst" zu sein.

So:

"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

Sie eine deterministische ersten Position, indem sie immer an der Stelle mit dem „niedrigsten“ (im Sinne der alphabetischer Reihenfolge) Teilzeichenfolge Ausgangs finden konnten. In deinem Fall würdest du immer bei "a" anfangen. Wenn es mehrere "a" s gäbe, müssten Sie zwei Zeichen berücksichtigen usw.

Answer 3

Ich bin sicher, dass Sie eine Funktion finden können, die unabhängig von der Zeichenposition in der Eingabe den gleichen Hash generieren kann. Wie stellen Sie sicher, dass h(abc)! = h(efg) für jeden erdenklichen Eingang? (Kollisionen werden für alle Hashalgorithmen auftreten, also wie minimieren Sie dieses Risiko.)

Sie würden einige zusätzliche Überprüfungen benötigen, auch nachdem Sie den Hash generiert haben, um sicherzustellen, dass die Zeichenfolgen dieselben Zeichen enthalten.

Answer 4

Update: Wie Jon darauf hingewiesen hat, behandelt der erste Ansatz Strings mit Wiederholung nicht sehr gut. Probleme treten auf, wenn doppelte Buchstabenpaare auftreten und das resultierende XOR 0 ist. Hier ist eine Modifikation, von der ich glaube, dass sie den ursprünglichen Algorithmus korrigiert. Es verwendet Euclid-Fermat sequences, paarweise Koprime-Ganzzahlen für jedes weitere Auftreten eines Zeichens in der Zeichenfolge zu generieren. Das Ergebnis ist, dass das XOR für doppelte Paare nicht Null ist.

Ich habe auch den Algorithmus etwas aufgeräumt. Beachten Sie, dass das Array, das die EF-Sequenzen enthält, nur Zeichen im Bereich 0x00 bis 0xFF unterstützt. Dies war nur eine billige Möglichkeit, den Algorithmus zu demonstrieren. Außerdem hat der Algorithmus noch die Laufzeit O (n), wobei n die Länge der Zeichenfolge ist.

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

Der Ausgang ist jetzt:

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

---

Erste Version (das ist nicht vollständig): Verwendung XOR, die (egal Reihenfolge) und ein anderer kleiner Trick kommutativ mit Koprime kombinieren geordnete Hashes von Buchstabenpaaren in der Zeichenfolge.Hier ist ein Beispiel 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())); 
} 

Die Ausgabe lautet:

4587590 
4587590 
4587590 
7077996 

Answer 5

Ich habe so etwas wie dies für ein Projekt in der Schule. Es gab zwei Ansätze, mit denen ich versuchte, ein Traveling-Salesman-Problem zu optimieren. Ich denke, wenn die Elemente NICHT garantiert einzigartig sind, würde die zweite Lösung ein wenig mehr Überprüfung erfordern, aber die erste sollte funktionieren.

Wenn Sie die Zeichenfolge als eine Matrix von Verbänden darstellen kann so abcdef würde aussehen wie

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

Aber würde so eine beliebige Kombination von diesen Verbänden. Es wäre trivial, diese Matrizen zu vergleichen.

---

Ein weiterer schneller Trick wäre, die Zeichenfolge zu drehen, so dass der "erste" Buchstabe zuerst ist. Wenn Sie denselben Startpunkt haben, sind die gleichen Strings identisch.

Hier einige Code in 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

eine Implementierung

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

vorausgesetzt Verfahren generic Generator Erweiterung mit Linq hier:

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

Anwendungsbeispiel:

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

output:

abcdef 
abcdef 
abcdef 
abcdef 
abcdef 
abcdef 
aacab 
abcabc 

dann .GetHashCode() aufrufen, auf das Ergebnis, wenn nötig.

Probe Nutzungs wenn ToCanonicalOrder(), um eine Erweiterungsmethode umgewandelt wird:

sequence.ToCanonicalOrder().GetHashCode(); 

Answer 7

Eine Möglichkeit ist es, die Hash-Funktionen aller Kreisverschiebungen Ihrer Eingabe in einer Meta-Hash zu kombinieren, die nicht auf das abhängt Reihenfolge der Eingänge.

formal betrachten

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

Wo Sie die^= mit jeder anderen kommutativen Operation ersetzen könnten.

Mehr examply, sollten Sie die Eingabe

"ABCD"

den Hash bekommen wir nehmen

Hash ("abcd")^Hash ("DABC")^Hash ("CDAB")^hash ("bcda").

Wie wir sehen können, wird der Hash einer dieser Permutationen nur die Reihenfolge ändern, in der Sie das XOR evaluieren, was seinen Wert nicht ändert.

Answer 8

Vielleicht verwenden Sie einen rollenden Hash für jeden Offset (RabinKarp like) und geben Sie den minimalen Hash-Wert zurück? Es könnte jedoch Kollisionen geben.