+++ /dev/null
-// Copyright 2019 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// Package fuzzy implements a fuzzy matching algorithm.
-package fuzzy
-
-import (
- "bytes"
- "fmt"
-)
-
-const (
- // MaxInputSize is the maximum size of the input scored against the fuzzy matcher. Longer inputs
- // will be truncated to this size.
- MaxInputSize = 127
- // MaxPatternSize is the maximum size of the pattern used to construct the fuzzy matcher. Longer
- // inputs are truncated to this size.
- MaxPatternSize = 63
-)
-
-type scoreVal int
-
-func (s scoreVal) val() int {
- return int(s) >> 1
-}
-
-func (s scoreVal) prevK() int {
- return int(s) & 1
-}
-
-func score(val int, prevK int /*0 or 1*/) scoreVal {
- return scoreVal(val<<1 + prevK)
-}
-
-// Matcher implements a fuzzy matching algorithm for scoring candidates against a pattern.
-// The matcher does not support parallel usage.
-type Matcher struct {
- pattern string
- patternLower []byte // lower-case version of the pattern
- patternShort []byte // first characters of the pattern
- caseSensitive bool // set if the pattern is mix-cased
-
- patternRoles []RuneRole // the role of each character in the pattern
- roles []RuneRole // the role of each character in the tested string
-
- scores [MaxInputSize + 1][MaxPatternSize + 1][2]scoreVal
-
- scoreScale float32
-
- lastCandidateLen int // in bytes
- lastCandidateMatched bool
-
- // Here we save the last candidate in lower-case. This is basically a byte slice we reuse for
- // performance reasons, so the slice is not reallocated for every candidate.
- lowerBuf [MaxInputSize]byte
- rolesBuf [MaxInputSize]RuneRole
-}
-
-func (m *Matcher) bestK(i, j int) int {
- if m.scores[i][j][0].val() < m.scores[i][j][1].val() {
- return 1
- }
- return 0
-}
-
-// NewMatcher returns a new fuzzy matcher for scoring candidates against the provided pattern.
-func NewMatcher(pattern string) *Matcher {
- if len(pattern) > MaxPatternSize {
- pattern = pattern[:MaxPatternSize]
- }
-
- m := &Matcher{
- pattern: pattern,
- patternLower: ToLower(pattern, nil),
- }
-
- for i, c := range m.patternLower {
- if pattern[i] != c {
- m.caseSensitive = true
- break
- }
- }
-
- if len(pattern) > 3 {
- m.patternShort = m.patternLower[:3]
- } else {
- m.patternShort = m.patternLower
- }
-
- m.patternRoles = RuneRoles(pattern, nil)
-
- if len(pattern) > 0 {
- maxCharScore := 4
- m.scoreScale = 1 / float32(maxCharScore*len(pattern))
- }
-
- return m
-}
-
-// Score returns the score returned by matching the candidate to the pattern.
-// This is not designed for parallel use. Multiple candidates must be scored sequentially.
-// Returns a score between 0 and 1 (0 - no match, 1 - perfect match).
-func (m *Matcher) Score(candidate string) float32 {
- if len(candidate) > MaxInputSize {
- candidate = candidate[:MaxInputSize]
- }
- lower := ToLower(candidate, m.lowerBuf[:])
- m.lastCandidateLen = len(candidate)
-
- if len(m.pattern) == 0 {
- // Empty patterns perfectly match candidates.
- return 1
- }
-
- if m.match(candidate, lower) {
- sc := m.computeScore(candidate, lower)
- if sc > minScore/2 && !m.poorMatch() {
- m.lastCandidateMatched = true
- if len(m.pattern) == len(candidate) {
- // Perfect match.
- return 1
- }
-
- if sc < 0 {
- sc = 0
- }
- normalizedScore := float32(sc) * m.scoreScale
- if normalizedScore > 1 {
- normalizedScore = 1
- }
-
- return normalizedScore
- }
- }
-
- m.lastCandidateMatched = false
- return 0
-}
-
-const minScore = -10000
-
-// MatchedRanges returns matches ranges for the last scored string as a flattened array of
-// [begin, end) byte offset pairs.
-func (m *Matcher) MatchedRanges() []int {
- if len(m.pattern) == 0 || !m.lastCandidateMatched {
- return nil
- }
- i, j := m.lastCandidateLen, len(m.pattern)
- if m.scores[i][j][0].val() < minScore/2 && m.scores[i][j][1].val() < minScore/2 {
- return nil
- }
-
- var ret []int
- k := m.bestK(i, j)
- for i > 0 {
- take := (k == 1)
- k = m.scores[i][j][k].prevK()
- if take {
- if len(ret) == 0 || ret[len(ret)-1] != i {
- ret = append(ret, i)
- ret = append(ret, i-1)
- } else {
- ret[len(ret)-1] = i - 1
- }
- j--
- }
- i--
- }
- // Reverse slice.
- for i := 0; i < len(ret)/2; i++ {
- ret[i], ret[len(ret)-1-i] = ret[len(ret)-1-i], ret[i]
- }
- return ret
-}
-
-func (m *Matcher) match(candidate string, candidateLower []byte) bool {
- i, j := 0, 0
- for ; i < len(candidateLower) && j < len(m.patternLower); i++ {
- if candidateLower[i] == m.patternLower[j] {
- j++
- }
- }
- if j != len(m.patternLower) {
- return false
- }
-
- // The input passes the simple test against pattern, so it is time to classify its characters.
- // Character roles are used below to find the last segment.
- m.roles = RuneRoles(candidate, m.rolesBuf[:])
-
- return true
-}
-
-func (m *Matcher) computeScore(candidate string, candidateLower []byte) int {
- pattLen, candLen := len(m.pattern), len(candidate)
-
- for j := 0; j <= len(m.pattern); j++ {
- m.scores[0][j][0] = minScore << 1
- m.scores[0][j][1] = minScore << 1
- }
- m.scores[0][0][0] = score(0, 0) // Start with 0.
-
- segmentsLeft, lastSegStart := 1, 0
- for i := 0; i < candLen; i++ {
- if m.roles[i] == RSep {
- segmentsLeft++
- lastSegStart = i + 1
- }
- }
-
- // A per-character bonus for a consecutive match.
- consecutiveBonus := 2
- wordIdx := 0 // Word count within segment.
- for i := 1; i <= candLen; i++ {
-
- role := m.roles[i-1]
- isHead := role == RHead
-
- if isHead {
- wordIdx++
- } else if role == RSep && segmentsLeft > 1 {
- wordIdx = 0
- segmentsLeft--
- }
-
- var skipPenalty int
- if i == 1 || (i-1) == lastSegStart {
- // Skipping the start of first or last segment.
- skipPenalty++
- }
-
- for j := 0; j <= pattLen; j++ {
- // By default, we don't have a match. Fill in the skip data.
- m.scores[i][j][1] = minScore << 1
-
- // Compute the skip score.
- k := 0
- if m.scores[i-1][j][0].val() < m.scores[i-1][j][1].val() {
- k = 1
- }
-
- skipScore := m.scores[i-1][j][k].val()
- // Do not penalize missing characters after the last matched segment.
- if j != pattLen {
- skipScore -= skipPenalty
- }
- m.scores[i][j][0] = score(skipScore, k)
-
- if j == 0 || candidateLower[i-1] != m.patternLower[j-1] {
- // Not a match.
- continue
- }
- pRole := m.patternRoles[j-1]
-
- if role == RTail && pRole == RHead {
- if j > 1 {
- // Not a match: a head in the pattern matches a tail character in the candidate.
- continue
- }
- // Special treatment for the first character of the pattern. We allow
- // matches in the middle of a word if they are long enough, at least
- // min(3, pattern.length) characters.
- if !bytes.HasPrefix(candidateLower[i-1:], m.patternShort) {
- continue
- }
- }
-
- // Compute the char score.
- var charScore int
- // Bonus 1: the char is in the candidate's last segment.
- if segmentsLeft <= 1 {
- charScore++
- }
- // Bonus 2: Case match or a Head in the pattern aligns with one in the word.
- // Single-case patterns lack segmentation signals and we assume any character
- // can be a head of a segment.
- if candidate[i-1] == m.pattern[j-1] || role == RHead && (!m.caseSensitive || pRole == RHead) {
- charScore++
- }
-
- // Penalty 1: pattern char is Head, candidate char is Tail.
- if role == RTail && pRole == RHead {
- charScore--
- }
- // Penalty 2: first pattern character matched in the middle of a word.
- if j == 1 && role == RTail {
- charScore -= 4
- }
-
- // Third dimension encodes whether there is a gap between the previous match and the current
- // one.
- for k := 0; k < 2; k++ {
- sc := m.scores[i-1][j-1][k].val() + charScore
-
- isConsecutive := k == 1 || i-1 == 0 || i-1 == lastSegStart
- if isConsecutive {
- // Bonus 3: a consecutive match. First character match also gets a bonus to
- // ensure prefix final match score normalizes to 1.0.
- // Logically, this is a part of charScore, but we have to compute it here because it
- // only applies for consecutive matches (k == 1).
- sc += consecutiveBonus
- }
- if k == 0 {
- // Penalty 3: Matching inside a segment (and previous char wasn't matched). Penalize for the lack
- // of alignment.
- if role == RTail || role == RUCTail {
- sc -= 3
- }
- }
-
- if sc > m.scores[i][j][1].val() {
- m.scores[i][j][1] = score(sc, k)
- }
- }
- }
- }
-
- result := m.scores[len(candidate)][len(m.pattern)][m.bestK(len(candidate), len(m.pattern))].val()
-
- return result
-}
-
-// ScoreTable returns the score table computed for the provided candidate. Used only for debugging.
-func (m *Matcher) ScoreTable(candidate string) string {
- var buf bytes.Buffer
-
- var line1, line2, separator bytes.Buffer
- line1.WriteString("\t")
- line2.WriteString("\t")
- for j := 0; j < len(m.pattern); j++ {
- line1.WriteString(fmt.Sprintf("%c\t\t", m.pattern[j]))
- separator.WriteString("----------------")
- }
-
- buf.WriteString(line1.String())
- buf.WriteString("\n")
- buf.WriteString(separator.String())
- buf.WriteString("\n")
-
- for i := 1; i <= len(candidate); i++ {
- line1.Reset()
- line2.Reset()
-
- line1.WriteString(fmt.Sprintf("%c\t", candidate[i-1]))
- line2.WriteString("\t")
-
- for j := 1; j <= len(m.pattern); j++ {
- line1.WriteString(fmt.Sprintf("M%6d(%c)\t", m.scores[i][j][0].val(), dir(m.scores[i][j][0].prevK())))
- line2.WriteString(fmt.Sprintf("H%6d(%c)\t", m.scores[i][j][1].val(), dir(m.scores[i][j][1].prevK())))
- }
- buf.WriteString(line1.String())
- buf.WriteString("\n")
- buf.WriteString(line2.String())
- buf.WriteString("\n")
- buf.WriteString(separator.String())
- buf.WriteString("\n")
- }
-
- return buf.String()
-}
-
-func dir(prevK int) rune {
- if prevK == 0 {
- return 'M'
- }
- return 'H'
-}
-
-func (m *Matcher) poorMatch() bool {
- if len(m.pattern) < 2 {
- return false
- }
-
- i, j := m.lastCandidateLen, len(m.pattern)
- k := m.bestK(i, j)
-
- var counter, len int
- for i > 0 {
- take := (k == 1)
- k = m.scores[i][j][k].prevK()
- if take {
- len++
- if k == 0 && len < 3 && m.roles[i-1] == RTail {
- // Short match in the middle of a word
- counter++
- if counter > 1 {
- return true
- }
- }
- j--
- } else {
- len = 0
- }
- i--
- }
- return false
-}
projects / dotfiles / .git / blobdiff