Регулярное выражение - это частный случай конечного автомата. Перед вами по сути стоит задача объединения всех выражений в один автомат, где начальным будет epsilon-состояние, т.е. в недетерминированный конечный автомат. Из него потом надо построить детерминированный КА с терминальными состояниями с соответствующими значениями из словоря. В общем, довольно непростое решение, но будет быстрее линейного перебора.
Как вариант, можно объединить все ключи словаря в одно регулярное выражение по принципу "(a1)|(a2)|...|(aN)", и затем определить, какая из групп окажется не пустой после матчинга. Это, по сути, то же самое, что я написал вначале, только гораздо проще.
