I built fzgrep, a lightweight, OpenMP-parallelized fuzzy line matcher written in pure C with zero external runtime dependencies.
The Problem
In standard UNIX pipelines, filtering text has two well-known extremes:
-
grep/ripgrep: Incredibly fast for exact substrings and regex, but completely unforgiving when handling typos or fuzzy criteria. -
fzf: A masterpiece for interactive TUI navigation, but not designed to be dropped headlessly into non-interactive batch pipelines.
I needed something in between: a pipeline-native fuzzy matcher that accepts stdin or files, runs headlessly, and fully utilizes modern multi-core CPUs.
Architecture & Design
1. Dynamic Single-Row Levenshtein
Instead of allocating a full $O(N \times M)$ distance matrix, fzgrep computes Levenshtein distance using a dynamic single-row cache ($O(N)$ space complexity).
2. Chunk-Based MapReduce via OpenMP
Fuzzy matching on large text streams is computationally heavy. fzgrep solves this with a chunk-based MapReduce model:
- The main thread buffers incoming lines into chunks (8,192 lines by default).
- Worker threads parallelize the distance calculations across available CPU cores (configurable with
-j). - Results are deterministically aggregated, sorted by similarity score (descending), and tie-broken alphabetically.
3. Word Match Mode (-w) and Coordinate Tracking (-n)
Beyond full-line distance checks, fzgrep can split lines into space-delimited tokens to match against individual words. Combining -w with -n emits compiler-friendly coordinates:
# Word match mode with coordinates & scores
echo "hello everyone" | fzgrep -s -n -w -t 0.3 "eve"
Enter fullscreen mode Exit fullscreen mode
0.38 1:7:2:hello everyone
Enter fullscreen mode Exit fullscreen mode
(Line 1, column 7, word 2)
Quick Example: Typo-Tolerant Pipeline
Filter a large list of symbols or logs with typo tolerance:
cat /usr/share/dict/words | fzgrep -j 8 -t 0.8 "algotithm"
Enter fullscreen mode Exit fullscreen mode
algorithm
Enter fullscreen mode Exit fullscreen mode
Prefixing matches with similarity scores (-s):
echo -e "apple\napplication\napricot\nbanana" | fzgrep -t 0.5 -s "appl"
Enter fullscreen mode Exit fullscreen mode
0.80 apple
0.57 application
Enter fullscreen mode Exit fullscreen mode
Source Code & Roadmap
The source code, automated test suite, and prebuilt binaries are available under GPL-2.0 on GitHub:
👉 https://github.com/xsigil/fzgrep
I would love to hear feedback from the community:
- How would you handle chunk sizing on gigabyte-scale streams?
- Are there specific distance metrics or pruning techniques you’d like to see added?
Feel free to check it out, run the tests, and leave your thoughts in the comments!
“””