Алгоритм Soundex или Metaphone для опечаток в поисковом запросе

В нашем поиске нам нужно возвращать результаты, которые соответствуют искомому термину с максимальным расстоянием Левенштейна, равным 2. Проблема заключается в том, что нам нужно применять алгоритм расстояния Левенштейна для каждой строки в таблице, содержащей миллионы строк, и тогда запрос выполняется очень медленно.

SOUNDEX и Metaphone хороши тем, что создают хеш, который можно сохранить в базе данных и сравнить с искомой строкой. Но они основаны на фонетике, а не на опечатках. Они работают для некоторых случаев, но не для всех.

Мне известно, что, по-видимому, невозможно сгенерировать хеш-код Левенштейна и сохранить его, потому что мы не знаем критерий поиска.

Таким образом, вопрос заключается в том, существует ли какой-либо алгоритм, такой как SOUNDEX или Metaphone, который ориентирован на опечатку.

Мы используем базу данных MariaDB и PHP, поэтому реализация любого должна быть осуществима в PHP.