fuzzy

package
Version: v0.25.0 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jul 18, 2020 License: MIT Imports: 7 Imported by: 0

Documentation

Overview

Package fuzzy implements fuzzy sorting and filtering.

Sort() and Match() implement fuzzy search, e.g. "of" will match "OmniFocus" and "got" will match "Game of Thrones".

Match() compares a query and a string, while Sort() sorts an object that implements fuzzy.Sortable. Both return Result structs for each compared string.

The algorithm is based on Forrest Smith's reverse engineering of Sublime Text's search: https://blog.forrestthewoods.com/reverse-engineering-sublime-text-s-fuzzy-match-4cffeed33fdb

It additionally strips diacritics from sort keys if the query is ASCII.

Index

Examples

Constants

View Source
const (
	DefaultAdjacencyBonus          = 5.0  // Bonus for adjacent matches
	DefaultSeparatorBonus          = 10.0 // Bonus if the match is after a separator
	DefaultCamelBonus              = 10.0 // Bonus if match is uppercase and previous is lower
	DefaultLeadingLetterPenalty    = -3.0 // Penalty applied for every letter in string before first match
	DefaultMaxLeadingLetterPenalty = -9.0 // Maximum penalty for leading letters
	DefaultUnmatchedLetterPenalty  = -1.0 // Penalty for every letter that doesn't match
	DefaultStripDiacritics         = true // Strip diacritics from sort keys if query is plain ASCII
)

Default bonuses and penalties for fuzzy sorting. To customise sorting behaviour, pass corresponding Options to New() or Sorter.Configure().

Variables

This section is empty.

Functions

This section is empty.

Types

type Option

type Option func(s *Sorter) Option

Option configures a Sorter. Pass one or more Options to New() or Sorter.Configure(). An Option returns another Option to revert the configuration to the previous state.

func AdjacencyBonus

func AdjacencyBonus(bonus float64) Option

AdjacencyBonus sets the bonus for adjacent matches.

func CamelBonus

func CamelBonus(bonus float64) Option

CamelBonus sets the bonus applied if match is uppercase and previous character is lowercase.

func LeadingLetterPenalty

func LeadingLetterPenalty(penalty float64) Option

LeadingLetterPenalty sets the penalty applied for every character before the first match.

func MaxLeadingLetterPenalty

func MaxLeadingLetterPenalty(penalty float64) Option

MaxLeadingLetterPenalty sets the maximum penalty for character preceding the first match.

func SeparatorBonus

func SeparatorBonus(bonus float64) Option

SeparatorBonus sets the bonus for matches directly after a separator.

func StripDiacritics

func StripDiacritics(on bool) Option

StripDiacritics sets whether diacritics should be stripped.

func UnmatchedLetterPenalty

func UnmatchedLetterPenalty(penalty float64) Option

UnmatchedLetterPenalty sets the penalty for characters that do not match.

type Result

type Result struct {
	// Match is whether or not the string matched the query,
	// i.e. if all characters in the query are present,
	// in order, in the string.
	Match bool
	// Query is the query that was matched against.
	Query string
	// Score is how well the string matched the query.
	// Higher is better.
	Score float64
	// SortKey is the string Query was compared to.
	SortKey string
}

Result stores the result of a single fuzzy ranking.

func Match

func Match(str, query string, opts ...Option) *Result

Match scores str against query using the specified sort options.

WARNING: Match creates a new Sorter for every call. Don't use this on large datasets.

func Sort

func Sort(data Sortable, query string) []*Result

Sort sorts data against query using a new default Sorter.

Example

Fuzzy sort contacts by name.

package main

import (
	"fmt"
)

// Contact is a very simple data model.
type Contact struct {
	Firstname string
	Lastname  string
}

// Name returns the full name of the Contact.
func (c *Contact) Name() string { return fmt.Sprintf("%s %s", c.Firstname, c.Lastname) }

