fuzzy.ts

// Fuzzy matching written by TANIGUCHI Masaya
// Public Domain

function findAllMatches(pattern: string, source:string) {
  const indicesList: number[][] = pattern.split("").map(char => {
    return ([] as number[]).concat(
      ...source.split("").map((c, i) => c === char ? [i] : [])
    )
  })
  function recur(acc: number[], i: number): number[][] {
    if (i === indicesList.length)
      return [acc]
    const candidates = indicesList[i]
      .slice(indicesList[i].findIndex(c => (acc.at(-1) ?? -1) < c))
      .map(c =>recur(acc.concat([c]), i + 1))
    return ([] as number[][]).concat(...candidates)
  }
  return recur([], 0)
}

function scoreMatch(match: number[]): number {
   const length = (match.at(-1) ?? 0) - match[0];
   let ngroup = 1
   for(let i = 0; i < match.length; i++) {
      if ((match.at(i - 1) ?? -1) + 1 !== match[i]) {
        ngroup += 1
      }
   }
   return 1 / length * 1 / ngroup
}

export function score(pattern: string, source: string): number {
  return Math.max(...findAllMatches(pattern, source).map(scoreMatch))
}

export function test(pattern: string, source: string): boolean {
  return new RegExp(pattern.split("").join(".*")).test(source)
}