Runtime Efficient Algorithm, um String-Kollision mit begrenztem Speicher zu überprüfen

Question

Ich habe eine große, aber endliche Reihe von Strings und es ist sehr unwahrscheinlich, dass zwei dieser Strings identisch sind, aber genau das möchte ich überprüfen. Alle Strings haben ungefähr die gleiche Länge +/- 1 Zeichen.

Nehmen wir als Beispiel (aber die Zahlen können sich ändern), habe ich eine Reihe von 30 Milliarden Strings, jeder etwa 30 Zeichen lang. In einem naiven Ansatz würde ich alle in einen Hash stopfen und nach Kollisionen suchen. Das wäre praktisch O (n) Laufzeit.

Da Speicher der limitierende Faktor ist und ich keine Möglichkeit habe, alle Strings in den Speicher zu stopfen, muss ich den Datensatz partitionieren. Nehmen wir an, ich kann 100 Millionen Strings in den Speicher stopfen und eine andere Zeichenfolge im Vergleich zu diesen 100 Millionen ist im Grunde O (1) Laufzeit.

Wie würde mein effizienter Algorithmus (in Bezug auf die Laufzeit) aussehen?

Answer 1

Wenn Sie N Saiten haben und Sie können k in Erinnerung behalten, dann müssen Sie N/k Partitionen haben und jede Saite wird nur einmal, sondern im Vergleich N/k - 1 mal gehasht werden. Daher muss die Komplexität O(N^2/k) sein.