Como posso particionar um conjunto de palavras com pares que devem terminar juntos?

Question

Eu tenho um espaço ou uma tabela separada por vírgulas com duas colunas, cada linha representando a equivalência das duas palavras.

A B  
B C  
B D  
C E  
F G

O que eu quero é uma tabela com cada linha listando todas as palavras mutuamente equivalentes.

A B C D E  
F G 

Isto é, se duas palavras ocorrerem na mesma linha de entrada, elas devem terminar na mesma linha da saída.

Qualquer ferramenta serve.

    

Answer 1

Em python, comece com o arquivo de entrada como um argumento:

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)

O teste if y not in l: ignora a adição do mesmo valor duas vezes, não tenho certeza se isso é desejado ou se a origem tem tais anomalias. Você pode deixar de fora o teste e sempre executar l.append(y) .

O código tenta primeiro se dividir no espaço e, em seguida, tenta novamente a vírgula. Isso pressupõe que linhas separadas por vírgula não possuem espaço nelas (ou seja, não são A, B ).

O loop aninhado for usa (AFAIK) uma particularidade de python: o else só é executado se o loop for terminar por esgotamento, o que não é por meio da instrução break. Isso significa que se x não for encontrado, o par será anexado como nova lista a res .

    

Answer 2

teoria

Esse problema é conhecido como particionando um conjunto em classes de equivalência , com o arquivo de entrada listando equivalências de pares. Isso pode ser resolvido com a ajuda de uma estrutura de dados disjoint .

Exemplo menos abstrato é, por exemplo, particionando palavras em grupos de sinônimos com pares de sinônimos:

large big
big great
great vast
small little
little tiny

torna-se:

large big great vast
small little tiny

solução de rubi

O conjunto Disjoint não está disponível na biblioteca padrão do ruby, então eu emulei usando um ruby Hash (conhecido em outros lugares como "array associativo", "dicionário", "mapa").

#!/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(" ")}

uso

isso espera nomes de arquivos na linha de comando ou dados em stdin:

$ 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

solução awk

Talvez seja mais apropriado para este site.

Aqui eu uso uma implementação ligeiramente diferente de conjunto disjunto: cada subconjunto é representado por um de seus elementos ("líder"). Isso torna a operação de união mais lenta, mas é mais fácil de implementar com os tipos de dados simples do 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;
  }
}

uso

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

Ou para espaços em branco ou entradas separadas por vírgula:

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