Introduction
Thetrie-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 originally created to replace transliterations of Arabic words in Roman text with their appropriate diacritics in a performant way. However, the rule set structure is flexible enough to apply to a wide range of applications.
Live Demo
Try the interactive demo to see trie-rules in action with real-world transliteration rules
Key features
High-performance trie builder
Use
buildTrie to normalize apostrophes and fan out case variants so that lookups remain fast even with thousands of rulesDeterministic matching utilities
Check for rule coverage with
containsSource and containsTarget, or run full replacements through searchAndReplace with opt-in confirmation callbacksRule optimization
Use
optimizeRules to automatically detect and consolidate redundant patterns: case-insensitive variants, apostrophe normalization, prefix deduplication, subset elimination, and conflict detectionComprehensive text helpers
Re-use the exported helpers such as
isAlphabeticLetter, findFirstAlphaIndex, generateCaseVariants, adjustCasing, and insertWordIntoTrie to implement bespoke trie-aware transformationsWhy trie-based search?
The trie-based approach offers several advantages over traditional regex-based search and replace:Performance for large pattern sets
Performance for large pattern sets
When you have thousands of strings to match, a regex with many alternatives becomes inefficient. A trie structures patterns in a tree, allowing simultaneous comparison of multiple patterns for faster searches, especially when patterns share common prefixes.
Predictable time complexity
Predictable time complexity
Trie-based search runs in linear time relative to the text length, while regex can degrade to exponential complexity with backtracking. The worst-case performance is O(l × k) where l is text length and k is average pattern length.
Custom matching rules
Custom matching rules
Easily implement custom matching logic like
MatchType.Whole (word boundaries) and MatchType.Alone (whitespace-surrounded) without complex lookahead/lookbehind assertions.Apostrophe normalization
Apostrophe normalization
Treats different apostrophe-like characters (’, ’, `, ʾ, ʿ) as equivalent, which would be complex and inefficient with regex patterns.
Performance benchmarks
Benchmarks conducted on Apple M2 Pro with 32GB RAM using the sample data fromtesting/rules.json:
| Operation | Average Time | Standard Deviation |
|---|---|---|
buildTrie | 2,767,130.81 ns | 12,732.94 ns |
containsSource | 81.69 ns | 0.22 ns |
containsTarget | 84,239.77 ns | 688.45 ns |
searchAndReplace | 71,031.31 ns | 95.09 ns |
These benchmarks demonstrate the efficiency of trie-based operations, with sub-microsecond lookups and fast replacement operations even on large rule sets.
Modern toolchain
- Built with lightweight
tsdownpipeline powered by Bun and TypeScript - Uses Biome for linting and formatting
- Export regression tests via
test:exportsto ensure all public API members are correctly exported - Full TypeScript support with comprehensive type definitions
Next steps
Installation
Install trie-rules with your preferred package manager
Quick start
Get started with a working code example