string-lerp.js

   1 (function (exports) {
   2     "use strict";
   3
   4     var MAX_MATRIX_SIZE = 256 * 256;
   5
   6     function createMatrix(i, j) {
   7         return new Uint32Array(i * j);
   8     }
   9
  10     function levenshteinMatrix(s, t) {
  11         /** Calculate the Levenshtein edit distance matrix for two strings
  12
  13             The matrix is returned as a flat unsigned typed array.
  14
  15             Following http://en.wikipedia.org/wiki/Levenshtein_distance
  16         */
  17         var m = s.length + 1;
  18         var n = t.length + 1;
  19         var d = createMatrix(m, n);
  20         var i, j;
  21         for (i = 1; i < m; ++i)
  22             d[n * i] = i;
  23         for (j = 1; j < n; ++j)
  24             d[j] = j;
  25         for (j = 1; j < n; ++j)
  26             for (i = 1; i < m; ++i)
  27                 if (s[i - 1] === t[j - 1])
  28                     d[n * i + j] = d[n * (i - 1) + j - 1];
  29                 else
  30                     d[n * i + j] = 1 + Math.min(d[n * (i - 1) + j    ],
  31                                                 d[n *    i    + j - 1],
  32                                                 d[n * (i - 1) + j - 1]);
  33         return d;
  34     }
  35
  36     function editPath(d, s, t) {
  37         /** Given a Levenshtein result matrix, trace the shortest edit */
  38         var path = []
  39         var i = s.length;
  40         var j = t.length;
  41         var n = j + 1;
  42         while (i || j) {
  43             var sub = (i && j) ? d[n * (i - 1) + j - 1] : Infinity;
  44             var del = i ? d[n * (i - 1) + j] : Infinity;
  45             var ins = j ? d[n * i + j - 1] : Infinity;
  46             if (sub <= ins && sub <= del) {
  47                 if (d[n * i + j] !== d[n * (i - 1) + j - 1])
  48                     path.push(["sub", i - 1, t[j - 1]]);
  49                 --i; --j;
  50             } else if (ins <= del) {
  51                 path.push(["ins", i, t[j - 1]]);
  52                 --j;
  53             } else {
  54                 path.push(["del", i - 1]);
  55                 --i;
  56             }
  57         }
  58         return path;
  59     }
  60
  61     function applyEdits(edits, s) {
  62         /** Apply the list of edits to s */
  63         var i;
  64         for (i = 0; i < edits.length; ++i) {
  65             var edit = edits[i];
  66             switch (edit[0]) {
  67             case "sub":
  68                 s = s.slice(0, edit[1]) + edit[2] + s.slice(edit[1] + 1);
  69                 break;
  70             case "ins":
  71                 s = s.slice(0, edit[1]) + edit[2] + s.slice(edit[1]);
  72                 break;
  73             case "del":
  74                 s = s.slice(0, edit[1]) + s.slice(edit[1] + 1);
  75                 break;
  76             }
  77         }
  78         return s;
  79     }
  80
  81     function slowLerp(a, b, p) {
  82         /** Interpolate between two strings slowly
  83
  84             This interpolation algorithm applys a partial edit of one
  85             string into the other. This produces nice looking results,
  86             but can take a significant amount of time and memory to
  87             compute the edits. It is not recommended for strings
  88             longer than a few hundred characters.
  89          */
  90         var edits = editPath(levenshteinMatrix(a, b), a, b);
  91         var partial = edits.slice(0, Math.round(p * edits.length));
  92         return applyEdits(partial, a);
  93     }
  94
  95     function fastLerp(a, b, p) {
  96         /** Interpolate between two strings very quickly
  97
  98             This interpolation algorithm progressively replaces the
  99             front of one string with another. This approach is fast
 100             but does not look good when the strings are similar.
 101          */
 102         var alen = Math.round(a.length * p);
 103         var blen = Math.round(b.length * p);
 104         return b.substring(0, blen) + a.substring(alen, a.length);
 105     }
 106
 107     function lerp(a, b, p) {
 108         a = a.toString();
 109         b = b.toString();
 110         var n = a.length * b.length;
 111         // TODO: if both strings are integers, do an integer lerp.
 112         // TODO: if both strings are numbers, do a numeric lerp.
 113         return (n && n < MAX_MATRIX_SIZE)
 114             ? slowLerp(a, b, p)
 115             : fastLerp(a, b, p);
 116     }
 117
 118     exports.levenshteinMatrix = levenshteinMatrix;
 119     exports.editPath = editPath;
 120     exports.fastLerp = fastLerp;
 121     exports.slowLerp = slowLerp;
 122     exports.applyEdits = applyEdits;
 123     exports.lerp = lerp;
 124
 125 })(typeof exports === "undefined" ? (this.stringLerp = {}) : exports);