How fzf's Fuzzy Matching Algorithm Works Internally: V1 vs V2 Implementation

fzf implements fuzzy matching through two selectable algorithms—V1 uses a greedy linear scan for speed, while V2 employs a modified Smith-Waterman dynamic programming approach for optimal scoring—both defined in src/algo/algo.go and invoked through the pattern matching pipeline in src/pattern.go.

The junegunn/fzf command-line fuzzy finder relies on a sophisticated scoring system to rank matches. Understanding how fzf's fuzzy matching algorithm works internally reveals why certain results appear first and how the tool balances search speed with result quality across large datasets.

The Matching Pipeline Architecture

fzf processes queries through a structured pipeline that transforms user input into ranked results. The journey from keystroke to sorted matches involves several coordinated components.

From Query to Pattern Object

When you type a query, options.ParseOptions builds a Pattern struct via BuildPattern in src/pattern.go (lines 76-118). This object stores:

• The raw query runes
• Case-sensitivity flags (CaseSmart, CaseIgnore, CaseRespect)
• Normalization settings
• A reference to the chosen fuzzy algorithm (algo.FuzzyMatchV1 or algo.FuzzyMatchV2)

By default, BuildPattern selects FuzzyMatchV2 for optimal scoring. Users can force the faster V1 algorithm by launching fzf with the --algo=v1 flag.

Chunk Scanning and Parallel Processing

The Matcher.scan method in src/matcher.go (lines 71-84) orchestrates parallel execution. It slices input data into chunks, then distributes these across multiple goroutines—one per CPU partition. Each goroutine calls Pattern.Match for every item in its assigned chunk.

Pattern.Match delegates to Pattern.iter (lines 55-68 in src/pattern.go), which selects the appropriate matching strategy based on pattern type (fuzzy, exact, prefix, or suffix). For fuzzy queries, it invokes the algorithm stored in p.fuzzyAlgo.

The Scoring Model

Both V1 and V2 algorithms share a common scoring schema defined by constants in src/algo/algo.go. The system rewards consecutive matches and boundary positions while penalizing gaps.

Core Scoring Constants

Constant	Value	Purpose
scoreMatch	16	Base points for each matched character
scoreGapStart	-3	Penalty for starting a gap between matches
scoreGapExtension	-1	Additional penalty for extending an existing gap
bonusBoundary	8	Bonus for matching at word boundaries
bonusNonWord	8	Bonus for matching after non-word characters
bonusCamel123	8	Bonus for camelCase or number transitions
bonusFirstCharMultiplier	2	Extra weight for the first character of the query

The Bonus Matrix

The bonusMatrix is a pre-computed lookup table for ASCII character classes (charWhite, charNonWord, charDelimiter, charLower, charUpper, charNumber). It is initialized once by algo.Init (lines 96-119 in src/algo/algo.go) and determines the bonus value for every possible character transition during matching.

Algorithm V1: Greedy Forward Scan

FuzzyMatchV1 in src/algo/algo.go (lines 14-30) prioritizes speed over absolute accuracy. It operates in O(n) time where n is the text length.

The algorithm executes three phases:

1. Index location: Uses asciiFuzzyIndex to find the first possible occurrence of the pattern through a simple forward scan.
2. Backward refinement: Walks backward from that position to locate the shortest substring that still contains all pattern characters in order, improving the match quality without full dynamic programming.
3. Score calculation: Calls calculateScore to compute the final score and optionally record match positions.

Because V1 stops after the first successful forward scan, it may miss optimal alignments when multiple candidate matches exist in the text. However, it runs approximately twice as fast as V2 on large inputs.

Algorithm V2: Dynamic Programming (Modified Smith-Waterman)

FuzzyMatchV2 in src/algo/algo.go (lines 32-70) implements a modified Smith-Waterman algorithm for optimal fuzzy matching. It runs in O(n·m) time where n is the text slice length and m is the pattern length, but guarantees the highest-scoring alignment.

The Four Phases of V2

