6

我认为示例将比 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。

谢谢！

4

5 回答 5

6

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

解决此问题的一种有效方法是执行“洪水填充”算法，该算法本质上是递归呼吸优先搜索。这个维基百科条目描述了洪水填充算法以及它如何应用于解决寻找图的连接区域的问题。

要查看如何将原始问题变成图表上的问题：使每个条目（例如“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)。

于 2011-05-26T06:40:23.627 回答
2

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

然后在你的集合中搜索，如果你找到两个带有索引的单词i并且j是同义词，然后用标记i和j较少数量的两个单词重新标记所有单词。迭代后N，您将获得所有同义词组。

这是一种肮脏且效率不高的解决方案，我相信可以通过联合查找结构获得更多性能。

于 2011-05-26T06:34:31.840 回答
1

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

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

输出：

Array
(
    [0] => Array
        (
            [0] => Server1
            [1] => Server_1
            [2] => Main Server
            [3] => 192.168.0.3
            [4] => VIP Server
            [6] => 192.168.0.5
        )

    [2] => Array
        (
            [0] => Server_2
            [1] => 192.168.0.4
            [3] => Backup
        )

)
于 2011-05-26T06:52:58.403 回答
1

这将产生比 PHP 示例（Python 3）更低的复杂性：

a = [set(("Server1", "Server_1", "Main Server", "192.168.0.3")),
    set(("Server_1", "VIP Server", "Main Server")),
    set(("Server_2", "192.168.0.4")),
    set(("192.168.0.3", "192.168.0.5")),
    set(("Server_2", "Backup"))]

b = {}
c = set()
for s in a:
    full_s = s.copy()
    for d in s:
        if b.get(d):
            full_s.update(b[d])
    for d in full_s:
        b[d] = full_s
    c.add(frozenset(full_s))

for k,v in b.items():
    fsv = frozenset(v)
    if fsv in c:
        print(list(fsv))
        c.remove(fsv)
于 2011-05-26T08:45:37.193 回答
0

我一直在寻找python中的解决方案，所以我想出了这个解决方案。如果您愿意使用像集合这样的 Python 数据结构，您也可以使用此解决方案。“它是如此简单，一个穴居人可以使用它。”

这就是它背后的逻辑。

foreach set_of_values in value_collection:
    alreadyInSynonymSet = false
    foreach synonym_set in synonym_collection:
        if set_of_values in synonym_set:
            alreadyInSynonymSet = true
            synonym_set = synonym_set.union(set_of_values)
    if not alreadyInSynonymSet:
        synonym_collection.append(set(set_of_values))

vals = (
    ("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"),
)

value_sets = (set(value_tup) for value_tup in vals)

synonym_collection = []

for value_set in value_sets:
    isConnected = False # If connected to a term in the graph

    print(f'\nCurrent Value Set: {value_set}')
    
    for synonyms in synonym_collection:
        # IF two sets are disjoint, they don't have common elements
        if not set(synonyms).isdisjoint(value_set):
            isConnected = True
            synonyms |= value_set # Appending elements of new value_set to synonymous set
            break

    # If it's not related to any other term, create a new set
    if not isConnected:
        print ('Value set not in graph, adding to graph...')
        synonym_collection.append(value_set)

print('\nDone, Completed Graphing Synonyms')
print(synonym_collection)

这将导致

Current Value Set: {'Server1', 'Main Server', '192.168.0.3', 'Server_1'}
Value set not in graph, adding to graph...

Current Value Set: {'VIP Server', 'Main Server', 'Server_1'}

Current Value Set: {'192.168.0.4', 'Server_2'}
Value set not in graph, adding to graph...

Current Value Set: {'192.168.0.3', '192.168.0.5'}

Current Value Set: {'Server_2', 'Backup'}

Done, Completed Graphing Synonyms
[{'VIP Server', 'Main Server', '192.168.0.3', '192.168.0.5', 'Server1', 'Server_1'}, {'192.168.0.4', 'Server_2', 'Backup'}]
于 2021-08-16T02:01:38.753 回答