Implementieren Sie Trie in Java auf eine speichereffiziente Weise

Question

Ich muss eine 10 GB-Datei lesen und herausfinden, die häufigsten Sätze in der Datei. Ich lese die Datei in Chunks mit einem Scanner und speichert die Phrasen in einer Trie Datenstruktur. Ich werde die Sätze später durchsuchen, um ihre Zählung zu aktualisieren und habe daher die Trie-Datenstruktur für eine effiziente Suche verwendet. Ich habe die Trie mit Hashmap in Java implementiert, wie unten gezeigt.

class TrieNode { 
     char data; 
     Map<Character, TrieNode> children = new HashMap<>(); 
     boolean isLeafNode; 
     int positionMinHeap = -1; 
     int frequency; 

     TrieNode() { 

     } 

     TrieNode(char data) { 
      this.data = data; 
     } 

    } 

Aber diese Lösung braucht viel Platz im Heap. Und wenn alle Phrasen in der Datei unterschiedlich sind, würde die Trie sehr viel Speicherplatz beanspruchen. Gibt es eine andere Möglichkeit, wie ich Trie auf speichereffiziente Weise implementieren kann?

Answer 1

Wenn Sie keine Angst vor ein wenig C++ - und JNI-Bindungen haben, hätten Sie mehr Möglichkeiten für optimierte Lösungen. Ich würde vorschlagen, marisa-trie, um zu versuchen:

https://github.com/s-yata/marisa-trie/tree/master

Ich habe versucht, einige andere Bibliotheken vor einer Weile (leider erinnere ich mich nicht mit dem anderen jetzt) ​​und für mein Datensatz marisa- trie hatte im Vergleich zu anderen C++ - Trie-Bibliotheken eine sehr gute Balance zwischen Performance und Speichernutzung.

Sie könnten auch von der speicherprogrammierten IO-Schnittstelle profitieren, wenn Ihre Daten größer werden (natürlich durch Abstriche bei der Leistung).