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.

  • Two copies of the "Internet". Google Bing and few other are a bit ahead of you. Maybe scale back a bit. – paparazzo Aug 18 '16 at 2:15
  • @Paparazzi: your point eludes me. – Violet Giraffe Aug 18 '16 at 4:58
  • 1
    Do you have the horsepower to crawl the Internet for the words let a alone build a search engine? – paparazzo Aug 18 '16 at 6:50
  • 1
    Really, Google goes to WA for cheap power and 1 acre facility and anyone these day has the power. – paparazzo Aug 18 '16 at 8:04
  • 1
    Your words - "having to keep two copies of the Internet". – paparazzo Aug 18 '16 at 8:14

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.

  • I didn't mean searching for arbitrary character sequences, just specific forms of words rather than their basic forms. – Violet Giraffe Aug 18 '16 at 9:19
  • In this case you can add a document to the list both for the stemmed form and the actually used form of the word and OR the lists together. It does make your index larger but that's how most search engines do it. If you have a position index for phrase search, both forms of the word are marked at the same position. – Michał Kosmulski Aug 18 '16 at 13:01
  • this post is rather hard to read (wall of text). Would you mind editing it into a better shape? – gnat Aug 18 '16 at 13:05
  • @MichałKosmulski: it does make the index larger because now you have to specify words twice, along with their occurrences (in the stemmed form and the actual form). – Violet Giraffe Aug 18 '16 at 13:38
  • @VioletGiraffe That's exactly what I wrote :) – Michał Kosmulski Aug 18 '16 at 13:40

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.

  • Not going to search the Internet with a dictionary. Too many words in the Internet for in memory collection. – paparazzo Aug 18 '16 at 6:30
  • Yeah, not completely sure why I wrote that. Corrected to "database" :) – Paul Ferris Aug 18 '16 at 6:41
  • Still not a good word. It would be two tables in a database. – paparazzo Aug 18 '16 at 6:44
  • Ugh, I'm half asleep. Sorry >.< – Paul Ferris Aug 18 '16 at 6:45
  • On that, wouldn't it technically use three or more tables? One table for the stems, one table for the suffixes, one relational table to combine them into something that the application can easily access? – Paul Ferris Aug 18 '16 at 6:54

You just need four tables

position PK



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.

  • A vote to delete without a comment? Come on what does not work here? I provide table design and search. – paparazzo Aug 18 '16 at 13:26
  • The votes didn't come from me. – Violet Giraffe Aug 18 '16 at 13:38
  • @VioletGiraffe You also asked how to have word and stem. I showed you how without two separate indexes. "And worse, for the common search queries that do benefit from stemming, how do I even implement it?" I showed you how to search on stem and word. Phrase search should apply equally to stem and word. You have position - hint it will differ by 1. – paparazzo Aug 18 '16 at 13:48
  • Really that much you understood? "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." Sure does not indicate to me you understood it. I was going to edit to add how to do a phrase search. – paparazzo Aug 18 '16 at 13:58
  • Ain't you a fun person to talk to ;) – Violet Giraffe Aug 18 '16 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.