More memory friendly Levenshtein distance for JavaScript

Levenshtein revisited - more memory friendly

require('benchmarks.js/index');

Array.prototype.clone = function () {

	return this.slice(0);
};

/**
 * Original Levenshtein implementation by Andrea Giammarchi
 * See http://webreflection.blogspot.com/2009/02/levenshtein-algorithm-revisited-25.html
 * It holds the whole matrix in memory, for 1000 bytes of text, this is minimum
 * 1000 x 1000 x 8 (JavaScript float) = 8MB
 */
var levenshtein = function(min, split){
    // Levenshtein Algorithm Revisited - WebReflection
    try{split=!("0")[0]}catch(i){split=true};
    return function(a, b){
        if(a == b)return 0;
        if(!a.length || !b.length)return b.length || a.length;
        if(split){a = a.split("");b = b.split("")};
        var len1 = a.length + 1,
            len2 = b.length + 1,
            I = 0,
            i = 0,
            d = [[0]],
            c, j, J;
        while(++i < len2)
            d[0][i] = i;
        i = 0;
        while(++i < len1){
            J = j = 0;
            c = a[I];
            d[i] = [i];
            while(++j < len2){
                d[i][j] = min(d[I][j] + 1, d[i][J] + 1, d[I][J] + (c != b[J]));
                ++J;
            };
            ++I;
        };
        
        //console.log(process.memoryUsage().heapUsed);
        return d[len1 - 1][len2 - 1];
    }
}(Math.min, false);

/**
 * My new Levenshtein implementation - inspired by Hirschberg algorithm
 * It only holds the the last 2 matrix lines in memory, for 1000 bytes of text
 * this is 2 x 1000 x 8 (JavaScript float) = 16K
 * It could by slower, but doesn't need as much memory.
 */
var nuLevenshtein = function(){
    
    var min = Math.min;
    try { split = !('0')[0]; } catch(i) { split = true; }
    
    return function (a, b) {
    
        if (a == b) return 0;
        if (!a.length || !b.length) return b.length || a.length;
        
        
        if (split) {
        
        	a = a.split('');
        	b = b.split('');
        };
        var l_a = a.length + 1,
            l_b = b.length + 1,
            I = 0,
            i = 0,
            d = [0],
            c, j = 0, J,
            ld;
        while(++j < l_b) d[j] = j;
        i = 0;
        while(++i < l_a){
            J = j = 0;
            c = a[I];
            
            ld = d.clone();
            d = [i];
            
            while(++j < l_b){

                d[j] = min(
                	ld[j] + 1,
                	d[J] + 1,
                	ld[J] + (c != b[J])
                );
                ++J;
            }
            ++I;
        }
        
        //console.log(process.memoryUsage().heapUsed);
        return d[l_b - 1];
    }
}();

var max = 3;

function testLevenshtein (a, b) {

	return levenshtein(a, b);
}

function testNuLevenshtein (a, b) {

	return nuLevenshtein(a, b);
}

