Здесь мой готовый алгоритм (на PHP) по нечёткому поиску цепочек слов с произвольным началом и окончанием слов, включая автоматическое исправление похожего начертания символов на нужный язык.
Что ищем: протектор зимней шины
Где ищем: Одним из основных элементов реnpoтeктушкатоpатора зимних шин являются ламели.
Результат: Найдено с 5-го слова: [реnpoтeктушкатоpатора]
PS: Кстати, вот ещё похожее на Сфинкс:
stumper.ru (видимо недавно сделали)
Вариант 2: Вырезаете все суффиксы из поискового запроса через regex и проблема решена:
-щик, -льщик
-анин, -янин
-ница, -тель
-льник
-ница
-ость, -есть
-ота, -ета
-ецо, -ице
-изна
-ство
-отня, -овня
-ство, -ество
-ина, -инка
-ёнок, -онок
-очка, -ечка, -ичка
-енька, -онька
-ушка, -юшка
-ышко
-ишко, -ишка
-ёнка, -онка
-инка, -енка
-ище, -ища
-ушк-, -юшк-, -ышк-
-ёнка, -онка, -ёнок, -онок, -юнок, -унок
-енька, -онька, -анька