Is all permutations of a string a good way to index full text search?

Question

I am writing an application to be used as a local disc documents store similar functionality to Firebase or MongoDB. The gist of how it works is a column hash table. For example:

Say I have a user document

{
  "first": "stack",
  "last": "overflow", 
  "age": 2147
}

I basically iterate each field as a column and save a hashed value as a filename for a file, that contains the unique row key(if multiple objects have the same value for a column there will be multiple row keys written to the file). Then save record in a directory with the key as the filename. So for a simple name = "stack" I have an O(1) lookup, hash the value, see if a file exists with the hashed value as a name, if exists, read all row keys from file. iterate each key and load data from file. I guess if the number of rows is large this will be a slower query.

What I am trying to do I want to ad a partial text search capability. My initial idea is to write all permutations of the value into the index and then do the same O(1) - file exists - check that I mentioned above. So if the query is name name contains st I will just look a filename for that value and read all rows keys.

Is this a good way to offer a partial text search? What are some common industry techniques?

Project

Answer 1

Is all permutations of a string a good way to index full text search?

Uhh, no. That is a very, very bad idea.

What happens when someone puts a moderately long string into your database? Say... like your question. Making a database of stack exchange questions seems like a normal sort of thing to do. At time of writing, just the content of the question is 1264 characters. The number of permutations of 1264 characters is... umm. Very large. My local calculator puts it around 4x10^3373. Even smaller strings will have enough permutations to fill up the entire bucket space of your hash, rendering it irrelevant.

I am not super familiar with common industry search techniques, but as I understand it they are largely machine learning algorithms these days. People do a search, you feed them some options, they pick the "right" one and your algorithm uses that feedback to correlate the search with the result to then find patterns in searches and results.

Answer 2

The most common indexes are balanced trees, where finding a partial match at the beginning is easy. A filesystem is not a good backing structure for any index because of the high overhead (I understand that you are doing this as a learning experience so performance doesn't matter as much) but certainly it's unsuitable for a tree as you need to access several nodes until you find the match and writes may require altering several nodes for rebalancing.

Full text indexes often are implemented as trees as well, for example PostgreSQL GIN indexes use a B-Tree. When partial matches beyond the word beginning and approximate matches are required some kind of n-gram index is a good choice, where consecutive groups of n characters are extracted from each word, as they are more robust against misspellings. A trigram index (n=3), like the one implemented in PostgreSQL, would split 'stack overflow' like 'sta'|'tac'|'ack'| |'ove'|'ver'|'erf'|'rfo'|'flo'|'low'.