Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
I implemented this at work. Sadly, I can't (yet) share the code, but I can certainly explain how it works.

As the article explains, you grovel over your corpus and extract a list of all the unique words from that corpus (after stemming and removing stopwords, of course). Each of those words will be represented by a dimension in an N-dimensional space. So, for example, if your list of words is "beer", "pie", "ninja" (the three best things ever), then you will be working with a three dimensional space whose axes are labelled "beer", "pie" and "ninja" instead of x, y and z.

Once you have the list of words, you construct a vector in your N-dimensional space for each document. You simply go through each document, stemming all the words and removing stopwords again, and each time a word appears, you add one to the relevant dimension.

The document "ninjas like pie" would therefore become:

[0, 1, 1]

and the document "I'll have beer, beer, more beer and a pie please" would be:

[3, 1, 0]

Those look exactly like co-ordinates in the N-dimensional space, which they are. However, because of what we do with them later, it is better to think of them as vectors - that is, they are directions from the [0, 0, 0] point, the "origin". [0, 1, 1] represents the direction "due east and up at an angle of 45 degrees", for example.

So now we have reduced each document to a vector, which we can store in a nice compact index. To search the index, we take the user's search terms and reduce them to a vector just like we did with the documents. Any words which don't appear in the index - ie for which we don't have a dimension - are ignored.

Now we need to see how close this vector is to all of the vectors in the index. Seeing that all the vectors are lines which cross at the origin, we can define their closeness as the angle between them. The smaller the angle, the closer the vectors. You need to do this for *all* document vectors.

You will note that there is an angle between all possible vectors, so you need to choose a cut-off angle so that you only return results which are reasonably close. What that angle is will depend on your data and your usage patterns.

The advantages of a vector search are:

  • You get document ranking for free - smaller angle == better match;
  • Users get sane results without having to learn about ANDs and ORs which is often beyond their poor little branes;

The disadvantages are:

  • Needs lots of tuning - what weight to give to different parts of the document, how to weight words which appear many times, what angle to start throwing results away;
  • Can't search for phrases;
  • Have to compare the search to all documents and perform a calculation, so won't scale to huge data sets

In reply to Re: OT: Vector based search engine by DrHyde
in thread OT: Vector based search engine by Ryszard

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others making s'mores by the fire in the courtyard of the Monastery: (7)
    As of 2014-07-12 13:18 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      When choosing user names for websites, I prefer to use:








      Results (240 votes), past polls