77 lines
2.0 KiB
Go
77 lines
2.0 KiB
Go
package kjv
|
|
|
|
// Ratcliff/Obershelp string similarity (the ratio of matching characters) and
|
|
// a closest match lookup, which the fuzzy book name matching relies on.
|
|
|
|
type matchBlock struct{ a, b, size int }
|
|
|
|
func longestMatch(a, b []rune, alo, ahi, blo, bhi int) matchBlock {
|
|
besti, bestj, bestsize := alo, blo, 0
|
|
prev := make([]int, len(b)+1)
|
|
cur := make([]int, len(b)+1)
|
|
for i := alo; i < ahi; i++ {
|
|
for j := blo; j < bhi; j++ {
|
|
if a[i] != b[j] {
|
|
cur[j+1] = 0
|
|
continue
|
|
}
|
|
k := prev[j] + 1
|
|
cur[j+1] = k
|
|
if k > bestsize {
|
|
besti, bestj, bestsize = i-k+1, j-k+1, k
|
|
}
|
|
}
|
|
prev, cur = cur, prev
|
|
for j := range cur {
|
|
cur[j] = 0
|
|
}
|
|
}
|
|
return matchBlock{besti, bestj, bestsize}
|
|
}
|
|
|
|
func matchedChars(a, b []rune) int {
|
|
type span struct{ alo, ahi, blo, bhi int }
|
|
queue := []span{{0, len(a), 0, len(b)}}
|
|
total := 0
|
|
for len(queue) > 0 {
|
|
q := queue[len(queue)-1]
|
|
queue = queue[:len(queue)-1]
|
|
m := longestMatch(a, b, q.alo, q.ahi, q.blo, q.bhi)
|
|
if m.size == 0 {
|
|
continue
|
|
}
|
|
total += m.size
|
|
if q.alo < m.a && q.blo < m.b {
|
|
queue = append(queue, span{q.alo, m.a, q.blo, m.b})
|
|
}
|
|
if m.a+m.size < q.ahi && m.b+m.size < q.bhi {
|
|
queue = append(queue, span{m.a + m.size, q.ahi, m.b + m.size, q.bhi})
|
|
}
|
|
}
|
|
return total
|
|
}
|
|
|
|
func similarity(a, b string) float64 {
|
|
ra, rb := []rune(a), []rune(b)
|
|
if len(ra)+len(rb) == 0 {
|
|
return 1
|
|
}
|
|
return 2.0 * float64(matchedChars(ra, rb)) / float64(len(ra)+len(rb))
|
|
}
|
|
|
|
// closestMatch is the best scoring possibility with a ratio of at least cutoff.
|
|
// Ties on score go to the lexicographically larger possibility.
|
|
func closestMatch(word string, possibilities []string, cutoff float64) (string, bool) {
|
|
best, bestScore, found := "", 0.0, false
|
|
for _, p := range possibilities {
|
|
score := similarity(p, word) // difflib compares possibility (a) against word (b)
|
|
if score < cutoff {
|
|
continue
|
|
}
|
|
if !found || score > bestScore || (score == bestScore && p > best) {
|
|
best, bestScore, found = p, score, true
|
|
}
|
|
}
|
|
return best, found
|
|
}
|