將Trie編碼爲一個文件以避免重建

我已經構建了一個具有大約180,000個字的字典中約400,000個節點的Trie。問題在於，我的手機上建立的時間太長。將Trie編碼爲一個文件以避免重建

所以我決定創建一次trie並將其以某種格式存儲到磁盤，以便在需要時進行快速重新創建。但我無法想出一個好的格式來存儲它。

什麼是編碼trie最有效的格式，以便它可以儘快從文件重建？

2013-09-25 Bruce

如果你的Trie數據結構實現了可串行化，那麼寫入文件和從文件寫入應該是相當直接的。 Java將負責文件表示。

請參閱link。

2013-09-25 23:04:48 Justin

哇。我不能相信我昨天剛剛學習了Serializable Java類 - 而且我沒有想到要使用它。謝謝，我會試試看！ – Bruce

嗨，它的工作原理，但它真的很慢。我沒有使用任何覆蓋來實現我自己的序列化 - 所以我不確定它是否可以做得更快。我爲此發佈了一個新問題。 – Bruce

順便說一句，這有幫助，upvoted！ – Bruce

也許是個好主意 - 在位置無關的代碼中試圖保存在內存緩衝區中，並通過mmap（）將它讀入內存。這大多是使用「冷啓動」中的trie工作的快速方式。

另外，也許你可以保持數據不在嘗試，但在哈希表。通過這種方法，你可以只在內存中保留「桶索引」，這是非常小的。並且，當從文件計算hash-pread（）桶到內存中時，並在加載的部分中搜索。

2013-09-25 19:34:41 maxihatop

恐怕內存緩衝區操作是不可能的，因爲我使用的是Java。另外，對於我的具體應用，嘗試對於速度來說絕對是關鍵。 – Bruce

布魯斯比嘗試更迅速。看到我的自動完成演示在這裏：http：//olegh.cc.st/autocomplete.html它適用於機器英特爾賽揚-300MHz，256MB總RAM。實時快速找到建議 - 嘗試玩字典「域名」，包含380,000條目 - 比您的字典多出兩倍。 – maxihatop

實際上，我做了數以千計的檢查，看看字符串是否是字典中任何字符串的前綴，這就是爲什麼我需要一個前綴樹，如trie。 – Bruce

回答