設計牛津英語詞典

我在採訪中被問及如何設計牛津英語詞典。設計牛津英語詞典

我告訴他我會使用TREE數據結構，但他回答說需要大量的內存。那麼應該使用哪種數據結構呢？

2011-12-10 AKIWEB

只是一個愚蠢的事情，但不牛津英語詞典使用，而不是映射到另一個詞的世界地圖單詞幾個句子/短語中單詞的含義？在這種情況下，單詞編碼是您問題最少的部分，您應該思考如何表達意義（語法等詞），甚至可以考慮使用基於字典的包裝（如LHARC）。幸運的是，英語並不是很複雜...... – Spektre

一種數據結構，我聽到在手機過去被用於存儲T9字典是以下（當然，這隻能解決問題的關鍵，而不是定義存儲）：

條目進行排序，並每個條目應該從前一個條目的偏移量開始，從該位置繼續它的位置，以及延續。例如：

apple 
4icable 
7tion

將解碼爲適用於Apple的應用程序。但是這可能不是從合併後的連鎖嘗試不同的，看到

appl -> e 
    -> ica -> ble 
      -> tion

維基百科發現的Directed acyclic word graph，從樹，它不僅樹枝，樹枝卻可以合併，字有相同後綴不同。這確實可能是一個優越的存儲。

 a 
    /\ 
    pplic utom 
     \/
     ation

2011-12-10 01:18:48 ron

順便說一下，維基百科告訴我，「如果存儲字典中的詞彙是必需的，那麼最小的非循環確定性有限自動機將比使用更少的空間使用更少的空間。添加回答。 – ron

它不會佔用大量內存。你的回答很好。也許在1995年。考慮你自己的幸運。

2011-12-10 01:05:34 jmacinnes

正如其他人所提到的，如果沒有足夠的屋頂來設計精心設計的提議，那麼可能沒有任何其他類型索引的空間。由於這是一個面試問題，這聽起來像他試圖引導你走向典型的核外數據結構，如B樹。

或者，一個好的反應可能是要求獲得更多的信息，比如「你想在這個數據結構上做什麼樣的操作，以及你需要什麼類型的性能？如果你只是想拼寫檢查，那麼布盧姆過濾器可能是最有效的「數據結構」...

2011-12-10 01:29:37 comingstorm

回答