String的HashSet佔用太多內存，建議......？

我目前在HashSet中存儲了一個單詞列表（大約120,000），目的是作爲一個列表來檢查反對的單詞是否拼寫正確，然後返回yes或no。String的HashSet佔用太多內存，建議......？

我想知道是否有辦法做到這一點，佔用更少的內存。目前120,000字大約是12meg，實際文件的讀取字數大約是900kb。

有什麼建議嗎？

在此先感謝

來源

2010-07-12 Dori

你怎麼知道數據結構是12MB？ – 2010-07-12 11:34:19

僅僅通過編寫一個小測試類 – Dori 2010-07-12 11:36:25

檢查布盧姆過濾器或杜鵑哈希。 Bloom filter or cuckoo hashing?

我不確定這是否是您的問題的答案，但值得研究這些替代方案。布隆過濾器主要用於拼寫檢查類的用例。

來源

2010-07-12 12:51:27

或http://stackoverflow.com/questions/2294915/what-algorithm-is-used-to-give-suggestions-in-a-spell-checker/2294926#2294926 – 2010-07-12 13:54:16

它認爲綻放哈希聲很好，因爲我可以應付在每個條目20b左右有0.01％的假陽性率，相當於我的100k單詞列表中的200Kb，這是一個巨大的改進。謝謝！（現在會讀取杜鵑哈希） – Dori 2010-07-13 10:41:11

找到了開源的Java Bloom Filter http://code.google.com/p/java-bloomfilter/ – Dori 2010-07-13 11:33:28

你可以使用一個前綴樹或特里：http://en.wikipedia.org/wiki/Trie

來源

2010-07-12 11:35:49 sandris

只需尋找任何trie或DAWG代碼，我就可以使用...！ – Dori 2010-07-12 11:47:00

我嘗試過從http：//forums.sun實施trie代碼。com/thread.jspa？threadID = 5295936，底部有額外的建議，它在31meg時大了3倍，這是怎麼回事？ – Dori 2010-07-12 12:35:43

乍一看，children = new TrieNode[26];行似乎不合理，它總是爲所有潛在的孩子分配記憶。 – sandris 2010-07-12 13:44:59

HashSet可能是不適合這個合理的結構。改爲使用Trie。

來源

2010-07-12 11:40:01

的問題是由設計：在一個HashSet存儲的話如此龐大的拼寫檢查 - 原因是不是一個好主意：

您可以使用拼寫檢查（例如：http://softcorporation.com/products/spellcheck/），或者你可以用一個前綴樹（描述：http://en.wikipedia.org/wiki/Trie）構建一個「auto-wordcompletion」。

無法在此設計中減少內存使用量。

來源

2010-07-12 11:40:13 Erik

節省內存以節省內存的一種方法是使用radix tree。這比trie好，因爲前綴不會被冗餘存儲。

由於你的字典是固定的，另一種方法是爲它建立一個完美的散列函數。你的哈希集不需要桶（和相關的開銷），因爲不會有衝突。每個使用open addressing的哈希表/哈希集的實現都可以用於此（如谷歌收集的ImmutableSet）。

來源

2010-07-12 11:45:44

你也可以試試Radix Tree（Wiki,Implementation）。這個有些像trie什麼的，但是內存效率更高。

來源

2010-08-03 06:33:18 Emil

這可能有點晚，但使用Google，您可以輕鬆找到前段時間發佈的DAWG調查和C代碼。

http://www.pathcom.com/~vadco/dawg.html

TWL06 - 178691字 - 融入494676個字節

壓縮共享節點的結構的缺點是，它不爲你的列表中的單詞的哈希函數工作。也就是說，它會告訴你一個單詞是否存在，但是它不會爲一個存在的單詞返回相關數據的索引。

如果您想要在處理器高速緩存大小的結構中完美和完整的散列功能，您將必須閱讀，理解和修改名爲ADTDAWG的數據結構。它會比傳統的DAWG稍大，但速度更快，更實用。

http://www.pathcom.com/~vadco/adtdawg.html

一切順利，

JohnPaul Adamovsky

來源

2010-09-03 18:40:06

12MB存儲12萬個字是每字約100個字節。可能至少有32個字節是字符串開銷。如果單詞平均爲10個字母，並且它們存儲爲2個字節的字符，則佔用另外20個字節。然後是HashSet中每個字符串的引用，這可能是另外4個字節。其餘的44個字節可能是HashSet條目和索引開銷，或者我上面沒有考慮的東西。

最簡單的事情就是String對象本身的開銷，它可能比存儲實際的字符數據需要更多的內存。所以你的主要方法是開發一個自定義表示，避免爲每個字符串存儲一個單獨的對象。在這樣做的過程中，您還可以擺脫HashSet開銷，因爲您真正需要的只是簡單的單詞查找，可以通過對數組進行簡單的二進制搜索來完成，這將成爲您的自定義實現的一部分。

您可以將您的自定義實現創建爲類型爲int的數組，每個單詞包含一個元素。這些int元素中的每一個都會被分成包含長度和偏移量的子字段，並指向char類型的單獨支持數組。將它們放入一個管理它們的類中，並且支持公共方法，允許您在給定字符串索引和可選字符索引的情況下檢索和/或轉換數據和單個字符，並對單詞列表執行簡單搜索這是您的拼寫檢查功能所需的。

如果底層字符串數據的字符數不超過16777216（例如，平均長度爲10個字符的120,000個字符串= 120萬個字符），則可以取每個int的低24位，並將起始將每個字符串偏移到char數據的後備數組中，並取每個int的高位8位並在其中存儲相應字符串的大小。

你的char數據會將你的舊字符串擠在一起而沒有任何分隔符，完全依賴int數組來知道每個字符串的開始和結束位置。

採取上述方法，您的120,000字（平均每個10個字母）將需要大約2,400,000字節的後備陣列數據和480,000字節的整數索引數據（120,000 x 4字節），總共2,880,000字節，與上面報告的目前的12MB數量相比，可節省大約75％的費用。

數組中的單詞將按字母順序排序，並且您的查找過程可能是對int數組的簡單二分搜索（從每個測試的char數組中檢索相應單詞），這應該非常有效。

如果您的文字碰巧完全是ASCII數據，您可以通過將備份數據存儲爲字節而不是字符來保存額外的1,200,000字節。

如果您需要更改這些字符串，這可能會變得更加困難。很顯然，在你的情況下（拼寫檢查器），你不需要（除非你想支持用戶添加到列表中，而這將不經常發生，所以重寫char數據和索引來添加或刪除單詞可能會可以接受）。

來源

2012-03-12 09:21:07 Carl

String的HashSet佔用太多內存，建議......？

回答

相關問題