| 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__ |