Signature Search

npm API reference

Full-text search for static sites.

Signature Search is a JavaScript library that indexes documents as compact Ribbon filters for searching. 

npm install @pacote/signature-search
A signature: a small table of bits, built once from a document’s words.

The problem

Hosting a static website and with no server to ask, search must run in the visitor’s browser and the index ships with the site. A conventional inverted index lists every word and every document it appears in. Even on a medium sized site, it can be a lot of bytes before anyone has typed anything.

Signature Search is for sites where that cost is too high and a hosted search service is either not an option or an unnecessary complication. It gives up some accuracy to offer you a considerably smaller index that you can query even while offline.

How it works

A Ribbon filter is a close cousin of the Bloom filter. It is built once from a complete set of words, which it stores as a compact table of bits. Asking about a word either rules it out for certain or says it probably was there. For the same error rate, the table is smaller than a Bloom filter’s, and the price is that it cannot be changed once built. A document is indexed in one go, so that costs nothing here. Try one by hand.

Signature Search keeps a set of filters per document. Adding a document runs its text through five steps. Here is one short passage going through all of them.

Original

“There! there again! there she breaches! right ahead! The White Whale, the White Whale!”

Tokens

there there again there she breaches right ahead the white whale the white whale

Stopwords

there (stop word) there (stop word) again (stop word) there (stop word) she (stop word) breaches right (stop word) ahead (stop word) the (stop word) white whale the (stop word) white whale

Stopwords are words so common they match almost every document and say nothing about any of them. Dropping them keeps the filters small.

Stems

breaches → breachwhitewhalewhitewhale

Stemming cuts a word back to its root, so “breaches” and “breaching” both become “breach”. A Ribbon filter only answers for whole words, so stemming is how a search finds other forms of the word. Signature Search takes any stemmer you give it. See what one does to a word.

Filters

seen 2× white, whale

seen 1× breach

The resulting stems are then counted, weighted by field, and grouped by how often they occur. Each group becomes its own Ribbon filter, a table of fingerprint rows. Shown here with 4-bit rows; build one yourself.

A search runs the query through the same steps, then asks every document’s filters about each stem. Which filter answered says roughly how often the word occurs, and that frequency is combined with how rare the word is across the candidates (using tf-idf) to order the results. Tokens are double hashed with xxHash64, so the filters need only two fast hash computations per word.

Because the index holds filters and not words, it cannot be read back as text, though it can still answer searches. Only the summary fields you choose are stored in the clear. See what that looks like.

What you get

  • A compact index. Size follows how many distinct words each document has and the error rate you choose.
  • No false negatives. If a document contains the word, it is returned.
  • Query operators. +word requires, -word excludes and "two words" matches a phrase.
  • Ranking. Results come back best first, with weights per field.
  • Hooks. Plug in your own stemmer, tokenizer, stopword rule and preprocessing.
  • Plain data. The index is an object you can write to JSON or MessagePack at build time and load in the browser.

Trade-offs

  • False positives. A document can match a word it does not contain. At the default errorRate of 0.0001 that is about one lookup in ten thousand, per filter. Lower it and the index grows.
  • Whole words only. No prefixes, suffixes, substrings or fuzzy matching. A stemmer recovers some of this (“searching” finds “searched”); the rest is out of reach.
  • Approximate ranking. Frequency is known only to its bucket, not exactly.
  • It does not scale forever. Each document repeats its own vocabulary, whereas an inverted index shares it. “Bloom filters are good for search that does not scale” puts the crossover for Bloom filters near 7,200 documents. Measure with your own content before you commit.
  • Build and browser must agree. Same stemmer, same seed, same tokenizer. Change one and you rebuild the index. The index carries a schema version, and load() throws on a mismatch.

Alternatives

The comparison measures six libraries on the same corpus. These are the trade-offs behind the numbers.

Library Index Good for
Signature Search A set of Ribbon filters per document Small to medium sites that want ranking and the smallest payload.
Bloom Search A set of Bloom filters per document The previous incarnation of this library, built on Bloom filters. Superseded by Signature Search, whose index is smaller.
Elasticlunr Inverted index Inspired by Lunr’s approach, with field search and query-time boosting.
Fuse.js Bitap algorithm Fuzzy matching on small data sets.
Lunr Inverted index Ranking, field boosting and stemming, when the full index is affordable.
MiniSearch Inverted index Prefix and fuzzy matching, with ranking.