Skip to content

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

License

Notifications You must be signed in to change notification settings

schulzch/edit-distance-js

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

48 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

edit-distance.js NPM version

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.

About

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

Resources

License

Stars

Watchers

Forks

Packages

No packages published