match

Documentation

Overview

Package match ranks dictionary words against a possibly-misspelled query.

The design point is that neither matching strategy alone is enough for spell checking. Fuzzy subsequence matching, which is what fzf does, is very good when you know how a word starts and not how it ends ("onomat" -> "onomatopoeia"), and structurally incapable of finding "receive" from "recieve", because the letters are out of order. Edit distance finds the transposition instantly but ranks poorly for the prefix case. So both run, and results are placed in tiers.

Index

• func Distance(a, b []rune, max int) int
• func Fuzzy(text, query []rune, fold bool, positions *[]int) (score int, ok bool)
• func HasUpper(s []rune) bool
• func MaxDistance(queryLen int) int
• type Index
  • func NewIndex(words []string) *Index
  • func (ix *Index) Search(query string, limit int) []Result
• type Result
• type Tier
  • func (t Tier) String() string

Functions

func Distance

func Distance(a, b []rune, max int) int

Distance returns the optimal string alignment distance between a and b: Levenshtein extended with adjacent transposition, so "recieve" is distance 1 from "receive" rather than 2.

The transposition case is the whole reason this package exists. A fuzzy subsequence matcher cannot find "receive" from "recieve" at any score, because the letters are not in order; an edit metric finds it immediately.

It returns max+1 as soon as it can prove the true distance exceeds max, so callers can filter a large word list cheaply. Computation is banded to the diagonal ±max, which is what makes a full pass over ~124k words affordable on every keystroke.

func Fuzzy

func Fuzzy(text, query []rune, fold bool, positions *[]int) (score int, ok bool)

Fuzzy reports whether query is a subsequence of text and, if so, scores the match. positions, when non-nil, is filled with the index in text of each matched query rune, for highlighting.

fold selects case-insensitive comparison. This is fzf's FuzzyMatchV1: a forward pass to find a match, then a backward pass to tighten it to the last starting point that still matches, then scoring over that window.

func HasUpper

func HasUpper(s []rune) bool

HasUpper reports whether s contains an uppercase rune. It drives smart case: an all-lowercase query matches case-insensitively, a query with any capital is taken literally.

func MaxDistance

func MaxDistance(queryLen int) int

MaxDistance is the edit budget allowed for a query of the given rune length. Short queries get a tight budget because almost everything is within two edits of a three-letter word; long queries can afford more slack.

Types

type Index

type Index struct {
	Words []string
	// contains filtered or unexported fields
}

Index holds a word list prepared for repeated queries.

func NewIndex

func NewIndex(words []string) *Index

NewIndex prepares words for searching. The folded forms are computed once here rather than per keystroke.

func (*Index) Search

func (ix *Index) Search(query string, limit int) []Result

Search ranks the index against query and returns at most limit results. A limit of zero or less means no limit.

type Result

type Result struct {
	Word       string
	Tier       Tier
	Distance   int   // edit distance, meaningful for TierEdit
	Score      int   // fuzzy score, meaningful for TierFuzzy
	Shared     int   // length of the common prefix with the query
	Transposed bool  // the single edit was an adjacent swap
	Positions  []int // rune indices matched, for highlighting
}

Result is one ranked word.

type Tier

type Tier int

Tier orders the kinds of match against each other. A word found by more than one strategy is reported in its best tier.

The split of edit matches either side of fuzzy is deliberate. A single edit is a strong signal: it is the whole transposition case, and nearly every common misspelling is exactly one edit from its target. Two or more edits on a short query is mostly noise -- "Como" is two edits from "accomo" -- and should not bury a genuine fuzzy hit like "accommodate". So distance 1 ranks above fuzzy and the rest ranks below it.

const (
	TierExact  Tier = iota // the query is already the word
	TierPrefix             // the word begins with the query
	TierNear               // exactly one edit away, transposition included
	TierFuzzy              // the query is a subsequence of the word
	TierEdit               // two or more edits away
	TierAll                // listed with no query at all, so unranked

)

func (Tier) String

func (t Tier) String() string