var a = 'er Aufbau-Verlag wurde am 16. August 1945 in Berlin gegründet und wuchs bald zum größten belletristischen Verlag der DDR heran. Er hatte sich zu Beginn auf kommunistische und antifaschistische Literatur sowie russische Bücher und Klassikerausgaben spezialisiert. In den folgenden Jahrzehnten erweiterte sich das Verlagsprogramm unter anderem auf Werke der Weltliteratur, zeitgenössische osteuropäische Bücher sowie lateinamerikanische Titel. 2008 war der Aufbau eine Verlagsgruppe, zu der der Aufbau-Verlag, der Aufbau Taschenbuch Verlag, der Verlag Rütten & Loening, der Gustav Kiepenheuer Verlag (Leipzig) sowie Der Audio Verlag (DAV) gehörten. Sie beschäftigte zuletzt 60 Mitarbeiter und veröffentlichte jährlich rund 350 Neu erscheinungen. Am 1. September 2008 wurde ein Insolvenzverfahren eröffnet. Der Unternehmer Matthias Koch übernahm im Oktober 2009 den Aufbau Verlag mit allen Rechten von Bernd F, Lunkewitz. er Aufbau-Verlag wurde am 16. August 1945 in Berlin gegründet und wuchs bald zum größten belletristischen Verlag der DDR heran. Er hatte sich zu Beginn auf kommunistische und antifaschistische Literatur sowie russische Bücher und Klassikerausgaben spezialisiert. In den folgenden Jahrzehnten erweiterte sich das Verlagsprogramm unter anderem auf Werke der Weltliteratur, zeitgenössische osteuropäische Bücher sowie lateinamerikanische Titel. 2008 war der Aufbau eine Verlagsgruppe, zu der der Aufbau-Verlag, der Aufbau Taschenbuch Verlag, der Verlag Rütten & Loening, der Gustav Kiepenheuer Verlag (Leipzig) sowie Der Audio Verlag (DAV) gehörten. Sie beschäftigte zuletzt 60 Mitarbeiter und veröffentlichte jährlich rund 350 Neu erscheinungen. Am 1. September 2008 wurde ein Insolvenzverfahren eröffnet. Der Unternehmer Matthias Koch übernahm im Oktober 2009 den Aufbau Verlag mit allen Rechten von Bernd F. Lunkewitz. er Aufbau-Verlag wurde am 16. August 1945 in Berlin gegründet und wuchs bald zum größten belletristischen Verlag der DDR heran. Er hatte sich zu Beginn auf kommunistische und antifaschistische Literatur sowie russische Bücher und Klassikerausgaben spezialisiert. In den folgenden Jahrzehnten erweiterte sich das Verlagsprogramm unter anderem auf Werke der Weltliteratur, zeitgenössische osteuropäische Bücher sowie lateinamerikanische Titel. 2008 war der Aufbau eine Verlagsgruppe, zu der der Aufbau-Verlag, der Aufbau Taschenbuch Verlag, der Verlag Rütten & Loening, der Gustav Kiepenheuer Verlag (Leipzig) sowie Der Audio Verlag (DAV) gehörten. Sie beschäftigte zuletzt 60 Mitarbeiter und veröffentlichte jährlich rund 350 Neu erscheinungen. Am 1. September 2008 wurde ein Insolvenzverfahren eröffnet. Der Unternehmer Matthias Koch übernahm im Oktober 2009 den Aufbau Verlag mit allen Rechten von Bernd F. Lunkewitz.er Aufbau-Verlag wurde am 16. August 1945 in Berlin gegründet und wuchs bald zum größten belletristischen Verlag der DDR heran. Er hatte sich zu Beginn auf kommunistische und antifaschistische Literatur sowie russische Bücher und Klassikerausgaben spezialisiert. In den folgenden Jahrzehnten erweiterte sich das Verlagsprogramm unter anderem auf Werke der Weltliteratur, zeitgenössische osteuropäische Bücher sowie lateinamerikanische Titel. 2008 war der Aufbau eine Verlagsgruppe, zu der der Aufbau-Verlag, der Aufbau Taschenbuch Verlag, der Verlag Rütten & Loening, der Gustav Kiepenheuer Verlag (Leipzig) sowie Der Audio Verlag (DAV) gehörten. Sie beschäftigte zuletzt 60 Mitarbeiter und veröffentlichte jährlich rund 350 Neu erscheinungen. Am 1. September 2008 wurde ein Insolvenzverfahren eröffnet. Der Unternehmer Matthias Koch übernahm im Oktober 2009 den Aufbau Verlag mit allen Rechten von Bernd F, Lunkewitz. er Aufbau-Verlag wurde am 16. August 1945 in Berlin gegründet und wuchs bald zum größten belletristischen Verlag der DDR heran. Er hatte sich zu Beginn auf kommunistische und antifaschistische Literatur sowie russische Bücher und Klassikerausgaben spezialisiert. In den folgenden Jahrzehnten erweiterte sich das Verlagsprogramm unter anderem auf Werke der Weltliteratur, zeitgenössische osteuropäische Bücher sowie lateinamerikanische Titel. 2008 war der Aufbau eine Verlagsgruppe, zu der der Aufbau-Verlag, der Aufbau Taschenbuch Verlag, der Verlag Rütten & Loening, der Gustav Kiepenheuer Verlag (Leipzig) sowie Der Audio Verlag (DAV) gehörten. Sie beschäftigte zuletzt 60 Mitarbeiter und veröffentlichte jährlich rund 350 Neu erscheinungen. Am 1. September 2008 wurde ein Insolvenzverfahren eröffnet. Der Unternehmer Matthias Koch übernahm im Oktober 2009 den Aufbau Verlag mit allen Rechten von Bernd F. Lunkewitz. er Aufbau-Verlag wurde am 16. August 1945 in Berlin gegründet und wuchs bald zum größten belletristischen Verlag der DDR heran. Er hatte sich zu Beginn auf kommunistische und antifaschistische Literatur sowie russische Bücher und Klassikerausgaben spezialisiert. In den folgenden Jahrzehnten erweiterte sich das Verlagsprogramm unter anderem auf Werke der Weltliteratur, zeitgenössische osteuropäische Bücher sowie lateinamerikanische Titel. 2008 war der Aufbau eine Verlagsgruppe, zu der der Aufbau-Verlag, der Aufbau Taschenbuch Verlag, der Verlag Rütten & Loening, der Gustav Kiepenheuer Verlag (Leipzig) sowie Der Audio Verlag (DAV) gehörten. Sie beschäftigte zuletzt 60 Mitarbeiter und veröffentlichte jährlich rund 350 Neu erscheinungen. Am 1. September 2008 wurde ein Insolvenzverfahren eröffnet. Der Unternehmer Matthias Koch übernahm im Oktober 2009 den Aufbau Verlag mit allen Rechten von Bernd F. Lunkewitz.';

