bpe.js

var assert = require( 'assert' );



function findFrequentBigram( s ) {
    var i, freqs = {}, topFreq = 0, topPair = null, bigram;

    for ( i = 0; i < s.length; i += 2 ) {
        bigram = s.slice( i, i + 2 );
        freq = ++freqs[bigram];
        if ( !( freq > 0 ) ) {
            freqs[bigram] = 1;
        } else if ( freq > topFreq ) {
            topPair = bigram;
            topFreq = freq;
        }
    }

    return topPair;
}

function compress( s ) {
    var available = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'.split( '' ),
        pair, replacement, header = '';

    while ( available.length ) {
        pair = findFrequentBigram( s, 3 );
        if ( pair === null ) {
            break;
        }
        replacement = available.shift();
        s = s.split( pair ).join( replacement );
        header += pair;
    }

    return header + '~' + s;
}

function decompress( s ) {
    var available = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'.split( '' ),
        header = s.slice( 0, s.indexOf( '~' ) ),
        map = {}, i;

    s = s.slice( header.length + 1 );

    for ( i = 0; i < header.length; i += 2 ) {
        map[ available.shift() ] = header.slice( i, i + 2 );
    }

    while ( /[A-Z]/.test( s ) ) {
        s = s.replace( /[A-Z]/g, function ( m ) {
            return map[ m ];
        } );
    }

    return s;
}

var s = 'ext.centralauth.foreignapi!ext.echo.api!ext.echo.init!ext.navigationtiming!ext.uls.eventlogger!ext.uls.interlanguage!ext.visualeditor.targetloader!ext.wikimediaevents!ext.wikimediaevents.loggedin!jquery.checkboxshiftclick!jquery.getattrs!jquery.highlighttext!jquery.makecollapsible!jquery.mw-jump!jquery.placeholder!jquery.suggestions!mediawiki.foreignapi!mediawiki.foreignapi.core!mediawiki.api.watch!mediawiki.page.ready!mediawiki.page.watch.ajax!mediawiki.searchsuggest!mediawiki.ui.button!mediawiki.ui.icon!mmv.bootstrap!mmv.bootstrap.autostart!oojs!schema.navigationtiming!schema.savetiming!schema.universallanguageselector!site';

var compressed = compress( s) ;

console.log( 'original: %s (%d)', s, s.length );
console.log( 'compressed: %s (%d)', compressed, compressed.length );
assert( decompress( compressed ) === s );