Savant Realms

FizzMatch: Building a Fuzzy Search Package

FizzMatch: Building a Native Fuzzy Search Package in TypeScript

—

by

Savant Realms Admin
in , , ,

Introduction

When users search, exact matches aren’t always enough. They type typos like “acress” instead of “access,” or “fuzz match” instead of “fuzzy match.” Enter FizzMatch, a TypeScript npm package that implements fuzzy string search from scratch—no wrappers around other libraries. In this step-by-step post, we’ll build:

  • A basic Levenshtein distance function.
  • An optimized distance function using a rolling matrix.
  • A search function that ranks an array of strings by similarity.
  • Configurable options for threshold and case-insensitivity.
  • A complete npm package that you can install with npm install fizzmatch.

Whether you need to power auto-complete, implement search-as-you-type, or provide typo-tolerant lookup, FizzMatch is ready for your project. Let’s start coding!

0. Initial Setup: Creating the Project

0.1 Create the Directory and Initialize npm

mkdir fizzmatch
cd fizzmatch
npm init -y

This gives us a package.json:

{
    "name": "fizzmatch",
    "version": "0.1.0",
    "description": "A TypeScript package for fuzzy string search",
    "main": "dist/index.js",
    "types": "dist/index.d.ts",
    "scripts": {
        "build": "tsc",
        "prepare": "npm run build"
    },
    "keywords": ["fuzzy", "search", "levenshtein", "typescript"],
    "author": "Your Name <[email protected]>",
    "license": "MIT",
    "dependencies": {},
    "devDependencies": {}
}

0.2 Install TypeScript and Testing Tools

{
    "compilerOptions": {
        "target": "ES2019",
        "module": "CommonJS",
        "declaration": true,
        "outDir": "./dist",
        "strict": true,
        "esModuleInterop": true,
        "forceConsistentCasingInFileNames": true,
        "skipLibCheck": true
    },
    "include": ["src"],
    "exclude": ["node_modules", "dist"]
}

0.3 Create the Source Folder

mkdir src
touch src/index.ts

Project structure now:

fizzmatch/
├── src/
│   └── index.ts
├── package.json
├── tsconfig.json
└── node_modules/

We’re ready to code the core functionality.

1. Step 1: Implementing Basic Levenshtein Distance

Fuzzy search relies on edit distance—the minimum number of single-character edits required to turn one string into another. The classic algorithm uses a 2D matrix. Let’s implement a straightforward version in src/index.ts.

// src/index.ts

/**
 * Compute the Levenshtein distance between two strings.
 * Basic implementation using a 2D matrix.
 */
export function levenshteinDistance(a: string, b: string): number {
    const m = a.length;
    const n = b.length;
    // Create a (m+1)x(n+1) matrix
    const dp: number[][] = Array.from({ length: m + 1 }, () =>
        Array(n + 1).fill(0)
    );

    // Initialize base cases
    for (let i = 0; i <= m; i++) {
        dp[i][0] = i;
    }
    for (let j = 0; j <= n; j++) {
        dp[0][j] = j;
    }

    // Populate matrix
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            const cost = a[i - 1] === b[j - 1] ? 0 : 1;
            dp[i][j] = Math.min(
                dp[i - 1][j] + 1,     // deletion
                dp[i][j - 1] + 1,     // insertion
                dp[i - 1][j - 1] + cost // substitution
            );
        }
    }

    return dp[m][n];
}

1.1 Testing the Distance Function

Create a quick test file test-lev.ts:

// test-lev.ts
import { levenshteinDistance } from "./dist/index";

console.log(levenshteinDistance("kitten", "sitting")); // expected 3
console.log(levenshteinDistance("flaw", "lawn"));      // expected 2
console.log(levenshteinDistance("saturday", "sunday")); // expected 3

Build and run:

npm run build
npx ts-node test-lev.ts

You should see 3, 2, and 3 respectively. Our basic Levenshtein implementation works!

2. Step 2: Optimizing with a Rolling Array

A full 2D matrix costs O(m×n) memory. We can optimize space to O(min(m, n)) by keeping only two rows at a time. Let’s refactor.

Replace the function in src/index.ts with:

/**
 * Optimized Levenshtein distance using only two rows.
 */
export function levenshteinDistance(a: string, b: string): number {
    const m = a.length;
    const n = b.length;

    // Ensure n &lt;= m to use less space
    if (n > m) {
        [a, b] = [b, a];
        [m, n] = [n, m];
    }

    let previousRow: number[] = Array.from({ length: n + 1 }, (_, i) => i);
    let currentRow: number[] = Array(n + 1).fill(0);

    for (let i = 1; i &lt;= m; i++) {
        currentRow[0] = i;
        for (let j = 1; j &lt;= n; j++) {
            const cost = a[i - 1] === b[j - 1] ? 0 : 1;
            currentRow[j] = Math.min(
                previousRow[j] + 1,       // deletion
                currentRow[j - 1] + 1,    // insertion
                previousRow[j - 1] + cost // substitution
            );
        }
        [previousRow, currentRow] = [currentRow, previousRow];
    }

    return previousRow[n];
}

This reduces memory usage while keeping O(m×n) time. Rebuild and rerun tests to confirm results remain the same.

3. Step 3: Building the Search Function

Now that we can compute distances, let’s create a function to search an array of strings given an input. We want:

  • A function search(query: string, list: string[], options?) that returns a sorted array of matches with distances.
  • Options like threshold to filter out anything above a max distance.
  • Option ignoreCase to compare case-insensitively.

Add to src/index.ts:

/**
 * Optimized Levenshtein distance using only two rows.
 */
export function levenshteinDistance(a: string, b: string): number {
    // ... existing code
}

/**
 * Search options.
 */
export interface SearchOptions {
    threshold?: number; // maximum distance allowed
    ignoreCase?: boolean; // compare without case
}

/**
 * A search result entry.
 */
export interface SearchResult {
    item: string;
    distance: number;
}

/**
 * Perform fuzzy search on a list of strings.
 * Returns matches sorted by ascending distance.
 */
export function search(
    query: string,
    list: string[],
    options: SearchOptions = {}
): SearchResult[] {
    const { threshold = Infinity, ignoreCase = true } = options;
    const results: SearchResult[] = [];

    // Normalize query if ignoring case
    const normQuery = ignoreCase ? query.toLowerCase() : query;

    for (const item of list) {
        const target = ignoreCase ? item.toLowerCase() : item;
        const dist = levenshteinDistance(normQuery, target);
        if (dist <= threshold) {
            results.push({ item, distance: dist });
        }
    }

    // Sort by distance (lower is better), then alphabetically
    return results.sort((a, b) => {
        if (a.distance === b.distance) {
            return a.item.localeCompare(b.item);
        }
        return a.distance - b.distance;
    });
}

3.1 Testing the Search Function

Create test-search.ts:

// test-search.ts
import { search } from "./dist/index";

const data = [
    "apple",
    "application",
    "banana",
    "bandana",
    "orange",
    "grape",
    "pineapple",
];

console.log("Search for 'appl':");
console.table(search("appl", data, { threshold: 3 }));

console.log("\nSearch for 'banan':");
console.table(search("banan", data, { threshold: 2 }));

Build and run:

npm run build
npx ts-node test-search.ts

Results might look like:

Search for 'appl':
┌─────────┬─────────────┬─────────┐
│ (index) │    item     │ distance │
├─────────┼─────────────┼─────────┤
│    0    │  'apple'    │    1    │
│    1    │ 'application'│   7    │ (filtered if threshold too low)
...

(Adjust threshold to see meaningful results.)

4. Step 4: Adding Convenience Functions

Basic search is great, but sometimes you want top N matches or just the best match. Let’s add:

  • topMatch(query, list, options): returns the single best match (if any).
  • topNMatches(query, list, n, options): returns top N results.

Add:

/**
 * Optimized Levenshtein distance using only two rows.
 */
export function levenshteinDistance(a: string, b: string): number {
    // ... existing code
}

/**
 * Search options.
 */
export interface SearchOptions {
    // ... existing code
}

/**
 * A search result entry.
 */
export interface SearchResult {
    // ... existing code
}

/**
 * Perform fuzzy search on a list of strings.
 * Returns matches sorted by ascending distance.
 */
export function search(
    query: string,
    list: string[],
    options: SearchOptions = {}
): SearchResult[] {
    // ... existing code
}

/**
 * Return the single best match, or undefined if none within threshold.
 */
export function topMatch(
    query: string,
    list: string[],
    options: SearchOptions = {}
): SearchResult | undefined {
    const results = search(query, list, options);
    return results.length > 0 ? results[0] : undefined;
}

/**
 * Return up to n top matches.
 */
export function topNMatches(
    query: string,
    list: string[],
    n: number,
    options: SearchOptions = {}
): SearchResult[] {
    const results = search(query, list, options);
    return results.slice(0, n);
}

4.1 Testing topMatch and topNMatches

Create test-top.ts:

// test-top.ts
import { topMatch, topNMatches } from "./dist/index";

const data = ["cat", "car", "cart", "dog", "door"];

console.log("Top match for 'caa':", topMatch("caa", data, { threshold: 2 }));
console.log("Top 3 matches for 'do':", topNMatches("do", data, 3));

Build and run:

npm run build
npx ts-node test-top.ts

Expected output:

Top match for 'caa': { item: 'car', distance: 1 }
Top 3 matches for 'do':
[ { item: 'do', distance: 0 }, { item: 'dog', distance: 1 }, { item: 'door', distance: 2 } ]

These convenience functions make FizzMatch easy to use in common scenarios.

5. Step 5: Packaging, Typings, and Publishing

With our core functions ready, we need to configure package.json and finish everything for npm.

5.1 Update package.json

Ensure it includes:

