Python's difflib.get_close_matches in TypeScript

How to use

Install via yarn add locutus and import: import { get_close_matches } from 'locutus/python/difflib/get_close_matches'.

Or with CommonJS: const { get_close_matches } = require('locutus/python/difflib/get_close_matches')

Use a bundler that supports tree-shaking so you only ship the functions you actually use. Vite, webpack, Rollup, and Parcel all handle this. For server-side use this is less of a concern.

Examples

These examples are extracted from test cases that automatically verify our functions against their native counterparts.

#	code	expected result
1	get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])	['apple', 'ape']
2	get_close_matches('wheel', ['while', 'whale', 'whole'], 2)	['whole', 'while']
3	get_close_matches('abc', ['xyz'], 3, 0.8)	[]

Notes

• Uses a SequenceMatcher-style similarity ratio to rank close string matches.

Here's what our current TypeScript equivalent to Python's difflib.get_close_matches looks like.

TSTypeScript JSJavaScript TSStandalone TS JSStandalone JS

Copy code

type MatchCandidate = { candidate: string; score: number }

function findLongestMatch(a: string, b: string, aStart: number, aEnd: number, bStart: number, bEnd: number) {
  let bestI = aStart
  let bestJ = bStart
  let bestSize = 0
  const previous = new Map<number, number>()

  for (let i = aStart; i < aEnd; i++) {
    const current = new Map<number, number>()
    const leftChar = a[i] ?? ''
    for (let j = bStart; j < bEnd; j++) {
      if (leftChar !== (b[j] ?? '')) {
        continue
      }

      const size = (previous.get(j - 1) ?? 0) + 1
      current.set(j, size)
      if (size > bestSize) {
        bestI = i - size + 1
        bestJ = j - size + 1
        bestSize = size
      }
    }
    previous.clear()
    for (const [key, value] of current) {
      previous.set(key, value)
    }
  }

  return { aIndex: bestI, bIndex: bestJ, size: bestSize }
}

function matchingBlocks(a: string, b: string): Array<{ aIndex: number; bIndex: number; size: number }> {
  const queue: Array<[number, number, number, number]> = [[0, a.length, 0, b.length]]
  const out: Array<{ aIndex: number; bIndex: number; size: number }> = []

  while (queue.length > 0) {
    const next = queue.pop()
    if (!next) {
      continue
    }

    const [aStart, aEnd, bStart, bEnd] = next
    const match = findLongestMatch(a, b, aStart, aEnd, bStart, bEnd)
    if (match.size === 0) {
      continue
    }

    out.push(match)

    if (aStart < match.aIndex && bStart < match.bIndex) {
      queue.push([aStart, match.aIndex, bStart, match.bIndex])
    }

    const aMatchEnd = match.aIndex + match.size
    const bMatchEnd = match.bIndex + match.size
    if (aMatchEnd < aEnd && bMatchEnd < bEnd) {
      queue.push([aMatchEnd, aEnd, bMatchEnd, bEnd])
    }
  }

  out.sort((left, right) => left.aIndex - right.aIndex || left.bIndex - right.bIndex)

  const merged: Array<{ aIndex: number; bIndex: number; size: number }> = []
  for (const block of out) {
    const previous = merged.at(-1)
    if (
      previous &&
      previous.aIndex + previous.size === block.aIndex &&
      previous.bIndex + previous.size === block.bIndex
    ) {
      previous.size += block.size
      continue
    }
    merged.push({ ...block })
  }

  merged.push({ aIndex: a.length, bIndex: b.length, size: 0 })
  return merged
}

function similarityRatio(left: string, right: string): number {
  if (left === right) {
    return 1
  }

  const totalLength = left.length + right.length
  if (totalLength === 0) {
    return 1
  }

  const matches = matchingBlocks(left, right).reduce((sum, block) => sum + block.size, 0)
  return (2 * matches) / totalLength
}

export function get_close_matches(
  word: string,
  possibilities: string[] | unknown,
  n: number = 3,
  cutoff: number = 0.6,
): string[] {
  //      discuss at: https://locutus.io/python/difflib/get_close_matches/
  // parity verified: Python 3.12
  //     original by: Kevin van Zonneveld (https://kvz.io)
  //          note 1: Uses a SequenceMatcher-style similarity ratio to rank close string matches.
  //       example 1: get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
  //       returns 1: ['apple', 'ape']
  //       example 2: get_close_matches('wheel', ['while', 'whale', 'whole'], 2)
  //       returns 2: ['whole', 'while']
  //       example 3: get_close_matches('abc', ['xyz'], 3, 0.8)
  //       returns 3: []

  const count = Math.trunc(Number(n))
  const threshold = Number(cutoff)

  if (!Number.isFinite(count) || count <= 0) {
    throw new RangeError('get_close_matches(): n must be a positive integer')
  }

  if (!Number.isFinite(threshold) || threshold < 0 || threshold > 1) {
    throw new RangeError('get_close_matches(): cutoff must be between 0 and 1')
  }

  if (!Array.isArray(possibilities) || possibilities.length === 0) {
    return []
  }

  const query = String(word)
  const scored: MatchCandidate[] = []

  for (let i = 0; i < possibilities.length; i++) {
    const candidate = String(possibilities[i] ?? '')
    const score = similarityRatio(query, candidate)
    if (score >= threshold) {
      scored.push({ candidate, score })
    }
  }

  scored.sort((left, right) => {
    if (right.score !== left.score) {
      return right.score - left.score
    }
    return right.candidate.localeCompare(left.candidate)
  })

  return scored.slice(0, count).map((entry) => entry.candidate)
}

