同義詞字典的實現？

我應該如何處理這個問題？我基本上需要實現同義詞的字典。它需要輸入一些「word/synonim」對，我必須能夠「查詢」它的單詞的所有synonims列表。同義詞字典的實現？

例如：


Dictionary myDic; 

myDic.Add("car", "automobile"); 
myDic.Add("car", "autovehicle"); 
myDic.Add("car", "vehicle"); 
myDic.Add("bike", "vehicle"); 

myDic.ListOSyns("car") // should return {"automobile","autovehicle","vehicle" ± "car"} 
         // but "bike" should NOT be among the words returned

我會在C++代碼這一點，但我感興趣的執行情況的總體思路，所以這個問題是不完全的特定語言。

PS：主要思想是有一些詞組（同義詞）。在上面的例子中，將有兩個這樣的基團：

{ 「汽車」，「autovehicle」，「車輛」，「汽車」} { 「自行車」，「車輛」}

「車輛」屬於這兩個，「自行車」剛剛到第二個，其他人只是在第一

來源

2011-03-17 cantrem

你問如何實現字典？或「相關」搜索（在你的例子中「車輛」的返回？也 - 你想要多深？如果你還添加（「車輛」，「摩托車」）是否也會返回「摩托車」？ – amit 2011-03-17 12:11:04

@skaffman：感謝您的編輯，這些標籤的方式更相關 – cantrem 2011-03-17 12:12:31

補貼，我寫錯了;讓我編輯帖子;我想在這兩個問題和深度的一些洞察力應該是1 ..我會讓帖子更清晰 – cantrem 2011-03-17 12:14:34

我會實現它作爲一個Graph + hash table/search tree
每個關鍵字將是一個頂點，和2個關鍵字之間的每個連接將是一個邊緣。
散列表或搜索樹將從每個單詞連接到其節點（反之亦然）。
提交查詢時 - 您可以找到包含散列/樹的節點，並執行所需深度的BFS/DFS。（這意味着你不能在一定深度後繼續）

複雜度：O（E（d）+ V（d））用於搜索圖（d =深度）（E（d）=相關深度中邊的數量，對於V（d））
O（1）用於創建邊（不包括搜索該節點，在其搜索下面詳述）
O（logn）/ O（1）用於查找節點（用於樹/散列表）
O（logn）/ O（1）用於向樹/散列表添加關鍵字並且O（1）添加頂點
ps如上所述：設計師應該記住，如果他需要一個定向或間接的圖表，如問題的評論中所述。
希望可以幫到...

來源

2011-03-17 12:25:16 amit

它的確如此。看起來哈希表是更好的方法，因爲它具有更好的查找時間（即使根據我的理解，查找/添加關鍵字到哈希表的複雜性由於碰撞而有點高問題）。 – cantrem 2011-03-17 12:34:50

如果字典不是固定大小，那麼哈希表的問題將會出現，您將需要花費一些時間來重新哈希，但平均時間仍然會更長，但最大延遲時間會更長，所以這是一個折中的選擇必須選擇作爲設計師。 – amit 2011-03-17 12:37:35

你是對的，但這僅僅是一個大學作業需要進一步，所以在這個特定情況下重新哈希大型字典將不會是一個問題 – cantrem 2011-03-17 12:41:11

隨着對問題的評論的澄清，它相對簡單，因爲您不存儲相互同義詞的組，而是單獨定義每個詞的可接受同義詞。最明顯的容器可以是：

std::map<std::string, std::set<std::string> >

或：

std::multi_map<std::string, std::string>

，如果你不擔心重複插入，就像這樣：

myDic.Add("car", "automobile"); 
myDic.Add("car", "auto"); 
myDic.Add("car", "automobile");

在multi_map，使用情況equal_range成員函數爲每個單詞提取同義詞，可能是這樣的：

struct Dictionary { 
    vector<string> ListOSyns(const string &key) const { 
     typedef multi_map<string, string>::const_iterator constit; 
     pair<constit, constit> x = innermap.equal_range(key); 
     vector<string> retval(x.first, x.second); 
     retval.push_back(key); 
     return retval; 
    } 
};

最後，如果你喜歡類似散列表的結構到樹狀結構，那麼你的C++實現中可能會有unordered_multimap，並且基本上相同的代碼可以工作。

來源

2011-03-17 13:27:04

同義詞字典的實現？

回答

相關問題