{
    "name": "fizzmatch",
    "version": "0.1.0",
    "description": "A TypeScript package for fuzzy string search",
    "main": "dist/index.js",
    "types": "dist/index.d.ts",
    "scripts": {
        "build": "tsc",
        "prepare": "npm run build"
    },
    "keywords": [
        "fuzzy",
        "search",
        "levenshtein",
        "typescript"
    ],
    "author": "Savant Realms <[email protected]>",
    "license": "MIT",
    "dependencies": {},
    "devDependencies": {
        "@types/node": "^22.15.29",
        "ts-node": "^10.9.2",
        "typescript": "^5.8.3"
    },
    "engines": {
        "node": ">=20.0.0",
        "npm": ">=10.0.0"
    }
}

prepare: runs npm run build before publishing.
types: points to our declaration file.

5.2 Add a README.md

# FizzMatch

FizzMatch: A TypeScript package for fuzzy string search, implemented from scratch.

## Overview

FizzMatch is a lightweight TypeScript module for fuzzy string search, implemented from scratch using Levenshtein distance. Perfect for auto-complete, typo-tolerant lookup, and search-as-you-type features.

## Installation

```bash
npm install fizzmatch
```

## Usage

```typescrip
import { search, topMatch } from &quot;fizzmatch&quot;;

const items = [&quot;apple&quot;, &quot;banana&quot;, &quot;orange&quot;];
console.log(search(&quot;appl&quot;, items));       // [ { item: &#039;apple&#039;, distance: 1 }, … ]
console.log(topMatch(&quot;banan&quot;, items));    // { item: &#039;banana&#039;, distance: 1 }
```

## Building Locally

```bash
npm install
npm run build
```

Usage

import {
    levenshteinDistance,
    search,
    topMatch,
    topNMatches,
    SearchOptions,
} from "fizzmatch";

// Compute distance
console.log(levenshteinDistance("kitten", "sitting")); // 3

// Search array
const data = ["apple", "application", "banana", "bandana"];
const options: SearchOptions = { threshold: 3 };
console.log(search("appl", data, options));

// Top match
console.log(topMatch("banan", data, { threshold: 2 }));

// Top N matches
console.log(topNMatches("ban", data, 2));

API

  • levenshteinDistance(a: string, b: string): number
  • search(query: string, list: string[], options?: SearchOptions): SearchResult[]
  • topMatch(query: string, list: string[], options?: SearchOptions): SearchResult | undefined
  • topNMatches(query: string, list: string[], n: number, options?: SearchOptions): SearchResult[]

SearchOptions

  • threshold?: number — Maximum edit distance allowed (default: Infinity).
  • ignoreCase?: boolean — Case-insensitive comparison (default: true).

Development

# Clone the repo
git clone https://github.com/savant-realms/fizzmatch.git
cd fizzmatch

# Install dependencies
npm install

# Build
npm run build

# Run tests/examples
npx ts-node examples/example.ts

License

MIT

### 5.3 Build and Link

```bash
npm run build
npm link
```

6.4 Publish to npm

Login (if not already):

npm login

Publish:

npm publish

Now anyone can install:

npm install fizzmatch

6. Step 6: Real-World Usage Examples

6.1 Auto-Complete Suggestions

Use FizzMatch in a Node.js script:

import { topNMatches } from "fizzmatch";

const items = ["Dashboard", "Settings", "Profile", "Logout", "Help"];

function suggest(query: string) {
    const suggestions = topNMatches(query, items, 3, { threshold: 2 });
    return suggestions.map((s) => s.item);
}

console.log(suggest("dasb")); // ['Dashboard']
console.log(suggest("profl")); // ['Profile']

Perfect for integrating into a backend or front-end auto-complete API.

6.2 Filtering Large Lists

When you have a big list of product names or tags, you can quickly find near-matches:

import { search } from "fizzmatch";

const products = [
    "Wireless Mouse",
    "Wired Mouse",
    "Wireless Keyboard",
    "Mechanical Keyboard",
    "USB-C Cable",
    "HDMI Cable",
];

const results = search("wireles mouze", products, { threshold: 3 });
console.log(results.map((r) => r.item));
// ['Wireless Mouse', 'Wireless Keyboard', ...]

7. Conclusion

Creating a useful npm package from scratch can be fulfilling—and with FizzMatch, you now have:

  • A native Levenshtein distance implementation in TypeScript.
  • A fuzzy search function that ranks matches by edit distance.
  • Convenience utilities (topMatch, topNMatches) for common scenarios.
  • Configurable options (threshold, ignoreCase) to tailor behavior.
  • A fully packaged module, ready to install via npm.

Whether you’re building CLI tools, backend services, or front-end components, FizzMatch can enhance your search features and handle user typos gracefully. Try it out:

npm install fizzmatch

Happy coding—and may your search results always find the right match!

GitHub Repo: https://github.com/savant-realms/fizzmatch

NPM package: https://www.npmjs.com/package/@savant-realms/fizzmatch

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *