Skip to content

Instantly share code, notes, and snippets.

@johan johan/editdistance

Last active Apr 29, 2020
Embed
What would you like to do?
list edit distances between all inputs of the same length, ascending order
#! /usr/bin/env node
// for a JSON array of strings, or an array of lines on stdin,
// shows edit distances between all the inputs, ascending
const fs = require('fs');
const ed = require('edit-distance');
// read all strings from stdin:
let names = fs.readFileSync(0, 'utf-8');
try {
names = JSON.parse(names);
} catch (e) {
names = names.trim().split('\n');
}
names = uniq(names);
function uniq(arr) {
const seen = {};
for (const n of arr) {
seen[n] = 1;
}
return Object.keys(seen);
}
function bySize(arr) {
const sized = {};
for (const n of arr) {
sized[n.length] = (sized[n.length] || []).concat(n);
}
return sized;
}
const bysize = bySize(names);
const moreThanOne = Object.keys(bysize).filter(k => bysize[k].length > 1);
const wanted = Object.fromEntries(moreThanOne.map(k => [k, bysize[k]]));
function insert(node) { return 1; }
function remove(node) { return 1; }
function update(a, b) { return a !== b ? 1 : 0; }
const ascending = (a, b) => a[0] - b[0];
const dist = (a, b) => ed.levenshtein(a, b, insert, remove, update).distance;
const maxDist = (w, i, a) => { const d = a.slice(i + 1).map(W => dist(w, W)); return d.map((n, j) => [n, w, a[i+j+1]]); }
const byDist = (w, i, a) => {
const d = a.slice(i + 1).map(W => dist(w, W));
return d.map((n, j) => [n, w, a[i+j+1]]).sort(ascending);
};
const concat = (arr) => arr.reduce((a, b) => a.concat(b), []);
const allDist = (arr) => concat(arr.map(byDist)).sort(ascending);
const distances = Object.fromEntries(Object.keys(wanted).map(
n => [n, allDist(wanted[n])]
));
const all = concat(Object.keys(distances).map(n => distances[n])).sort(ascending);
console.log(all);
{
"name": "editdistance-cli",
"version": "1.0.0",
"description": "list edit distances between all inputs, ascending order",
"main": "editdistance",
"license": "MIT",
"dependencies": {
"edit-distance": "^1.0.2"
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.