fastest-levenshtein - npm Package Compare versions

Comparing version 1.0.9 to 1.0.10

.eslintrc.js

@@ -0,0 +0,0 @@ module.exports = {

index.d.ts

 export function distance(a: string, b: string): number;
-export function closest(a: number, b: string): number;
+export function closest(str: string, arr: string[]): string;

index.js

@@ -0,0 +0,0 @@ const peq = new Uint32Array(0x10000);

LICENSE.md

@@ -0,0 +0,0 @@ MIT License

mod.ts

@@ -1,9 +0,123 @@
-import * as levenshtein from "./index.js";
+const peq = new Uint32Array(0x10000);
+const myers_32 = (a: string, b: string) => {
+  const n = a.length;
+  const m = b.length;
+  const lst = 1 << (n - 1);
+  let pv = -1;
+  let mv = 0;
+  let sc = n;
+  let i = m;
+  while (i--) peq[b.charCodeAt(i)] = 0;
+  i = n;
+  while (i--) peq[a.charCodeAt(i)] |= 1 << i;
+  for (i = 0; i < m; i++) {
+    let eq = peq[b.charCodeAt(i)];
+    const xv = eq | mv;
+    eq |= ((eq & pv) + pv) ^ pv;
+    mv |= ~(eq | pv);
+    pv &= eq;
+    if (mv & lst) sc++;
+    if (pv & lst) sc--;
+    mv = (mv << 1) | 1;
+    pv = (pv << 1) | ~(xv | mv);
+    mv &= xv;
+  }
+  return sc;
+};
 
+const myers_x = (b: string, a: string) => {
+  const n = a.length;
+  const m = b.length;
+  const mhc = [];
+  const phc = [];
+  const hsize = Math.ceil(n / 32);
+  const vsize = Math.ceil(m / 32);
+  let score = m;
+  for (let i = 0; i < hsize; i++) {
+    phc[i] = -1;
+    mhc[i] = 0;
+  }
+  let j = 0;
+  for (; j < vsize - 1; j++) {
+    let mv = 0;
+    let pv = -1;
+    const start = j * 32;
+    const vlen = Math.min(32, m - start);
+    let k = n;
+    while (k--) peq[a.charCodeAt(k)] = 0;
+    for (k = start; k < start + vlen; k++) {
+      peq[b.charCodeAt(k)] |= 1 << k;
+    }
+    score = m;
+    for (let i = 0; i < n; i++) {
+      const eq = peq[a.charCodeAt(i)];
+      const pb = (phc[(i / 32) | 0] >>> i % 32) & 1;
+      const mb = (mhc[(i / 32) | 0] >>> i % 32) & 1;
+      const xv = eq | mv;
+      const xh = ((((eq | mb) & pv) + pv) ^ pv) | eq | mb;
+      let ph = mv | ~(xh | pv);
+      let mh = pv & xh;
+      if ((ph >>> 31) ^ pb) phc[(i / 32) | 0] ^= 1 << i % 32;
+      if ((mh >>> 31) ^ mb) mhc[(i / 32) | 0] ^= 1 << i % 32;
+      ph = (ph << 1) | pb;
+      mh = (mh << 1) | mb;
+      pv = mh | ~(xv | ph);
+      mv = ph & xv;
+    }
+  }
+  let mv = 0;
+  let pv = -1;
+  const start = j * 32;
+  const vlen = Math.min(32, m - start);
+  let k = n;
+  while (k--) peq[a.charCodeAt(k)] = 0;
+  for (k = start; k < start + vlen; k++) {
+    peq[b.charCodeAt(k)] |= 1 << k;
+  }
+  score = m;
+  for (let i = 0; i < n; i++) {
+    const eq = peq[a.charCodeAt(i)];
+    const pb = (phc[(i / 32) | 0] >>> i % 32) & 1;
+    const mb = (mhc[(i / 32) | 0] >>> i % 32) & 1;
+    const xv = eq | mv;
+    const xh = ((((eq | mb) & pv) + pv) ^ pv) | eq | mb;
+    let ph = mv | ~(xh | pv);
+    let mh = pv & xh;
+    score += (ph >>> ((m % 32) - 1)) & 1;
+    score -= (mh >>> ((m % 32) - 1)) & 1;
+    if ((ph >>> 31) ^ pb) phc[(i / 32) | 0] ^= 1 << i % 32;
+    if ((mh >>> 31) ^ mb) mhc[(i / 32) | 0] ^= 1 << i % 32;
+    ph = (ph << 1) | pb;
+    mh = (mh << 1) | mb;
+    pv = mh | ~(xv | ph);
+    mv = ph & xv;
+  }
+  return score;
+};
+
+
 export function distance(a: string, b: string): number {
-  return levenshtein.distance(a, b);
+  if (a.length < b.length) {
+    const tmp = b;
+    b = a;
+    a = tmp;
+  }
+  if (b.length === 0) return a.length;
+  if (a.length <= 32) {
+    return myers_32(a, b);
+  }
+  return myers_x(a, b);
 }
 
-export function closest(a: string, b: string[]): number {
-  return levenshtein.closest(a, b);
+export function closest(str: string, arr: string[]): string {
+  let min_distance = Infinity;
+  let min_index = 0;
+  for (let i = 0; i < arr.length; i++) {
+    const dist = distance(str, arr[i]);
+    if (dist < min_distance) {
+      min_distance = dist;
+      min_index = i;
+    }
+  }
+  return arr[min_index];
 }

package.json

 {
   "name": "fastest-levenshtein",
-  "version": "1.0.9",
+  "version": "1.0.10",
   "description": "Fastest Levenshtein distance implementation in JS.",
@@ -5,0 +5,0 @@ "main": "index.js",

README.md

@@ -13,3 +13,3 @@ # fastest-levenshtein :rocket:
 ## Usage
-
+### Node
 ```javascript
@@ -27,2 +27,15 @@ const {distance, closest} = require('fastest-levenshtein')
 
+### Deno
+```javascript
+import {distance, closest} from 'https://deno.land/x/fastest_levenshtein/mod.ts'
+
+// Print levenshtein-distance between 'fast' and 'faster' 
+console.log(distance('fast', 'faster'))
+//=> 2
+
+// Print string from array with lowest edit-distance to 'fast'
+console.log(closest('fast', ['slow', 'faster', 'fastest']))
+//=> 'faster'
+```
+
 ## Benchmark
@@ -29,0 +42,0 @@ I generated 500 pairs of strings with length N. I measured the ops/sec each library achieves to process all the given pairs. Higher is better. `fastest-levenshtein` is a lot faster in all cases.

test.js

@@ -0,0 +0,0 @@ const {distance, closest} = require("./index.js");

No alert changes

Improved metrics

Total package byte prevSize

14561

increased by35.36%

Lines of code

316

increased by54.9%

Number of lines in readme file

57

increased by29.55%

No dependency changes