Levenshtein distance (v13)

Revision 13 of this benchmark created on

Description

Prompted by a [Stack Overflow question][http://stackoverflow.com/questions/11919065/sort-an-array-by-the-levenshtein-distance-with-best-performance-in-javascript], this will compare implementations of the Levenshtein distance algorithm.

By adding a limit and optimising comparison operators, I hope to further increase the performance of the Westgate implementation.

Preparation HTML

<script src="//ajax.googleapis.com/ajax/libs/jquery/1/jquery.min.js"></script>

Setup

// Screen names grabbed from Lady Gaga's twitter followers.
    // http://jsfiddle.net/Jordan/UMKzq/1/
    window.screenNames = ["@deeia2000", "@bryankristanto", "@G_EZ_2012", "@alemayehulakew", "@SandraVeneva", "@celebiyesim", "@dior_rf", "@Stiffalator", "@IzmanMahmudi", "@judith_16", "@jele1199", "@Belenisortiz", "@lablabchi", "@alhamwaleed96", "@Frankie_W88", "@Surinaamse_", "@kotikibarsiki", "@pradeepnkt", "@vanimahajan37", "@mayrarodrigue46", "@OpsMiguel", "@s_sxt", "@ALIMayri24", "@NOT_forFREE", "@MiamiBitchez", "@paul__wayne", "@shinnydun", "@teamo_minhavida", "@Male_Jayerr", "@soniandikha", "@smokedoutsammy", "@indahcynkkeluar", "@Rhea_Scherbert", "@kemassiabdelgan", "@FacescoutZa", "@minhthanhphan", "@LhinaEndarlina", "@F6ame_R", "@geo_luiza", "@tt_hwi", "@ikmngkr_ykh", "@vutruonggiang3", "@rachelconroyxx", "@maychelerryans1", "@bonu58", "@fikirreta", "@amitbhagat17", "@OhliviaEs", "@Zh_Indira", "@akbarr_maulana", "@ReyvellRogado", "@eMxcee", "@maina_annie", "@angelohipolito1", "@luckgas", "@erdigulec", "@RadicBane", "@7co8oki", "@egoses", "@shirleyhemingw1", "@NascimentoKim", "@sirma_h", "@HoneyDanaE", "@ayhanturk60", "@JohnWan64688411", "@kharis_novelia", "@finkbina", "@domele94", "@anayieee", "@basakras", "@LipeSecretos55", "@Nirvana_Kurt_Co", "@putrajelek123", "@JLS_lulu13", "@EnashYaomatu", "@JamieRaymond8", "@Aulia_Fitri5", "@nabilmstrieux", "@ChelMaeAlinsunu", "@AryoJr", "@GreeneChae", "@whatsupardee", "@LarisaMaric", "@DanaeFlanagan", "@ChixDmusicBand", "@masyanya1995_", "@LetiziaCipriani", "@HiaAde", "@JoannaKarai", "@ivonlidya", "@akanchanchan", "@MiaaGotSwagg", "@lorinsh", "@OlurotimiKush", "@tiapav23", "@ganesh02222", "@Rodrigox_18", "@kayhan_Dre", "@1johnsonranch", "@aldidharro", "@meliamurph", "@Himansh21495710", "@gsli05necip", "@bgtmr025", "@925Aoi", "@GalauPangeran", "@ShaynalOranaise", "@tnk_pnpn", "@rizzajoybriza", "@JoshuaJojack", "@ilyascoskun1", "@WanAriff3", "@blondinen0221", "@johnkarlsosa", "@Derbora18", "@TmarYaha", "@Cristiano_88_", "@chloe11235", "@AliARSAL2", "@The_Super_zizo", "@waiyanhtoo13445", "@ime1608", "@marissemendoza", "@Deea182", "@kraravind07", "@cih3315", "@gui_assunao", "@CodiAnnW", "@Perfect_Belinda", "@AchmadHisyam1", "@baldo_cristian", "@ulrikaberg1", "@yuichiro15sai", "@PatrickSlavin2", "@Jean_249", "@LYrelax", "@yoganfb", "@malcolmcroberts", "@KorgPumba", "@AllProsAndCONs", "@khalreaees2", "@laurencool2", "@akkitab3", "@loove1Dloove", "@joshua010499", "@ishtyle79", "@khalid55_55", "@Victori05028144", "@alk35319034", "@Morgane_Mllr", "@linwanhsi", "@nadine_mongare", "@serenacast", "@MustafaMuhamm14", "@EleElena4", "@salvalaz_20", "@khalunaamira", "@iDriver_Crazy", "@Xanni2", "@Afsal_music", "@gjaymie", "@RhenTacAn", "@olsdhol", "@ChiaraRapali", "@Sex_Couture", "@nikolaowczorz", "@Williamsss7", "@junaid26959651", "@EhkaluPoe", "@gene_mika09", "@Bieber_124", "@AngeAngel199", "@MBTek1", "@AllisonKadoche", "@LyubashaN", "@estaloco1", "@rizal_aripin", "@taffytops99", "@JanineFeldkamp", "@ChsnLucie", "@mandeep15734355", "@K13R4N86", "@ShLelo", "@NinaPhung", "@yazeedzuod", "@LesroyMC7", "@Romy1298", "@adolescentes_12", "@geraglezZ", "@rafyrodz0334", "@SilvB20", "@santo_nubia", "@suepur", "@thebigchalenger", "@PalominoLuz1", "@CriisloveMiley", "@ANJEANETTEFERNA", "@ashlyn_ya", "@pastoredoyak", "@HeyyitsMichael", "@ATayden", "@leahmil84388097", "@ArafahSyafiq", "@NetyRamadan", "@kne_tt", "@mario33216140", "@9108810", "@raniabella5", "@Metshiyatz", "@AyudiahW", "@LiekeSays", "@ThebeastNr", "@JospedroRamos", "@Ariane555Silva", "@mirekgrzadziela", "@BubbieBonkers", "@DIBOLL", "@AnicetoHo", "@Faaaaaan1D", "@pophina", "@lexiwalters", "@bahhwhuut", "@fratyalva", "@ANdriANggRo", "@lyndz_xoxo", "@LiziStyless", "@ShindinaO", "@MalAaron", "@j_conradie", "@niffynog87", "@ZyreenReen", "@surewaterdrilli", "@GretaPanarotto", "@yeliz323232", "@nico14210", "@TheOnlyStarAnni", "@do_amigos", "@PachecoHopper84", "@AsiaSzostak", "@missfading", "@LasagnaCatt", "@AnjuliAng", "@PiotrBanan", "@EmersonViegas2", "@SashkaMilenova", "@nurlela82722746", "@Meme_Nathalia", "@Petrus1991", "@dakala3", "@WilleJanina", "@kkjh87it6", "@JNeeeeeeee", "@Unwingedfairy", "@violet9803", "@thaliaortizz", "@JoeySawyers", "@Ishwar73907748", "@1DTurkishGirls", "@ghalib_legendz", "@AliceJ_McIntosh", "@vivienp_", "@hannahadamss_", "@josete2310", "@samuellozano12", "@tygapkhiangte", "@Aditiya_ramdn24", "@BratuAlecs", "@Nussy_Ns", "@RaZenGrg", "@lj_bataller", "@LezMeBe", "@keithleamilitan", "@marjanadeli", "@AsMinaDePollo", "@kinkyminxsykes", "@AldrienAldriene", "@GRasonable", "@dheavidd", "@RandomPplNews", "@Josh_McMurtry", "@Kindajezzy", "@anjalinatz", "@jellydavies", "@milkyleavy", "@yellaboi_", "@sourysoura", "@AmazingSelenita", "@Denisse836", "@deliane_silva", "@tpwhd64a", "@TheMrG88", "@LauraHoggarth", "@Sofia_klark", "@VrAj_15", "@MArwa_SAied", "@asep_rover20", "@AsLizeth", "@AnnaLeeman", "@abbie_scannell", "@Boum_Abbou", "@miamingos123", "@jean_lising", "@chang4sheng1", "@AngelaVilei", "@KSUGossipGirl_", "@calesaric", "@Alejandro55alle", "@aliciadlhg", "@analaura_rg", "@mithawidiyanty", "@elinchixx", "@xyzhasan1998", "@daisybirkenhead", "@injy1998", "@nisan2020", "@qierstenwilson8", "@Smeib", "@DRmahmoud_M", "@harriet1304", "@tahertarmizi2", "@candelatorres6", "@anamari_96", "@KYMANO14", "@quiones_angie", "@rerefadila", "@PolinaJ", "@unikamg", "@c4ptainpsycho", "@Giu_Jonectioner", "@evilefebrianti", "@kirstyjo_bruce", "@SizZilinqPwince", "@Teo_Dora1D", "@DontCallMePanii", "@Xxzxx0Edcrfgr", "@AnsharKurniawan", "@ivanfaruolo", "@_BasitAliRaza", "@NO_De_luza", "@HoranBackup", "@HandFullOfRain", "@SmileNunnin", "@juliana50182518", "@Alinca4", "@andrea_wh", "@valerie33550099", "@allie_m1", "@JosanFranz", "@JackyRomuga", "@mimonzi", "@RismanFansIqbal", "@pauly_arco", "@KakoParker", "@PetterElfving", "@iJelenaGoogle", "@Tweets_Nikita", "@bikersbrother99", "@LisaFerera", "@Dragosh_Man", "@aannstephen", "@JuniorUFCRamos", "@Lewiskelly012", "@them12345", "@ThemTweetsPink", "@irem_justin126", "@emilyfr59168189", "@AoUsanee", "@hobelisk", "@rebeccamcmahon_", "@vicentepacheco7", "@paaooollooo", "@Choi248109", "@Daniell63850634", "@DoaaAboud1", "@wwsohj", "@acap_z", "@FuatFuatarkn", "@Gezimkrosa", "@hannzu43", "@lukman44492601", "@Sonata86460024", "@Leonardoojames", "@benny_benny1999", "@sanchez_diego", "@agastyashindu", "@ElwinataShirazy", "@Eja_Muhammad", "@elephantqw", "@snglesound", "@TEAMNACSsige", "@indahSwann", "@saoapple0112", "@petervhulst", "@NapashaMir", "@RubnChaval", "@LucieTouss", "@lowry_g", "@real_campaign", "@JonazFerrera", "@ChloEmmerson"];
    
    Math.RandomInt = function(min, max) {
      return Math.floor(Math.random() * (max - min + 1)) + min;
    };
    
    window.randomScreenName = function() {
      return screenNames[Math.RandomInt(0, screenNames.length - 1)];
    }
    
    window.CompareLD1 = function(min, split) {
      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;
        }
        return d[len1 - 1][len2 - 1];
      }
    }(Math.min, false);
    
    
    window.CompareLD2 = function(s, t) {
      var d = [];
      var n = s.length;
      var m = t.length;
      if (n === 0) return m;
      if (m === 0) return n;
      for (var i = n; i >= 0; i--) d[i] = [];
      for (var i = n; i >= 0; i--) d[i][0] = i;
      for (var j = m; j >= 0; j--) d[0][j] = j;
      for (var i = 1; i <= n; i++) {
        var s_i = s.charAt(i - 1);
        for (var j = 1; j <= m; j++) {
          if (i === j && d[i][j] > 4) return n;
          var t_j = t.charAt(j - 1);
          var cost = (s_i === t_j) ? 0 : 1;
          var mi = d[i - 1][j] + 1;
          var b = d[i][j - 1] + 1;
          var c = d[i - 1][j - 1] + cost;
          if (b < mi) mi = b;
          if (c < mi) mi = c;
          d[i][j] = mi;
          if (i > 1 && j > 1 && s_i === t.charAt(j - 2) && s.charAt(i - 2) === t_j) {
            d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost);
          }
        }
      }
      return d[n][m];
    };
    
    
    function minn(a, b, c) {
      if (a > b) a = b;
      if (a < c) return a;
      return c;
    }
    
    window.CompareLD3 = function(S1, S2, limit) {
      if (S1 == null || S2 == null || typeof(S1) != "string" || typeof(S2) != "string") return 9999999;
      if (limit == null) limit = 9999999;
      if (Math.abs(S1.length - S2.length) > limit) return 9999999;
      S1 = S1.toLowerCase();
      S2 = S2.toLowerCase();
      if (S1 == S2) return 0;
      var n = S1.length;
      var m = S2.length;
      dist = new Array(new Array(m + 2), new Array(m + 2));
      current = 0;
      for (i = 0; i <= m + 1; i++) {
        dist[1][i] = i;
      }
      for (i = 1; i <= n; i++) {
        ok = 0;
        dist[current][0] = i;
        if (i - limit >= 1) dist[current][i - limit - 1] = 9999999;
        for (j = Math.max(i - limit, 1); j <= Math.min(i + limit, m); j++) {
          if (S1.substr(i - 1, 1) == S2.substr(j - 1, 1)) dist[current][j] = dist[1 - current][j - 1];
          else dist[current][j] = minn(dist[1 - current][j - 1], dist[1 - current][j], dist[current][j - 1]) + 1;
          if (dist[current][j] <= limit) ok = 1;
        }
        if (i + limit <= m) {
          dist[current][i + limit + 1] = 9999999;
        }
        if (!ok) return 9999999;
        current = 1 - current;
      }
      if (dist[1 - current][m] > limit) return 9999999;
      return dist[1 - current][m];
    };
    
    window.CompareLD6 = function(s, t, lim) {
      if (!lim) lim = 20;
      if (Math.abs(s.length - t.length) > lim) return lim;
    
      var d = []; //2d matrix
      // Step 1
      var n = s.length,
          m = t.length;
    
      if (n === 0) return m;
      if (m === 0) return n;
    
      var i = n + 1;
      do {
        d[i] = [];
      } while (i--);
    
      // Step 2
      i = n + 1, j = m + 1;
      do {
        d[i][0] = i;
      } while (i--);
      do {
        d[0][j] = j;
      } while (j--);
    
      // Step 3
      for (var i = 1; i <= n; i++) {
        var s_i = s.charAt(i - 1);
    
        // Step 4
        for (var j = 1; j <= m; j++) {
    
          //Check the jagged ld total so far
          if (i === j && d[i][j] > 4) return n;
    
          var t_j = t.charAt(j - 1);
          var cost = (s_i === t_j) ? 0 : 1; // Step 5
          //Calculate the minimum
          var mi = d[i - 1][j] + 1;
          var b = d[i][j - 1] + 1;
          var c = d[i - 1][j - 1] + cost;
    
          if (b < mi) mi = b;
          if (c < mi) mi = c;
    
          d[i][j] = mi; // Step 6
        }
      }
    
      // Step 7
      return d[n][m];
    }
    
    var window.CompareLD7 = function(s, t, lim) {
        var d = []; //2d matrix
        if(!lim) {
            lim == 10;
        }
    
        // Step 1
        var n = s.length;
        var m = t.length;
        var dl = n - m;
        dl = (dl > 0 ? dl : -dl)
        if (dl > lim) return Infinity;
        if (n == 0) return m;
        if (m == 0) return n;
    
        //Create an array of arrays in javascript (a descending loop is quicker)
        for (var i = n; i >= 0; i--) d[i] = [];
    
        // Step 2
        for (var i = n; i >= 0; i--) d[i][0] = i;
        for (var j = m; j >= 0; j--) d[0][j] = j;
    
        // Step 3
        for (var i = 1; i <= n; i++) {
            var s_i = s[i - 1];
    
            // Step 4
            for (var j = 1; j <= m; j++) {
    
                //Check the jagged ld total so far
                if (i == j && d[i][j] > 4) return n;
    
                var t_j = t[j - 1];
                var cost = (s_i == t_j) ? 0 : 1; // Step 5
    
                //Calculate the minimum
                var mi = d[i - 1][j] + 1;
                var b = d[i][j - 1] + 1;
                var c = d[i - 1][j - 1] + cost;
    
                if (b < mi) mi = b;
                if (c < mi) mi = c;
    
                d[i][j] = mi; // Step 6
    
                //Damerau transposition
                if (i > 1 && j > 1 && s_i == t[j - 2] && s[i - 2] == t_j) {
                    var q = d[i][j];
                    var r = d[i - 2][j - 2] + cost;
                    d[i][j] = q < r ? q : r;
                }
            }
            if(d[n][m] > lim) return Infinity;
        }
    
        // Step 7
        return d[n][m];
    }

Test runner

Ready to run.

Testing in
TestOps/sec
Original implementation
CompareLD1(randomScreenName(), randomScreenName());
ready
Westgate's implementation
CompareLD2(randomScreenName(), randomScreenName());
ready
Stoianovici's implementation (no limit)
CompareLD3(randomScreenName(), randomScreenName());
ready
Stoianovici's implementation (limit of 10)
CompareLD3(randomScreenName(), randomScreenName(), 10);
ready
Stoianovici's implementation (limit of 5)
CompareLD3(randomScreenName(), randomScreenName(), 5);
ready
Westgate's implementation (sans Damerau)
CompareLD6(randomScreenName(), randomScreenName(), 5);
ready
Westgate's Implementation + optimization
CompareLD7(randomScreenName(), randomScreenName(), 5);
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.