同义词查找算法

Question

我认为这个例子会比loooong的描述好得多：）

假设我们有一个数组：

("Server1", "Server_1", "Main Server", "192.168.0.3")
("Server_1", "VIP Server", "Main Server")
("Server_2", "192.168.0.4")
("192.168.0.3", "192.168.0.5")
("Server_2", "Backup")

每行包含同义词字符串。作为这个数组的处理结果，我想得到：

^{pr2}$

所以我想我需要一种递归算法。编程语言实际上并不重要-我只需要一点点关于idea的帮助。我将使用php或python。在

谢谢你！在

Answer 1

引入整数标记，表示同义词组。在开始时，一个标记从1到N的所有单词。在

然后在集合中搜索，如果发现索引为i和j的两个单词是同义词，则用标记i和{}的单词加上两者中较少的一个。在N迭代之后，您将得到所有同义词组。在

这是一个肮脏且不完全有效的解决方案，我相信使用union-find结构可以获得更高的性能。在

Answer 2

这个问题可以归结为图论中的一个问题，即在图中找到所有连通的节点组。在

解决这个问题的一个有效方法是使用“洪水填充”算法，这本质上是一个递归的呼吸优先搜索。这个wikipedia entry描述了泛洪填充算法及其如何应用于解决图的连通区域的问题。在

要了解如何将原始问题转化为图形问题，请将每个条目（例如“Server1”、“Server1”等）设为图形上的一个节点。当且仅当节点是同义词时，才使用边连接节点。如果有足够的内存，矩阵数据结构特别适合于跟踪边。否则，像地图这样的稀疏数据结构将起作用，特别是因为同义词的数量可能会受到限制。在

• 服务器1是节点0
• 服务器1是节点1
• 服务器2是节点2

然后edge[0][1]=edge[1][0]=1，表示节点0和节点1之间有一条边（这意味着它们是同义词）。而edge[0][2]=edge[2][0]=0，表示Server1和server2是非同义词。在

复杂性分析

创建这个数据结构是非常有效的，因为一个单一的线性过程和查找字符串到节点号的映射就足够了。如果在字典中存储字符串到节点号的映射，那么这将是一个O（n logn）步骤。在

执行泛洪填充是O（n），您只访问图中的每个节点一次。因此，该算法是O（nlogn）。在

Answer 3

编辑：这可能不是解决问题最有效的方法。如果您对max performance感兴趣（例如，如果您有数百万个值），您可能会对编写更复杂的算法感兴趣。在

---

PHP似乎正在工作（至少使用给定示例中的数据）：

$data = array(
    array("Server1", "Server_1", "Main Server", "192.168.0.3"),
    array("Server_1", "VIP Server", "Main Server"),
    array("Server_2", "192.168.0.4"),
    array("192.168.0.3", "192.168.0.5"),
    array("Server_2", "Backup"),
);

do {
    $foundSynonyms = false;
    foreach ( $data as $firstKey => $firstValue ) {
        foreach ( $data as $secondKey => $secondValue ) {
            if ( $firstKey === $secondKey ) {
                continue;
            }
            if ( array_intersect($firstValue, $secondValue) ) {
                $data[$firstKey] = array_unique(array_merge($firstValue, $secondValue));
                unset($data[$secondKey]);
                $foundSynonyms = true;
                break 2; // outer foreach
            }
        }
    }
} while ( $foundSynonyms );

print_r($data);

输出：

^{pr2}$