You're Invited:Meet the Socket Team at BlackHat and DEF CON in Las Vegas, Aug 7-8.RSVP
Socket
Socket
Sign inDemoInstall

edit-distance

Package Overview
Dependencies
0
Maintainers
1
Versions
8
Alerts
File Explorer

Advanced tools

Install Socket

Detect and block malicious and high-risk dependencies

Install

edit-distance

String and tree edit distance


Version published
Weekly downloads
1.7K
decreased by-26.49%
Maintainers
1
Created
Weekly downloads
 

Readme

Source

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.

Keywords

FAQs

Package last updated on 08 Feb 2022

Did you know?

Socket

Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.

Install

Related posts

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

Packages

Stay in touch

Get open source security insights delivered straight into your inbox.


  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc