4 var MAX_MATRIX_SIZE
= 256 * 256;
6 function levenshteinMatrix(s
, t
, ins
, del
, sub
) {
7 /** Calculate the Levenshtein edit distance matrix for two strings
9 The matrix is returned as a flat typed array.
11 Following http://en.wikipedia.org/wiki/Levenshtein_distance
15 var d
= new Uint32Array(m
* n
);
17 for (i
= 1; i
< m
; ++i
)
19 for (j
= 1; j
< n
; ++j
)
21 for (j
= 1; j
< n
; ++j
)
22 for (i
= 1; i
< m
; ++i
)
23 if (s
[i
- 1] === t
[j
- 1])
24 d
[n
* i
+ j
] = d
[n
* (i
- 1) + j
- 1];
26 d
[n
* i
+ j
] = Math
.min(del
+ d
[n
* (i
- 1) + j
],
27 ins
+ d
[n
* i
+ j
- 1],
28 sub
+ d
[n
* (i
- 1) + j
- 1]);
32 function editPath(d
, t
) {
33 /** Given a Levenshtein matrix and target, create an edit list */
37 var i
= d
.length
/ n
- 1;
39 var sub
= (i
&& j
) ? d
[n
* (i
- 1) + j
- 1] : Infinity
;
40 var del
= i
? d
[n
* (i
- 1) + j
] : Infinity
;
41 var ins
= j
? d
[n
* i
+ j
- 1] : Infinity
;
42 if (sub
<= ins
&& sub
<= del
) {
43 if (d
[n
* i
+ j
] !== d
[n
* (i
- 1) + j
- 1])
44 path
.push(["sub", i
- 1, t
[j
- 1]]);
46 } else if (ins
<= del
) {
47 path
.push(["ins", i
, t
[j
- 1]]);
50 path
.push(["del", i
- 1]);
58 /** Create a diff between string s and t */
59 return editPath(levenshteinMatrix(s
, t
, 2, 2, 3), t
);
62 function patch(edits
, s
) {
63 /** Apply the list of edits to s */
67 if (Array
.isArray(s
)) {
68 for (i
= 0; i
< edits
.length
; ++i
) {
75 s
.splice(edit
[1], 0, edit
[2]);
83 for (i
= 0; i
< edits
.length
; ++i
) {
87 s
= s
.slice(0, edit
[1]) + edit
[2] + s
.slice(edit
[1] + 1);
90 s
= s
.slice(0, edit
[1]) + edit
[2] + s
.slice(edit
[1]);
93 s
= s
.slice(0, edit
[1]) + s
.slice(edit
[1] + 1);
101 var MULTI
= /[\uD800-\uDBFF][\uDC00-\uDFFF]|[\u0300-\u036F\u1DC0-\u1DFF\u20D0-\u20FF\uFE20-\uFE2F]/;
103 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;
105 function diffLerp(a
, b
, p
) {
106 /** Interpolate between two strings based on edit operations
108 This interpolation algorithm applys a partial edit of one
109 string into the other. This produces nice looking results,
110 but can take a significant amount of time and memory to
111 compute the edits. It is not recommended for strings
112 longer than a few hundred characters.
115 // If given strings with astral codepoints or combining
116 // characters, split them into arrays of "glyphs" first,
117 // do the edit on the list of "glyphs", and rejoin them.
119 // This split is not perfect for all languages, but at least
120 // it won't create invalid surrogate pairs or orphaned
121 // combining characters.
122 if (a
.match
&& a
.match(MULTI
) || b
.match
&& b
.match(MULTI
)) {
123 var ca
= a
.match(GLYPH
) || [];
124 var cb
= b
.match(GLYPH
) || [];
125 return diffLerp(ca
, cb
, p
).join("");
128 // The edit path works from the string end, forwards, because
129 // that's how Levenshtein edits work. To match LTR reading
130 // direction (and the behavior of fastLerp), swap the strings
131 // and invert the parameter when editing.
132 var edits
= diff(b
, a
);
133 var partial
= edits
.slice(0, Math
.round((1 - p
) * edits
.length
));
134 return patch(partial
, b
);
137 var NUMBERS
= /(-?\d+(?:\.\d+)?)/g;
139 function areNumericTwins(a
, b
) {
140 /** Check if a and b differ only in numerals
142 A leading "-" counts as part of numbers; a leading "+"
143 does not. Numbers may contain a single ".", but no other
144 floating point syntax.
146 return a
.replace(NUMBERS
, "0") === b
.replace(NUMBERS
, "0");
149 function nlerp(a
, b
, p
) {
150 return a
+ (b
- a
) * p
;
153 function numericLerp(a
, b
, p
) {
154 /** Interpolate numerically between two strings containing numbers
156 Numbers may have a leading "-" and a single "." to mark
157 the decimal point, but something must be after the ".".
158 If both of the numbers in a pair are integers, the result
159 is clamped to an integer.
161 For example, numericLerp("0.0", "100", 0.123) === "12.3"
162 because the "." in "0.0" is interpreted as a decimal
163 point. But numericLerp("0.", "100.", 0.123) === "12."
164 because the strings are interpreted as integers followed
167 Calling this functions on strings that differ in more than
168 numerals gives undefined results.
170 var aParts
= a
.split(NUMBERS
);
171 var bParts
= b
.split(NUMBERS
);
172 for (var i
= 1; i
< aParts
.length
; i
+= 2) {
173 var part
= nlerp(+aParts
[i
], +bParts
[i
], p
);
174 if (aParts
[i
].indexOf(".") === -1 && bParts
[i
].indexOf(".") === -1)
175 part
= Math
.round(part
);
176 aParts
[i
] = part
.toString();
178 return aParts
.join("");
181 function fastLerp(a
, b
, p
) {
182 /** Interpolate between two strings based on length
184 This interpolation algorithm progressively replaces the
185 front of one string with another. This approach is fast
186 but does not look good when the strings are similar.
189 // TODO: Consider fast-pathing this even more for very large
190 // strings, e.g. in the megabyte range. These are large enough
192 if (a
.match(MULTI
) || b
.match(MULTI
)) {
193 var ca
= a
.match(GLYPH
) || [];
194 var cb
= b
.match(GLYPH
) || [];
195 var calen
= Math
.round(ca
.length
* p
);
196 var cblen
= Math
.round(cb
.length
* p
);
197 var r
= cb
.slice(0, cblen
);
198 r
.push
.apply(r
, ca
.slice(calen
, ca
.length
));
201 var alen
= Math
.round(a
.length
* p
);
202 var blen
= Math
.round(b
.length
* p
);
203 return b
.substring(0, blen
) + a
.substring(alen
, a
.length
);
207 function lerp(a
, b
, p
) {
208 /** Interpolate between two strings as best as possible
210 If the strings are identical aside from numbers in them,
211 they are passed through numericLerp.
213 If the strings are not numbers and short, they are passed
216 Otherwise, they are passed through fastLerp.
221 // Fast path for boundary cases.
222 if (p
=== 0) return a
;
223 if (p
=== 1) return b
;
225 if (areNumericTwins(a
, b
))
226 return numericLerp(a
, b
, p
);
228 // Numeric lerps should over- and under-shoot when fed numbers
229 // outside 0 to 1, but other types cannot.
233 var n
= a
.length
* b
.length
;
234 return ((n
&& n
< MAX_MATRIX_SIZE
) ? diffLerp
: fastLerp
)(a
, b
, p
);
237 exports
.levenshteinMatrix
= levenshteinMatrix
;
238 exports
.patch
= patch
;
240 exports
.fastLerp
= fastLerp
;
241 exports
.diffLerp
= diffLerp
;
242 exports
.numericLerp
= numericLerp
;
245 })(typeof exports
=== "undefined" ? (this.stringLerp
= {}) : exports
);