Ich habe eine 40 MB (zu groß für den Speicher in diesem Fall) Liste der Zeichenfolgen, die ich tun möchte "beginnt mit" Abfragen an, um Übereinstimmungen zu extrahieren. Wer kennt eine gute Datenstruktur dafür? Bonuspunkte für eine bestehende os Java-Implementierung. Ich wäre bereit zu opfern "beginnt mit", um genau zu entsprechen, wenn etwas bereits existiert. Ein Laufwerk-basierter Trie klingt ideal.Ultra-schnelle "Beginnt mit" Abfrage von der Festplatte
Es sieht aus wie Sie so etwas wie dieses benötigen: http://en.wikipedia.org/wiki/Trie
Eine Implementierung in Java here gefunden werden kann, obwohl es nicht Disk-basierte ist. Ich werde weitersuchen:/
Nützliche Papiere: Trie methods for text and spatial data on secondary storage, B-tries for disk-based string management
Edit: Ich habe dies könnte dies nützlich sein könnte: MG4J: Managing Gigabytes for Java™
Kann keine vorhandene Bibliothek vorschlagen, aber ich behandeln ähnlich Problem vorher. Es ist ziemlich einfach, wenn Sie nicht vorhaben, Ihre Liste dynamisch zu ändern und Strings in der Datei zu sortieren (für die binäre Suche).
Lassen Sie uns Ihre 40Mb in 1000 Chunks von ungefähr gleicher Größe zerlegen und die erste Zeichenfolge von jedem Chunk im Speicher behalten. Das wäre eine Anordnung von 1000 Saiten. Sie sind bestellt, weil die ursprüngliche Liste geordnet ist.
Wenn Sie eine Abfrage ausführen müssen, können Sie die binäre Suche für dieses Array verwenden. Dies zeigt Ihnen, in welcher Chunk-Ergebnis-Zeichenfolge liegt. Dann können Sie diesen Chunk von der Festplatte lesen (ca. 40kb) und in seinem Inhalt suchen. Wenn z. B. das Array die Werte ["andrew", "brian", "donald", "john"] enthält und Sie nach dem Präfix "cris" suchen, wissen Sie, dass alle Cristophers und Cristians im zweiten Chunk sind.
Haben die Saiten die gleiche Länge? Wäre das Auffüllen auf die längste Länge ein Problem? – thejh
Was ist die Struktur/Architektur der Quelle der Strings? Ist es eine 40gb Zeile getrennte Textdatei? ist das für die Spam-Produktion? ;) – pstanton
Es ist nur 40 mb nicht GB und sie sind einzelne Begriffe. Es ist im Grunde nur für eine super schnelle Existenzprüfung für einen Begriff (<40 Zeichen). Ich könnte sogar sql oder lucene dafür verwenden, aber da die Daten statisch sein werden, nehme ich an, dass ich es viel besser machen könnte. – ghempton