# trie-rules

> Performs fast search and replace on a text based on a set of rules.

Latest version **3.3.0** (published 2026-02-11) · MIT license · 0 weekly downloads

## Install

```sh
npm install trie-rules
pnpm add trie-rules
yarn add trie-rules
bun add trie-rules
```

## Health

**Score 60/100 (C)** — status: stable.

Positive: has types; esm support; no vulnerabilities; has provenance.

Warnings: low downloads.

## Facts

| | |
|---|---|
| Version | 3.3.0 |
| Published | 2026-02-11 |
| First published | 2023-09-11 |
| Weekly downloads | 0 |
| License | MIT |
| TypeScript types | bundled |
| Module format | ESM + CommonJS |
| Node | >=24.0.0 |
| Dependencies | 0 |
| Unpacked size | 137.9 KB |
| Known vulnerabilities | 0 |
| Install scripts | no |
| Provenance | attested (GitHub Actions) |
| Author | Ragaeeb Haq |
| Maintainers | ragaeeb |
| Keywords | search, replace, trie |

## Links

- npm: https://www.npmjs.com/package/trie-rules
- Repository: https://github.com/ragaeeb/trie-rules
- Issues: https://github.com/ragaeeb/trie-rules/issues
- npm.io page: https://npm.io/package/trie-rules

## Alternatives

