Фильтр блума пробуйте
исходные сортируйте и 2-3-4 словным наборам и каждый набор - в фильтр,
входящий - нарезайте по 4-3-2 и прогоняйте через фильтры
думаю, все же проше будет по-быстрому всунуть приходящий текст в RT индекс сфинкс и по всем фразам
php.net/manual/en/sphinxclient.setmatchmode.php SPH_MATCH_PHRASE
