+/* string-lerp - progressively turn one string into another
+ Copyright 2014 Joe Wreschnig
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+*/
+
+/* @license Copyright 2014 Joe Wreschnig - GNU GPL v2 or later */
+
(function (exports) {
"use strict";
var MAX_MATRIX_SIZE = 256 * 256;
- function levenshteinMatrix(s, t) {
- /** Calculate the Levenshtein edit distance matrix for two strings
+ function costMatrix(source, target, ins, del, sub) {
+ /** Calculate the Levenshtein cost matrix for source and target
+
+ If source and target are strings, they cannot contain any
+ astral or combining codepoints. Such data must be passed
+ as arrays of strings with one element per glyph.
+
+ ins, del, and sub are the costs for insertion, deletion,
+ and substition respectively. Their default value is 1. If
+ only ins is passed, del and sub are set to the same cost.
+ If ins and del are passed, sub is set to the more
+ expensive of the two.
+
+ The matrix is returned as a flat typed array.
- The matrix is returned as a flat unsigned typed array.
-
Following http://en.wikipedia.org/wiki/Levenshtein_distance
*/
- var m = s.length + 1;
- var n = t.length + 1;
+ ins = ins === undefined ? 1 : (ins | 0);
+ del = (del | 0) || ins;
+ sub = (sub | 0) || Math.max(ins, del);
+ var m = source.length + 1;
+ var n = target.length + 1;
var d = new Uint32Array(m * n);
var i, j;
for (i = 1; i < m; ++i)
d[j] = j;
for (j = 1; j < n; ++j)
for (i = 1; i < m; ++i)
- if (s[i - 1] === t[j - 1])
+ if (source[i - 1] === target[j - 1])
d[n * i + j] = d[n * (i - 1) + j - 1];
else
- d[n * i + j] = 1 + Math.min(d[n * (i - 1) + j ],
- d[n * i + j - 1],
- d[n * (i - 1) + j - 1]);
+ d[n * i + j] = Math.min(del + d[n * (i - 1) + j ],
+ ins + d[n * i + j - 1],
+ sub + d[n * (i - 1) + j - 1]);
return d;
}
- function editPath(d, t) {
- /** Given a Levenshtein matrix and target, create an edit list */
+ // First, note that deletion is just substition with nothing, so
+ // any DEL operation can be replaced by a SUB. Second, the
+ // operation code *is* the necessary slice offset for applying the
+ // diff.
+ var INS = 0, SUB = 1;
+
+ function editPath(costs, target) {
+ /** Given a cost matrix and a target, create an edit list */
var path = [];
- var j = t.length;
+ var j = target.length;
var n = j + 1;
- var i = d.length / n - 1;
+ var i = costs.length / n - 1;
while (i || j) {
- var sub = (i && j) ? d[n * (i - 1) + j - 1] : Infinity;
- var del = i ? d[n * (i - 1) + j] : Infinity;
- var ins = j ? d[n * i + j - 1] : Infinity;
+ var sub = (i && j) ? costs[n * (i - 1) + j - 1] : Infinity;
+ var del = i ? costs[n * (i - 1) + j] : Infinity;
+ var ins = j ? costs[n * i + j - 1] : Infinity;
if (sub <= ins && sub <= del) {
- if (d[n * i + j] !== d[n * (i - 1) + j - 1])
- path.push(["sub", i - 1, t[j - 1]]);
+ if (costs[n * i + j] !== costs[n * (i - 1) + j - 1])
+ path.push([SUB, i - 1, target[j - 1]]);
--i; --j;
} else if (ins <= del) {
- path.push(["ins", i, t[j - 1]]);
+ path.push([INS, i, target[j - 1]]);
--j;
} else {
- path.push(["del", i - 1]);
+ path.push([SUB, i - 1, ""]);
--i;
}
}
return path;
}
- function diff(s, t) {
- /** Create a diff between string s and t */
- return editPath(levenshteinMatrix(s, t), t);
+ function diff(source, target, ins, del, sub) {
+ /** Create a diff between string source and target
+
+ ins, del, and sub are as passed to levenshtein
+ */
+ return editPath(costMatrix(source, target, ins, del, sub), target);
}
- function patch(edits, s) {
+ function patch(diff, source) {
/** Apply the list of edits to s */
+ var edit;
var i;
- for (i = 0; i < edits.length; ++i) {
- var edit = edits[i];
- switch (edit[0]) {
- case "sub":
- s = s.slice(0, edit[1]) + edit[2] + s.slice(edit[1] + 1);
- break;
- case "ins":
- s = s.slice(0, edit[1]) + edit[2] + s.slice(edit[1]);
- break;
- case "del":
- s = s.slice(0, edit[1]) + s.slice(edit[1] + 1);
- break;
+
+ if (Array.isArray(source)) {
+ for (i = 0; i < diff.length; ++i) {
+ edit = diff[i];
+ source.splice(edit[1], edit[0], edit[2]);
+ }
+ } else {
+ for (i = 0; i < diff.length; ++i) {
+ edit = diff[i];
+ var head = source.slice(0, edit[1]);
+ var tail = source.slice(edit[1] + edit[0]);
+ source = head + edit[2] + tail;
}
}
- return s;
+ return source;
}
+ var MULTI = /[\uD800-\uDBFF][\uDC00-\uDFFF]|[\u0300-\u036F\u1DC0-\u1DFF\u20D0-\u20FF\uFE20-\uFE2F]/;
+
+ var GLYPH = /([\0-\u02FF\u0370-\u1DBF\u1E00-\u20CF\u2100-\uD7FF\uDC00-\uFE1F\uFE30-\uFFFF]|[\uD800-\uDBFF][\uDC00-\uDFFF]|[\uD800-\uDBFF])([\u0300-\u036F\u1DC0-\u1DFF\u20D0-\u20FF\uFE20-\uFE2F]*)/g;
+
function diffLerp(a, b, p) {
- /** Interpolate between two strings based on edit distance
+ /** Interpolate between two strings based on edit operations
This interpolation algorithm applys a partial edit of one
string into the other. This produces nice looking results,
compute the edits. It is not recommended for strings
longer than a few hundred characters.
*/
- var edits = diff(a, b);
- var partial = edits.slice(0, Math.round(p * edits.length));
- return patch(partial, a);
+
+ // If given strings with astral codepoints or combining
+ // characters, split them into arrays of "glyphs" first,
+ // do the edit on the list of "glyphs", and rejoin them.
+ //
+ // This split is not perfect for all languages, but at least
+ // it won't create invalid surrogate pairs or orphaned
+ // combining characters.
+ if (a.match && a.match(MULTI) || b.match && b.match(MULTI)) {
+ var ca = a.match(GLYPH) || [];
+ var cb = b.match(GLYPH) || [];
+ return diffLerp(ca, cb, p).join("");
+ }
+
+ // The edit path works from the string end, forwards, because
+ // that's how Levenshtein edits work. To match LTR reading
+ // direction (and the behavior of fastLerp), swap the strings
+ // and invert the parameter when editing.
+ var edits = diff(b, a, 2, 2, 3);
+ var partial = edits.slice(0, Math.round((1 - p) * edits.length));
+ return patch(partial, b);
}
var NUMBERS = /(-?\d+(?:\.\d+)?)/g;
is clamped to an integer.
For example, numericLerp("0.0", "100", 0.123) === "12.3"
- because the "." in "0.0" is intepreted as a decimal point.
- But numericLerp("0.", "100.", 0.123) === "12." because the
- strings are interpreted as integers followed by a full
- stop.
+ because the "." in "0.0" is interpreted as a decimal
+ point. But numericLerp("0.", "100.", 0.123) === "12."
+ because the strings are interpreted as integers followed
+ by a full stop.
Calling this functions on strings that differ in more than
numerals gives undefined results.
front of one string with another. This approach is fast
but does not look good when the strings are similar.
*/
- var alen = Math.round(a.length * p);
- var blen = Math.round(b.length * p);
- return b.substring(0, blen) + a.substring(alen, a.length);
+
+ // TODO: Consider fast-pathing this even more for very large
+ // strings, e.g. in the megabyte range. These are large enough
+ // that
+ if (a.match(MULTI) || b.match(MULTI)) {
+ var ca = a.match(GLYPH) || [];
+ var cb = b.match(GLYPH) || [];
+ var calen = Math.round(ca.length * p);
+ var cblen = Math.round(cb.length * p);
+ var r = cb.slice(0, cblen);
+ r.push.apply(r, ca.slice(calen, ca.length));
+ return r.join("");
+ } else {
+ var alen = Math.round(a.length * p);
+ var blen = Math.round(b.length * p);
+ return b.substring(0, blen) + a.substring(alen, a.length);
+ }
}
function lerp(a, b, p) {
return ((n && n < MAX_MATRIX_SIZE) ? diffLerp : fastLerp)(a, b, p);
}
- exports.levenshteinMatrix = levenshteinMatrix;
+ exports.costMatrix = costMatrix;
exports.patch = patch;
exports.diff = diff;
exports.fastLerp = fastLerp;
projects / string-lerp.git / blobdiff