var b = 'er Aufbau-Verlag wurde am 16. August 1945 in Berlin gegründet und wuchs bald zum größten belletristischen Verlag der DDR heran. Er hatte sich zu Beginn auf kommunistische und antifaschistische Literatur sowie russische Bücher und Klassikerausgaben spezialisiert. In den folgenden Jahrzehnten erweiterte sich das Verlagsprogramm unter anderem auf Werke der Weltliteratur, zeitgenössische osteuropäische Bücher sowie lateinamerikanische Titel. 2008 war der Aufbau eine Verlagsgruppe, zu der der Aufbau-Verlag, der Aufbau Taschenbuch Verlag, der Verlag Rütten & Loening, der Gustav Kiepenheuer Verlag (Leipzig) sowie Der Audio Verlag (DAV) gehörten. Sie beschäftigte zuletzt 60 Mitarbeiter und veröffentlichte jährlich rund 350 Neu erscheinungen. Am 1. September 2008 wurde ein Insolvenzverfahren eröffnet. Der Unternehmer Matthias Koch übernahm im Oktober 2009 den Aufbau Verlag mit allen Rechten von Bernd F, Lunkewitz. er Aufbau-Verlag wurde am 16. August 1945 in Berlin gegründet und wuchs bald zum größten belletristischen Verlag der DDR heran. Er hatte sich zu Beginn auf kommunistische und antifaschistische Literatur sowie russische Bücher und Klassikerausgaben spezialisiert. In den folgenden Jahrzehnten erweiterte sich das Verlagsprogramm unter anderem auf Werke der Weltliteratur, zeitgenössische osteuropäische Bücher sowie lateinamerikanische Titel. 2008 war der Aufbau eine Verlagsgruppe, zu der der Aufbau-Verlag, der Aufbau Taschenbuch Verlag, der Verlag Rütten & Loening, der Gustav Kiepenheuer Verlag (Leipzig) sowie Der Audio Verlag (DAV) gehörten. Sie beschäftigte zuletzt 60 Mitarbeiter und veröffentlichte jährlich rund 350 Neu erscheinungen. Am 1. September 2008 wurde ein Insolvenzverfahren eröffnet. Der Unternehmer Matthias Koch übernahm im Oktober 2009 den Aufbau Verlag mit allen Rechten von Bernd F. Lunkewitz. er Aufbau-Verlag wurde am 16. August 1955 in Berlin gegründet und wuchs bald zum größten belletristischen Verlag der DDR heran. Er hatte sich zu Beginn auf kommunistische und antifaschistische Literatur sowie russische Bücher und Klassikerausgaben spezialisiert. In den folgenden Jahrzehnten erweiterte sich das Verlagsprogramm unter anderem auf Werke der Weltliteratur, zeitgenössische osteuropäische Bücher sowie lateinamerikanische Titel. 2008 war der Aufbau eine Verlagsgruppe, zu der der Aufbau-Verlag, der Aufbau Taschenbuch Verlag, der Verlag Rütten & Loening, der Gustav Kiepenheuer Verlag (Leipzig) sowie Der Audio Verlag (DAV) gehörten. Sie beschäftigte zuletzt 60 Mitarbeiter und veröffentlichte jährlich rund 350 Neu erscheinungen. Am 1. September 2008 wurde ein Insolvenzverfahren eröffnet. Der Unternehmer Matthias Koch übernahm im Oktober 2009 den Aufbau Verlag mit allen Rechten von Bernd F. Lunkewitz.er Aufbau-Verlag wurde am 16. August 1945 in Berlin gegründet und wuchs bald zum größten belletristischen Verlag der DDR heran. Er hatte sich zu Beginn auf kommunistische und antifaschistische Literatur sowie russische Bücher und Klassikerausgaben spezialisiert. In den folgenden Jahrzehnten erweiterte sich das Verlagsprogramm unter anderem auf Werke der Weltliteratur, zeitgenössische osteuropäische Bücher sowie lateinamerikanische Titel. 2008 war der Aufbau eine Verlagsgruppe, zu der der Aufbau-Verlag, der Aufbau Taschenbuch Verlag, der Verlag Rütten & Loening, der Gustav Kiepenheuer Verlag (Leipzig) sowie Der Audio Verlag (DAV) gehörten. Sie beschäftigte zuletzt 60 Mitarbeiter und veröffentlichte jährlich rund 350 Neu erscheinungen. Am 1. September 2008 wurde ein Insolvenzverfahren eröffnet. Der Unternehmer Matthias Koch übernahm im Oktober 2009 den Aufbau Verlag mit allen Rechten von Bernd F, Lunkewitz. er Aufbau-Verlag wurde am 16. August 1945 in Berlin gegründet und wuchs bald zum größten belletristischen Verlag der DDR heran. Er hatte sich zu Beginn auf kommunistische und antifaschistische Literatur sowie russische Bücher und Klassikerausgaben spezialisiert. In den folgenden Jahrzehnten erweiterte sich das Verlagsprogramm unter anderem auf Werke der Weltliteratur, zeitgenössische osteuropäische Bücher sowie lateinamerikanische Titel. 2008 war der Aufbau eine Verlagsgruppe, zu der der Aufbau-Verlag, der Aufbau Taschenbuch Verlag, der Verlag Rütten & Loening, der Gustav Kiepenheuer Verlag (Leipzig) sowie Der Audio Verlag (DAV) gehörten. Sie beschäftigte zuletzt 60 Mitarbeiter und veröffentlichte jährlich rund 350 Neu erscheinungen. Am 1. September 2008 wurde ein Insolvenzverfahren eröffnet. Der Unternehmer Matthias Koch übernahm im Oktober 2009 den Aufbau Verlag mit allen Rechten von Bernd F. Lunkewitz. er Aufbau-Verlag wurde am 16. August 1955 in Berlin gegründet und wuchs bald zum größten belletristischen Verlag der DDR heran. Er hatte sich zu Beginn auf kommunistische und antifaschistische Literatur sowie russische Bücher und Klassikerausgaben spezialisiert. In den folgenden Jahrzehnten erweiterte sich das Verlagsprogramm unter anderem auf Werke der Weltliteratur, zeitgenössische osteuropäische Bücher sowie lateinamerikanische Titel. 2008 war der Aufbau eine Verlagsgruppe, zu der der Aufbau-Verlag, der Aufbau Taschenbuch Verlag, der Verlag Rütten & Loening, der Gustav Kiepenheuer Verlag (Leipzig) sowie Der Audio Verlag (DAV) gehörten. Sie beschäftigte zuletzt 60 Mitarbeiter und veröffentlichte jährlich rund 350 Neu erscheinungen. Am 1. September 2008 wurde ein Insolvenzverfahren eröffnet. Der Unternehmer Matthias Koch übernahm im Oktober 2009 den Aufbau Verlag mit allen Rechten von Bernd F. Lunkewitz.';

testLevenshtein.benchmark(null, max, a, b); // 2.3, 3.2

testNuLevenshtein.benchmark(null, max, a, b); // 1.0, 2.2

console.log(Function.getBenchmarks());

Results for max=3:

Performance:

testLevenshtein: 19280 ms (6426 per call)
testNuLevenshtein: 16406 ms (5469 per call)

Memory usage (execute separately by commenting out one of the two tests for this):

testLevenshtein: 183779435 = ~ 184 M
testNuLevenshtein: 4635416 = ~ 5 M

Using long strings will make your script go out of memory!