- [jsforce](https://npm.io/package/jsforce.md) — 851.2K weekly downloads
- [react-native-qrcode-svg](https://npm.io/package/react-native-qrcode-svg.md) — 693.5K weekly downloads
- [@salesforce/plugin-data](https://npm.io/package/@salesforce/plugin-data.md) — 394.9K weekly downloads
- [@backstage/plugin-search-common](https://npm.io/package/@backstage/plugin-search-common.md) — 308.5K weekly downloads
- [@chain-registry/types](https://npm.io/package/@chain-registry/types.md) — 38.4K weekly downloads

## Recent versions

- 3.3.0 (latest) — 2026-02-11
- 3.2.0 — 2025-08-24
- 3.1.0 — 2024-11-10
- 3.0.1 — 2024-11-10
- 3.0.0 — 2024-11-09
- 2.0.2 — 2024-10-19
- 2.0.1 — 2024-09-08
- 2.0.0 — 2024-08-14
- 1.0.3 — 2023-11-05
- 0.1.0 — 2023-09-11

## README

<p align="center">
  <img src="icon.png" width="128" alt="trie-rules icon">
</p>

# Table of Contents

- [Introduction](#introduction)
- [Features](#features)
- [Live Demo](#live-demo)
- [Usage Guide](#trie-rules-usage-guide)
    - [Installation](#installation)
    - [API](#api)
        - [buildTrie](#buildtrie)
        - [searchAndReplace](#searchandreplace)
        - [containsTarget](#containstarget)
        - [containsSource](#containssource)
        - [confirmCallback](#confirmcallback)
        - [optimizeRules](#optimizerules)
- [Performance](#performance)
    - [Background History](#background-history)
    - [Advantages of trie-based search over regex](#advantages-of-trie-based-search-over-regex)
- [Development](#development)

# Introduction

[![wakatime](https://wakatime.com/badge/user/a0b906ce-b8e7-4463-8bce-383238df6d4b/project/58624615-104c-4910-9245-ff6a17984295.svg)](https://wakatime.com/badge/user/a0b906ce-b8e7-4463-8bce-383238df6d4b/project/58624615-104c-4910-9245-ff6a17984295)
![GitHub](https://img.shields.io/github/license/ragaeeb/trie-rules)
![npm](https://img.shields.io/npm/v/trie-rules)
![npm](https://img.shields.io/npm/dm/trie-rules)
![GitHub issues](https://img.shields.io/github/issues/ragaeeb/trie-rules)
![GitHub stars](https://img.shields.io/github/stars/ragaeeb/trie-rules?style=social)
![GitHub Release](https://img.shields.io/github/v/release/ragaeeb/trie-rules)
[![codecov](https://codecov.io/gh/ragaeeb/trie-rules/graph/badge.svg?token=GI262PTZB8)](https://codecov.io/gh/ragaeeb/trie-rules)
[![Size](https://deno.bundlejs.com/badge?q=trie-rules@latest&badge=detailed)](https://bundlejs.com/?q=trie-rules%40latest)
![typescript](https://badgen.net/badge/icon/typescript?icon=typescript&label&color=blue)
[![Demo](https://img.shields.io/badge/demo-live-brightgreen)](https://trie-rules.surge.sh)

The `trie-rules` project is an efficient search and replace algorithm that performs replacements on any given text based on a predefined rule set.

This project was mainly created to replace transliterations of Arabic words in Roman text along with their appropriate diacritics in a performant way.

However the rule set structure is flexible enough to apply to a wide range of applications.

## Features

- **High-performance trie builder** – Use `buildTrie` to normalise apostrophes and fan out case variants so that lookups remain fast even with thousands of rules.
- **Deterministic matching utilities** – Check for rule coverage with `containsSource` and `containsTarget`, or run full replacements through `searchAndReplace` with opt-in confirmation callbacks.
- **Rule optimization** – Use `optimizeRules` to automatically detect and consolidate redundant patterns: case-insensitive variants, apostrophe normalization, prefix deduplication, subset elimination, and conflict detection.
- **Comprehensive text helpers** – Re-use the exported helpers such as `isAlphabeticLetter`, `findFirstAlphaIndex`, `generateCaseVariants`, `adjustCasing`, `adjustClipping`, and `insertWordIntoTrie` to implement bespoke trie-aware transformations.
- **Rule-level ergonomics** – Fine-tune matching with `CaseSensitivity`, `MatchType`, `TriePattern`, and contextual clipping support.
- **Modern toolchain** – The project now builds with a lightweight `tsdown` pipeline (powered by Bun and TypeScript) and uses Biome for linting and formatting.
- **Export regression tests** – A post-build validation step (`test:exports`) type-checks and runtime-tests the built bundle to ensure all public API members and types are correctly exported.

## Live Demo

Try the interactive demo at **[trie-rules.surge.sh](https://trie-rules.surge.sh)**.

The demo loads a real-world transliteration rule set, builds a trie, and lets you see `searchAndReplace` in action — click the text area to apply formatting, click outside to see the original, and hit Randomize for a fresh sample.

The demo source lives in [`demo/`](./demo) and is deployed to [Surge](https://surge.sh) via `bun run deploy`.

## trie-rules Usage Guide
# trie-rules Usage Guide

This guide explains how to use the exported functions from `trie-rules`.

## Installation

```bash
npm install trie-rules
# or
yarn add trie-rules
# or
pnpm i trie-rules
# or
bun add trie-rules
```

## `buildTrie(rules: Rule[], options?: BuildTrieOptions): TrieNode`

The `buildTrie` function constructs a trie data structure from an array of `rules`. This trie is used to efficiently search through text and replace specified source words with their corresponding to words.

### Parameters:

- `rules` (Array of `Rule` objects): Each `Rule` object should have the following properties:
    - `from` (Array of strings): The words to search for in the text.
    - `to` (string): The word to replace the from with in the text.
    - `options` (optional `RuleOptions`):
        - `match` (optional `MatchType`):
            - `MatchType.Whole`: The match must be a whole word (letters/diacritics around it disallowed; punctuation/symbols allowed).
            - `MatchType.Alone`: The match must be surrounded by whitespace.
            - `MatchType.Any` (default): Match in any context.
        - `prefix` (optional `string`): If absent in text, add this before the replacement.
        - `casing` (optional `CaseSensitivity`):
            - `CaseSensitivity.Insensitive`: Adjust replacement letter casing to input.
            - `CaseSensitivity.Sensitive`: Preserve replacement casing as-is.
        - `clipStartPattern` (optional `RegExp` | `TriePattern`): Characters to trim immediately before the match.
        - `clipEndPattern` (optional `RegExp` | `TriePattern`): Characters to trim immediately after the match.
        - `confirm` (optional `ConfirmOptions`): Conditions that must be met for the rule to apply.
- `options` (optional `BuildTrieOptions`): Global options for the trie:
    - `normalizeApostrophes` (optional `boolean`): When true, treats all apostrophe-like characters as equivalent during matching. This allows a rule with "don't" to match variants like "don't", "don`t", etc. Normalization is applied to rule sources during build time and to input text during search time. Defaults to false.

### Returns:

- `TrieNode`: The root node of the trie data structure that represents the rules for search and replacement.

### Usage:

```js
import { buildTrie, MatchType, CaseSensitivity, TriePattern } from 'trie-rules';

const rules = [
    {
        from: ['example', 'sample'],
        to: 'demo',
    },
    {
        from: ['specificword'],
        to: 'replacement',
        options: {
            match: MatchType.Whole,
        },
    },
    {
        from: ['anotherword'],
        to: 'substitute',
        options: {
            match: MatchType.Alone,
            prefix: 'pre-',
        },
    },
    {
        from: ['testword'],
        to: 'tested',
        options: {
            casing: CaseSensitivity.Insensitive,
            clipStartPattern: TriePattern.Apostrophes,
            clipEndPattern: /[`'ʾʿ'']+$/,
            confirm: { anyOf: ['condition1', 'condition2'] },
        },
    },
    {
        from: ["al-Qur'an"],
        to: 'al-Qurʾān',
        options: {
            match: MatchType.Whole,
        },
    },
];

// Build trie with apostrophe normalization enabled
const trie = buildTrie(rules, { normalizeApostrophes: true });

// The trie can now be used with the searchAndReplace function to process text.
// With normalizeApostrophes enabled, "al-Qur'an" will match "al-Qur'an", "al-Qur`an", etc.
```

Note:
The function assumes case-sensitive matching by default. The trie constructed is optimized for the `searchAndReplace` function provided in the same library, and it may not be compatible with other search functions or trie implementations.

## `searchAndReplace(trie: TrieNode, text: string, options?: SearchAndReplaceOptions): string`

The `searchAndReplace` function takes a trie data structure and a text string as inputs and searches the text for words that match any of the from described in the trie. When a match is found, it replaces the word in the text with the corresponding to word from the trie.

### Parameters:

- `trie` (`TrieNode`): The trie data structure that should be used for the search-and-replace operation. This trie should be constructed using the `buildTrie` function.
- `text` (string): The text in which to search for and replace words.
- `options` (`SearchAndReplaceOptions`, optional): Additional options to customize the search and replace behavior.
  • confirmCallback (ConfirmCallback): A callback function to determine whether a replacement should proceed based on confirmation options.
  • log (function): A logging function that receives information about the current node being processed. Useful for debugging or tracking the replacement process.

### Returns:

- `string`: A new string with all occurrences of the source words replaced by their corresponding to words as defined by the rules in the trie.

### Usage:

```js
import { buildTrie, searchAndReplace } from 'trie';

// Define your rules
const rules = [
    {
        from: ["Ka'bah"],
        to: 'Kaʿbah',
    },
    // ... (other rules as defined in the buildTrie documentation) ...
];

// Build the trie from the rules with apostrophe normalization
const trie = buildTrie(rules, { normalizeApostrophes: true });

// The text you want to process
const text = 'We visited the Ka`bah yesterday.'; // Note the backtick apostrophe

// Perform the search and replace operation
const replacedText = searchAndReplace(trie, text);

console.log(replacedText); // Outputs: 'We visited the Kaʿbah yesterday.'
```

Note: If the trie was built with `normalizeApostrophes: true`, the search operation will automatically treat all apostrophe-like characters (', ', `, ʾ, ʿ) as equivalent to the standard apostrophe (') for matching purposes.

## `containsTarget(trie: TrieNode, to: string): boolean`

The `containsTarget` function checks whether a given to string is present as a replacement in the trie data structure.

### Parameters:

- `trie` (`TrieNode`): The trie data structure to search within. This trie should be constructed using the `buildTrie` function.
- `to` (string): The to replacement string to search for in the trie.

### Returns:

- `boolean`: Returns `true` if the to is present in the trie as a replacement, `false` otherwise.

### Usage:

```js
// Assuming trie is already built using buildTrie
const targetExists = containsTarget(trie, 'demo');
console.log(targetExists); // Outputs true if 'demo' is a to in the trie, false otherwise.
```

## `containsSource(trie: TrieNode, source: string): boolean`

The `containsSource` function determines if a given source string is represented within the trie data structure. This can be particularly useful to verify if a source word has been included in the trie and is therefore searchable and replaceable using the `searchAndReplace` function.

### Parameters:

- `trie` (`TrieNode`): The trie data structure previously built using the `buildTrie` function.
- `source` (string): The source string for which to check presence in the trie.

### Returns:

- `boolean`: True if the source string is present in the trie, false otherwise.

### Usage Example:

```js
// Assuming the trie has been built using the buildTrie function with your rules
const trie = buildTrie(rules);

// Check if the source 'example' is in the trie
const isSourceInTrie = containsSource(trie, 'example');
console.log(isSourceInTrie); // Outputs true if 'example' is a source in the trie, false otherwise.
```

## `confirmCallback` Feature

The `confirmCallback` feature in `searchAndReplace` function adds a confirmation step before making a replacement. It uses the `confirmCallback` provided by the user to decide whether the replacement should proceed.

### Functionality:

When the `searchAndReplace` function encounters a source string that matches a rule with a `confirm` option, it will invoke the `confirmCallback` with an object containing the rule's `anyOf` array. The callback should return `true` to allow the replacement, or `false` to prevent it.

The callback is crucial for situations where context-sensitive replacements are needed, such as matching transliterations based on the presence of specific Arabic phrases in the surrounding text. If the callback returns false, or if it is not provided, the function defaults to making the replacement based on the standard rule set.

### Edge Case Handling:

If the `confirmCallback` is not provided, the replacement will proceed as normal without confirmation. This ensures backward compatibility and allows for optional usage of the feature.

### Example Usage:

```js
const rules = [
    {
        to: 'Mālik',
        from: ['Maalik', 'Malik'],
        options: { match: 'whole', confirm: { anyOf: ['مالك', 'مَالِكٍ', 'مَالِكٌ'] } },
    },
];

const trie = buildTrie(rules);
const text = 'Maalik went home.';
const confirmCallback = (options) => options.anyOf.some((word) => text.includes(word));

const replacedText = searchAndReplace(trie, text, { confirmCallback });
console.log(replacedText); // Outputs: 'Mālik went home.'
```

## optimizeRules

`optimizeRules(rules: Rule[], options?: BuildTrieOptions): OptimizeResult`

The `optimizeRules` function analyzes an array of rules and automatically consolidates redundant patterns, returning an optimized rule set along with statistics and warnings.

### Optimizations Performed

1. **Case sensitivity consolidation** – Detects sources that differ only in case (e.g., `['Source', 'source']`) and consolidates them into a single source with `casing: CaseSensitivity.Insensitive`.
2. **Apostrophe normalization** – When `normalizeApostrophes: true` is set, consolidates sources that differ only in apostrophe-like characters.
3. **Prefix optimization** – Detects redundant prefix variations (e.g., `['Bukhari', 'al-Bukhari']`) and adds a `prefix` option instead.
4. **Clip pattern optimization** – Detects leading/trailing apostrophe-like characters and adds `clipStartPattern` / `clipEndPattern` options.
5. **Subset elimination** – Removes rules whose sources are a subset of another rule with the same target.
6. **Conflict detection** – Warns when the same source maps to different targets.
7. **Match type consolidation** – Merges rules with different `MatchType` values for the same source/target, keeping the most permissive.

### Parameters

- `rules` (Array of `Rule` objects): The rules to optimize.
- `options` (optional `BuildTrieOptions`): Same options as `buildTrie` (e.g., `normalizeApostrophes`).

### Returns

- `OptimizeResult`:
    - `optimizedRules` (`Rule[]`): The optimized array of rules.
    - `savings.sourcesRemoved` (`number`): How many individual sources were eliminated.
    - `savings.rulesRemoved` (`number`): How many entire rules were eliminated.
    - `warnings.conflicts` (`array`): Sources that map to different targets.
    - `warnings.overwrittenRules` (`array`): Rules that would be overwritten in the trie.

### Usage

```js
import { optimizeRules } from 'trie-rules';

const rules = [
    { from: ['Source', 'source'], to: 'Target' },
    { from: ['Bukhari', 'al-Bukhari'], to: 'Bukhari' },
    { from: ['Source1', 'Source2', 'Source3'], to: 'Target' },
    { from: ['Source1', 'Source2'], to: 'Target' },
];

const result = optimizeRules(rules);
console.log(result.optimizedRules);
// Consolidated rules with fewer sources and automatic options
console.log(result.savings);
// { sourcesRemoved: N, rulesRemoved: M }
console.log(result.warnings);
// { conflicts: [...], overwritten: [...] }
```

## Apostrophe Normalization

The `normalizeApostrophes` feature allows for flexible matching of words containing apostrophe-like characters. When enabled, the following characters are treated as equivalent:

- Standard apostrophe: ' (U+0027)
- Curly apostrophe: ’ (U+2019)
- Backtick: ` (U+0060)
- Modifier letter apostrophe: ʼ (U+02BC)
- Arabic hamza above: ʾ (U+02BE)
- Arabic ain: ʿ (U+02BF)

### Example Usage:

```js
const rules = [
    {
        from: ["al-Qur'an"],
        to: 'al-Qurʾān',
        options: { match: MatchType.Whole },
    },
    {
        from: ["Ka'bah"],
        to: 'Kaʿbah',
    },
];

const trie = buildTrie(rules, { normalizeApostrophes: true });

// All of these will match and be replaced:
console.log(searchAndReplace(trie, "The recitation of al-Qur'an is important"));
// Output: "The recitation of al-Qurʾān is important"

console.log(searchAndReplace(trie, 'We went by the Ka`bah yesterday.'));
// Output: "We went by the Kaʿbah yesterday."

console.log(searchAndReplace(trie, 'The holy al-Qurʾan and sacred Kaʿbah'));
// Output: "The holy al-Qurʾān and sacred Kaʿbah"
```

# Performance

## Background History

Initially the rule sets were being compiled into a single Regex function.

```js
const Alone = (word) => `(?<!\\S)${word}(?!\\S) `;
const Bounded = (word) => `\\b${word}\\b`;

const sentenceCase = (text) => text.charAt(0).toUpperCase() + text.slice(1);

const applyRules = (dictionary, text) => {
    const regex = new RegExp(Object.keys(dictionary).join('|'), 'g');

    return text.replace(
        regex,
        (matched) => dictionary[Alone(matched.trim())] || dictionary[Bounded(matched)] || dictionary[matched] || '',
    );
};

const boundedSource = (whole, source) => {
    if (Number(whole) === 2) {
        return Alone(source);
    }

    return whole ? Bounded(source) : source;
};

const reduceSourceToTarget =
    ({ to, whole, caseless }) =>
    (full, source) => {
        const toReturn = { ...full };
        const wrappedSource = boundedSource(whole, source);

        toReturn[wrappedSource] = to;

        if (caseless) {
            toReturn[boundedSource(whole, sentenceCase(source))] = Number(caseless) === 1 ? sentenceCase(to) : to;
            toReturn[boundedSource(whole, source.toLowerCase())] = Number(caseless) === 1 ? to.toLowerCase() : to;
        }

        return toReturn;
    };

const reduceRuleToDictionary = (dictionary, rule) =>
    rule.from.split('|').reduce(reduceSourceToTarget(rule), dictionary);

describe('applyRules', () => {
    it('sentence with whole word and normal text', () => {
        const dictionary = {
            Sufyan: 'Sufyān',
            '\\bAli\\b': 'ʿAlī',
        };

        expect(applyRules(dictionary, 'Ali and Sufyan went with Alison to the park.')).toEqual(
            'ʿAlī and Sufyān went with Alison to the park.',
        );
    });

    it('should not replace az to al-', () => {
        const dictionary = {
            '\\baz\\b': 'al-',
        };

        expect(applyRules(dictionary, 'az-Zuhri')).toEqual('al--Zuhri');
    });

    it('should not replace az to al-', () => {
        const dictionary = {
            '(?<!\\S)az(?!\\S) ': 'al-',
            '(?<!\\S)Az(?!\\S) ': 'al-',
            '(?<!\\S)ath(?!\\S) ': 'al-',
            '(?<!\\S)al(?!\\S) ': 'al-',
            '(?<!\\S)Al(?!\\S) ': 'al-',
        };

        expect(applyRules(dictionary, 'az-Zuhri')).toEqual('az-Zuhri');
        expect(applyRules(dictionary, 'az Zuhri')).toEqual('al-Zuhri');
        expect(applyRules(dictionary, 'Az Zuhri')).toEqual('al-Zuhri');
        expect(applyRules(dictionary, 'ath Thawri')).toEqual('al-Thawri');
        expect(applyRules(dictionary, 'al Imam')).toEqual('al-Imam');
        expect(applyRules(dictionary, 'Al Imam')).toEqual('al-Imam');
    });
});
```

However this was very expensive to perform and it was increasingly complex to support custom rules as look-aheads and lookbacks can become more and more inefficient.

The `\b` word boundaries also did not match the diacritic characters.

The Regex engine performance is also platform dependent, so while on a Intel based chip it can perform well, on a ARM64 Apple silicon chip it can be suboptimal as has been witnessed.

### Advantages of regex based search and replacements:

The trie-based `searchAndReplace` algorithm has several advantages over a regular expression (regex) that uses the pipe `|` to match any one of multiple substrings:

1. **Performance for Large Sets of Patterns**: When you have a large number of strings to match against, a regex with many alternatives separated by pipes can become inefficient. The regex engine must check each alternative one by one every time it attempts a match. In contrast, a trie structures the search patterns in a tree, allowing for simultaneous comparison of multiple patterns. This can lead to faster searches, especially when the set of source strings share common prefixes.

2. **Worst-Case Time Complexity**: The time complexity of matching text using a regex can vary depending on the regex engine and the specific patterns being matched. In the worst case, particularly with complex patterns or when backtracking occurs, regex matching can degrade to exponential time complexity. On the other hand, a trie-based search can be performed in linear time relative to the length of the text being searched, which is generally more predictable and often faster.

3. **Memory Efficiency**: Although a trie may consume more memory than a compact regex pattern, the trie's memory usage is more predictable and scales linearly with the size of the input patterns. A complex regex, particularly one with many capturing groups or backreferences, can consume a large and unpredictable amount of memory during matching.

4. **Match Precedence and Overlap**: With a regex, if multiple patterns can match the same part of the text, the regex engine will choose based on the order of the patterns. This can be problematic if you have overlapping patterns and need to prioritize longer matches over shorter ones, which can be easily handled by a trie by storing the length of the matched patterns and checking for the longest match first.

5. **Custom Matching Rules**: A trie-based approach allows for custom matching logic, such as the `whole` and `alone` match options in your case, which would be more complex to implement with regex. With regex, you'd need to construct lookbehind and lookahead assertions for each pattern, which can become cumbersome and may not be supported in all regex engines.

6. **Dynamic Updates**: If the set of patterns needs to be updated frequently, updating a trie can be more efficient. Adding or removing a pattern from a trie is a matter of inserting or deleting nodes, whereas modifying a regex pattern string requires recompiling the entire regex.

7. **Complex Replacements**: Your trie-based approach allows for complex replacements based on custom logic, like adding prefixes where they are missing. This kind of logic goes beyond simple pattern matching and substitution and would require additional processing outside of the regex replace function.

8. **Apostrophe Normalization**: The trie-based approach allows for sophisticated character normalization, such as treating different apostrophe-like characters as equivalent, which would be complex and inefficient to implement with regex patterns.

In summary, while a regex can be a powerful tool for pattern matching, a trie-based approach can offer better performance, especially with a large and complex set of patterns, and provides more flexibility for custom matching and replacement logic.

### Runtime Complexity

Let's analyze the runtime complexity of both functions separately:

#### `buildTrie` Function

The `buildTrie` function takes an array of rule objects, each with a `from` array and a `to` string. For each source word in each rule, it inserts the word into the trie.

- Let \( n \) be the number of rules.
- Let \( m \) be the average number of source words per rule.
- Let \( k \) be the average length of the source words.

The function iterates over each rule and each source word within that rule. For each character in a source word, it performs a constant time check and possibly inserts a new node into the trie.

The complexity is then \( O(n \cdot m \cdot k) \). Since \( n \), \( m \), and \( k \) are independent, you can think of this as the total number of characters across all source words in all rules.

#### `searchAndReplace` Function

The `searchAndReplace` function iterates over the characters in the input text and attempts to match substrings to words in the trie.

- Let \( l \) be the length of the text to search through.
- Let \( k \) be the average length of the source words (as defined above).

For each character in the text, in the worst case, the function might have to check \( k \) characters deep into the trie (if there's a potential match). However, note that due to the nature of a trie, the function does not always perform a linear scan of \( k \) characters for every character in \( l \); it can skip ahead whenever a complete word is matched and replaced. Therefore, the worst-case scenario would be if the text consisted of repeating patterns that are all present in the trie.

The complexity for this function can be \( O(l \cdot k) \) in the worst case.

However, if we consider that each character leads to a potential match and we have to check the longest possible match each time, and if there are \( p \) potential matches for each position in the worst case, we might need to consider this as well, leading to a complexity of \( O(l \cdot k \cdot p) \). The value of \( p \) would typically be small and could be considered constant if we assume a limit on the number of variations for a source word in the rules.

In the average and best-case scenarios, where the text doesn't consist of repeating patterns and not every character leads to a match, the performance would be closer to \( O(l) \), since the trie structure allows for quick elimination of non-matching paths.

In practice, the actual performance would depend on the specifics of the input data, such as the size and structure of the trie, and the distribution and frequency of potential matches in the text.

## Performance

We conducted benchmarks on core functions using [ESBench](https://esbench.vercel.app/). The following results reflect the average time per operation on real-world data sets.

Text reporter: Format benchmark results of 1 suites:
Suite: benchmark/trie-benchmark.ts
| No. | Name | time | time.SD |
| --: | ---------------: | --------------: | -----------: |
| 0 | `buildTrie` | 2,767,130.81 ns | 12,732.94 ns |
| 1 | `containsSource` | 81.69 ns | 0.22 ns |
| 2 | `containsTarget` | 84,239.77 ns | 688.45 ns |
| 3 | `searchAndReplace` | 71,031.31 ns | 95.09 ns |

These benchmarks were performed on a `Apple M2 Pro` with `32GB RAM` specifications, using the `testing/rules.json` sample data.

## Development

The repository ships with Bun-based scripts to keep builds reproducible:

| Command | Description |
| --- | --- |
| `bun run build` | Bundles the library through the local `tsdown` pipeline and emits type declarations. Automatically runs `test:exports` post-build. |
| `bun test` | Executes the unit test suite via Bun's test runner. |
| `bun run test:exports` | Type-checks and runs the exports validation test (`testing/exports.test.ts`) against the built `dist/` bundle. |
| `bun run lint` | Runs Biome using the settings in `biome.json` for linting. |
| `bun run format` | Formats source files with Biome's formatter. |
| `bun run benchmark` | Runs ESBench performance suites from `benchmark/`. |

### Demo

The interactive demo lives in `demo/` and is a Vite + Preact app that imports `trie-rules` from npm.

| Command | Description |
| --- | --- |
| `bun run dev` | Starts the Vite dev server at `http://localhost:5173`. |
| `bun run build` | Builds the production bundle into `demo/dist/`. |
| `bun run deploy` | Builds and deploys to [trie-rules.surge.sh](https://trie-rules.surge.sh) via Surge. |

When dependencies need updating, run `bun update --latest`. If your environment has restricted registry access, configure an appropriate mirror before running the command.

---
_Source: https://npm.io/package/trie-rules · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._