Efficiently Searching for Partial Match in Large String Database [closed]

Question

I want to create a database of library book titles that can be searched efficiently for sub-string matches. That is, if I search for "Programming" then all of the book titles containing the word programming will be returned. This database may be pre-processed and will be stored entirely in memory.

What is an efficient data-structure and search algorithm to solve this? I would like to implement this entirely in C++, so please no 3rd party libraries.

Answer 1

Suffix tree is an efficient data structure for substrings search.

The idea is:
Create your suffix tree data structure, and from each leaf connect to the entry related to the book/s this suffix represents.
On query time - traverse the tree with the substring - and from the end point you reached (the longest match) - do some traversal (DFS for example) and retrieve all entries related to all suffixes that the query is a prefix of.

---

Of course, if you want only words and not all substrings, a map (tree/hash based) will probably be enough, and much easier to implement and use (The type should be map<string,list<book> > for example with the tree based approach, and it will map from each word to a list that contains all the books containing this word in the title).
You can also use a trie to implement the map.

Answer 2

For substring matching there is a simple scheme: split out the full title in "chunks" and create your database in the following fashion:

• each book is identified uniquely (ID/pointer)
• each "chunk" points to a set of book identifiers

When the user queries the system, split her request in chunks the same way to identify the matching books.

With this simple scheme, you have 2 points of functional customization: how to derive the chunks and how to rank the books; and 1 point of technical customization: how to "merge/join" the sets of the different matching chunks, which hinges on the way you want to rank the books.

How to derive chunks ?

A simple (but efficient) way would be to split on words boundary: The C++ Programming Language becomes {the, c++, programming, language}.

Note: often times, some words are ignored (black-listed). For example, The probably appear in 80% of the titles so it's not useful to consider it most of the times.

Note: the search should probably be case insensitive.

How to rank books ?

A naive algorithm is to return all the matches. A better one is to rank them according to the number of chunks in the query that matched that ID. An even better one is to rank higher those titles in which the words appear in the same order than the query (longest submatch). And of course you should perhaps consider synonyms.

The ranking is probably the heart of the system, Google is popular because its ranking algorithm works well meaning that if finds what you want.

How to implement the merge/join ?

Unless you only want to return search results that match all chunks in the original query (which is useful, but annoying because of synonyms), then you should keep ordered sets and build their intersection for each chunk:

• chunk1: {B1, B2, B7, B9, B15}
• chunk2: {B1, B7, B8, B13, B15}
• chunk3: {B1, B3, B4, B7, B9, B12, B13, B14, B15}

Then, intersect the sets of chunk1 and chunk2, leading to {B1, B7, B15} and intersect that with chunk3 (which does not change anything).

Note: beginning with the smaller sets allow you to keep smaller intermediate results which speeds up the result.

Note: when intersecting a small set with a much bigger set, linear walk of the bigger set might be much slower than binary search.

On the other hand, if you want to rank search results, then it's likely that you will need to keep as intermediary result a map ID -> score. That map may be either a binary search tree or a hash map (the latter being faster for very large collection but having some overhead for small ones in general).

Note that this ranking stuff is quite slow, in general, but easily parallelizable. That's what Google does with MapReduce.