Ich entwickle ein Stück Software, das doppelten kleinen Text überprüfen muss (normalerweise weniger als 2 kb) verwenden vorberechnete Signatur (4 Bytes). Derzeit habe ich CRC32 (4byte) implementierterreichen diesen Zweck, aber ich vermute, dass CRC32 viele doppelte Werte erzeugt hätte. Ich weiß, dass es unmöglich ist, es wirklich einzigartig zu machen, aber zumindest möchte ich diese Wahrscheinlichkeit minimieren.
- AKTUALISIERUNG 1 -
HINWEIS: Ich kann die Größe der Hash-Bytes nicht erhöhen. Es kostet mich viel Speicher. Ich spreche über Einträge Größe mehr als 1.000.000. zum Beispiel 1.000.000 * 4 Byte = 4.000.000 Bytes. Ich kann MD5 nicht benutzen, weil es 16 Bytes nimmt!
- UPDATE 2 - Ich wollte das ganze Problem nicht öffnen, aber jetzt muss ich es tun.
Mein Projekt ist eine Wörterbuch-Engine, die suchen kanneine Menge unabhängiger Datenbanken, um die vom Nutzer gestellte Phrase zu finden. Alle Ergebnisse müssen sofort vorbereitet werden (Auto-Vervollständigen-Funktion). Alle Textdaten sind komprimiert, so dass ich sie nicht entpacken kann, um die duplizierten Ergebnisse zu überprüfen komprimierter Text in meinem Index. So erhöhen Hash-Bytes die Indexgröße und Datenträger-E / A Indexblöcke lesen, dekomprimieren und decodieren(Indexblöcke werden ebenfalls komprimiert). Die Hash-Werte sind im Allgemeinen nicht komprimierbar. Das Design dieser Software zwang mich, alles zu komprimieren, um die Bedürfnisse des Benutzers zu erfüllen (unter Verwendung von eingebettet Systeme). Jetzt möchte ich doppelten Text aus dem Suchergebnis mit Hash-Werten entfernen, um einen (un) komprimierten Textvergleich zu vermeiden (was in meinem Fall wegen der Festplatten-E / A nicht sinnvoll ist).
Es scheint, dass wir eine benutzerdefinierte Prüfsumme entwerfen können, die die Bedingungen erfüllt. Zum Beispiel speichere ich Textlänge in 2 Bytes und erzeuge 2-Byte-Prüfsumme, um doppelte Möglichkeit zu prüfen?!
Ich schätze jeden Vorschlag im Voraus.
- AKTUALISIERUNG 3 -
Nach vielen Nachforschungen und dank der Informationen, die die Antworten liefern, danke ich euch allen CRC32 ist in meinem Fall gut genug. Ich führte einige statistische Benchmarks auf meinen generierten CRCs durch, nachdem ich die doppelten Werte überprüft hatte, war das Ergebnis zufriedenstellend.
Danke an euch alle.
Ich stimme alle Antworten ab.
Antworten:
3 für die Antwort № 1Ohne weiteres Wissen über small textDas Beste, auf das Sie hoffen können, ist jeder Hashwertgleich wahrscheinlich, und die meisten 2³² 4-Oktett-Werte verwendet. Selbst dann kollidieren Sie eher mit etwa 77000 Texten, geschweige denn mit einer Million. Mit wenigen Ausnahmen (Adler32 fällt mir ein) unterscheiden sich bekannte Hash-Funktionen sehr wenig in der Kollisionswahrscheinlichkeit. (Sie unterscheiden sich in der Schwierigkeit, Kollisionen / gegebene Werte absichtlich und in den Berechnungs- / Schaltungskosten zu erzeugen.)
→ Wählen Sie einen Kompromiss zwischen Kollisionswahrscheinlichkeit und Speicheranforderungen.
Sehen Sie sich einfach an, welche Prüfsummen Sie berechnen möchten Fletcher "s - Adler32 ist sehr ähnlich, hat aber eine erhöhte Kollisionswahrscheinlichkeit bei kurzen Eingaben.
1 für die Antwort № 2
Falls Sie in Hash Kollision geraten, müssen SieÜberprüfen Sie, ob der Text gleich ist. Der beste Weg wäre, zu zählen, wie oft es passiert, dass eine Kollision einige Statistiken macht und wenn es schlecht aussieht, es zu optimieren. Ich habe diese Idee, dass Sie 2 verschiedene Hash-Werte crc32 und md5 (oder Luhn oder was auch immer Sie wollen) erstellen und prüfen Sie auf Gleichheit nur, wenn beide Hashes die gleichen Werte haben.
1 für die Antwort № 3
Ich habe etwas sehr ähnliches in einem meiner Projekte gemacht. In meinem Projekt benutzte ich etwas namens a BLÜHENFILTER , Uhr über die gesamte Sache hier und wie man es implementiert, verringert Bloom-Filter die Chancen von HASH-SAMMLUNGEN massiv dank seiner Verwendung mehrerer HashingAlgorithmen (es ist jedoch möglich, mehrere Hash-Funktionen mit nur einer Hash-Funktion zu simulieren, aber das, wofür wir hier sind.) Probieren Sie es aus !! es hat für mich funktioniert und wird auch für dich funktionieren
Eine tatsächliche Arbeitsimplementierung eines Blütenfilters