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 slowLerp(a
, b
, p
) {
83 /** Interpolate between two strings slowly
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.
91 var edits
= diff(a
, b
);
92 var partial
= edits
.slice(0, Math
.round(p
* edits
.length
));
93 return patch(partial
, a
);
96 function fastLerp(a
, b
, p
) {
97 /** Interpolate between two strings very quickly
99 This interpolation algorithm progressively replaces the
100 front of one string with another. This approach is fast
101 but does not look good when the strings are similar.
103 var alen
= Math
.round(a
.length
* p
);
104 var blen
= Math
.round(b
.length
* p
);
105 return b
.substring(0, blen
) + a
.substring(alen
, a
.length
);
108 function lerp(a
, b
, p
) {
111 var n
= a
.length
* b
.length
;
112 // TODO: if both strings are integers, do an integer lerp.
113 // TODO: if both strings are numbers, do a numeric lerp.
114 return (n
&& n
< MAX_MATRIX_SIZE
)
119 exports
.levenshteinMatrix
= levenshteinMatrix
;
120 exports
.patch
= patch
;
122 exports
.fastLerp
= fastLerp
;
123 exports
.slowLerp
= slowLerp
;
126 })(typeof exports
=== "undefined" ? (this.stringLerp
= {}) : exports
);