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" 
0.38 1:7:2:hello everyone

(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" 
algorithm

Prefixing matches with similarity scores (-s):

echo -e "apple\napplication\napricot\nbanana" | fzgrep -t 0.5 -s "appl" 
0.80 apple 0.57 application

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!
"""