Поиск шаблона среди строк

1,00
р.
У меня есть огромное число строк, и я знаю, что они построены по ограниченному набору шаблонов, но мне неизвестно каких. Мне нужно вычислить эти шаблоны довольно быстро при очень большом наборе данных.
Например, такому набору шаблонов (неизвестному мне):
"Hello, my {0} is: {1}" "{0} has left our team." "{0} has joined the team {1}!"
Соответствует набор строк ниже, только которые есть у меня:
Hello, my name is: Slim Shady Mike has left our team. Mike has joined the team Liquid! Hello, my name is Nikole Nick has joined the team Spirit! Elizabeth has left our team.
Задача: найти шаблоны по подобным строкам. То есть, найти закономерности в тексте, которые позволяют придумать такие шаблоны автоматически. Строк может быть очень много.
Я пока придумал использовать что-то вроде редакционного расстояния с помощью N-грамм.
Но у этой штуки более широкая область применения, чем мне нужно, а время работы не менее важно, чем точность нахождения шаблонов.
Так как у меня есть слова, которые будут совпадать полностью и без ошибок, и мне кажется, что тут можно как-то повысить быстродействие за счёт этого.
Я подумал над составлением алфавита из слов, а не букв, чтобы поиск по предложениям шёл по словам.
UPD: На всякий случай уточню, что на момент компиляции нет ни шаблонов, ни самих строк. Строки подаются программе на вход, а шаблоны никто нам не даст.
UPD2: Нужно в реальном времени находить шаблоны в уже пройденных строках так, чтобы в последующих мы могли находить их соответствие.
(Комментарий) Предположим, у нас есть n предложений Мама наша мыла раму и m предложений Мама мыла мою раму. Это должен быть один шаблон Мама {0} мыла {1} раму или два шаблона: Мама {0} мыла раму, Мама мыла {0} раму? Таких примеров можно придумать крайне много. Для того, чтобы избегать таких неоднозначностей, нужно либо дательнее понять, что за задача перед Вами, либо же, нужно Вам указать конкретный смысл, чтобы можно было найти единственное решение.
Шаблон должен быть как можно более общим из возможных, т.е. Мама {0} мыла {1} раму. Но именно для похожих строк. А не один шаблон {0}
(Комментарий) Возникает вопрос, почему не использовать шаблон {0}? Он -- максимально общий. Кажется, проблема в том, что над множеством шаблонов нужно ввести какой-то порядок. В общем случае, этот порядок нелинеен. Его нужно как-то линеаризовать. Это кажется сложной задачей. Если Вы скажете, зачем эта задача Вам нужна, можно на эту тему подумать.
В этом и заключается вся задача :D Мне нужно находить шаблоны этих строк, так чтобы в шаблоны объединялись сильно схожие строки, можно, например, взять что-то вроде процента схожести в виде критения.
UPD3: Шаблон должен объединить похожие строки. Похожими строками будем считать строки, которые совпадают на N%.

Ответ
Если количество шаблонов ограничено, и они довольно равномерно распределены в данных, то смысла в очень большом наборе данных нет. Вы можете добыть шаблоны и из набора данных поменьше.
Решение "в лоб" представляется таким:
Можно придумать некоторую функцию получающую слова из строк (например просто разбить по пробелам и вырезать знаки препинания).
Затем, составить частотный словарь. Например слово 'Hello' встречается дважды в наборе из примера. Кроме того, можно ещё посчитать количество вхождений слова в определённой позиции, чтобы смотреть потом не просто частоту слова, а частоту слова где-то в районе 3-5 позиции, например.
Теперь для любого слова можно сделать предположение о том, является оно частью шаблона или нет. Если слово достаточно часто встречается где-то в районе текущей позиции, то скорее всего оно часть шаблона.
Для каждой строки из набора данных строим шаблон и оставляем только уникальные значения.
В этом случае данные придётся обработать дважды (первый раз строя частотный словарь, второй -- шаблоны), потому что нам сперва нужна информация о том, что из себя представляет весь набор.
Нейронка может помочь подобрать пороговые значения и получить лучшие результаты.