Maybe you could build a (sorted) tree and do the search "manually", ie without regexes?

Even if you only build one file for each possible first character you gain a factor of 26 (if you reduce it to latin alphabet).