PHP's levenshtein in TypeScript

How to use

Install via yarn add locutus and import: import { levenshtein } from 'locutus/php/strings/levenshtein'.

Or with CommonJS: const { levenshtein } = require('locutus/php/strings/levenshtein')

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	levenshtein('Kevin van Zonneveld', 'Kevin van Sommeveld')	3
2	levenshtein("carrrot", "carrots")	2
3	levenshtein("carrrot", "carrots", 2, 3, 4)	6

Here's what our current TypeScript equivalent to PHP's levenshtein looks like.

TSTypeScript JSJavaScript TSStandalone TS JSStandalone JS

Copy code

export function levenshtein(s1: string, s2: string, costIns?: number, costRep?: number, costDel?: number): number {
  //       discuss at: https://locutus.io/php/levenshtein/
  //  parity verified: PHP 8.3
  //      original by: Carlos R. L. Rodrigues (https://www.jsfromhell.com)
  //      bugfixed by: Onno Marsman (https://twitter.com/onnomarsman)
  //       revised by: Andrea Giammarchi (https://webreflection.blogspot.com)
  // reimplemented by: Brett Zamir (https://brett-zamir.me)
  // reimplemented by: Alexander M Beedie
  // reimplemented by: Rafał Kukawski (https://blog.kukawski.pl)
  //        example 1: levenshtein('Kevin van Zonneveld', 'Kevin van Sommeveld')
  //        returns 1: 3
  //        example 2: levenshtein("carrrot", "carrots")
  //        returns 2: 2
  //        example 3: levenshtein("carrrot", "carrots", 2, 3, 4)
  //        returns 3: 6

  // var LEVENSHTEIN_MAX_LENGTH = 255 // PHP limits the function to max 255 character-long strings

  costIns = costIns == null ? 1 : +costIns
  costRep = costRep == null ? 1 : +costRep
  costDel = costDel == null ? 1 : +costDel

  if (s1 === s2) {
    return 0
  }

  const l1 = s1.length
  const l2 = s2.length

  if (l1 === 0) {
    return l2 * costIns
  }
  if (l2 === 0) {
    return l1 * costDel
  }

  // Enable the 3 lines below to set the same limits on string length as PHP does
  // if (l1 > LEVENSHTEIN_MAX_LENGTH || l2 > LEVENSHTEIN_MAX_LENGTH) {
  //   return -1;
  // }

  const chars1 = s1.split('')
  const chars2 = s2.split('')

  let p1: number[] = new Array(l2 + 1)
  let p2: number[] = new Array(l2 + 1)

  let i1
  let i2
  let c0
  let c1
  let c2
  let tmp: number[]

  const at = (arr: number[], idx: number): number => arr[idx] ?? 0

  for (i2 = 0; i2 <= l2; i2++) {
    p1[i2] = i2 * costIns
  }

  for (i1 = 0; i1 < l1; i1++) {
    p2[0] = at(p1, 0) + costDel

    for (i2 = 0; i2 < l2; i2++) {
      c0 = at(p1, i2) + (chars1[i1] === chars2[i2] ? 0 : costRep)
      c1 = at(p1, i2 + 1) + costDel

      if (c1 < c0) {
        c0 = c1
      }

      c2 = at(p2, i2) + costIns

      if (c2 < c0) {
        c0 = c2
      }

      p2[i2 + 1] = c0
    }

    tmp = p1
    p1 = p2
    p2 = tmp
  }

  c0 = at(p1, l2)

  return c0
}

export function levenshtein(s1, s2, costIns, costRep, costDel) {
  //       discuss at: https://locutus.io/php/levenshtein/
  //  parity verified: PHP 8.3
  //      original by: Carlos R. L. Rodrigues (https://www.jsfromhell.com)
  //      bugfixed by: Onno Marsman (https://twitter.com/onnomarsman)
  //       revised by: Andrea Giammarchi (https://webreflection.blogspot.com)
  // reimplemented by: Brett Zamir (https://brett-zamir.me)
  // reimplemented by: Alexander M Beedie
  // reimplemented by: Rafał Kukawski (https://blog.kukawski.pl)
  //        example 1: levenshtein('Kevin van Zonneveld', 'Kevin van Sommeveld')
  //        returns 1: 3
  //        example 2: levenshtein("carrrot", "carrots")
  //        returns 2: 2
  //        example 3: levenshtein("carrrot", "carrots", 2, 3, 4)
  //        returns 3: 6

  // var LEVENSHTEIN_MAX_LENGTH = 255 // PHP limits the function to max 255 character-long strings

  costIns = costIns == null ? 1 : +costIns
  costRep = costRep == null ? 1 : +costRep
  costDel = costDel == null ? 1 : +costDel

  if (s1 === s2) {
    return 0
  }

  const l1 = s1.length
  const l2 = s2.length

  if (l1 === 0) {
    return l2 * costIns
  }
  if (l2 === 0) {
    return l1 * costDel
  }

  // Enable the 3 lines below to set the same limits on string length as PHP does
  // if (l1 > LEVENSHTEIN_MAX_LENGTH || l2 > LEVENSHTEIN_MAX_LENGTH) {
  //   return -1;
  // }

  const chars1 = s1.split('')
  const chars2 = s2.split('')

  let p1 = new Array(l2 + 1)
  let p2 = new Array(l2 + 1)

  let i1
  let i2
  let c0
  let c1
  let c2
  let tmp

  const at = (arr, idx) => arr[idx] ?? 0

  for (i2 = 0; i2 <= l2; i2++) {
    p1[i2] = i2 * costIns
  }

  for (i1 = 0; i1 < l1; i1++) {
    p2[0] = at(p1, 0) + costDel

    for (i2 = 0; i2 < l2; i2++) {
      c0 = at(p1, i2) + (chars1[i1] === chars2[i2] ? 0 : costRep)
      c1 = at(p1, i2 + 1) + costDel

      if (c1 < c0) {
        c0 = c1
      }

      c2 = at(p2, i2) + costIns

      if (c2 < c0) {
        c0 = c2
      }

      p2[i2 + 1] = c0
    }

    tmp = p1
    p1 = p2
    p2 = tmp
  }

  c0 = at(p1, l2)

  return c0
}

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

---

« More PHP strings functions

Star