LcsTs — Longest Common Subsequence in TypeScript

LcsTs is a TypeScript implementation of the Longest Common Subsequence (LCS) algorithm. It compares two token sequences and returns correlated subsequences describing which runs are equal, inserted, or deleted.

Documentation

Full API reference is published at ericwhitedev.github.io/LcsTs.

To build the documentation locally:

npm run docs
Copy

Output is written to docs/api/. Open docs/api/index.html in a browser.

Quick Start

import { compare, createLcsSettings, CorrelationStatus } from '@ericwhitedev/lcsts';

const result = compare(
  ['the', 'quick', 'brown', 'fox'],
  ['the', 'slow', 'brown', 'dog'],
  createLcsSettings(),
);

for (const seq of result) {
  switch (seq.correlationStatus) {
    case CorrelationStatus.Equal:
      console.log('Equal:', seq.comparisonUnitList1!.map(t => t.getShortString()));
      break;
    case CorrelationStatus.Deleted:
      console.log('Deleted:', seq.comparisonUnitList1!.map(t => t.getShortString()));
      break;
    case CorrelationStatus.Inserted:
      console.log('Inserted:', seq.comparisonUnitList2!.map(t => t.getShortString()));
      break;
  }
}
// Equal:    ['the']
// Deleted:  ['quick']
// Inserted: ['slow']
// Equal:    ['brown']
// Deleted:  ['fox']
// Inserted: ['dog']
Copy

Custom Tokens

For advanced matching, subclass ComparisonUnitToken or use the built-in ComparisonUnitTokenRegex:

import {
  ComparisonUnitTokenString,
  ComparisonUnitTokenRegex,
  compare,
  createLcsSettings,
} from '@ericwhitedev/lcsts';

const tokens1 = [
  new ComparisonUnitTokenString('hello'),
  new ComparisonUnitTokenString('42'),
];

const tokens2 = [
  new ComparisonUnitTokenString('hello'),
  new ComparisonUnitTokenRegex(/^\d+$/),
];

const result = compare(tokens1, tokens2, createLcsSettings());
// Both tokens match — 'hello' === 'hello', and '42' matches /^\d+$/
Copy

Settings

Use createLcsSettings() to get sensible defaults, or pass overrides:

const settings = createLcsSettings({
  detailThreshold: 5,
  findCommonAtBeginning: true,
  findCommonAtEnd: true,
});
Copy

License

MIT © Eric White