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, 2016 at 2:15
  • @Paparazzi: your point eludes me. Aug 18, 2016 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, 2016 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, 2016 at 8:04
  • 1
    Your words - "having to keep two copies of the Internet".
    – paparazzo
    Aug 18, 2016 at 8:14

3 Answers 3


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. Aug 18, 2016 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. Aug 18, 2016 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, 2016 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). Aug 18, 2016 at 13:38
  • @VioletGiraffe That's exactly what I wrote :) Aug 18, 2016 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, 2016 at 6:30
  • Yeah, not completely sure why I wrote that. Corrected to "database" :) Aug 18, 2016 at 6:41
  • Still not a good word. It would be two tables in a database.
    – paparazzo
    Aug 18, 2016 at 6:44
  • Ugh, I'm half asleep. Sorry >.< Aug 18, 2016 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? Aug 18, 2016 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, 2016 at 13:26
  • The votes didn't come from me. Aug 18, 2016 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, 2016 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, 2016 at 13:58
  • Ain't you a fun person to talk to ;) Aug 18, 2016 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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