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

> Explore fzf's fuzzy matching algorithm V1 vs V2. Learn how fzf uses greedy linear scan and dynamic programming for fast, optimal pattern matching.

- Repository: [Junegunn Choi/fzf](https://github.com/junegunn/fzf)
- Tags: internals
- Published: 2026-03-01

---

**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`](https://github.com/junegunn/fzf/blob/main/src/algo/algo.go) and invoked through the pattern matching pipeline in [`src/pattern.go`](https://github.com/junegunn/fzf/blob/main/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`](https://github.com/junegunn/fzf/blob/main/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`](https://github.com/junegunn/fzf/blob/main/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`](https://github.com/junegunn/fzf/blob/main/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`](https://github.com/junegunn/fzf/blob/main/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`](https://github.com/junegunn/fzf/blob/main/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`](https://github.com/junegunn/fzf/blob/main/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`](https://github.com/junegunn/fzf/blob/main/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`](https://github.com/junegunn/fzf/blob/main/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`](https://github.com/junegunn/fzf/blob/main/src/pattern.go):

```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`](https://github.com/junegunn/fzf/blob/main/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`](https://github.com/junegunn/fzf/blob/main/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`](https://github.com/junegunn/fzf/blob/main/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`](https://github.com/junegunn/fzf/blob/main/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`](https://github.com/junegunn/fzf/blob/main/src/merger.go) combines these partial results, applies sorting strategies like `ByRelevance`, and emits the final ranked list to the UI.