js-lcs
TypeScript icon, indicating that this package has built-in type declarations

1.0.1 • Public • Published

js-lcs

npm version License: MIT Build Status

Partial1 implementation of Longest common substring problem in TypeScript/JavaScript, relatively fast and memory-optimized2.

Usage

Simple

import { LCS } from 'js-lcs';
 
LCS.size("aababcabcdabcaba", "eabcde"); // 4

Advanced

You can get more performance if you switch to typed arrays like Uint8Array, Uint16Array, and instantiate only one instance of LCS class:

import { LCS } from 'js-lcs';
 
const rawFiles = [
  // Uint16Array of char codes in file_1.txt
  // ...
  // Uint16Array of char codes in file_n.txt
];
 
const maxSize = Math.max(...rawFiles.map(f => f.length));
const lcs = new LCS({ maxSize }); // in this way you reuse once allocated memory for every lcs.size() call
 
for (let i = 0; i < rawFiles.length; i++) {
  for (let j = 0; j < i; j++) {
      const [a, b] = [rawFiles[j], rawFiles[i]];
      console.log(lcs.size(a, b));
    }
  }
}

Please always make sure you don't mix types of arguments to lcs.size(), e.g. if you start passing typed arrays, do not pass strings anymore and vice versa. Otherwise, you risk getting size() function deoptimized by V8.

Footnotes

  1. At the moment, it can calculate only size of the longest common substring, not the string itself.
  2. Processing two 3,000-char strings takes under 2 seconds, however, memory consumption still can be improved a bit, from O(max(r, n)) to O(min(r, n)) with a little pull request. Performance improvements are very welcome!

Package Sidebar

Install

npm i js-lcs

Weekly Downloads

1

Version

1.0.1

License

MIT

Unpacked Size

5.53 kB

Total Files

11

Last publish

Collaborators

  • noomorph