4 var MAX_MATRIX_SIZE
= 256 * 256;
6 function levenshteinMatrix(s
, t
) {
7 /** Calculate the Levenshtein edit distance matrix for two strings
9 The matrix is returned as a flat unsigned 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
] = 1 + Math
.min(d
[n
* (i
- 1) + j
],
28 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
), t
);
62 function patch(edits
, s
) {
63 /** Apply the list of edits to s */
65 for (i
= 0; i
< edits
.length
; ++i
) {
69 s
= s
.slice(0, edit
[1]) + edit
[2] + s
.slice(edit
[1] + 1);
72 s
= s
.slice(0, edit
[1]) + edit
[2] + s
.slice(edit
[1]);
75 s
= s
.slice(0, edit
[1]) + s
.slice(edit
[1] + 1);
82 function diffLerp(a
, b
, p
) {
83 /** Interpolate between two strings based on edit distance
85 This interpolation algorithm applys a partial edit of one
86 string into the other. This produces nice looking results,
87 but can take a significant amount of time and memory to
88 compute the edits. It is not recommended for strings
89 longer than a few hundred characters.
92 // The edit path works from the string end, forwards, because
93 // that's how Levenshtein edits work. To match LTR reading
94 // direction (and the behavior of fastLerp), swap the strings
95 // and invert the parameter when editing.
96 var edits
= diff(b
, a
);
97 var partial
= edits
.slice(0, Math
.round((1 - p
) * edits
.length
));
98 return patch(partial
, b
);
101 var NUMBERS
= /(-?\d+(?:\.\d+)?)/g;
103 function areNumericTwins(a
, b
) {
104 /** Check if a and b differ only in numerals
106 A leading "-" counts as part of numbers; a leading "+"
107 does not. Numbers may contain a single ".", but no other
108 floating point syntax.
110 return a
.replace(NUMBERS
, "0") === b
.replace(NUMBERS
, "0");
113 function nlerp(a
, b
, p
) {
114 return a
+ (b
- a
) * p
;
117 function numericLerp(a
, b
, p
) {
118 /** Interpolate numerically between two strings containing numbers
120 Numbers may have a leading "-" and a single "." to mark
121 the decimal point, but something must be after the ".".
122 If both of the numbers in a pair are integers, the result
123 is clamped to an integer.
125 For example, numericLerp("0.0", "100", 0.123) === "12.3"
126 because the "." in "0.0" is intepreted as a decimal point.
127 But numericLerp("0.", "100.", 0.123) === "12." because the
128 strings are interpreted as integers followed by a full
131 Calling this functions on strings that differ in more than
132 numerals gives undefined results.
134 var aParts
= a
.split(NUMBERS
);
135 var bParts
= b
.split(NUMBERS
);
136 for (var i
= 1; i
< aParts
.length
; i
+= 2) {
137 var part
= nlerp(+aParts
[i
], +bParts
[i
], p
);
138 if (aParts
[i
].indexOf(".") === -1 && bParts
[i
].indexOf(".") === -1)
139 part
= Math
.round(part
);
140 aParts
[i
] = part
.toString();
142 return aParts
.join("");
145 function fastLerp(a
, b
, p
) {
146 /** Interpolate between two strings based on length
148 This interpolation algorithm progressively replaces the
149 front of one string with another. This approach is fast
150 but does not look good when the strings are similar.
152 var alen
= Math
.round(a
.length
* p
);
153 var blen
= Math
.round(b
.length
* p
);
154 return b
.substring(0, blen
) + a
.substring(alen
, a
.length
);
157 function lerp(a
, b
, p
) {
158 /** Interpolate between two strings as best as possible
160 If the strings are identical aside from numbers in them,
161 they are passed through numericLerp.
163 If the strings are not numbers and short, they are passed
166 Otherwise, they are passed through fastLerp.
171 // Fast path for boundary cases.
172 if (p
=== 0) return a
;
173 if (p
=== 1) return b
;
175 if (areNumericTwins(a
, b
))
176 return numericLerp(a
, b
, p
);
178 // Numeric lerps should over- and under-shoot when fed numbers
179 // outside 0 to 1, but other types cannot.
183 var n
= a
.length
* b
.length
;
184 return ((n
&& n
< MAX_MATRIX_SIZE
) ? diffLerp
: fastLerp
)(a
, b
, p
);
187 exports
.levenshteinMatrix
= levenshteinMatrix
;
188 exports
.patch
= patch
;
190 exports
.fastLerp
= fastLerp
;
191 exports
.diffLerp
= diffLerp
;
192 exports
.numericLerp
= numericLerp
;
195 })(typeof exports
=== "undefined" ? (this.stringLerp
= {}) : exports
);