algorithm - 逻辑编程 - 查找给定单词的同义词

Question

任务是编写一个程序，可以判断两个词是否是同义词。

我有成对的同义词，例如：

 [big large]  
 [large huge]  
 [small little] 

我们可以间接推导出同义关系：如果 big 是 large 的同义词，而 large 是 huge 的同义词，那么 big 是 huge 的同义词。
成为同义词不依赖于顺序，例如，如果 big 是 large 的同义词，那么 large 是 big 的同义词。

程序必须回答给定的两个词是否是同义词。

在我看来，这似乎是逻辑编程的一个很好的候选，例如使用 clojure.core.logic。

一个。如何将输入的同义词对声明为逻辑语句/约束？
湾。如何执行查询以查找给定单词的所有同义词？

或者我正在刮胡子？解决这个问题的更简单方法是什么？

标签： algorithmlogic-programmingclojure-core.logic

Answer 1

一般来说，这看起来就像您对（图的）传递闭包感兴趣？

对于无向图（“同义词不依赖于顺序”），这与连通分量有关（在这里我们直接看到一些逻辑关系，因为2-SAT算法也利用连通分量）。

也许也可以看看：Algowiki

基本上：

• 预处理时间：计算输入的传递闭包
• query-time -> synonym(a,b): 检查边 (a,b) 是否存在

或者不进行预处理：只需按需查找路径：

• query-time -> synonym(a,b): 检查a, b之间是否有路径
  • BFS/DFS