align-arr

Find the minimal edit path between two generic arrays.

Installation

npm i align-arr

or

yarn add align-arr

Usage

Find the difference between two arrays of number.

1import { align } from 'align-arr';
2
3const source = [1, 3, 3];
4const target = [1, 2, 3];
5
6const alignment: Edit<number>[] = align(source, target);
7
8console.log(alignment);

1[
2  {
3    operation: 'equal',
4    source: { position: 0, data: 1 },
5    target: { position: 0, data: 1 },
6    cost: 0
7  },
8  {
9    operation: 'substitute',
10    source: { position: 1, data: 3 },
11    target: { position: 1, data: 2 },
12    cost: 1
13  },
14  {
15    operation: 'equal',
16    source: { position: 2, data: 3 },
17    target: { position: 2, data: 3 },
18    cost: 0
19  }
20]

The console logs an array of Edit objects describing the difference between source and target.

1export type Edit<S = any, T = S> = {
2  operation: Operation;
3  source: Chunk<S>;
4  target: Chunk<T>;
5  cost: number;
6};
7
8export type Operation = 'equal' | 'insert' | 'delete' | 'substitute';
9
10export type Chunk<T = any> = {
11  position: number;
12  data?: T;
13};

Customizing The Aligner

By default, the algorithm compares two elements as a === b, and has a fixed cost of 1 for each operation.

In this example, we override the equals method to compare between a number and a string, and assign a fixed cost of 10 to the substitute operation, which causes the algorithm to favour insert and delete instead.

1const source = [1, 3, 3];
2const target = ['1', '2', '3'];
3
4const alignment = align(source, target, {
5  equals: (a, b) => a === Number.parseFloat(b),
6  insCost: (a) => 1,
7  delCost: (a) => 1,
8  subCost: (a, b) => 10,
9});
10
11console.log(alignment);

1[
2  {
3    operation: 'equal',
4    source: { position: 0, data: 1 },
5    target: { position: 0, data: '1' },
6    cost: 0
7  },
8  {
9    operation: 'insert',
10    source: { position: 1, data: undefined },
11    target: { position: 1, data: '2' },
12    cost: 1
13  },
14  {
15    operation: 'delete',
16    source: { position: 1, data: 3 },
17    target: { position: 2, data: undefined },
18    cost: 1
19  },
20  {
21    operation: 'equal',
22    source: { position: 2, data: 3 },
23    target: { position: 2, data: '3' },
24    cost: 0
25  }
26]

Contributions

To contribute to align-arr, follow these steps:

1. Fork this repository.
2. Create a branch: git checkout -b <branch_name>.
3. Make your changes and commit them: git commit -m '<commit_message>'
4. Push to the original branch: git push origin <project_name>/<location>
5. Create the pull request.

Alternatively see the GitHub documentation on creating a pull request.

Contributors

Thanks to the following people who have contributed to this project:

• @manzurola 🐈

Contact

If you want to contact me you can reach me at guy.manzurola@gmail.com.

License

This project uses the following license: MIT.