Javascript String utilities. Can be used to calculate similarity of two strings by Levenshtein distance algorithm or Dice's Coefficient.

string-utils.js

const editDistance = Symbol('editDistance')
const Levenshtein = Symbol('Levenshtein')
const Dice = Symbol('Dice')

class StringUtils {
  static get similarityAlgorithms () { return ['Levenshtein', 'Dice'] }

  /**
   * @param {string} firstString
   * @param {string} secondString
   * @param {('Levenshtein'|'Dice')} algorithm
   */
  static similarity (firstString, secondString, algorithm) {
    if (!algorithm) {
      throw new Error('Similarity algorithm required')
    }

    switch (algorithm) {
      case 'Levenshtein':
        return this[Levenshtein](firstString, secondString)
      case 'Dice':
        return this[Dice](firstString, secondString)
      default:
        throw new TypeError(`Invalid algorithm. Expected ${this.similarityAlgorithms}, but found ${algorithm}`)
    }
  }

  // Finds degree of similarity between two strings, based on Levenshtein distance
  static [Levenshtein] (s1, s2) {
    let longer = s1
    let shorter = s2
    if (s1.length < s2.length) {
      longer = s2
      shorter = s1
    }
    let longerLength = longer.length
    if (longerLength === 0) {
      return 1.0
    }
    return (longerLength - this[editDistance](longer, shorter)) / parseFloat(longerLength)
  }

  static [editDistance] (s1, s2) {
    s1 = s1.toLowerCase()
    s2 = s2.toLowerCase()

    let costs = []
    for (let i = 0; i <= s1.length; i++) {
      let lastValue = i
      for (let j = 0; j <= s2.length; j++) {
        if (i === 0) { costs[j] = j } else {
          if (j > 0) {
            let newValue = costs[j - 1]
            if (s1.charAt(i - 1) !== s2.charAt(j - 1)) {
              newValue = Math.min(Math.min(newValue, lastValue),
                costs[j]) + 1
            }
            costs[j - 1] = lastValue
            lastValue = newValue
          }
        }
      }
      if (i > 0) { costs[s2.length] = lastValue }
    }
    return costs[s2.length]
  }

  // Finds degree of similarity between two strings, based on Dice's Coefficient, which is mostly better than Levenshtein distance.
  static [Dice] (first, second) {
    first = first.replace(/\s+/g, '')
    second = second.replace(/\s+/g, '')

    if (!first.length && !second.length) return 1 // if both are empty strings
    if (!first.length || !second.length) return 0 // if only one is empty string
    if (first === second) return 1 // identical
    if (first.length === 1 && second.length === 1) return 0 // both are 1-letter strings
    if (first.length < 2 || second.length < 2) return 0 // if either is a 1-letter string

    let firstBigrams = new Map()
    for (let i = 0; i < first.length - 1; i++) {
      const bigram = first.substr(i, 2)
      const count = firstBigrams.has(bigram)
        ? firstBigrams.get(bigram) + 1
        : 1

      firstBigrams.set(bigram, count)
    };

    let intersectionSize = 0
    for (let i = 0; i < second.length - 1; i++) {
      const bigram = second.substr(i, 2)
      const count = firstBigrams.has(bigram)
        ? firstBigrams.get(bigram)
        : 0

      if (count > 0) {
        firstBigrams.set(bigram, count - 1)
        intersectionSize++
      }
    }

    return (2.0 * intersectionSize) / (first.length + second.length - 2)
  }
}

module.exports = StringUtils