Ermittlung von Änderungen in zufälligem geordneten Eingang (Hash-Funktion?)

StackOverflow https://stackoverflow.com/questions/64209

  •  09-06-2019
  •  | 
  •  

Frage

ich Textzeilen zu lesen, die in beliebiger Reihenfolge kommen. Das Problem ist, dass der Ausgang tatsächlich indentical zum vorherigen ausgegeben werden kann. Wie kann ich dies erkennen, ohne die Ausgabe ersten Sortierung?

Gibt es irgendeine Art von Hash-Funktion, die identischen Eingang nehmen kann, aber in beliebiger Reihenfolge, und immer noch das gleiche Ergebnis?

War es hilfreich?

Lösung

Der einfachste Weg, um jede Zeile auf dem Weg zu sein scheint, in Hash, die Hash-Speicherung und die ursprünglichen Daten, und vergleichen Sie dann jeden neuen Hash mit Ihrer Sammlung von bestehenden Hashes. Wenn Sie eine positive bekommen, könnten Sie die aktuellen Daten zu vergleichen, um sicherzustellen, dass es nicht um einen Fehlalarm - obwohl dies äußerst selten sein würde, Sie mit einem schnelleren Hash-Algorithmus, wie MD5 oder CRC (anstatt etwas wie SHA gehen könnte, die nur so schnell kollidieren ist langsamer, aber weniger wahrscheinlich), es ist, und dann die eigentlichen Daten vergleichen, wenn Sie einen Treffer erhalten.

Andere Tipps

Sie haben also Eingabe wie 

A B C D
D E F G
C B A D

und Sie müssen erkennen, dass die erste und dritte Zeile identisch sind?

Wenn Sie herausfinden möchten, ob zwei Dateien mit dem gleichen Satz von Zeilen enthalten, aber in einer anderen Reihenfolge, können Sie eine regelmäßige Hash-Funktion auf jede Zeile einzeln verwenden, dann verbinden sie mit einer Funktion, bei Bestellung keine Rolle spielt, wie Addition.

Wenn die Linien ziemlich lang sind, könnten Sie halten nur eine Liste der Hash-Werte jeder Zeile -. Sortieren diese und vergleichen mit früheren Ausgaben

Wenn Sie nicht 100% narrensichere Lösung benötigen, können Sie den Hash jeder Zeile gespeichert werden in einem Bloom-Filter (es auf Wikipedia nachschlagen) und die Bloom-Filter am Ende der Verarbeitung vergleichen. Dies können Sie Fehlalarme geben (das heißt Sie denken, Sie die gleiche Leistung haben, aber es ist nicht wirklich das gleiche), aber sie kann durch Einstellen der Größe des Bloom-Filter, die Fehlerrate zwicken ...

Wenn Sie die ASCII-Werte der einzelnen Zeichen addieren, würden Sie das gleiche Ergebnis unabhängig von der Reihenfolge.

(Dies kann ein bisschen sein zu vereinfacht, aber vielleicht funkt es eine Idee für Sie. Siehe Programmierung von Perlen, Abschnitt 2.8, für eine interessante Geschichte zurück.)

Jeder der Hash-basierte Verfahren können schlechte Ergebnisse produzieren, weil mehr als eine Zeichenfolge, die den gleichen Hash erzeugen kann. (Es ist nicht wahrscheinlich, aber es ist möglich.) Das gilt insbesondere für den Vorschlag, die Hash-Werte hinzuzufügen, da Sie im Wesentlichen nehmen würden ein besonders schlecht Hash der Hash-Werte.

Eine Hash-Methode nur dann versucht werden soll, wenn es nicht entscheidend ist, dass Sie eine Änderung verpassen oder eine Änderung erkennen, wo keiner vorhanden ist.

Die genaueste Methode wäre, eine Karte zu halten, um die Linie Strings als Schlüssel verwendet und die Anzahl der jeweils als Wert zu speichern. (Wenn jeder Zeichenfolge nur einmal vorkommen kann, brauchen Sie nicht die Zählung.) Berechnen Sie dies für die erwartete Menge von Linien. Duplizieren Sie diese Sammlung, die eingehenden Leitungen zu prüfen, für jede Zeile der Zählung zu reduzieren, wie Sie es sehen.

  • Wenn Sie eine Linie mit einer Nullzählung (oder gar keine MapEintrag überhaupt) begegnen, haben Sie eine Linie gesehen Sie haben nicht erwartet.
  • Wenn Sie dies mit Nicht-Null-Einträge in der Karte verbleibende Ende, hast du nicht sehen, was Sie erwartet.

Nun das Problem Spezifikation ist ein bisschen eingeschränkt.

Wie ich es verstehe Sie wollen sehen, ob mehrere Strings die gleichen Elemente unabhängig von der Reihenfolge enthalten.

Zum Beispiel: 

A B C
C B A

sind gleich.

Die Art und Weise, dies zu tun ist, einen Satz der Werte erstellen dann die Sätze vergleichen. So erstellen Sie ein Set: 

HashSet set = new HashSet();
foreach (item : string) {
   set.add(item);
}

Dann vergleichen Sie einfach den Inhalt der Sätze, indem er durch einen der Sätze laufen und es w / anderen zu vergleichen. Die Ausführungszeit O(N) statt O(NlogN) für das Sortier Beispiel wird.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top