Levenshtein on Firefox tags!

gistfile1.js

 function levenshtein(s1, s2) {
        var i, j, cost, v0, v1, v_tmp, a, b, c,
            L1 = s1.length,
            L2 = s2.length;

        if (L1 === 0) {
            return L2;
        } else if (L2 === 0) {
            return L1;
        } else if (s1 === s2) {
            return 0;
        }
        v0 = new Array(L1 + 1);
        v1 = new Array(L1 + 1);
        for (i = 0; i < L1 + 1; i++) {
            v0[i] = i;
        }
        for (j = 1; j <= L2; j++) {
            v1[0] = j;
            for (i = 0; i < L1; i++) {
                cost = (s1[i] === s2[j - 1]) ? 0 : 1;
                a = v0[i + 1] + 1;
                b = v1[i] + 1;
                c = v0[i] + cost;
                v1[i + 1] = a < b ? a < c ? a : c : b < c ? b : c;
            }
            v_tmp = v0;
            v0 = v1;
            v1 = v_tmp;
        }
        return v0[L1];
    };

var historyService = Components.classes["@mozilla.org/browser/nav-history-service;1"]
                               .getService(Components.interfaces.nsINavHistoryService);
var options = historyService.getNewQueryOptions();
options.resultType = Components.interfaces.nsINavHistoryQueryOptions.RESULTS_AS_TAG_QUERY;

var query = historyService.getNewQuery();

var result = historyService.executeQuery(query, options);
var container = result.root;
container.containerOpen = true;

var list = [];
for (var i = 0; i < container.childCount; i++) {
    var node = container.getChild(i);
    list.push(node.title);
}
list.sort(function (a, b) {
    return a.localeCompare(b);
});
container.containerOpen = false;

var levs = [];
for (var m = 0; m < list.length; m++) {
    for (var n = m + 1; n < list.length; n++) {
        var dist = levenshtein(list[m],list[n]);
        if (dist > 0) {
            if (!levs[dist]) {
                levs[dist] = [];
            }
            levs[dist].push(list[m] + " | " + list[n]);
        }
    }
}

alert(levs[1].join("\n"));