☰

理论

tag-icon • tag-icon text-processing awk algorithms
理论

我有一个空格或逗号分隔的表，有两列，每行代表两个单词的等价性。

A B  
B C  
B D  
C E  
F G

我想要的是一个表格，每行列出所有相互等效的单词。

A B C D E  
F G

也就是说，如果两个单词出现在输入的同一行上，那么它们最终必须出现在输出的同一行中。

任何工具都可以。

答案1

在 python 中，以输入文件作为参数开始： 

import sys

res = []  # list of lists
for line in open(sys.argv[1]):
    try:
        x, y = line.split()  # split on space
    except ValueError:
        line = line.rstrip()
        x, y = line.split(',')  # retry with comma
    for l in res:
        if x in l:
            if y not in l:
                l.append(y)
            break
    else:
        res.append([x, y])

for line in res:
    print ' '.join(line)

测试if y not in l:跳过两次添加相同的值，我不确定是否需要这样做，或者源是否存在此类异常。您可以省略测试并始终执行l.append(y)。

该代码首先尝试按空格分割，然后重试逗号。这假设逗号分隔的行中没有空格（即不是A, B）。

嵌套for循环使用（据我所知）python 的一个特殊性：else只有当循环通过穷举结束时才会执行for，而不是通过 break 语句。这意味着如果x未找到，则该对将作为新列表附加到res。

答案2

理论

这个问题被称为划分一个集合进入等价类，输入文件列出两两等价。可以借助以下工具解决不相交集数据结构。

不太抽象的例子是，例如，给定同义词对，将单词划分为同义词组：

large big
big great
great vast
small little
little tiny

变成：

large big great vast
small little tiny

红宝石溶液

不相交集在 ruby​​ 标准库中不可用，因此我使用 ruby​​ 来模拟它Hash（在其他地方称为“关联数组”、“字典”、“映射”）。

#!/usr/bin/env ruby
# new elements end up in "singleton subsets"
subsets = Hash.new { |subsets, element| subsets[element] = [element] }
ARGF.each do |line|
  x, y = line.scan(/[^\s,]/)
  # these two emulate disjoint-set's "find" operation
  x_set = subsets[x]
  y_set = subsets[y]
  # and this loop implements disjoint-set's "union"
  y_set.each do |element, _|
    subsets[element] = x_set << element
  end unless x_set == y_set
end
puts subsets.values.uniq.map{|set| set.join(" ")}

用法

这需要命令行上的文件名或标准输入上的数据：

$ ruby so-162730.rb input.txt
A B C D E
F G

$ ruby so-162730.rb < input.txt
A B C D E
F G

awk解决方案

也许更适合这个网站。

在这里，我使用了稍微不同的不相交集实现：每个子集由其元素之一（“领导者”）表示。这使得联合操作变慢，但使用 awk 的简单数据类型更容易实现。

{
  union(find($1), find($2));
}

END {
  format_subsets();
  for(i in subsets)
    print subsets[i];
}

function find(element) {
  if (!leaders[element])
    leaders[element] = element;
  return leaders[element];
}

function union(leader_1, leader_2) {
  for(i in leaders)
    if (leaders[i] == leader_2)
      leaders[i] = leader_1;
}

function format_subsets() {
  for(element in leaders) {
    leader = leaders[element]
    subsets[leader] = (subset = subsets[leader]) ? (subset OFS element) : element;
  }
}

用法

$ awk -f so-162730.awk < input.txt
A B C D E
F G

或者对于空格或逗号分隔的输入：

$ awk -f so-162730.awk -F '[[:space:]]+|,' input.txt
A B C D E
F G

相关内容