同义词查找器算法

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")

每行包含作为同义词的字符串.由于处理这个数组我希望得到这个:

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

所以我想我需要一种递归算法.编程语言实际上并不重要 - 一般来说我只需要一点点帮助.我将使用php或python.

谢谢!

Answer 1

这个问题可以简化为图论中的一个问题,在图论中,您可以在图中找到所有连接节点组.

解决此问题的有效方法是执行"泛洪填充"算法,该算法本质上是递归呼吸首次搜索.此维基百科条目描述了泛洪填充算法以及它如何应用于解决查找图的连通区域的问题.

要查看原始问题如何在图表上形成问题:将每个条目(例如"Server1","Server_1"等)作为图表上的节点.当且仅当它们是同义词时,用边连接节点.如果有足够的内存,矩阵数据结构特别适合跟踪边缘.否则,像地图这样的稀疏数据结构将起作用,尤其是因为同义词的数量可能会受到限制.

• Server1是节点#0
• Server_1是节点#1
• Server_2是节点#2

然后edge [0] [1] = edge [1] [0] = 1,表示节点#0和#1之间存在边缘(这意味着它们是同义词).edge [0] [2] = edge [2] [0] = 0,表示Server1和Server_2 不是同义词.

复杂性分析

创建这种数据结构非常有效,因为单个线性传递可以查找字符串到节点编号的映射就足够了.如果将字符串的映射存储到字典中的节点编号,那么这将是O(n log n)步骤.

执行泛洪填充是O(n),您只访问图表中的每个节点一次.所以,算法都是O(n log n).