kstafford3/custom-edit-distance

The usual edit distance algorithm with user-defined edit costs.

Custom Edit Distance¹

The usual algorithm² with customizable costs.

Install

npm install custom-edit-distance

Calculate

const defaultCalculator = new CustomEditDistance();
defaultCalculator.editDistance('sitting', 'kitten').should.equal(3);

Customize Costs

const LEVENSHTEIN = {
  getKeepCost(unchangedValue) {
    return 0;
  },
  getInsertCost(insertedValue) {
    return 1;
  },
  getRemoveCost(removedValue) {
    return 1;
  },
  getSubstituteCost(fromValue, toValue) {
    return 1;
  },
};
const defaultCalculator = new CustomEditDistance(LEVENSHTEIN);

For convenience, we default to the Levenshtein³ distance costs. We also export it as LEVENSHTEIN.

Customize Equivalence

const equivalence = function(a, b) {
  a == b; // Only check for abstract equivalence
};

const defaultCalculator = new CustomEditDistance(null, equivalence);

For convenience we default to strict equality (===).

Sequences don't have to be Strings

const defaultCalculator = new CustomEditDistance();
defaultCalculator.editDistance([1, 2, 3], [1, 4, 3]).should.equal(1);

This is where defining cost can shine:

const valueDistanceCalculator = new CustomEditDistance({
  getInsertCost(insertedValue) {
    return insertedValue;
  },
  getRemoveCost(removedValue) {
    return removedValue;
  },
  getSubstituteCost(fromValue, toValue) {
    return Math.abs(toValue - fromValue);
  },
});
valueDistanceCalculator.editDistance([2, 3, 4], [1, 2, 3]).should.equal(3);

Get the cost matrix

const defaultCalculator = new CustomEditDistance();
const costMatrix = defaultCalculator.editCosts('sitting', 'kitten').should.equal(3);

From this you could determine the edit path, or inspect the cost of other edit paths.

Reference

Edit Distance ↩

The Wagner-Fischer Algorithm ↩

Levenshtein Distance ↩