Magyar fuzzy search algoritmus#

const ACCENTS_MAP: Record<string, string> = {
  á: "a", é: "e", í: "i", ó: "o", ö: "o", ő: "o",
  ú: "u", ü: "u", ű: "u",
  Á: "a", É: "e", Í: "i", Ó: "o", Ö: "o", Ő: "o",
  Ú: "u", Ü: "u", Ű: "u",
}

function normalize(s: string): string {
  let out = ""
  for (const ch of s) out += ACCENTS_MAP[ch] ?? ch.toLowerCase()
  return out
}

function levenshtein(a: string, b: string): number {
  if (a === b) return 0
  if (!a.length) return b.length
  if (!b.length) return a.length
  const m = a.length, n = b.length
  const prev = new Array<number>(n + 1)
  for (let j = 0; j <= n; j++) prev[j] = j
  for (let i = 1; i <= m; i++) {
    let curr = i
    let prevDiag = prev[0]
    prev[0] = i
    for (let j = 1; j <= n; j++) {
      const tmp = prev[j]
      curr = Math.min(
        prev[j] + 1,                                 // deletion
        prev[j - 1] + 1,                             // insertion
        prevDiag + (a[i - 1] === b[j - 1] ? 0 : 1)   // substitution
      )
      prevDiag = tmp
      prev[j] = curr
    }
  }
  return prev[n]
}

function scoreMatch(target: string, query: string): number {
  // target+query már normalizált (no-accent, lowercase)
  const tokens = query.split(/\s+/).filter(Boolean)
  if (tokens.length === 0) return Infinity

  let totalScore = 0
  for (const tok of tokens) {
    // 1. Exact substring → 0 (vagy 1 ha NEM szó-elején van)
    if (target.includes(tok)) {
      const at = target.indexOf(tok)
      const isStartOfWord = at === 0 || target[at - 1] === " " || target[at - 1] === "-"
      totalScore += isStartOfWord ? 0 : 1
      continue
    }
    // 2. Fuzzy: legjobb Levenshtein a target szavain (csak ha hossz közel ±2)
    const targetWords = target.split(/[\s/]+/)
    let bestLev = Infinity
    for (const tw of targetWords) {
      if (tw.length < 3) continue
      if (Math.abs(tw.length - tok.length) > 2) continue
      bestLev = Math.min(bestLev, levenshtein(tw, tok))
    }
    if (bestLev === 1) totalScore += 5
    else if (bestLev === 2) totalScore += 12
    else return Infinity   // egyik token-re sincs match → skip
  }
  // tie-breaker: rövidebb target preferált
  return totalScore + Math.min(target.length / 100, 0.5)
}

const nq = normalize(q)
const scored = items
  .map((m) => ({ m, score: scoreMatch(normalize(`${m.name} ${m.path}`), nq) }))
  .filter((x) => x.score < Infinity)
  .sort((a, b) => a.score - b.score)
  .slice(0, 8)