將trie保存到磁盤

這聽起來像一個簡單的問題，但我不知道如何搜索它的答案。將trie保存到磁盤

我在C＃中有一個trie實現，它將從字典文件中存儲大約80K個字。加載所有這些單詞需要相當長的時間（超過5分鐘）。我想知道，「堅持」這些數據的最佳方法是什麼，所以我不必每次啓動應用程序時重新加載所有的單詞？

謝謝。

2010-09-20 Dervin Thunk

由於我們沒有代碼，因此我們要根據您的情況對其進行配置，至少足以確定瓶頸的位置。 – 2010-09-20 01:46:59

我發現很難相信，只需要五分鐘來填充只包含80,000個單詞的trie。我的實現在大約60毫秒內插入「0」到「999999」。在這種情況下，我會簡單地保存單詞的原始列表並根據需要重新創建這個單詞。 – Rafe 2010-09-20 05:17:21

你的特里算法聽起來對我來說很重要。在5分鐘內，您可以運行80k^2〜= 6.4G的字符串操作，而不會有太多的麻煩，這表明您的「trie」表現得像鏈表一樣。 – 2010-09-20 05:43:33

與所有其他性能問題一樣，理想的解決方案將通過分析您當前的解決方案和您提出的其他候選解決方案進行分析。瓶頸在哪裏？ I/O？閱讀文本？在樹中形成鏈接？如果不知道您的績效目標，目前存在的使用情況和瓶頸的性質，很難制定一個具體的建議。

要考慮的問題：

存儲格式：文字？二進制？
保留的數據：trie的整個結構（例如XML）還是隻是一個單詞列表，依賴運行時代碼將它們推送到數據結構中的正確位置？標記數據比例是多少？它有多重要解析？
存儲位置：DB/flat-file/...？
增量加載：可能嗎？

一種可能的策略：用最常用的1,000個單詞創建並保留一個「最常見單詞」字典。在啓動時將這些單詞加載到trie中，並在另一個線程上產生全字典的加載;隨着新單詞被讀取，逐漸添加到創建的單詞樹中。

優點：用戶將看到更快的啓動時間。
缺點：可能需要跨線程同步，用戶將看到一個不完整trie，直到加載完全是。這可能是也可能不是一個showstopper，取決於使用的是什麼。

來源

2010-09-20 01:39:38 Ani

我最近重構了一個類似的數據結構，由於性能低下，序列化/反序列化時間很慢。

我的解決方案是完全廢除trie，並與本地.NET集合 - 字典和查找。

我正在用約400k字。從內存開始，構建數據結構需要大約5秒的時間，這是一系列由多個字典和查找索引的對象列表。

結構的頂層是一個 Dictionary<int, var>其中關鍵爲n - 在搜索詞的字母數。
在詞典裏，每個值是Lookup<string, string>其中關鍵是一個字符串與N個字母，並且該值是所有字符串以該字符串開始。 e。g的關鍵'st'值可能是 'start'，'stop'和'string'。

要創建數據結構，只需遍歷整個i = 1到maxlength的單詞列表，爲每個i創建一個查看所有不同'開始'的字符串。將這些插入到頂級字典中即可完成。

這消除了對定製的trie的需求。我發現性能差異（搜索時間）是微不足道的，但加載速度非常有利於我的設計（更不用說使用簡單.NET類型的簡單性和可維護性）。

來源

2010-09-20 02:10:49

我意識到這並不能真正回答你如何序列化的問題，但我強烈建議你重新考慮自定義trie。這個解決方案需要不到一個小時的時間來執行，而且根據我的經驗 - 性能要高得多。 – 2010-09-20 02:13:48

我只是以舊的MFC二進制方式序列化它。基本上，閱讀/寫作應該儘可能快，唯一留下的就是分配和初始化輸入結構，無論如何你需要這樣做。

也就是說，序列化特里結構的一個節點，你這樣做：

Read/Write number N of subnodes 
For each subnode 
    If reading, allocate a subnode in this node 
    Read/Write the character for the subnode 
    Serialize the subnode 
End

編輯：剛纔重讀你的問題，你想從單詞表從頭開始構建的線索？正如其他人所說，簡介，但不只是與任何舊的配置文件。他們並不都能找到你的問題。 Here's what I do.花費的時間不應該超過讀取文件所花費的時間以及創建結構所花費的時間。

來源

2010-09-20 16:25:49

將trie保存到磁盤

回答

相關問題