同义字典实现？ [英] Synonym dictionary implementation?

问题描述

我应该如何解决这个问题？我基本上需要实现一个同义词的字典。它需要输入一些word / synonim对，我必须能够查询它的一个单词的所有synonims列表。

How should I approach this problem? I basically need to implement a dictionary of synonyms. It takes as input some "word/synonim" pairs and I have to be able to "query" it for the list of all synonims of a word.

例如：

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 ++中编写代码，但我对整体想法感兴趣的实现，所以问题不完全是语言特定的。

I'll code this in C++, but I'm interested in an overall idea of the implementation, so the question is not exactly language-specific.

PS：主要思想是有一些单词（同义词）。在上面的示例中，将有两个这样的组：

PS: The main idea is to have some groups of words (synonyms). In the example above there would be two such groups:

{汽车，汽车，车辆，汽车}
{自行车，车}

{"automobile","autovehicle","vehicle", "car"} {"bike", "vehicle"}

车属于两者，自行车只是第二个，其他只是第一个

"vehicle" belongs to both, "bike" just to the second one, the others just to the first

推荐答案

我将其实现为图 + 哈希表 / 搜索树

每个关键字将是一个顶点，两个关键字之间的每个连接都将是一个优势。

哈希表或搜索树将从每个单词连接到其节点（反之亦然）。

当提交查询时 - 您会发现具有哈希/树的节点，并执行所需深度的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如上所述：设计师应该记住，如果他需要一个直接或间接的图表，如问题的意见所述。

希望能帮助...

I would implement it as a Graph + hash table / search tree
each keyword would be a Vertex, and each connection between 2 keywords would be an edge.
a hash table or a search tree will connect from each word to its node (and vice versa).
when a query is submitted - you find the node with your hash/tree and do BFS/DFS of the required depth. (meaning you cannot continue after a certain depth)

complexity: O(E(d)+V(d)) for searching graph (d = depth) (E(d) = number of edges in the relevant depth, same for V(d))
O(1) for creating an edge (not including searching for the node, detailed below its search)
O(logn) / O(1) for finding node (for tree/hash table)
O(logn) /O(1) for adding a keyword to the tree/hash table and O(1) to add a Vertex
p.s. as mentioned: the designer should keep in mind if he needs a directed or indirected Graph, as mentioned in the comments to the question.
hope that helps...

这篇关于同义字典实现？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！