# How Ngram Similarity Enhances Fuzzy Search in 30 Seconds of Code

> Discover how ngram similarity improves fuzzy search in 30 Seconds of Code. Learn to implement typo tolerant matching with trigram comparison for better search results.

- Repository: [Angelos Chalaris/30-seconds-of-code](https://github.com/Chalarangelo/30-seconds-of-code)
- Tags: deep-dive
- Published: 2026-02-25

---

**Ngram similarity augments the TF-IDF scoring in 30 Seconds of Code by comparing overlapping character trigrams between queries and documents, enabling typo-tolerant matching when the fuzzy factor is above zero.**

The 30 Seconds of Code repository (`Chalarangelo/30-seconds-of-code`) implements a client-side search engine that combines traditional term frequency scoring with character-level n-gram analysis. When the `fuzzy` parameter is set above zero, the system blends TF-IDF term matching with trigram similarity to gracefully handle misspellings and partial queries, as orchestrated through [`src/lib/searchIndex.js`](https://github.com/Chalarangelo/30-seconds-of-code/blob/main/src/lib/searchIndex.js).

## Generating Character Trigrams

The search engine breaks each token into overlapping substrings of length three—trigrams—using the `generateNgrams` function in [`src/lib/search/utils.js`](https://github.com/Chalarangelo/30-seconds-of-code/blob/main/src/lib/search/utils.js):

```javascript
export const generateNgrams = (term, n = 3) => {
  const ngrams = [];
  for (let i = 0; i < term.length - n + 1; i++)
    ngrams.push(term.slice(i, i + n));
  return ngrams;
};

```

By default, this produces trigrams (3-character sequences) that capture the local character structure of terms without requiring exact lexical matches.

## Indexing N-grams for Fast Lookup

When documents are added to the search corpus, [`src/lib/search/documentIndex.js`](https://github.com/Chalarangelo/30-seconds-of-code/blob/main/src/lib/search/documentIndex.js) pre-computes trigrams for every term and stores them in an **inverted n-gram index**. This index maps each unique trigram to the set of document IDs containing it:

```javascript
const ngrams = new Set(
  [...terms.keys()].reduce((ngrams, term) => {
    ngrams.push(...generateNgrams(term));
    return ngrams;
  }, [])
);
// ...
ngrams.forEach(ngram => {
  if (!this.ngramsInvertedIndex.has(ngram))
    this.ngramsInvertedIndex.set(ngram, new Set());
  this.ngramsInvertedIndex.get(ngram).add(docId);
});

```

This inverted structure allows the engine to quickly locate candidate documents that share trigrams with the query, regardless of exact term boundaries.

## Computing Query-Document Ngram Similarity

During search execution, [`src/lib/search/documentSearch.js`](https://github.com/Chalarangelo/30-seconds-of-code/blob/main/src/lib/search/documentSearch.js) calculates similarity by comparing the query's trigrams against each document's stored n-gram set. The similarity score is the ratio of matching trigrams to the minimum number of trigrams present in either the query or document:

```javascript
const searchForNgrams = (documentIndex, terms) => {
  const ngramSimilarities = [];
  const queryNgrams = terms.reduce((acc, term) => {
    const ngrams = generateNgrams(term);
    acc.push(...ngrams);
    return acc;
  }, []);

  documentIndex.documents.forEach((doc, docId) => {
    const docNgrams = doc.ngrams;
    let matches = 0;
    const totalPossible = Math.min(queryNgrams.length, docNgrams.size);

    queryNgrams.forEach(ngram => {
      if (documentIndex.ngramsInvertedIndex.has(ngram) &&
          documentIndex.ngramsInvertedIndex.get(ngram).has(docId))
        matches++;
    });

    const ngramSimilarity = matches / totalPossible;
    if (ngramSimilarity > 0) ngramSimilarities.push([docId, ngramSimilarity]);
  });

  return ngramSimilarities;
};

```

This normalization using `Math.min` prevents short queries or documents from receiving artificially low scores, ensuring that a query like `"ar"` can still match `"array"` with high similarity if all query trigrams are present.

## Blending TF-IDF and Ngram Scores

The final relevance score blends the traditional TF-IDF term score with the ngram similarity using the configurable `fuzzy` parameter (default `0.7`). In [`src/lib/search/documentSearch.js`](https://github.com/Chalarangelo/30-seconds-of-code/blob/main/src/lib/search/documentSearch.js), the weighted combination is calculated as:

```javascript
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());
}

```

When `fuzzy` is `0.0`, the search relies purely on exact term matching. When `fuzzy` approaches `1.0`, ngram similarity dominates the ranking, making the search more permissive.

## Configuring Fuzzy Search Behavior

You can control the contribution of ngram similarity by adjusting the `fuzzy` parameter when calling the search function:

**Disable fuzzy matching (exact TF-IDF only):**

```javascript
const results = runSearch('array', 10, 0);

```

**Default behavior (30% ngram weight):**

```javascript
const results = runSearch('arrw', 10); // typo for "array", fuzzy defaults to 0.7

```

**Aggressive fuzzy matching (90% ngram weight):**

```javascript
const results = runSearch('ar', 10, 0.9);

```

## Summary

- **Ngram similarity** acts as a character-level fallback when exact term matching fails, using trigrams generated by `generateNgrams` in [`src/lib/search/utils.js`](https://github.com/Chalarangelo/30-seconds-of-code/blob/main/src/lib/search/utils.js).
- The **inverted n-gram index** in [`src/lib/search/documentIndex.js`](https://github.com/Chalarangelo/30-seconds-of-code/blob/main/src/lib/search/documentIndex.js) enables efficient lookup of documents sharing character sequences with the query.
- Similarity is computed as the ratio of shared trigrams to the minimum possible count, preventing short queries from being unfairly penalized.
- The final score blends TF-IDF and ngram similarity according to the `fuzzy` parameter, allowing developers to tune between precision and recall.

## Frequently Asked Questions

### How does ngram similarity handle typos in search queries?

Ngram similarity handles typos by matching overlapping character trigrams between the misspelled query and correct document terms. For example, a query like `"arrw"` shares trigrams `"arr"` and `"rrw"` with the word `"array"`, allowing the engine to surface the correct snippet despite the missing character.

### What is the default fuzzy factor and how does it affect results?

The default fuzzy factor is **0.7**, meaning the final relevance score combines 30% of the TF-IDF exact-match score with 70% weight on the ngram similarity score. This default provides a balance that catches moderate typos while maintaining precision for exact matches.

### Can I adjust the ngram size from the default of 3 characters?

The `generateNgrams` function accepts an optional `n` parameter, but the search implementation throughout `src/lib/search/` calls it with the default value of 3 (trigrams). While the function supports arbitrary lengths, the indexing and search pipelines are optimized for trigrams, which provide the best balance between specificity and typo tolerance for code snippet searches.

### Why does the similarity calculation use the minimum trigram count for normalization?

The calculation uses `Math.min(queryNgrams.length, docNgrams.size)` as the denominator to implement a **Jaccard-like similarity** that avoids penalizing short queries or documents. This ensures that a query with few trigrams can still achieve a high similarity score against a longer document if all its trigrams match, rather than being diluted by the document's total ngram count.