94 lines
2.8 KiB
TypeScript
94 lines
2.8 KiB
TypeScript
/**
|
||
* Typo-tolerant word matching, shared by library search, lyrics search and
|
||
* in-list song filters.
|
||
*/
|
||
|
||
/**
|
||
* Lowercase words without accents or apostrophes, so "Don't Stop Beyoncé"
|
||
* gives ["dont", "stop", "beyonce"].
|
||
*/
|
||
export function searchWords(text: string): string[] {
|
||
return (
|
||
text
|
||
.normalize("NFKD")
|
||
.replace(/\p{M}/gu, "")
|
||
.toLowerCase()
|
||
.replace(/['’]/g, "")
|
||
.match(/[\p{L}\p{N}]+/gu) ?? []
|
||
)
|
||
}
|
||
|
||
/** Typos a query word may hold. Short words get none, or they match too much. */
|
||
function allowedTypos(term: string) {
|
||
if (term.length < 4) return 0
|
||
return term.length < 8 ? 1 : 2
|
||
}
|
||
|
||
/**
|
||
* Edits (insert, delete, substitute or swap neighbors) turning `a` into `b`,
|
||
* or `max + 1` once it is sure to exceed `max`.
|
||
*/
|
||
function editDistance(a: string, b: string, max: number): number {
|
||
if (Math.abs(a.length - b.length) > max) return max + 1
|
||
let before: number[] = []
|
||
let previous = Array.from({ length: b.length + 1 }, (_, j) => j)
|
||
for (let i = 1; i <= a.length; i++) {
|
||
const current = [i]
|
||
let rowMin = i
|
||
for (let j = 1; j <= b.length; j++) {
|
||
const cost = a[i - 1] === b[j - 1] ? 0 : 1
|
||
let distance = Math.min(
|
||
previous[j]! + 1,
|
||
current[j - 1]! + 1,
|
||
previous[j - 1]! + cost
|
||
)
|
||
if (i > 1 && j > 1 && a[i - 1] === b[j - 2] && a[i - 2] === b[j - 1]) {
|
||
distance = Math.min(distance, before[j - 2]! + 1)
|
||
}
|
||
current.push(distance)
|
||
rowMin = Math.min(rowMin, distance)
|
||
}
|
||
if (rowMin > max) return max + 1
|
||
before = previous
|
||
previous = current
|
||
}
|
||
return previous[b.length]!
|
||
}
|
||
|
||
/**
|
||
* Whether `word` is query `term` give or take a few typos. With `prefix` the
|
||
* word may also just start with the term, as when it is still being typed.
|
||
*/
|
||
function wordMatchesTerm(term: string, word: string, prefix: boolean) {
|
||
const typos = allowedTypos(term)
|
||
if (typos === 0) return false
|
||
if (editDistance(term, word, typos) <= typos) return true
|
||
return (
|
||
prefix &&
|
||
word.length > term.length &&
|
||
editDistance(term, word.slice(0, term.length), typos) <= typos
|
||
)
|
||
}
|
||
|
||
/**
|
||
* How every query term (from `searchWords`) appears among `words`: "exact"
|
||
* when each is a word, "fuzzy" when some only match give or take typos, or
|
||
* null when one is missing. The last term may be a word's prefix.
|
||
*/
|
||
export function matchWords(
|
||
words: readonly string[],
|
||
terms: readonly string[]
|
||
): "exact" | "fuzzy" | null {
|
||
let quality: "exact" | "fuzzy" = "exact"
|
||
for (const [index, term] of terms.entries()) {
|
||
const prefix = index === terms.length - 1
|
||
const exact = words.some((word) =>
|
||
prefix ? word.startsWith(term) : word === term
|
||
)
|
||
if (exact) continue
|
||
if (!words.some((word) => wordMatchesTerm(term, word, prefix))) return null
|
||
quality = "fuzzy"
|
||
}
|
||
return terms.length > 0 ? quality : null
|
||
}
|