unicode - Programatic Accent Reduction in JavaScript (aka text normalization or unaccenting)

Question

I need to compare 2 strings as equal such as these:

Lubeck == Lübeck

In JavaScript.

Why? Well, I have an auto-completion field that's going out to a Java service using Lucene, where place names are stored naturally (as Lübeck), but also indexed as normalized text,

import sun.text.Normalizer;
oDoc.setNameLC = Normalizer.normalize(oLocName, Normalizer.DECOMP, 0)
    .toLowerCase().replaceAll("[^\p{ASCII}]","");

This way some-one who doesn't know to type "Mèxico" can type "mexico" and get a match which returns "Mèxico" (among a lot of other possible hits, like "Café Mèxico, Dubai, UAE").

Now the thing is I don't have the ability to change the service to do any highlighting on the server side, therefore I am highlighting on the client JavaScript side with something like:

return result.replace( input.replace(/[aeiou]/g,"."), "<b>$1</b>");

It's a little more fancy because I am escaping special regex characters in the input. This is fine for simple one word matches at the beginning of a hit, but it really breaks down if you suddenly wish to support multi-word matches like "london cafe":

input = input.strip().toLowerCase(); //fyi prototype's strip is like trim
re = new RegEx(input.replace(/[aeiou]/g,".").replace(/s+/g,"|"),"gi");
return result.replace(re, "<b>$1</b>");

This doesn't work for say "london ca" (was typing london cafe), because it would mark "Jack London Cabin, Dawson City, Canada" as: "Ja<b>ck</b> <b>London</b> <b>ca</b>bin, Dawson <b>Ci</b>ty, <b>Ca<b/>nada" [note the "ck" and "Ci" particularly]

Therefore I'm sort of looking for something that's not as crazy as:

input = input.strip().toLowerCase();
input = input.replace(/a/g,"[ààáá?a????????āā????]");
input = input.replace(/e/g,"[èèééêê??ēē??????ěě]");
// ditto for i, o, u, y, c, n, maybe also d, g, h, j, k, l, r, s, t, w, z 
re = new RegEx(input.replace(/s+/g,"|"),"gi");
return result.replace(re, "<b>$1</b>");

Is there a compiled table I can refer to mapping a range of characters which are accented versions of an other character to that character, by which I don't mean the plain unicode chart. And if so, could I avoid using weird, possibly slow, RegEx statements?

About the bounty:
Before I started a bounty there were two answers, the one pointing me to doing it in Ruby, and the one that MizzardX wrote which was a completion of the basic form I'd put in my question. Now don't get me wrong, I really appreciate working it out as completely as he did, but I just wished that there might be another way. It seems so far that everyone who's dropped by to look at the question and answer has decided that MizzardX covers it just fine, or that they have no different approach. I would be interested in a different approach, and if it simply isn't available before the bounty closes, MizzardX will win the bounty (though in a cruel twist, his edits mad it a community wiki answer, so I'm not sure if he'll get the bounty!)

Answer 1

/**
 * Creates a RegExp that matches the words in the search string.
 * Case and accent insensitive.
 */