// Contacts is a collection of Contact items. This is where fuzzy.Sortable
// must be implemented to enable fuzzy sorting.
type Contacts []*Contact

// Default sort.Interface methods
func (co Contacts) Len() int           { return len(co) }
func (co Contacts) Swap(i, j int)      { co[i], co[j] = co[j], co[i] }
func (co Contacts) Less(i, j int) bool { return co[i].Name() < co[j].Name() }

// Keywords implements Sortable.
// Comparisons are based on the the full name of the contact.
func (co Contacts) Keywords(i int) string { return co[i].Name() }

// Fuzzy sort contacts by name.
func main() {
	// My imaginary friends
	var c = Contacts{
		&Contact{"Meggan", "Siering"},
		&Contact{"Seraphin", "Stracke"},
		&Contact{"Sheryll", "Steckel"},
		&Contact{"Erlene", "Vollbrecht"},
		&Contact{"Kayla", "Gumprich"},
		&Contact{"Jimmy", "Johnson"},
		&Contact{"Jimmy", "Jimson"},
		&Contact{"Mischa", "Witting"},
	}
	// Unsorted
	fmt.Println(c[0].Name())

	Sort(c, "mw")
	fmt.Println(c[0].Name())

	Sort(c, "meg")
	fmt.Println(c[0].Name())

	Sort(c, "voll")
	fmt.Println(c[0].Name())

	Sort(c, "ser")
	fmt.Println(c[0].Name())

	Sort(c, "ss")
	fmt.Println(c[0].Name())

	Sort(c, "jim")
	fmt.Println(c[0].Name())

	Sort(c, "jj")
	fmt.Println(c[0].Name())

	Sort(c, "jjo")
	fmt.Println(c[0].Name())

	Sort(c, "kg")
	fmt.Println(c[0].Name())
}
Output:

Meggan Siering
Mischa Witting
Meggan Siering
Erlene Vollbrecht
Seraphin Stracke
Sheryll Steckel
Jimmy Jimson
Jimmy Jimson
Jimmy Johnson
Kayla Gumprich

func SortStrings

func SortStrings(data []string, query string) []*Result

SortStrings fuzzy-sorts a slice of strings.

type Sortable added in v0.15.0

type Sortable interface {
	sort.Interface
	// Keywords returns the string to compare to the sort query
	Keywords(i int) string
}

Sortable makes the implementer fuzzy-sortable. It is a superset of sort.Interface (i.e. your struct must also implement sort.Interface).

type Sorter

type Sorter struct {
	Data                    Sortable // Data to sort
	AdjacencyBonus          float64  // Bonus for adjacent matches
	SeparatorBonus          float64  // Bonus if the match is after a separator
	CamelBonus              float64  // Bonus if match is uppercase and previous is lower
	LeadingLetterPenalty    float64  // Penalty applied for every letter in string before first match
	MaxLeadingLetterPenalty float64  // Maximum penalty for leading letters
	UnmatchedLetterPenalty  float64  // Penalty for every letter that doesn't match
	StripDiacritics         bool     // Strip diacritics from sort keys if query is plain ASCII
	// contains filtered or unexported fields
}

Sorter sorts Data based on the query passsed to Sorter.Sort().

func New

func New(data Sortable, opts ...Option) *Sorter

New creates a new Sorter for the given data.

func (*Sorter) Configure

func (s *Sorter) Configure(opts ...Option) Option

Configure applies one or more Options to Sorter.

func (*Sorter) Len

func (s *Sorter) Len() int

Len implements sort.Interface.

func (*Sorter) Less

func (s *Sorter) Less(i, j int) bool

Less implements sort.Interface.

func (*Sorter) Match

func (s *Sorter) Match(str string) *Result

Match scores str against Sorter's query using fuzzy matching.

func (*Sorter) Sort

func (s *Sorter) Sort(query string) []*Result

Sort sorts data against query.

func (*Sorter) Swap

func (s *Sorter) Swap(i, j int)

Swap implements sort.Interface.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL