Festplattenbasierter Trie?

Question

Ich versuche, ein Trie aber auf einem Handy zu bauen, das sehr begrenzte Speicherkapazität hat.

Ich dachte, dass es wahrscheinlich am besten ist, dass die gesamte Struktur auf der Festplatte gespeichert und nur bei Bedarf geladen wird, da ich ein paar Disk-Lesevorgänge tolerieren kann. Aber nach ein paar Versuchen scheint das eine sehr komplizierte Sache zu sein.

Welche Möglichkeiten gibt es, ein Trie auf Festplatte zu speichern (d. H. Nur teilweise geladen) und die Fast-Lookup-Eigenschaft beizubehalten?
Ist das überhaupt eine gute Idee?

Answer 1

Das Papier B-tries for disk-based string management beantwortet Ihre Frage.

Es macht die Beobachtung:

Unseres Wissens gibt es noch einen Vorschlag in der Literatur für eine Trie-basierte Datenstruktur, wie der Burst-trie sein muss, die effizient auf der Festplatte befinden können um gängige String-Verarbeitungsaufgaben zu unterstützen.

Answer 2

Ich habe es nur kurz angeschaut, aber Shang's "Trie methods for text and spatial data on secondary storage" diskutiert paged Trie-Darstellungen, und könnte ein nützlicher Ausgangspunkt sein.