function make_pattern(search_string) {
    // escape meta characters
    search_string = search_string.replace(/([|()[{.+*?^$\])/g,"\$1");

    // split into words
    var words = search_string.split(/s+/);

    // sort by length
    var length_comp = function (a,b) {
        return b.length - a.length;
    };
    words.sort(length_comp);

    // replace characters by their compositors
    var accent_replacer = function(chr) {
        return accented[chr.toUpperCase()] || chr;
    }
    for (var i = 0; i < words.length; i++) {
        words[i] = words[i].replace(/S/g,accent_replacer);
    }

    // join as alternatives
    var regexp = words.join("|");
    return new RegExp(regexp,'g');
}

var accented = {
    'A': '[Aaxaaxc0-xc5xe0-xe5u0100-u0105u01cdu01ceu0200-u0203u0226u0227u1d2cu1d43u1e00u1e01u1e9au1ea0-u1ea3u2090u2100u2101u213bu249cu24b6u24d0u3371-u3374u3380-u3384u3388u3389u33a9-u33afu33c2u33cau33dfu33ffuff21uff41]',
    'B': '[Bbu1d2eu1d47u1e02-u1e07u212cu249du24b7u24d1u3374u3385-u3387u33c3u33c8u33d4u33dduff22uff42]',
    'C': '[Ccxc7xe7u0106-u010du1d9cu2100u2102u2103u2105u2106u212du216du217du249eu24b8u24d2u3376u3388u3389u339du33a0u33a4u33c4-u33c7uff23uff43]',
    'D': '[Ddu010eu010fu01c4-u01c6u01f1-u01f3u1d30u1d48u1e0a-u1e13u2145u2146u216eu217eu249fu24b9u24d3u32cfu3372u3377-u3379u3397u33ad-u33afu33c5u33c8uff24uff44]',
    'E': '[Eexc8-xcbxe8-xebu0112-u011bu0204-u0207u0228u0229u1d31u1d49u1e18-u1e1bu1eb8-u1ebdu2091u2121u212fu2130u2147u24a0u24bau24d4u3250u32cdu32ceuff25uff45]',
    'F': '[Ffu1da0u1e1eu1e1fu2109u2131u213bu24a1u24bbu24d5u338a-u338cu3399ufb00-ufb04uff26uff46]',
    'G': '[Ggu011c-u0123u01e6u01e7u01f4u01f5u1d33u1d4du1e20u1e21u210au24a2u24bcu24d6u32ccu32cdu3387u338d-u338fu3393u33acu33c6u33c9u33d2u33ffuff27uff47]',
    'H': '[Hhu0124u0125u021eu021fu02b0u1d34u1e22-u1e2bu1e96u210b-u210eu24a3u24bdu24d7u32ccu3371u3390-u3394u33cau33cbu33d7uff28uff48]',
    'I': '[Iixcc-xcfxec-xefu0128-u0130u0132u0133u01cfu01d0u0208-u020bu1d35u1d62u1e2cu1e2du1ec8-u1ecbu2071u2110u2111u2139u2148u2160-u2163u2165-u2168u216au216bu2170-u2173u2175-u2178u217au217bu24a4u24beu24d8u337au33ccu33d5ufb01ufb03uff29uff49]',
    'J': '[Jju0132-u0135u01c7-u01ccu01f0u02b2u1d36u2149u24a5u24bfu24d9u2c7cuff2auff4a]',
    'K': '[Kku0136u0137u01e8u01e9u1d37u1d4fu1e30-u1e35u212au24a6u24c0u24dau3384u3385u3389u338fu3391u3398u339eu33a2u33a6u33aau33b8u33beu33c0u33c6u33cd-u33cfuff2buff4b]',
    'L': '[Llu0139-u0140u01c7-u01c9u02e1u1d38u1e36u1e37u1e3a-u1e3du2112u2113u2121u216cu217cu24a7u24c1u24dbu32cfu3388u3389u33d0-u33d3u33d5u33d6u33ffufb02ufb04uff2cuff4c]',
    'M': '[Mmu1d39u1d50u1e3e-u1e43u2120u2122u2133u216fu217fu24a8u24c2u24dcu3377-u3379u3383u3386u338eu3392u3396u3399-u33a8u33abu33b3u33b7u33b9u33bdu33bfu33c1u33c2u33ceu33d0u33d4-u33d6u33d8u33d9u33deu33dfuff2duff4d]',
    'N': '[Nnxd1xf1u0143-u0149u01ca-u01ccu01f8u01f9u1d3au1e44-u1e4bu207fu2115u2116u24a9u24c3u24ddu3381u338bu339au33b1u33b5u33bbu33ccu33d1uff2euff4e]',
    'O': '[Ooxbaxd2-xd6xf2-xf6u014c-u0151u01a0u01a1u01d1u01d2u01eau01ebu020c-u020fu022eu022fu1d3cu1d52u1ecc-u1ecfu2092u2105u2116u2134u24aau24c4u24deu3375u33c7u33d2u33d6uff2fuff4f]',
    'P': '[Ppu1d3eu1d56u1e54-u1e57u2119u24abu24c5u24dfu3250u3371u3376u3380u338au33a9-u33acu33b0u33b4u33bau33cbu33d7-u33dauff30uff50]',
    'Q': '[Qqu211au24acu24c6u24e0u33c3uff31uff51]',
    'R': '[Rru0154-u0159u0210-u0213u02b3u1d3fu1d63u1e58-u1e5bu1e5eu1e5fu20a8u211b-u211du24adu24c7u24e1u32cdu3374u33ad-u33afu33dau33dbuff32uff52]',
    'S': '[Ssu015a-u0161u017fu0218u0219u02e2u1e60-u1e63u20a8u2101u2120u24aeu24c8u24e2u33a7u33a8u33ae-u33b3u33dbu33dcufb06uff33uff53]',
    'T': '[Ttu0162-u0165u021au021bu1d40u1d57u1e6a-u1e71u1e97u2121u2122u24afu24c9u24e3u3250u32cfu3394u33cfufb05ufb06uff34uff54]',
    'U': '[Uuxd9-xdcxf9-xfcu0168-u0173u01afu01b0u01d3u01d4u0214-u0217u1d41u1d58u1d64u1e72-u1e77u1ee4-u1ee7u2106u24b0u24cau24e4u3373u337auff35uff55]',
    'V': '[Vvu1d5bu1d65u1e7c-u1e7fu2163-u2167u2173-u2177u24b1u24cbu24e5u2c7du32ceu3375u33b4-u33b9u33dcu33deuff36uff56]',
    'W': '[Wwu0174u0175u02b7u1d42u1e80-u1e89u1e98u24b2u24ccu24e6u33ba-u33bfu33dduff37uff57]',
    'X': '[Xxu02e3u1e8a-u1e8du2093u213bu2168-u216bu2178-u217bu24b3u24cdu24e7u33d3uff38uff58]',
    'Y': '[Yyxddxfdxffu0176-u0178u0232u0233u02b8u1e8eu1e8fu1e99u1ef2-u1ef9u24b4u24ceu24e8u33c9uff39uff59]',
    'Z': '[Zzu0179-u017eu01f1-u01f3u1dbbu1e90-u1e95u2124u2128u24b5u24cfu24e9u3390-u3394uff3auff5a]'
};