blib/lib/Search/VectorSpace.pm untested

filter: Statementstmt 0.0% 0 / 91 Branchbran 0.0% 0 / 4 Conditioncond 0.0% 0 / 8 MC/DCmcdc 0.0% 0 / 4 Subroutinesub 0.0% 0 / 15 Podpod 0.0% 0 / 10 totaltotal 0.0% 0 / 132 CC 3 SCAR 10.8
CC
3
Cov
0%
new
6.0
get_cosines
6.0
build_index
2.0
CRAP 2.9
1 package Search::VectorSpace;
2  
3 use warnings;
4 use strict;
5 use Lingua::Stem;
6 use Carp;
7 use PDL;
8  
9 our $VERSION = '0.02';
10  
11 =head1 TITLE
12  
13 Search::VectorSpace - a very basic vector-space search engine
14  
15 =head1 SYNOPSIS
16  
17 use Search::VectorSpace;
18
19 my @docs = ...;
20 my $engine = Search::VectorSpace->new( docs => \@docs, threshold => .04);
21 $engine->build_index();
22
23 while ( my $query = <> ) {
24 my %results = $engine->search( $query );
25 print join "\n", keys %results;
26 }
27  
28 =head1 DESCRIPTION
29  
30 This module takes a list of documents (in English) and builds a simple in-memory
31 search engine using a vector space model. Documents are stored as PDL objects,
32 and after the initial indexing phase, the search should be very fast. This
33 implementation applies a rudimentary stop list to filter out very common words, and
34 uses a cosine measure to calculate document similarity. All documents above
35 a user-configurable similarity threshold are returned.
36  
37 =head1 METHODS
38  
39 =over
40  
41 =item new docs => ARRAYREF [, threshold => VALUE ]
42  
43 Object constructor. Argument hash must contain a key 'docs' whose value is a reference
44 to an array of documents. The hash can also contain an optional threshold setting,
45 between zero and one, to serve as a relevance cutoff for search results.
46
47 =cut
48  
49 sub new {
50 my ( $class, %params ) = @_;
51 croak 'Usage: Search::VectorSpace->new( docs => \@docs);' unless
52 exists ( $params{'docs'} ) and
53 ref( $params{'docs'} ) and
54 ref( $params{'docs'}) eq 'ARRAY';
55
56 my $self =
57 {
58 docs => $params{'docs'},
59 threshold => $params{'threshold'} || .001,
60 stop_list => load_stop_list(),
61 };
62
63 return bless $self, $class;
64 }
65  
66 =item build_index
67  
68 Creates the document vectors and stores them in memory, along with a master
69 word list for the document collection.
70  
71 =cut
72  
73 sub build_index() {
74 my ( $self ) = @_;
75 print "Making word list:\n";
76 $self->make_word_list();
77 my @vecs;
78 foreach my $doc ( @{ $self->{'docs'} }) {
79 my $vec = $self->make_vector( $doc );
80 push @vecs, norm $vec;
81 }
82 $self->{'doc_vectors'} = \@vecs;
83 print "Finished with word list\n";
84 }
85  
86 =item search QUERY
87  
88 Returns all documents matching the QUERY string above the set relevance threshold.
89 Unlike regular search engines, the query can be arbitrarily long, and contain
90 pretty much anything. It gets mapped into a query vector just like the documents
91 in the collection were.
92 Returns a hash in the form RESULT => RELEVANCE, where the relevance value is between
93 zero and one.
94  
95 =cut
96  
97 sub search {
98 my ( $self, $query ) = @_;
99 my $qvec = $self->make_vector( $query );
100
101 my %result_list = $self->get_cosines( norm $qvec );
102 my %documents;
103 foreach my $index ( keys %result_list ) {
104 my $doc = $self->{'docs'}->[$index];
105 my $relevance = $result_list{$index};
106 $documents{$doc} = $relevance;
107 }
108 return %documents;
109 }
110  
111 =item get_words STRING
112  
113 Rudimentary parser, splits string on whitespace and removes punctuation.
114 Returns a hash in the form WORD => NUMBER, where NUMBER is how many times
115 the word was found.
116  
117 =cut
118  
119 sub get_words {
120
121 # Splits on whitespace and strips some punctuation
122 my ( $self, $text ) = @_;
123 my %doc_words;
124 my @words = map { stem($_) }
125 grep { !( exists $self->{'stop_list'}->{$_} ) }
126 map { lc($_) }
127 map { $_ =~/([a-z\-']+)/i}
128 split /\s+/, $text;
129 do { $_++ } for @doc_words{@words};
130 return %doc_words;
131 }
132  
133 =item stem WORD
134  
135 Convenience wrapper for Lingua::Stem::stem()
136  
137 =cut
138  
139 sub stem {
140 my ( $word) = @_;
141 my $stemref = Lingua::Stem::stem( $word );
142 return $stemref->[0];
143 }
144  
145  
146 sub make_word_list {
147 my ( $self ) = @_;
148 my %all_words;
149 foreach my $doc ( @{ $self->{docs} } ) {
150 my %words = $self->get_words( $doc );
151 foreach my $k ( keys %words ) {
152 #print "Word: $k\n";
153 $all_words{$k} += $words{$k};
154 }
155 }
156
157 # create a lookup hash of word to position
158 my %lookup;
159 my @sorted_words = sort keys %all_words;
160 @lookup{@sorted_words} = (1..$#sorted_words );
161
162 $self->{'word_index'} = \%lookup;
163 $self->{'word_list'} = \@sorted_words;
164 $self->{'word_count'} = scalar @sorted_words;
165 }
166  
167 sub make_vector {
168 my ( $self, $doc ) = @_;
169 my %words = $self->get_words( $doc );
170 my $vector = zeroes $self->{'word_count'};
171
172 foreach my $w ( keys %words ) {
173 my $value = $words{$w};
174 my $offset = $self->{'word_index'}->{$w};
175 index( $vector, $offset ) .= $value;
176 }
177 return $vector;
178 }
179  
180  
181 sub get_cosines {
182 my ( $self, $query_vec ) = @_;
183 my %cosines;
184 my $index = 0;
185 foreach my $vec ( @{ $self->{'doc_vectors'} }) {
186 my $cosine = cosine( $vec, $query_vec );
187 $cosines{$index} = $cosine if $cosine > $self->{'threshold'};
188 $index++;
189 }
190 return %cosines;
191 }
192  
193 # Assumes both incoming vectors are normalized
194 sub cosine {
195 my ( $vec1, $vec2 ) = @_;
196 my $cos = inner( $vec1, $vec2 ); # inner product
197 return $cos->sclr(); # converts PDL object to Perl scalar
198 }
199  
200  
201 sub load_stop_list {
202 my %stop_words;
203 while (<DATA>) {
204 chomp;
205 $stop_words{$_}++;
206 }
207 return \%stop_words;
208 }
209  
210  
211  
212 1;
213  
214 =back
215  
216 =head1 AUTHOR
217  
218 Maciej Ceglowski <maciej@ceglowski.com>
219  
220 This program is free software, released under the GNU public license
221  
222 =cut
223  
224 __DATA__