時空高效字典實現

我想創造一個空間和時間有效的實現Java中的常見字字典。時空高效字典實現

字典，而不是從AZ排序，將以某種方式將包含字母「A」，「B」等的所有單詞組合在一起。應用程序需要能夠刪除包含用戶輸入的任何字母的所有單詞。因此，如果用戶輸入「L」，則包含「L」的所有單詞都被刪除。

我已經創建：

集< String>的字典 - 存儲所有的話。

地圖<字符，集<字符串>> - 映射字符A到Z各自具有包含所有從字典包含該信詞的集合。

實施例：

dictionary {"AAB", "ABB", "BBC", "BBA", "CBB"}

地圖：

A - "AAB", "ABB", "BBA" 

B - "AAB", "ABB", "BBC", "BBA", "CBB" 

C - "BBC", "CBB"

如果用戶選擇「A」，該組A的，從字典移除和地圖被重建，等待用戶移除另一封信。

我的問題是，這將導致巨大的數據重複和低效。我想不出另一種有效實現這一點的方法。我一直在暗示，樹木可能是解決此問題的方法，但我看不到自己的實現怎麼會在這兩個時間&空間效率更高。

非常感謝您的幫助。

2011-12-09 Palo

似乎是確定的，只是繼續它。沒有重複，因爲所有集合都會引用相同的字符串對象（單詞）。你也可以通過使用Lists而不是Sets來減少開銷。 – unbeli

使用一棵樹，每個數據節點包含它下面的節點列表。你會有一個A節點，它下面有AB，AC，AA和AD。通過這種方法可以屏蔽掉所有A字，只需刪除A節點即可。過濾掉所有的廣告語，刪除廣告節點，等你將不得不編寫這個自己，我相信，但它應該是有效的。 – Sheriff

基數樹？ http://en.wikipedia.org/wiki/Radix_tree – maximdim

聽起來像是你應該使用特里。這是一個非常簡單的樹結構，細節和實施例可以在維基百科中找到：

根據您的需求，您可以使用後綴壓縮進一步提高空間效率或打包（小心，在你做完這些之後，你的特里將不再是可修改的）。

而且，如果你確實需要刪除從你的字典結構的所有項目不給定的前綴匹配，我會考慮。通過嘗試，您可以通過簡單地「查看」相關的子樹並僅考慮那些條目來消除無效的單詞。

希望它有幫助

2011-12-11 15:08:06 DeX3

回答