Other possible "rough matching" filters to apply before the full matching routine:

- the first characters must match

- one of first two characters must match

- 2 out of the first three characters must match

Tests such as these can be hardcoded ar prefilters to allow the full matching routine to be invoked as rarely as possible. They are a compromise, but some of them may be acceptable compromises, if an impossible task becomes possible. Maybe you can plow through "the rest" in background as a long running low priority task, so you can evaluate the effect of the compromises. Or a sample of "the rest", at least.