38 lines
1.6 KiB
JavaScript
38 lines
1.6 KiB
JavaScript
import { buildBigrams } from '#tofu/tools/text/buildBigrams.js'
|
|
import { normalizeSearchText } from '#tofu/tools/text/normalizeSearchText.js'
|
|
|
|
// Similarity between a typed query and a candidate text, from 0 to 1.
|
|
// Exact match wins, then prefix, then containment, then the Dice coefficient
|
|
// on character bigrams for approximate (misspelled) matches.
|
|
const PREFIX_SCORE = 0.9
|
|
const PREFIX_BONUS = 0.1
|
|
const CONTAINS_SCORE = 0.75
|
|
|
|
export function scoreTextSimilarity(query, candidate) {
|
|
const normalizedQuery = normalizeSearchText(query)
|
|
const normalizedCandidate = normalizeSearchText(candidate)
|
|
if (normalizedQuery.length === 0 || normalizedCandidate.length === 0) return 0
|
|
if (normalizedQuery === normalizedCandidate) return 1
|
|
if (normalizedCandidate.startsWith(normalizedQuery)) {
|
|
const coverage = normalizedQuery.length / normalizedCandidate.length
|
|
return PREFIX_SCORE + PREFIX_BONUS * coverage
|
|
}
|
|
if (normalizedCandidate.includes(normalizedQuery)) return CONTAINS_SCORE
|
|
|
|
const queryBigrams = buildBigrams(normalizedQuery)
|
|
const candidateBigrams = buildBigrams(normalizedCandidate)
|
|
if (queryBigrams.length === 0 || candidateBigrams.length === 0) return 0
|
|
// Dice coefficient on multisets: each query bigram can only be matched once.
|
|
const unmatched = new Map()
|
|
for (const bigram of queryBigrams) {
|
|
unmatched.set(bigram, (unmatched.get(bigram) ?? 0) + 1)
|
|
}
|
|
let shared = 0
|
|
for (const bigram of candidateBigrams) {
|
|
const remaining = unmatched.get(bigram) ?? 0
|
|
if (remaining === 0) continue
|
|
unmatched.set(bigram, remaining - 1)
|
|
shared += 1
|
|
}
|
|
return (2 * shared) / (queryBigrams.length + candidateBigrams.length)
|
|
}
|