blib/lib/Algorithm/MLCS.pm

filter: Statementstmt 100% 64 / 64 Branchbran 77.7% 14 / 18 Conditioncond 33.3% 1 / 3 MC/DCmcdc 0.0% 0 / 2 Subroutinesub 100% 6 / 6 Podpod 100% 1 / 1 totaltotal 91.4% 86 / 94 CC 17 SCAR 19.3
CC
17
Cov
93%
lcs
10.4
_build_seq
6.0
_get_dict
3.0
CRAP 6.9
↑ Summary
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
BranchTrueFalseTotal
if (@seq and not grep({not @$_;} @seq)) 88 0 88
Condition33%1/3
@seq and not grep({not @$_;} @seq)
!ll&&!rl&&r
0088
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)
ABresult
0X0
100
111
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
BranchTrueFalseTotal
$dict{$_} > $s->[0]{$_} ? : 2808 17402 20210
26 1492 } grep { $s->[0]{$_} } keys %dict;
27 }
28  
29 88 ▶ last unless %dict;
Branch: 1 branch
BranchTrueFalseTotal
unless %dict 6 82 88
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
BranchTrueFalseTotal
if (@$_) 18175 0 18175
if @$_ == shift(@$_)->{$lcs[-1]} 1470 16705 18175
35 }
36 }
37  
38 6 ▶ wantarray ? @lcs : scalar @lcs;
Branch: 1 branch
BranchTrueFalseTotal
wantarray ? : 6 0 6
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
BranchTrueFalseTotal
if ($dict{$_}[0] == $i) 22010 303541 325551
54 22010 shift @{ $dict{$_} };
55 22010 ▶ delete $dict{$_} if !@{ $dict{$_} };
Branch: 1 branch
BranchTrueFalseTotal
unless @{$dict{$_};} 1760 20250 22010
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
BranchTrueFalseTotal
unless %dict 0 104 104
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  
↑ Summary