var MAX_MATRIX_SIZE = 256 * 256;
- function repeat(n, v) {
- var r = [];
- while (n--)
- r.push(v);
- return r;
- }
-
- function createMatrix(i, j) {
- var m = [];
- while (i--)
- m.push(repeat(j, 0));
- return m;
- }
-
function levenshteinMatrix(s, t) {
/** Calculate the Levenshtein edit distance matrix for two strings
+
+ The matrix is returned as a flat unsigned typed array.
- // Following http://en.wikipedia.org/wiki/Levenshtein_distance
+ Following http://en.wikipedia.org/wiki/Levenshtein_distance
*/
var m = s.length + 1;
var n = t.length + 1;
- var d = createMatrix(m, n);
+ var d = new Uint32Array(m * n);
var i, j;
for (i = 1; i < m; ++i)
- d[i][0] = i;
+ d[n * i] = i;
for (j = 1; j < n; ++j)
- d[0][j] = j;
+ d[j] = j;
for (j = 1; j < n; ++j)
for (i = 1; i < m; ++i)
if (s[i - 1] === t[j - 1])
- d[i][j] = d[i - 1][j - 1];
+ d[n * i + j] = d[n * (i - 1) + j - 1];
else
- d[i][j] = 1 + Math.min(d[i - 1][ j ],
- d[ i ][j - 1],
- d[i - 1][j - 1]);
+ d[n * i + j] = 1 + Math.min(d[n * (i - 1) + j ],
+ d[n * i + j - 1],
+ d[n * (i - 1) + j - 1]);
return d;
}
- function editPath(m, s, t) {
- var path = []
- var i = s.length;
+ function editPath(d, t) {
+ /** Given a Levenshtein matrix and target, create an edit list */
+ var path = [];
var j = t.length;
+ var n = j + 1;
+ var i = d.length / n - 1;
while (i || j) {
- var sub = (i && j) ? m[i - 1][j - 1] : Infinity;
- var del = i ? m[i - 1][j] : Infinity;
- var ins = j ? m[i][j - 1] : Infinity;
+ 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;
if (sub <= ins && sub <= del) {
- if (m[i][j] !== m[i - 1][j - 1])
+ if (d[n * i + j] !== d[n * (i - 1) + j - 1])
path.push(["sub", i - 1, t[j - 1]]);
--i; --j;
} else if (ins <= del) {
return path;
}
- function applyEdits(edits, s, t) {
+ function diff(s, t) {
+ /** Create a diff between string s and t */
+ return editPath(levenshteinMatrix(s, t), t);
+ }
+
+ function patch(edits, s) {
+ /** Apply the list of edits to s */
var i;
for (i = 0; i < edits.length; ++i) {
var edit = edits[i];
return s;
}
- function slowLerp(a, b, p) {
- var m = levenshteinMatrix(a, b);
- var edits = editPath(m, a, b);
+ function diffLerp(a, b, p) {
+ /** Interpolate between two strings based on edit distance
+
+ This interpolation algorithm applys a partial edit of one
+ string into the other. This produces nice looking results,
+ but can take a significant amount of time and memory to
+ 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 applyEdits(partial, a, b);
+ return patch(partial, a);
+ }
+
+ var NUMBERS = /(-?\d+(?:\.\d+)?)/g;
+
+ function areNumericTwins(a, b) {
+ /** Check if a and b differ only in numerals
+
+ A leading "-" counts as part of numbers; a leading "+"
+ does not. Numbers may contain a single ".", but no other
+ floating point syntax.
+ */
+ return a.replace(NUMBERS, "0") === b.replace(NUMBERS, "0");
+ }
+
+ function nlerp(a, b, p) {
+ return a + (b - a) * p;
+ }
+
+ function numericLerp(a, b, p) {
+ /** Interpolate numerically between two strings containing numbers
+
+ Numbers may have a leading "-" and a single "." to mark
+ the decimal point, but something must be after the ".".
+ If both of the numbers in a pair are integers, the result
+ 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.
+
+ Calling this functions on strings that differ in more than
+ numerals gives undefined results.
+ */
+ var aParts = a.split(NUMBERS);
+ var bParts = b.split(NUMBERS);
+ for (var i = 1; i < aParts.length; i += 2) {
+ var part = nlerp(+aParts[i], +bParts[i], p);
+ if (aParts[i].indexOf(".") === -1 && bParts[i].indexOf(".") === -1)
+ part = Math.round(part);
+ aParts[i] = part.toString();
+ }
+ return aParts.join("");
}
function fastLerp(a, b, p) {
+ /** Interpolate between two strings based on length
+
+ This interpolation algorithm progressively replaces the
+ 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);
}
function lerp(a, b, p) {
+ /** Interpolate between two strings as best as possible
+
+ If the strings are identical aside from numbers in them,
+ they are passed through numericLerp.
+
+ If the strings are not numbers and short, they are passed
+ through diffLerp.
+
+ Otherwise, they are passed through fastLerp.
+ */
a = a.toString();
b = b.toString();
+
+ // Fast path for boundary cases.
+ if (p === 0) return a;
+ if (p === 1) return b;
+
+ if (areNumericTwins(a, b))
+ return numericLerp(a, b, p);
+
+ // Numeric lerps should over- and under-shoot when fed numbers
+ // outside 0 to 1, but other types cannot.
+ if (p < 0) return a;
+ if (p > 1) return b;
+
var n = a.length * b.length;
- return (n && n < MAX_MATRIX_SIZE)
- ? slowLerp(a, b, p)
- : fastLerp(a, b, p);
+ return ((n && n < MAX_MATRIX_SIZE) ? diffLerp : fastLerp)(a, b, p);
}
exports.levenshteinMatrix = levenshteinMatrix;
- exports.editPath = editPath;
+ exports.patch = patch;
+ exports.diff = diff;
exports.fastLerp = fastLerp;
- exports.slowLerp = slowLerp;
- exports.applyEdits = applyEdits;
+ exports.diffLerp = diffLerp;
+ exports.numericLerp = numericLerp;
exports.lerp = lerp;
})(typeof exports === "undefined" ? (this.stringLerp = {}) : exports);
projects / string-lerp.git / blobdiff