Designing a simple web search engine: how to address the need to search for exact phrases?

Question

I'm strongly considering a web search engine for my next pet project. All the basic principles are clear, but some details are not. Namely, I can't find a neat way to search by exact match, e. g. "The Who".

This requirement imposes limitations on how I can modify the source text:

1. I can't use a list of stop words (high frequency, low relevance words like prepositions - they might be very relevant in some corner cases!).
2. I can't use stemming (converting words to their basic lexical form). If I do use it, I can't tell "program" from "programmed" and so on.

Not being able to cast all words to their basic forms and to throw away common low value words means a much, MUCH larger index. And worse, for the common search queries that do benefit from stemming, how do I even implement it? The only solution I see is keeping two indices - one with actual words and one with stemmed words, but having to keep two copies of the Internet is not really a solution - one is already plenty to make me scratch my head.

Answer 1

A search engine would normally use an inverted index in order to be able to efficiently search through large amounts of data (the same principle is used if the documents come from a source different than a web crawler). You split the text into words, and for each word the inverted index contains IDs of the documents which contain that word. In order to search for a phrase, such as "internet search", you need to find documents which contain both words, and contain them exactly in the order given. This means you need an additional structure to hold the positions of words in each document.

Now, if you want an "exact match", things become much more complicated. There are countless possibilities for even two words, they could be separated by some special sequence such as "internet??#++-search" and you can't have all possible values as keys in your inverted index.

So, if you want to be able to match any substring, you are pretty much bound to using linear search instead of an index, which is prohibitively slow. As you will easily check, even google doesn't support search for arbitrary character sequences and will strip most non-alphanumeric characters.

So, implementing phrase search is quite possible, but exact match search for any arbitrary character search is not feasible for huge amounts of data such as internet search.

Answer 2

Stem, but sort by relationship. So exact matches come first, then close lexical pairs (programmed vs. programming, programmer), then stems, then entirely different forms (programmatic, programmatical...). English suffixes are fairly consistent, so while you'll need to store your data across two related tables (for the sake of the answer I'll assume your search terms are stored in a database) one of them is much shorter than the other; table [x] contains all the stems you can think of (or generate, you'd be insane to do it manually), while table [y] contains every relevant suffix. Given words are broken into two indices, one stem-index and one suffix-index, and that pair is used in the search process itself.

The related words ("lexical pairs") can be generated by repeating the search process with increasingly different suffixes: first you'd search with suffixes that are only one or two characters off from the input, then three or four, and so on. If you're handling arbitrary-length words, then you might store a standard length property for each class of suffixes and vary the repeated searches by proportional difference instead of absolute character length.

You could build a lexical parser that sorts words into adjectives, nouns, or verbs to possibly make the stem-suffix match more efficient, but it's not strictly necessary.

Answer 3

You just need four tables

Document
ID PK
position PK
wordID

Word
ID PK
word

stem
ID PK
stem

StemWord
stemID PK
wordID PK

Search word

select distinct d.ID
from Document d
join Word w
on w.ID = d.wordID
and w.word = 'diminished'

Search stem

select distinct d.ID
from Document d
join StemWord sw
on sw.wordID = d.wordID
join stem s
on s.ID = sw.stemID
and s.stem = stem('diminished')

It is simple. If you find that complex then I suggest you use a free library like Solr.