How 30 Seconds of Code Implements Fuzzy Matching in Search

The 30 Seconds of Code search blends TF-IDF exact-term scoring with n-gram similarity to deliver fuzzy matching that tolerates typos and partial matches by weighting and combining these two metrics.

The fuzzy matching system in the Chalarangelo/30-seconds-of-code repository powers the Omni-search feature, allowing users to find code snippets even with misspelled or incomplete queries. Unlike simple substring matching, this implementation indexes content using inverted n-gram tables and applies a weighted scoring algorithm at query time. Understanding this architecture reveals how the site achieves sub-100ms search responses across thousands of snippets.

Building the N-Gram Search Index

The search index construction happens in src/lib/search/documentIndex.js, where the system creates two complementary data structures for every document. The addDocument method populates an invertedIndex for exact-term TF-IDF scoring and an ngramsInvertedIndex for fuzzy matching using 3-grams (trigrams).

When indexing content, the code generates n-grams from each term using the generateNgrams utility from src/lib/search/utils.js. This creates overlapping three-character sequences that catch character-level similarities between query terms and indexed content.

// src/lib/search/documentIndex.js
const ngrams = new Set(
  [...terms.keys()].reduce((ngrams, term) => {
    ngrams.push(...generateNgrams(term));   // ← creates 3-grams
    return ngrams;
  }, [])
);

The resulting ngramsInvertedIndex maps every 3-gram to a Set of document IDs, enabling rapid lookup of candidate documents during fuzzy search operations.

Query Scoring and Result Ranking

The core search logic resides in src/lib/search/documentSearch.js. The exported search function accepts a DocumentIndex instance and returns a curried function with the signature search(documentIndex)(query, limit, fuzzy).

Exact-Term Scoring

First, searchForTerms computes TF-IDF scores for stemmed tokens that exactly match the query. This provides the baseline relevance ranking based on precise term frequency calculations.

Fuzzy-Term Scoring

When the fuzzy parameter is greater than 0 (default 0.7), the engine executes searchForNgrams. This function:

• Tokenizes the query using tokenizeTokens
• Generates 3-grams for each token
• Counts n-gram intersections with documents via ngramsInvertedIndex
• Returns a similarity ratio calculated as matches / totalPossible

Blending the Scores

The final ranking combines exact and fuzzy scores using a weighted formula. With the default fuzzy = 0.7, n-gram similarity contributes 70% of the final score, while exact TF-IDF contributes 30%.

// src/lib/search/documentSearch.js – fuzzy scoring block
if (fuzzy > 0.0) {
  const ngramSimilarities = new Map(
    searchForNgrams(documentIndex, tokenizeTokens(query))
  );

  results = results.length
    ? results.map(([docId, score]) => {
        const ngramSimilarity = ngramSimilarities.get(docId) || 0;
        const finalScore = score * (1 - fuzzy) + ngramSimilarity * fuzzy;
        return [docId, finalScore];
      })
    : Array.from(ngramSimilarities.entries());
}

Setting fuzzy to 0 disables the n-gram component entirely, enforcing strict exact-match behavior.

Client-Side Search Integration

The browser-side implementation in src/astro/scripts/omnisearch.js loads the pre-generated index from public/search-data.json and instantiates a DocumentIndex. On every keystroke, it invokes the search function with the default threshold:

// src/astro/scripts/omnisearch.js
const results = this.searchDocuments(q, 100); // uses default fuzzy = 0.7

This configuration ensures users experience typo-tolerant fuzzy matching automatically without configuration options in the UI.

Implementing Fuzzy Search in Your Own Project

You can reuse the search library directly in Node.js or browser environments by importing the core modules.

Basic Search Usage

import DocumentIndex from '#src/lib/search/documentIndex.js';
import search from '#src/lib/search/documentSearch.js';
import { deserializeTokens } from '#src/lib/search/utils.js';

// Prepare documents with serialized search tokens
const docs = documents.map(({ url, searchTokens, ...rest }) => ({
  id: url,
  content: deserializeTokens(searchTokens),
  rawContent: searchTokens,
  url,
  ...rest,
}));

const index = new DocumentIndex(docs);
const runSearch = search(index);

// Search with default 70% fuzzy weighting
const results = runSearch('arry metods', 10);

Adjusting Fuzzy Sensitivity

To require stricter matches, pass a lower fuzzy value (between 0.0 and 1.0):

// 20% fuzzy weight, 80% exact match requirement
const strictResults = runSearch('arry metods', 10, 0.2);

// Disable fuzzy matching completely
const exactResults = runSearch('array methods', 10, 0.0);

Summary

• Dual-index architecture: The system maintains both a term-based inverted index for TF-IDF scoring and an n-gram index for character-level similarity.
• Configurable weighting: The fuzzy parameter (default 0.7) controls the blend between exact TF-IDF scores and n-gram similarity ratios.
• 3-gram analysis: Fuzzy matching relies on overlapping three-character sequences generated in src/lib/search/utils.js to detect typos and partial matches.
• Client-side execution: src/astro/scripts/omnisearch.js runs the search algorithm in the browser using a static index loaded from public/search-data.json.

Frequently Asked Questions

How does the fuzzy matching algorithm work in 30 Seconds of Code?

The algorithm combines TF-IDF exact-term scoring with n-gram similarity matching. It first calculates exact match scores using stemmed tokens, then generates 3-grams from the query to find character-sequence overlaps with indexed documents. These scores are blended using the formula score * (1 - fuzzy) + ngramSimilarity * fuzzy, where the default fuzzy value of 0.7 gives n-gram matches 70% weight in the final ranking.

What is the default fuzzy matching threshold?

The default fuzzy matching threshold is 0.7 (70%), as defined in the search function signature in src/lib/search/documentSearch.js. This means n-gram similarity contributes 70% of the final relevance score, while exact-term TF-IDF scoring contributes 30%, providing high tolerance for typos while maintaining exact match precision.

How can I disable fuzzy matching in the search?

To disable fuzzy matching, pass 0 as the third argument to the search function: search(index)(query, limit, 0). When the fuzzy parameter is set to 0.0, the conditional block in src/lib/search/documentSearch.js skips the n-gram scoring entirely, and results rely solely on exact TF-IDF term matching.

Which data structures enable the fuzzy search capability?

The fuzzy search relies on the ngramsInvertedIndex built in src/lib/search/documentIndex.js, which maps every 3-character n-gram to a Set of document IDs containing that sequence. This structure allows searchForNgrams in src/lib/search/documentSearch.js to quickly calculate Jaccard-like similarity scores without iterating through all documents linearly.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}