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 reverse (s
) {
83 return s
.split("").reverse().join("");
86 function diffLerp(a
, b
, p
) {
87 /** Interpolate between two strings based on edit distance
89 This interpolation algorithm applys a partial edit of one
90 string into the other. This produces nice looking results,
91 but can take a significant amount of time and memory to
92 compute the edits. It is not recommended for strings
93 longer than a few hundred characters.
97 var edits
= diff(a
, b
);
98 var partial
= edits
.slice(0, Math
.round(p
* edits
.length
));
99 return reverse(patch(partial
, a
));
102 var NUMBERS
= /(-?\d+(?:\.\d+)?)/g;
104 function areNumericTwins(a
, b
) {
105 /** Check if a and b differ only in numerals
107 A leading "-" counts as part of numbers; a leading "+"
108 does not. Numbers may contain a single ".", but no other
109 floating point syntax.
111 return a
.replace(NUMBERS
, "0") === b
.replace(NUMBERS
, "0");
114 function nlerp(a
, b
, p
) {
115 return a
+ (b
- a
) * p
;
118 function numericLerp(a
, b
, p
) {
119 /** Interpolate numerically between two strings containing numbers
121 Numbers may have a leading "-" and a single "." to mark
122 the decimal point, but something must be after the ".".
123 If both of the numbers in a pair are integers, the result
124 is clamped to an integer.
126 For example, numericLerp("0.0", "100", 0.123) === "12.3"
127 because the "." in "0.0" is intepreted as a decimal point.
128 But numericLerp("0.", "100.", 0.123) === "12." because the
129 strings are interpreted as integers followed by a full
132 Calling this functions on strings that differ in more than
133 numerals gives undefined results.
135 var aParts
= a
.split(NUMBERS
);
136 var bParts
= b
.split(NUMBERS
);
137 for (var i
= 1; i
< aParts
.length
; i
+= 2) {
138 var part
= nlerp(+aParts
[i
], +bParts
[i
], p
);
139 if (aParts
[i
].indexOf(".") === -1 && bParts
[i
].indexOf(".") === -1)
140 part
= Math
.round(part
);
141 aParts
[i
] = part
.toString();
143 return aParts
.join("");
146 function fastLerp(a
, b
, p
) {
147 /** Interpolate between two strings based on length
149 This interpolation algorithm progressively replaces the
150 front of one string with another. This approach is fast
151 but does not look good when the strings are similar.
153 var alen
= Math
.round(a
.length
* p
);
154 var blen
= Math
.round(b
.length
* p
);
155 return b
.substring(0, blen
) + a
.substring(alen
, a
.length
);
158 function lerp(a
, b
, p
) {
159 /** Interpolate between two strings as best as possible
161 If the strings are identical aside from numbers in them,
162 they are passed through numericLerp.
164 If the strings are not numbers and short, they are passed
167 Otherwise, they are passed through fastLerp.
172 // Fast path for boundary cases.
173 if (p
=== 0) return a
;
174 if (p
=== 1) return b
;
176 if (areNumericTwins(a
, b
))
177 return numericLerp(a
, b
, p
);
179 // Numeric lerps should over- and under-shoot when fed numbers
180 // outside 0 to 1, but other types cannot.
184 var n
= a
.length
* b
.length
;
185 return ((n
&& n
< MAX_MATRIX_SIZE
) ? diffLerp
: fastLerp
)(a
, b
, p
);
188 exports
.levenshteinMatrix
= levenshteinMatrix
;
189 exports
.patch
= patch
;
191 exports
.fastLerp
= fastLerp
;
192 exports
.diffLerp
= diffLerp
;
193 exports
.numericLerp
= numericLerp
;
196 })(typeof exports
=== "undefined" ? (this.stringLerp
= {}) : exports
);