function findLongestMatch(a, b, aStart, aEnd, bStart, bEnd) {
  let bestI = aStart
  let bestJ = bStart
  let bestSize = 0
  const previous = new Map()

  for (let i = aStart; i < aEnd; i++) {
    const current = new Map()
    const leftChar = a[i] ?? ''
    for (let j = bStart; j < bEnd; j++) {
      if (leftChar !== (b[j] ?? '')) {
        continue
      }

      const size = (previous.get(j - 1) ?? 0) + 1
      current.set(j, size)
      if (size > bestSize) {
        bestI = i - size + 1
        bestJ = j - size + 1
        bestSize = size
      }
    }
    previous.clear()
    for (const [key, value] of current) {
      previous.set(key, value)
    }
  }

  return { aIndex: bestI, bIndex: bestJ, size: bestSize }
}

function matchingBlocks(a, b) {
  const queue = [[0, a.length, 0, b.length]]
  const out = []

  while (queue.length > 0) {
    const next = queue.pop()
    if (!next) {
      continue
    }

    const [aStart, aEnd, bStart, bEnd] = next
    const match = findLongestMatch(a, b, aStart, aEnd, bStart, bEnd)
    if (match.size === 0) {
      continue
    }

    out.push(match)

    if (aStart < match.aIndex && bStart < match.bIndex) {
      queue.push([aStart, match.aIndex, bStart, match.bIndex])
    }

    const aMatchEnd = match.aIndex + match.size
    const bMatchEnd = match.bIndex + match.size
    if (aMatchEnd < aEnd && bMatchEnd < bEnd) {
      queue.push([aMatchEnd, aEnd, bMatchEnd, bEnd])
    }
  }

  out.sort((left, right) => left.aIndex - right.aIndex || left.bIndex - right.bIndex)

  const merged = []
  for (const block of out) {
    const previous = merged.at(-1)
    if (
      previous &&
      previous.aIndex + previous.size === block.aIndex &&
      previous.bIndex + previous.size === block.bIndex
    ) {
      previous.size += block.size
      continue
    }
    merged.push({ ...block })
  }

  merged.push({ aIndex: a.length, bIndex: b.length, size: 0 })
  return merged
}

function similarityRatio(left, right) {
  if (left === right) {
    return 1
  }

  const totalLength = left.length + right.length
  if (totalLength === 0) {
    return 1
  }

  const matches = matchingBlocks(left, right).reduce((sum, block) => sum + block.size, 0)
  return (2 * matches) / totalLength
}

export function get_close_matches(word, possibilities, n = 3, cutoff = 0.6) {
  //      discuss at: https://locutus.io/python/difflib/get_close_matches/
  // parity verified: Python 3.12
  //     original by: Kevin van Zonneveld (https://kvz.io)
  //          note 1: Uses a SequenceMatcher-style similarity ratio to rank close string matches.
  //       example 1: get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
  //       returns 1: ['apple', 'ape']
  //       example 2: get_close_matches('wheel', ['while', 'whale', 'whole'], 2)
  //       returns 2: ['whole', 'while']
  //       example 3: get_close_matches('abc', ['xyz'], 3, 0.8)
  //       returns 3: []

  const count = Math.trunc(Number(n))
  const threshold = Number(cutoff)

  if (!Number.isFinite(count) || count <= 0) {
    throw new RangeError('get_close_matches(): n must be a positive integer')
  }

  if (!Number.isFinite(threshold) || threshold < 0 || threshold > 1) {
    throw new RangeError('get_close_matches(): cutoff must be between 0 and 1')
  }

  if (!Array.isArray(possibilities) || possibilities.length === 0) {
    return []
  }

  const query = String(word)
  const scored = []

  for (let i = 0; i < possibilities.length; i++) {
    const candidate = String(possibilities[i] ?? '')
    const score = similarityRatio(query, candidate)
    if (score >= threshold) {
      scored.push({ candidate, score })
    }
  }

  scored.sort((left, right) => {
    if (right.score !== left.score) {
      return right.score - left.score
    }
    return right.candidate.localeCompare(left.candidate)
  })

  return scored.slice(0, count).map((entry) => entry.candidate)
}

Improve this function

Locutus is a community effort following The McDonald's Theory: we ship first iterations, hoping others will improve them. If you see something that could be better, we'd love your contribution.

View on GitHub · Edit on GitHub · View Raw

---

We have 34 Python functions so far - help us add more

Got a rainy Sunday afternoon and a taste for a porting puzzle?

• Get inspiration from the Python 3 standard library string page.
• Click "New file" in the appropriate folder on GitHub. This will fork the project to your account, directly add the file to it, and send a Pull Request to us.

We will then review it. If it's useful to the project and in line with our contributing guidelines your work will become part of Locutus and you'll be automatically credited in the authors section accordingly.

« More Python difflib functions

Star