Wade is a 1kb Javascript search library. It allows you to create a function that can search an array of strings for a set of keywords, which is run through the processor. After this, it is searched for in each item of the data.

API

The API is extremely minimal and self-explanatory. It looks like:

const search = Wade(["He saves on socks.", "You are being silly."]);
search("save socks");

Preprocessor

Wade preprocesses all data to search for, and any search queries. This works by moving each item through a pipeline. This will do the following operations:

When you first give Wade an array of data, it will create a trie representing all indexes of the data.

The best way to understand how this works is to use an example. Say that the data given looks like:

["Hey", "Hello", "Greetings"]

After preprocessing, the data will look like:

["hey", "hello", "greetings"]

The generated trie for this will have an array holding the indexes the of items that have the keyword.

{
  "h": {
    "e": {
      "y": {
        "indexes": [0]
      },
      "l": {
        "l": {
          "o": {
            "indexes": [1]
          }
        }
      }
    }
  },
  "g": {
    "r": {
      "e": {
        "e": {
          "t": {
            "i": {
              "n": {
                "g": {
                  "s": {
                    "indexes": [2]
                  }
                }
              }
            }
          }
        }
      }
    }
  }
}

As you can see, the trie will make a single data structure representing all of the strings. Whenever a node has had the content of a string so far, it will contain an indexes property holding the indexes in the data that the node refers to.

This data structure can take some time to generate, but searching through it is a breeze.

Say we would like to search for "he". Wade will split this into keywords, and search for each of them in the trie individually, updating the score for the indexes as it goes.

Since there is only one keyword, Wade will treat it as a prefix, meaning that it will perform a depth-first search.

This works by traveling as far down the trie as possible, and then grabbing the index of itself and every node under it.

Let's go through this step by step. Wade will go through the keyword one by one, and see if it is in the trie.

  1. The current character is "h", it is inside of the trie, set the current node to it and continue.
  2. The current character is "e", set the current node to it.
  3. We have arrived at the end of the keyword, check all nodes below.
  4. Check "y". The node has an indexes property, increment the score for the index inside ([0]).
  5. Traverse through "e", "l", "l", and "o". The node has an indexes property, increment the score for the index inside ([1]).
  6. Nothing left, abort the search.

In the end, we will be left with a results array like:

[1, 1]

Both items have a score of 1, hence the value of each item in the results array being 1. The index of the item corresponds to the index in the data. Index 0 in the data ("Hey") has a score of 1, and index 1 in the data ("Hello"), has a score of 1.

We can see that we have returned the results for:

["Hey", "Hello"]

These both do indeed have the prefix of "he", which means we have successfully performed a search! For keyword that aren't treated as prefixes, Wade will not perform a depth-first search, and will increment the score for any indexes found if the whole keyword was matched. The last keyword of a query will be treated as a prefix, as the user might still be typing.

Conclusion

That is how Wade works! In a nutshell, it preprocesses data, splits it into keywords, and searches within a trie.

Be sure to check out the source on Github