schulzch/edit-distance-js

JavaScript library to compute the edit distance for strings and trees.

edit-distance.js

edit-distance.js computes the edit distance for strings [1, 2] and trees [3].

It computes the plain edit distance (number), as well as the mapping (pairs), and alignment (sequences). The edit distance is defined as the minimum number of insert, remove, and update operations to transform between A and B (symmetric).

Installation

Download a release (browserfied version) or:

$ npm install edit-distance 

Usage

var ed = require('edit-distance');
//Browserfied version:
//<script src="edit-distance.js"></script>
//<script>var ed = global.editDistance;</script>

Levenshtein Distance

// Define cost functions.
var insert, remove, update;
insert = remove = function(node) { return 1; };
update = function(stringA, stringB) { return stringA !== stringB ? 1 : 0; };

// Define two strings.
var stringA = "abcdef";
var stringB = "abdfgh";

// Compute edit distance, mapping, and alignment.
var lev = ed.levenshtein(stringA, stringB, insert, remove, update);
console.log('Levenshtein', lev.distance, lev.pairs(), lev.alignment());

Tree Edit Distance

// Define cost functions.
var insert, remove, update;
insert = remove = function(node) { return 1; };
update = function(nodeA, nodeB) { return nodeA.id !== nodeB.id ? 1 : 0; };

// Define two trees.
var rootA = {id: 1, children: [{id: 2}, {id: 3}]};
var rootB = {id: 1, children: [{id: 4}, {id: 3}, {id: 5}]};
var children = function(node) { return node.children; };

// Compute edit distance, mapping, and alignment.
var ted = ed.ted(rootA, rootB, children, insert, remove, update);
console.log('Tree Edit Distance', ted.distance, ted.pairs(), ted.alignment());

References

[1] Levenshtein, Vladimir I. "Binary codes capable of correcting deletions, insertions and reversals." Soviet physics doklady. Vol. 10. 1966.

[2] Wagner, Robert A., and Michael J. Fischer. "The string-to-string correction problem." Journal of the ACM (JACM) 21.1 (1974): 168-173.

[3] Zhang, Kaizhong, and Dennis Shasha. "Simple fast algorithms for the editing distance between trees and related problems." SIAM journal on computing 18.6 (1989): 1245-1262.

Versioning

This project is maintained under the Semantic Versioning guidelines.

License

Licensed under the Apache 2.0 License. Copyright © 2016 Christoph Schulz.

edit-distance-js's Issues

Question

How to use this library as native javascript?

v1.0.3 release is broken

If I install v1.0.3, in my node_modules folder, edit-distance/dist/ is empty. If I try to require the library, it can't be found.

If I install v1.0.2, everything works ok.

strange test?

Hi,

Thanks for making this package; I've been trying to use it for a project.

One question about one of the tests:

edit-distance-js/test/ted.test.coffee

Line 64 in 0c39456

shouldBeSymmetrical "(b,c)a", "b", 2, [["a", null], ["c", "b"], ["b", null]]

It seems to me that the alignment should show [a, null], [b, b], and [c, null] like the preceding test and have a distance of 2; as the alignment is written, wouldn't the distance be 3 with a remove, remove, rename operation?