search

bun add @stopcock/search

Search data structures and algorithms. Fuzzy matching (Levenshtein, Jaro-Winkler, n-gram), a Trie for autocomplete, Bloom filters for probabilistic set membership, and an inverted index with BM25 ranking for full-text search.

import { Fuzzy, Trie, Bloom } from '@stopcock/search'

const results = Fuzzy.search('react', ['react', 'preact', 'vue', 'svelte'])
// [{ item: 'react', score: 1 }, { item: 'preact', score: 0.83 }]

Real-world patterns

Autocomplete search box

import { Trie, Fuzzy } from '@stopcock/search'

// Build index once
const trie = products.reduce((t, p) => Trie.insert(t, p.name), Trie.empty())

// Fast prefix match (typing "mac" → "MacBook Pro", "Mac Mini")
const prefixResults = Trie.startsWith(trie, query)

// Fuzzy fallback for typos ("macbok" → "MacBook")
const fuzzyResults = Fuzzy.searchBy(products, query, p => p.name, 0.6)

Full-text search with BM25 ranking

import { Index } from '@stopcock/search'

const docs = articles.map(a => ({ id: a.slug, text: `${a.title} ${a.body}` }))
const index = Index.buildIndex(docs)

const results = Index.search(index, 'functional programming typescript', { limit: 10 })
// [{ id: 'intro-to-fp', score: 4.2, text: '...' }, ...]

Bloom filter for seen-URL dedup

import { Bloom } from '@stopcock/search'

let seen = Bloom.create(100_000, 0.01)  // 100k URLs, 1% false positive rate

for (const url of crawlQueue) {
  if (Bloom.has(seen, url)) continue    // probably seen, skip
  seen = Bloom.add(seen, url)
  await crawl(url)
}

Fuzzy

Approximate string matching with scoring.

Fuzzy.search<T>(query: string, items: T[], opts?: FuzzyOptions<T>): FuzzyMatch<T>[]
Fuzzy.match(query: string, target: string): number

Binary

Binary search on sorted arrays.

Binary.search<A>(arr: A[], target: A, cmp?: (a: A, b: A) => number): number
Binary.lowerBound<A>(arr: A[], target: A, cmp?: (a: A, b: A) => number): number
Binary.upperBound<A>(arr: A[], target: A, cmp?: (a: A, b: A) => number): number

Trie

Prefix tree for fast string lookup and autocomplete.

Trie.empty(): Trie
Trie.insert(trie: Trie, word: string): Trie
Trie.has(trie: Trie, word: string): boolean
Trie.remove(trie: Trie, word: string): Trie
Trie.startsWith(trie: Trie, prefix: string): string[]
Trie.size(trie: Trie): number

Bloom

Probabilistic set membership. May return false positives, never false negatives.

Note

A Bloom filter that says “no” is always right. A Bloom filter that says “yes” is probably right. The false positive rate is configurable at creation time.

Bloom.create(expectedSize: number, falsePositiveRate?: number): BloomFilter
Bloom.add(filter: BloomFilter, item: string): BloomFilter
Bloom.has(filter: BloomFilter, item: string): boolean

Tokenize

Text tokenization for indexing.

Tokenize.words(text: string): string[]
Tokenize.ngrams(text: string, n: number): string[]
Tokenize.stem(word: string): string

Index

Inverted index for full-text search.

Index.create<T>(): InvertedIndex<T>
Index.add<T>(index: InvertedIndex<T>, id: T, text: string): InvertedIndex<T>
Index.search<T>(index: InvertedIndex<T>, query: string): T[]