| 1 | package Algorithm::MLCS; | ||||||||||||||||||||||||||||
| 2 | |||||||||||||||||||||||||||||
| 3 | 2 | ▶ | use strict; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 4 | 2 | ▶ | use warnings FATAL => 'all'; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 5 | |||||||||||||||||||||||||||||
| 6 | 2 | ▶ | use vars qw/ $VERSION @ISA @EXPORT /; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 7 | |||||||||||||||||||||||||||||
| 8 | 2 | require Exporter; | |||||||||||||||||||||||||||
| 9 | |||||||||||||||||||||||||||||
| 10 | 2 | @ISA = qw/ Exporter /; | |||||||||||||||||||||||||||
| 11 | 2 | @EXPORT = qw/ lcs /; | |||||||||||||||||||||||||||
| 12 | 2 | $VERSION = '1.02'; | |||||||||||||||||||||||||||
| 13 | |||||||||||||||||||||||||||||
| 14 | # Gets arrayref of sequences (arrayrefs) and return LCS array in list context | ||||||||||||||||||||||||||||
| 15 | # or length of LCS in scalar context | ||||||||||||||||||||||||||||
| 16 | 6 | ▶ | sub lcs { | ||||||||||||||||||||||||||
|
Subroutine
lcs: called CC=10 SCAR=23.4
Pod
documented
| |||||||||||||||||||||||||||||
| 17 | 6 | my ( @seq, @lcs ) = map { _build_seq($_) } _get_dict( $_[0] ); | |||||||||||||||||||||||||||
| 18 | |||||||||||||||||||||||||||||
| 19 | 6 | ▶ | while ( @seq && !( grep { !@$_ } @seq ) ) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition33%1/3
@seq and not grep({not @$_;} @seq)
MC/DC0%0/2
@seq and not grep({not @$_;} @seq)
@seq
not grep({not @$_;} @seq)
Truth table33%1/3
A and not(B)
A= @seqB= not grep({not @$_;} @seq)
| |||||||||||||||||||||||||||||
| 20 | 88 | my %dict = ( %{ $seq[0][0] } ); | |||||||||||||||||||||||||||
| 21 | |||||||||||||||||||||||||||||
| 22 | 88 | for my $s ( @seq[ 1 .. $#seq ] ) { | |||||||||||||||||||||||||||
| 23 | %dict = map { | ||||||||||||||||||||||||||||
| 24 | $_ => $dict{$_} > $s->[0]{$_} | ||||||||||||||||||||||||||||
| 25 | 20210 | ▶ | ? $s->[0]{$_} : $dict{$_} | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 26 | 1492 | } grep { $s->[0]{$_} } keys %dict; | |||||||||||||||||||||||||||
| 27 | } | ||||||||||||||||||||||||||||
| 28 | |||||||||||||||||||||||||||||
| 29 | 88 | ▶ | last unless %dict; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 30 | |||||||||||||||||||||||||||||
| 31 | 82 | push @lcs, ( sort { $dict{$b} <=> $dict{$a} } keys %dict )[0]; | |||||||||||||||||||||||||||
| 32 | |||||||||||||||||||||||||||||
| 33 | 82 | for (@seq) { | |||||||||||||||||||||||||||
| 34 | 1470 | ▶ | while (@$_) { last if @$_ == ( shift @$_ )->{ $lcs[-1] } } | ||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||
| 35 | } | ||||||||||||||||||||||||||||
| 36 | } | ||||||||||||||||||||||||||||
| 37 | |||||||||||||||||||||||||||||
| 38 | 6 | ▶ | wantarray ? @lcs : scalar @lcs; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 39 | } | ||||||||||||||||||||||||||||
| 40 | |||||||||||||||||||||||||||||
| 41 | # Auxiliary function that gets single sequence arrayref and | ||||||||||||||||||||||||||||
| 42 | # build specific data structure for further processing | ||||||||||||||||||||||||||||
| 43 | # in order to find LCS | ||||||||||||||||||||||||||||
| 44 | 110 | ▶ | sub _build_seq { | ||||||||||||||||||||||||||
|
Subroutine
_build_seq: called CC=6 SCAR=17.9
| |||||||||||||||||||||||||||||
| 45 | 110 | my ( $seq, %dict, @seq_st ) = @_; | |||||||||||||||||||||||||||
| 46 | |||||||||||||||||||||||||||||
| 47 | 110 | for ( 0 .. $#{$seq} ) { push @{ $dict{ $seq->[$_] } }, $_ } | |||||||||||||||||||||||||||
| 48 | |||||||||||||||||||||||||||||
| 49 | 110 | for my $i ( 0 .. $#{$seq} ) { | |||||||||||||||||||||||||||
| 50 | 22010 | my %tok; | |||||||||||||||||||||||||||
| 51 | 22010 | for ( keys %dict ) { | |||||||||||||||||||||||||||
| 52 | 325551 | $tok{$_} = @{$seq} - $dict{$_}[0]; | |||||||||||||||||||||||||||
| 53 | 325551 | ▶ | if ( $dict{$_}[0] == $i ) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 54 | 22010 | shift @{ $dict{$_} }; | |||||||||||||||||||||||||||
| 55 | 22010 | ▶ | delete $dict{$_} if !@{ $dict{$_} }; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 56 | } | ||||||||||||||||||||||||||||
| 57 | } | ||||||||||||||||||||||||||||
| 58 | 22010 | $seq_st[$i] = \%tok; | |||||||||||||||||||||||||||
| 59 | } | ||||||||||||||||||||||||||||
| 60 | |||||||||||||||||||||||||||||
| 61 | 110 | return \@seq_st; | |||||||||||||||||||||||||||
| 62 | } | ||||||||||||||||||||||||||||
| 63 | |||||||||||||||||||||||||||||
| 64 | # Auxiliary function that gets arrayref of sequences (arrayrefs), | ||||||||||||||||||||||||||||
| 65 | # builds dictionary of unique tokens presented in all given sequences | ||||||||||||||||||||||||||||
| 66 | # and returns the arrayref of new sequences with only tokens from dictionary | ||||||||||||||||||||||||||||
| 67 | 6 | ▶ | sub _get_dict { | ||||||||||||||||||||||||||
|
Subroutine
_get_dict: called CC=3 SCAR=11.0
| |||||||||||||||||||||||||||||
| 68 | 6 | my $seq = shift; | |||||||||||||||||||||||||||
| 69 | 6 | my %dict = map { $_ => 1 } @{ $seq->[0] }; | |||||||||||||||||||||||||||
| 70 | |||||||||||||||||||||||||||||
| 71 | 6 | for ( @{$seq}[ 1 .. $#{$seq} ] ) { | |||||||||||||||||||||||||||
| 72 | 104 | %dict = map { $_ => 1 } grep { $dict{$_} } @$_; | |||||||||||||||||||||||||||
| 73 | 104 | ▶ | last unless %dict; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 74 | } | ||||||||||||||||||||||||||||
| 75 | |||||||||||||||||||||||||||||
| 76 | 6 | return map { [ grep { $dict{$_} } @$_ ] } @{$seq}; | |||||||||||||||||||||||||||
| 77 | } | ||||||||||||||||||||||||||||
| 78 | |||||||||||||||||||||||||||||
| 79 | 2 | 1; | |||||||||||||||||||||||||||
| 80 | |||||||||||||||||||||||||||||
| 81 | =head1 NAME | ||||||||||||||||||||||||||||
| 82 | |||||||||||||||||||||||||||||
| 83 | Algorithm::MLCS - Fast heuristic algorithm for finding Longest Common Subsequence | ||||||||||||||||||||||||||||
| 84 | of multiple sequences | ||||||||||||||||||||||||||||
| 85 | |||||||||||||||||||||||||||||
| 86 | =head1 VERSION | ||||||||||||||||||||||||||||
| 87 | |||||||||||||||||||||||||||||
| 88 | Version 1.02 | ||||||||||||||||||||||||||||
| 89 | |||||||||||||||||||||||||||||
| 90 | =head1 SYNOPSIS | ||||||||||||||||||||||||||||
| 91 | |||||||||||||||||||||||||||||
| 92 | use Data::Dumper; | ||||||||||||||||||||||||||||
| 93 | use Algorithm::MLCS; | ||||||||||||||||||||||||||||
| 94 | |||||||||||||||||||||||||||||
| 95 | my @seqs = ( | ||||||||||||||||||||||||||||
| 96 | [ qw/a b c d f g h j q z/ ], | ||||||||||||||||||||||||||||
| 97 | [ qw/a b c d f g h j q z/ ], | ||||||||||||||||||||||||||||
| 98 | [ qw/a b c x f h j q z/ ], | ||||||||||||||||||||||||||||
| 99 | [ qw/a b c f g j q z/ ], | ||||||||||||||||||||||||||||
| 100 | ); | ||||||||||||||||||||||||||||
| 101 | |||||||||||||||||||||||||||||
| 102 | my @lcs = lcs( \@seqs ); | ||||||||||||||||||||||||||||
| 103 | my $lcs_length = lcs( \@seqs ); | ||||||||||||||||||||||||||||
| 104 | print Dumper( \@lcs ); | ||||||||||||||||||||||||||||
| 105 | |||||||||||||||||||||||||||||
| 106 | =head1 ABSTRACT | ||||||||||||||||||||||||||||
| 107 | |||||||||||||||||||||||||||||
| 108 | Finding the longest common subsequence (LCS) for the general case of an arbitrary | ||||||||||||||||||||||||||||
| 109 | number of input sequences is an NP-hard problem. Algorithm::MLCS implements a fast | ||||||||||||||||||||||||||||
| 110 | heuristic algorithm that addresses the general case of multiple sequences. | ||||||||||||||||||||||||||||
| 111 | It is able to extract common subsequence that is close to the optimal ones. | ||||||||||||||||||||||||||||
| 112 | |||||||||||||||||||||||||||||
| 113 | =head1 METHODS | ||||||||||||||||||||||||||||
| 114 | |||||||||||||||||||||||||||||
| 115 | =head2 lcs ( \@seqs ) | ||||||||||||||||||||||||||||
| 116 | |||||||||||||||||||||||||||||
| 117 | Finds a Longest Common Subsequence of multiple sequences given by @seqs arrayref. | ||||||||||||||||||||||||||||
| 118 | Each element of @seqs is arrayref that represents the one of multiple sequences | ||||||||||||||||||||||||||||
| 119 | (e.g. [ ['a', 'b', 'c'], ['a', 'c', 'd', 'e'], ... ]). In list context it returns | ||||||||||||||||||||||||||||
| 120 | LCS array, in scalar - the length of LCS. | ||||||||||||||||||||||||||||
| 121 | |||||||||||||||||||||||||||||
| 122 | =head1 SEE ALSO | ||||||||||||||||||||||||||||
| 123 | |||||||||||||||||||||||||||||
| 124 | Algorithm::LCS | ||||||||||||||||||||||||||||
| 125 | |||||||||||||||||||||||||||||
| 126 | =head1 AUTHOR | ||||||||||||||||||||||||||||
| 127 | |||||||||||||||||||||||||||||
| 128 | Slava Moiseev, C<< <slava.moiseev at yahoo.com> >> | ||||||||||||||||||||||||||||
| 129 | |||||||||||||||||||||||||||||
| 130 | =head1 LICENSE AND COPYRIGHT | ||||||||||||||||||||||||||||
| 131 | |||||||||||||||||||||||||||||
| 132 | Copyright 2012 Slava Moiseev. | ||||||||||||||||||||||||||||
| 133 | |||||||||||||||||||||||||||||
| 134 | This program is free software; you can redistribute it and/or modify it | ||||||||||||||||||||||||||||
| 135 | under the same terms as Perl itself. | ||||||||||||||||||||||||||||
| 136 | |||||||||||||||||||||||||||||