Levensthein расстояние идет в правильном направлении, но только на полпути. Есть несколько приемов, чтобы заставить его использовать и половинные совпадения.
Можно было бы использовать динамическую деформацию времени подпоследовательности (DTW на самом деле является обобщением расстояния Левенштейна). Для этого вы ослабляете начальный и конечный случаи при расчете матрицы затрат. Если вы ослабите только одно из условий, вы можете получить автозаполнение с проверкой орфографии. Я не уверен, есть ли доступная реализация Python, но если вы хотите реализовать ее для себя, она не должна превышать 10-20 LOC.
Другой идеей было бы использовать Trie для ускорения, которое может одновременно выполнять DTW / Levensthein для нескольких результатов (огромное ускорение, если ваша база данных велика). В IEEE есть статья о Levensthein о попытках, поэтому вы можете найти там алгоритм. Опять же, для этого вам нужно ослабить конечное граничное условие, чтобы получить частичные совпадения. Однако, поскольку вы уходите в три, вам просто нужно проверить, когда вы полностью использовали вход, а затем вернуть все листья.