# minimum-edit-distance

> diff strings and lists with levenshtein distance

Latest version **1.1.7** (published 2017-06-08) · MIT license · 0 weekly downloads

## Install

```sh
npm install minimum-edit-distance
pnpm add minimum-edit-distance
yarn add minimum-edit-distance
bun add minimum-edit-distance
```

## Health

**Score 15/100 (F)** — status: abandoned.

Positive: no vulnerabilities.

Warnings: low downloads; no types; no esm support.

Negative: abandoned; low maintenance score.

## Facts

| | |
|---|---|
| Version | 1.1.7 |
| Published | 2017-06-08 |
| First published | 2017-06-03 |
| Weekly downloads | 0 |
| License | MIT |
| TypeScript types | none |
| Module format | CommonJS |
| Dependencies | 0 |
| Known vulnerabilities | 0 |
| Install scripts | no |
| GitHub stars | 3 |
| Author | Jake Wood |
| Maintainers | jzwood |
| Keywords | levenshtein, diff, edit, distance, backtrace |

## Links

- npm: https://www.npmjs.com/package/minimum-edit-distance
- Repository: https://github.com/jzwood/minimum-edit-distance
- Homepage: https://github.com/jzwood/minimum-edit-distance#readme
- Issues: https://github.com/jzwood/minimum-edit-distance/issues
- npm.io page: https://npm.io/package/minimum-edit-distance

## Alternatives

- [ext-list](https://npm.io/package/ext-list.md) — 6.3M weekly downloads
- [@lexical/selection](https://npm.io/package/@lexical/selection.md) — 3.8M weekly downloads
- [@lexical/text](https://npm.io/package/@lexical/text.md) — 3.6M weekly downloads
- [@lexical/clipboard](https://npm.io/package/@lexical/clipboard.md) — 3.0M weekly downloads
- [@tiptap/extension-mention](https://npm.io/package/@tiptap/extension-mention.md) — 3.0M weekly downloads

## Recent versions

- 1.1.7 (latest) — 2017-06-08
- 1.1.6 — 2017-06-08
- 1.1.5 — 2017-06-06
- 1.1.4 — 2017-06-04
- 1.1.3 — 2017-06-03
- 1.1.2 — 2017-06-03
- 1.1.1 — 2017-06-03
- 1.1.0 — 2017-06-03
- 1.0.0 — 2017-06-03

## README

# minimum-edit-distance

The **minimum edit distance** is the integer number of character insertions, deletions, and substitutions required to transform one string into another.

[![Build Status](https://travis-ci.org/jzwood/minimum-edit-distance.svg?branch=master)](https://travis-ci.org/jzwood/minimum-edit-distance) [![](https://img.shields.io/badge/awesome-yes-FF7AA8.svg)](https://giphy.com/search/awesome)

## Info
The minimum edit distance on its own is, albeit interesting, not terribly useful. However, the minimum edit matrix _backtrace_ is both interesting and useful. This backtrace contains, not only all the information necessary to determine the minimum edit distance, but also the smallest amount of information required to transform the second string back into the first (see **usage** section).

### install

```shell
    $ npm install minimum-edit-distance
```
### require
```javascript
    const minimumEditDistance = require('minimum-edit-distance');
```    

## Usage

```javascript
    let str1 = 'dhyfldnsgagfhc';
    let str2 = 'dososjhbabadhfhshdsjds';

    let difference = minimumEditDistance.diff(str1, str2)

    console.log(difference.distance); // 18

    console.log(difference.backtrace);
    // [ 'sc', 'sh', 'sf', 'sg', 'sa', 'sg', '1', 'sn', 'd2', '1', 'sl', 'sf', 'sy', 'd', '1', 'd5', '1' ]

    /*
     *  prefix key:
     *    s = substitute
     *    i = insertion
     *    d = deletion #
     *    # = skip num
     */

    let stringOne = minimumEditDistance.reconstruct(str2, difference.backtrace)

    console.log(str1 === stringOne); // true
```

## Usage for Arrays

```javascript
    let array1 = ['cat', 'fees', 'hound']
    let array2 = ['cat', 'kite', 'undo', 'hound']

    let arrayDifference = minimumEditDistance.diff(array1, array2)

    console.log(arrayDifference.distance) //2

    console.log(arrayDifference.backtrace) // [ '1', 'sfees', 'd', '1' ]

    console.log(minimumEditDistance.reconstruct(array2, arrayDifference.backtrace)) // [ 'cat', 'fees', 'hound' ]
```

## API
```java
      /**
       * p1 - first string or array
       * p2 - second string or array
       * distance - integer minimum edit distance
       * backtrace - array of strings specifying edit operations
       */
      diff(p1, p2, substitutionCost=1, insertionCost=1, deletionCost=1){
        ...
        return {"distance": distance, "backtrace": backtrace}
      }

      /**
       * p2 - p2 used in diff
       * trace - backtrace from diff
       * p1 - equal to p1 used in diff
       */
      reconstruct(p2, trace){
        ...
        return p1
      }
```

## license

MIT

---
_Source: https://npm.io/package/minimum-edit-distance · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._
