的Perl - 尋找類似協會

Question

組我有以下數據集

A  C 
A  S 
B  F 
B  Q 
C  A 
C  I 
D  K 
E  Y 
F  B 
F  R 
I  Y 
K  P 

在第一列中的每個值具有在第二列中的相關聯的值。行1中的值「A」具有相關值「C」。在第二行中，值「A」具有關聯的值「S」。

使用Perl，我想找到所有關聯值的集合。使用上面的規則，我會得到集合（ACEISY），（BFQR）和（DKP）。

我正在尋找關於算法或如何解決此問題的示例的建議。我不確定散列表是否適合用於此目的的適當數據結構。任何幫助，將不勝感激。

下面是我的實現：

while<INPUT>{ 
    my ($c1, $c2) = split; 
    my %clusterhash =(); 
    if (exists $clusterhash{$c1}){ 
     if (exists $clusterhash{$c1}{$c2}){ 
      #do nothing 
     } 
     else { 
      $clusterhash{$c1}{$c2} = $c2; 
     } 
    } 
    else{ 
     foreach my $key (keys %clusterhash) { 
      if (exists $clusterhash{$key}{$c1}{ 
       $clusterhash{$c1}{$key} = $key; 
      } 
     } 
     $clusterhash{$c1}{$c2} = $c2; 
    } 
} 

Answer 1

這是不是真的應該成爲一個答案，但評論卻變得過長，不適合的註釋字段：

的是速度的任何問題？如同那樣，是否有這麼多的數據，經常循環播放它可能是一個糟糕的主意？因爲如果循環重複是沒有的問題，而不是一個散列將是一個簡單的解決方案：採取列1中尚未在您的哈希中的第一個元素;將它添加到散列作爲密鑰與一個新的集號碼;遍歷所有行，將所有與ist關聯的值作爲關鍵字添加到散列中，並使用相同的集合數;如果您在最後一次迭代中添加了新密鑰，請爲這些密鑰重新執行一次，直到您不添加新密鑰;將尚未包含在下一個元素中的下一個元素添加到下一個集合索引中; 一旦沒有未分配的元素，您將所有元素都作爲一個散列值作爲鍵值。 您可能需要將其格式化爲最後的格式。

編輯：好的，如果速度是一個問題，如何縮放值的數量而不是行數？

有一個外部哈希值，它將set indides作爲鍵和內部哈希值作爲值。這些內部哈希將元素作爲鍵和「1」作爲值。通過線路迭代。在每一行中，檢查這些值是否已經是一個或兩個內部哈希值中的一個鍵。如果它們處於不同的哈希值，則合併這些哈希值並刪除外部哈希值的一個鍵。如果其中一個在一個散列中，另一個不在散列中，則將該新值添加到第一個散列的散列中，如果它們在同一個散列中，則什麼也不做，如果兩個散列都不是，則爲外部散列創建一個新的關鍵字，並且將這兩個值添加到相應的內部散列中。

如果內部哈希值可能會變大或者可能有很多集合，這可能會變得非常緩慢。但是，如果可能值的集合與行數相比較小，則這可能相當快。

BEST EDIT： 我剛剛有另一個想法。這一個最多查看三行（更可能是兩次假設隨機關聯），我認爲是相當快的，但需要更多的內存。用兩個大的哈希值迭代遍歷線。在每一行中，將cell2添加到key1單元格中存儲在hash1中的Array中，並將cell1添加到key2單元格中存儲在hash2中的Array中。基本上，你將所有的信息讀入這兩個散列。現在你拿一個hash1的隨機密鑰，並將相應的密鑰以及對應數組中的所有elemts添加到你希望存儲最終集合的任何結構中（我假定它是密鑰轉換爲第三個哈希，集合數爲值），並從hash1中刪除密鑰。現在你還可以在hash2中查找所有這些元素作爲關鍵字，並將這些數組中的所有內容添加到集合中，並從hash2中刪除這些關鍵字。現在，您將已添加到集合中的所有內容作爲hash1的鍵，並再次將所有內容添加到集合中，依此類推。您必須繼續這樣做，直到hash1和hash2連續沒有任何內容添加到集合中。然後你再拿一把隨機鑰匙開始下一組。刪除所有使用的密鑰可以保證你不會得到兩次任何東西，而且你不會經常檢查同一行。這是假設查找一個密鑰是否存在於一個哈希實際上是一樣快，因爲我相信它。

Answer 2

您的數據集可以視爲可能斷開連接的有向圖。在我看來，你想爲每個弱連接的子圖設置節點。自己寫這個並不難：

• 我們將該圖視爲無向圖。
• 我們將邊緣存儲在散列中，以便條目$edge{$a}{$b}是從頂點$a到$b的有向邊。
• 現在我們需要的是一個迭代搜索，在我們去的時候刪除所有訪問的邊。

示例代碼：

use strict; use warnings; use feature qw/say/; 

# build the graph 
my %edge; 
while (<>) { 
    my ($from, $to) = split; 
    $edge{$from}{$to} = $edge{$to}{$from} = undef; 
} 

while (my ($start) = keys %edge) { 
    my @seen = ($start); 
    my @stack = ($start); 

    while (@stack) { 
    my $vertex = pop @stack; 

    # delete edges from and to this vertex 
    # NB: any connections to seen vertices are already removed. 
    my @reachable = keys %{ delete($edge{$vertex}) // {} }; 
    delete $edge{$_}{$vertex} for @reachable; 

    # mark new vertices as seen, and enqueue them 
    push @seen, @reachable; 
    push @stack, @reachable; 
    } 

    my $nodes = join ', ', sort @seen; 
    say "node set: {$nodes}"; 
} 

輸出爲數據：

node set: {B, F, Q, R} 
node set: {D, K, P} 
node set: {A, C, E, I, S, Y} 

該算法已相當最佳的，並運行在Ö（ñ·ķ）時間和空間（其中k是鄰居的平均數量）。

當然，已經有一個模塊實現圖算法。不言而喻地，它被稱爲Graph。上面的代碼等同於：

use strict; use warnings; use feature qw/say/; 
use Graph; 

my $graph = Graph::Undirected->new; 
while (<>) { 
    my ($from, $to) = split; 
    $graph->add_edge($from, $to); 
} 

for my $nodes_array ($graph->connected_components) { 
    my $nodes = join ', ', sort @$nodes_array; 
    say "node set: {$nodes}"; 
} 

有可能在更短的存儲器和可能的更短的時間通過跟蹤所連接的部件的，因爲我們建立圖以進行這些計算。爲此，我們有一個將頂點映射到子圖的散列。

1. 如果一個邊的兩個頂點都是未知的，他們將創建一個新的子圖。
2. 如果只有一個頂點已知，則另一個節點映射到第一個節點的子圖，並在那裏作爲成員列出。
3. 如果兩個頂點是已知的，那麼
   1. 如果它們指向同一個子圖，什麼都不會發生。
   2. 如果它們指向不同的子圖，則所有條目都更新爲指向相同的子圖，該子圖現在包含先前子圖的組合節點。

代碼：

use strict; use warnings; use feature qw/say/; 

my %subgraph_by_id; 
my %subgraph_by_vertex; 
while(<>) { 
    my ($x, $y) = split; 
    # case 1: 
    # If an both vertices of an edge are unknown, they create a new subgraph. 
    if (not exists $subgraph_by_vertex{$x} and not exists $subgraph_by_vertex{$y}) { 
    my $new = [$x, $y]; 
    $subgraph_by_id{0+ $new} = $new; 
    $subgraph_by_vertex{$_} = $new for $x, $y; 
    } 
    # case 2: 
    # If exactly one vertex is known, the other node maps to the subgraph of the 
    # first node, and is listed there as a member. 
    elsif (not exists $subgraph_by_vertex{$x} or not exists $subgraph_by_vertex{$y}) { 
    my ($known, $unknown) = (exists $subgraph_by_vertex{$x}) ? ($x, $y) : ($y, $x); 
    my $subgraph = $subgraph_by_vertex{$unknown} = $subgraph_by_vertex{$known}; 
    push @$subgraph, $unknown; 
    } 
    # case 3: 
    # both vertices are known. If they point to different subgraphs, all entries 
    # are updated to point to the same subgraph which now contains the combined 
    # nodes of the previous subgraphs. 
    # Except all that copying would make for a horrible worst case. 
    # Instead, we just add a reference to the smaller list, flattening it later. 
    else { 
    my $prev_x = $subgraph_by_vertex{$x}; 
    my $prev_y = $subgraph_by_vertex{$y}; 
    # don't test for inequality directly to allow subgraph nesting 
    if ($subgraph_by_id{0+ $prev_x} != $subgraph_by_id{0+ $prev_y}) { 
     my ($new, $old) = (@$prev_x > @$prev_y) ? ($prev_x, $prev_y) : ($prev_y, $prev_x); 
     push @$new, $old; 
     # $old not needed on top level any longer – associate it with $new by id 
     $subgraph_by_id{0+ $old} = 0+ $new; 
    } 
    } 
} 

# skip symbolic IDs 
for my $nodes_array (grep ref, values %subgraph_by_id) { 
    my $nodes = join ', ', flatten($nodes_array); 
    say "node set: {$nodes}"; 
} 

sub flatten { 
    return map { ref $_ ? flatten($_) : $_ } @{ shift() }; 
} 

這僅使用Ø（ñ）的空間和時間，採用了很多尷尬的招數。在構建子圖的過程中，我不合並兩個相關的子圖，而是推遲到最後。否則，一個邊緣情況（自下而上建立的平衡樹 - 對於每個非葉節點，樹的一半將被複制）可能需要指數時間 - 我沒有做完整的分析。 0+「venus」僞操作符對其參數進行了編號，用於此處獲取數組引用的ID。