<p>首先,这里不清楚你是如何定义关系的。如果你
“猫”有同义词:[“猫”,“小猫”,“老鼠”],这是否意味着“老鼠”有同义词“猫”。在</p>
<p>根据我的理解,答案是否定的。下面是python中的一个解决方案:</p>
<pre><code>G = {
"cat": ["feline", "kitten", "mouser"],
"kitten": ["kitty", "kit"],
"kit": ["pack", "bag", "gear"],
"computer": ["electronics", "PC", "abacus"]
}
def areWordsRelated(G, w1, w2):
if w1 == w2:
return True
frontier = [w1]
checked = set()
while len(frontier):
el = frontier.pop()
if el in G:
neighbors = G[el]
for i in neighbors:
if i == w2:
return True
if i not in checked:
frontier.append(i)
checked.add(i)
return False
areWordsRelated(G, "cat", "pack") #true
areWordsRelated(G, "cat", "computer") #false
</code></pre>
<p>那我们在这里干什么?首先你有你的图表,这只是字典(地图在go)显示你的关系(我基本上采取了你的切片)。在</p>
<p>我们的算法像一个模子一样增长,保持了一组检查过的元素和一个当前的边界。如果边疆是空的(没有什么可探索的,那么元素就没有连接)。我们一次从边界提取一个元素并检查所有的邻居。如果其中任何一个元素是我们要寻找的元素-那么就有一个连接。否则,请检查我们是否已经看到这样的元素(如果没有,则将其添加到边界和选中的集合中)。在</p>
<p>请注意,如果您的关系以稍微不同的方式工作,则只需修改图形。在</p>
<hr/>
<p>最后一句话,如果您正在寻找一种普通的方法来查找同义词,请看一下<a href="https://www.kaggle.com/c/word2vec-nlp-tutorial/details/part-2-word-vectors" rel="nofollow">word to vector algorithm</a>和一个漂亮的<a href="https://code.google.com/p/word2vec/" rel="nofollow">implementation in python</a>。这将允许您找到非常复杂的关系,即使在没有指定关系的情况下,也可以发现<code>California</code>和{<cd2>}是相关联的。在</p>