алгоритм сжатия пучка (пары строк)

Question

У меня есть набор строк, которые попадают парами Например, это три пары. Первая имеет две строки: «a», «1»

a,1 
a,2 
b,1 

В моем проекте мне нужно сжать эти данные. Для приведенных данных сжатые данные. (Сжатые несжатое является декартово произведение)

{a} <=> {1,2} 
{b} <=> {1} 

Каков наилучший алгоритм придумать оптимальные сжимаются данные. Оптимально здесь меньше числа отображений Я мог бы написать простой скрипт, который создает хеш-таблицу с первой строкой. Несмотря на то, что он дает оптимальные сжатые данные в некоторых случаях (выше случая), но он не всегда. Например,

a,1 
a,2 
b,1 
c,2 

Хэш таблица с первой строкой в ​​качестве ключа даст мне ниже сжатые данные

{a} <=> {1,2} 
{b} <=> {1} 
{c} <=> {2} 

Но это не оптимальные сжатые данные. Я получу ниже сжатия, если я использовал вторую строку

{a,b} <=> {1} 
{a,c} <=> {2} 

Каков наилучший алгоритм сжатия данных?

Answer 1

Эта проблема эквивалентна покрытию 1 или 0 двоичной матрицы с минимальным количеством строк.

Например, рассмотрим пример: a1, b1, b2, c1, c2, d2, d3, d4, e3, e4, e5. Это может быть введен в матрицу следующим образом:

1 2 3 4 5 
a 1 
b 1 1 
c 1 1 
d 1 1 1 
e  1 1 1 

Минимальное решение, чтобы пересечь линии д и е, чтобы дать:

d : {2, 3, 4} 
e : {3, 4, 5} 

и столбцы 1 и 2

1 : {a, b, c} 
2 : {b, c, d} 

, чтобы достичь минимального количества записей на сжатой карте 4.

Решение этой проблемы обработано els где в stackoverflow в Hungarian Algorithm: How to cover 0 elements with minimum lines?

Answer 2

Это определенно не оптимизировано по скорости, но эта проблема действительно привлекла мое внимание. Я не был уверен в исходном формате, но это должно быть тривиально для изменения. Вот моя идея, в принципе, я думаю, что вам нужно двухпроходным, потому что вы не можете знать, какой сжатие лучше, пока вы не дойдете до конца ваших данных:

use strict; 
use warnings; 

use Data::Dumper; 

sub compress_strings { 
    my @strings = @_; 
    my %keys_hash; 
    my %values_hash; 
    my %second_hash; 
    my %third_hash; 

    foreach my $string (@strings) { 
     my ($key, $value) = split /,/, $string; 
     push(@{$keys_hash{$key}}, $value); 
     push(@{$values_hash{$value}}, $key); 
    } 

    foreach my $key (keys(%keys_hash)) { 
     my $found = 0; 
     foreach my $value (@{$keys_hash{$key}}) { 
      if (@{$values_hash{$value}} > 1) { 
       if (!grep {$value} @{$second_hash{join(',', @{$values_hash{$value}})}}) { 
        push(@{$second_hash{join(',', @{$values_hash{$value}})}}, $value); 
       } 
       $found = 1; 
      } 
     } 
     if (!$found) { 
      $second_hash{$key} = $keys_hash{$key}; 
     } 
    } 

    %third_hash = map { $_ => join(',',@{$second_hash{$_}}) } keys(%second_hash); 

    return \%third_hash; 
} 

print Dumper compress_strings('a,1', 'a,2', 'b,1', 'c,2', 'd,4'); 
print Dumper compress_strings('a,1', 'a,2', 'b,3', 'c,3'); 
print Dumper compress_strings('a,1', 'b,1' ,'b,2' ,'c,1' ,'c,2' ,'d,2' ,'d,3' ,'d,4' ,'e,3' ,'e,4' ,'e,5'); 

Выход:

$VAR1 = { 
      'a,c' => '2', 
      'a,b' => '1', 
      'd' => '4' 
     }; 
$VAR1 = { 
      'a' => '1,2', 
      'b,c' => '3' 
     }; 
$VAR1 = { 
      'a,b,c' => '1', 
      'b,c,d' => '2', 
      'd,e' => '3' 
     };