DEV Community

Masahiro Sugaya
Masahiro Sugaya

Posted on

fzgrep: A zero-dependency, OpenMP-parallelized fuzzy line matcher in C

#linux #c #opensource #cli

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

Top comments (1)

Some comments may only be visible to logged-in visitors. Sign in to view all comments.