Phase 1: Bonus Collection The algorithm first narrows the search window using asciiFuzzyIndex to find the region between the first and last possible matches. It copies the relevant text slice into a temporary rune buffer T, then pre-computes a per-character bonus array B using the bonus matrix.

Phase 2: First-Row DP Builds the initial row (H0) of the Smith-Waterman scoring matrix. This row represents matching the first pattern character against each position in the text slice. The algorithm simultaneously tracks the best score encountered so far.

Phase 3: Full DP Fills the remainder of the matrix (H) while maintaining a "consecutive-match" helper array (C). The matrix dimensions are M × (lastIdx-firstIdx+1), where M is the pattern length. This phase handles gap penalties, bonus additions, and match continuity.

Phase 4: Backtrace (Optional) When withPos is true, the algorithm walks backward from the highest-scoring cell to recover the exact character positions of the match. This reconstructs the optimal alignment path through the matrix.

Fallback Mechanism

V2 includes safeguards to prevent excessive resource consumption. If the pattern requires more than 1000 characters or the allocated integer slab is insufficient (lines 49-52 in src/algo/algo.go), the algorithm automatically falls back to FuzzyMatchV1 to ensure responsiveness.

Integration with the Matcher Pipeline

The algorithm selection occurs in Pattern.iter within src/pattern.go:

if p.fuzzy {
    return p.iter(p.fuzzyAlgo, …)   // V1 or V2
}

The p.fuzzyAlgo field is populated during BuildPattern initialization. By default, it points to algo.FuzzyMatchV2, but users can override this via the --algo=v1 command-line flag.

Once matching completes, the Result struct ({Start, End, Score}) is wrapped by buildResult and passed to the Merger in src/merger.go. The Merger combines results from parallel goroutines and applies sorting strategies (ByRelevance or ByRelevanceTac) before presenting the final ranked list to the user interface.

Summary

• fzf provides two algorithms: V1 (greedy, O(n)) for speed and V2 (dynamic programming, O(n·m)) for optimal scoring.
• Scoring rewards word boundaries, camelCase transitions, and consecutive matches while penalizing gaps.
• V2 uses a modified Smith-Waterman approach with four distinct phases: bonus collection, first-row DP, full matrix calculation, and optional backtracing.
• Parallel execution occurs in src/matcher.go, with the Merger combining results from multiple goroutines.
• Algorithm selection happens at pattern construction time via BuildPattern, defaulting to V2 but allowing V1 via --algo=v1.

Frequently Asked Questions

What is the difference between fzf's V1 and V2 algorithms?

V1 uses a greedy forward scan followed by a backward refinement pass to find matches in O(n) time, making it roughly twice as fast as V2 on large inputs but potentially missing optimal alignments. V2 implements a modified Smith-Waterman dynamic programming algorithm that runs in O(n·m) time to guarantee the highest possible score for every match, providing better result quality at the cost of computational overhead.

How does fzf calculate match scores?

fzf calculates scores using a weighted system defined in src/algo/algo.go that awards scoreMatch (16 points) for each character found, adds bonuses for word boundaries (bonusBoundary), camelCase transitions (bonusCamel123), and consecutive matches, while deducting scoreGapStart (-3) and scoreGapExtension (-1) for gaps between matched characters. The first character of the query receives a bonusFirstCharMultiplier (2x) weight to prioritize matches at the start of words.

When should I use the V1 algorithm instead of V2?

Use the V1 algorithm when processing extremely large datasets where search latency is critical and slight reductions in match quality are acceptable, or when running fzf on resource-constrained systems. You can activate V1 by starting fzf with the --algo=v1 command-line flag, which forces BuildPattern to use algo.FuzzyMatchV1 instead of the default algo.FuzzyMatchV2.

How does fzf handle parallel matching across multiple CPU cores?

fzf parallelizes matching through the Matcher struct in src/matcher.go, which splits input chunks across multiple goroutines using sliceChunks to create partitions equal to the number of available CPUs. Each goroutine independently calls Pattern.Match (which delegates to either V1 or V2 algorithms) on its assigned chunk, and the Merger in src/merger.go combines these partial results, applies sorting strategies like ByRelevance, and emits the final ranked list to the UI.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}