алгоритм поиска общего шаблона для двух заданных текстов

[lexand]

заранее извиняюсь за терминологию, могу сильно ошибаться, или запутать

изначально задача звучит так
к слову задача по работе, а не из праздного интереса, это что бы сразу отсеять лишние вопросы

на вход последовательно поступает куча текстов, с высокой вероятностью все эти тексты созданы на основании каких-то шаблонов (одного и более)

к примеру
"Петрович, забери ЗП, 900 тугриков"
"Ольга Петровна, забери ЗП, 1500 тугриков"
что отвечает шаблону
"{name}, забери ЗП, {amount} тугриков"

1. Шаблон нужно определить
2. Тексты группируются вместе по соответсвию определенному шаблону.

первое что пришло в голову это представить тексты (и шаблон) в виде слов состоящих из символов отдельного алфавита (сжать тексты)
и свести задачу к нахождению одинаковых подстрок в только двух строках

допустим

каждый токен (слово, разделитель, пробел/группа пробелов) входного текста - заменяется отдельным символом
заранее резирвируются символы 0 - окончание строки (для дерева), n>0 - номер заменителя (placeholder)

"Петрович, забери ЗП, 900 тугриков" == abcdcebcfcg0
"Ольга Петровна, забери ЗП, 1500 тугриков" == hcibcdcebcjcg0
что отвечает шаблону
"{name}, забери ЗП, {amount} тугриков" == 1bcdcebc2cg0

txt1. __abcdcebcfcg0
txt2. hcibcdcebcjcg0
tpl . __1bcdcebc2cg0

теперь задача сводится к нахождению всех одинаковых подстрок в двух текстах
далее имея на руках координаты повторяющих последовательностей, можем заменить все что между ними на заменители и получаем искомый шаблон

и вот тут я вообще почти ноль
думаю за осонову взять поиск longest common substring основанный на суффиксных деревьях, только искать не максимальную последовательность, а все.
еще как вариант использовать суффиксный массив, хотя я вообще не понял как с ним подойти для решения этой задачи

после решения этой задачи надо вернуться к изначальной
1. приходит текст используя алфавит, сжимаем текст до одного слова, если нужно расширяем алфавит
2. проводим поиск
2.1. на максимальное соответствие слова - группе (группа уже создана и представлена шаблоном)
2.2. на максимальное соответствие слова - текстам которые еще не попали в группу
3. сравнивая результаты 2.1 и 2.2
3.1 если максимальное совпадение пошло по группе, добавляем текст в группу
3.2 если пошло по тексту, восстанавливаем шаблон, создаем группу, добавляем тексты в группу

вообщем нужна помощь
0. а я вообще на правильном пути ?
1. по суффиксному дереву/массиву с поиском всех повторябщихся последовательностей, лучше конечно дать ссылки на разжованные примеры
2. предвижу ложные срабатывания - не представляю как с ними бороться.
4. как в числовой форме выразить "максимальное соответвие"? для того что бы сравнивать результаты
5. существует ли что-то наподобии поиска максимально похожей строки, возможно (скажем, можно пропустить определение шаблона если это значительно сократит кол-во операций) существует алгоритм такого поиска без лишних извращений. Я бы конечно обратил внимание на растояние Хемминга, но оно задается для строк одинаковой длинны (покрайней мере я не слышал что его можно задать для строк разной длинны, да оно вроде и смысла не имеет). В принципе после сжатия и нахождения шаблона я могу получить строки одинаковой длинный как для Петровича так и для Ольги Петровны... но в таком случае какой смысл в Хемминге....
6. возможно использовать нечеткий поиск, после сжатия, но он тоже основан на деревьях...хм...

написал все, а теперь думаю, а может ну его...

заранее спасибо

[lexand]

вот еще размышления на тему

можно попробовать использовать расстояние Левенштайна как меру схожести строк
или что-то типа http://www.php.net/manual/ru/function.similar-text.php ,вот только самого алгоритма найти не могу

но...пришла мысль в голову
ведь определяя шаблон для группы мы получаем как бы опорную строку с которй потом будут сравниваться входящие сжатые тексты
без шаблона, придется сравнивать с какимто случайным, скорее всего первым попавшимся текстом, для которого была создана новая группа (учитывая конечно что текст не подошел к другим группам)

[lexand]

верно, по шаблону, при условии правильного его использования
тоесть без учета символов представляющих собой заменители, точность этого самого соответствия была бы выше точности прамого сравнения между текстами

[_Ivana]

1. Задача проверки текста на соответствие имеющемуся шаблону решается в три строчки кода.
2 . Задача угадывания общего шаблона двух текстов чуть более творческая, например по вашим данным я могу угадать шаблон
"Петрович, забери ЗП, 900 тугриков"
"Ольга Петровна, забери ЗП, 1500 тугриков"
что отвечает шаблону
"{first_name}Петров{second_name_suffix}, забери ЗП, {amount_hundreds}00 тугриков"

[lexand]

2. Согласен. Но нет. Так тексты почти никогда не генерируют.
Тогда доп.условие слова языка в исходном тексте не должны разбиваться на составные части. Или по другому: заменитель всегда меняется на законченное слово или группу слов.

[bin]

Так, как задача сформулирована, единственного решения может и не быть. Нпр.,

lexand в сообщении #854646 писал(а):

"Петрович, забери ЗП, 900 тугриков"
"Ольга Петровна, забери ЗП, 1500 тугриков"
что отвечает шаблону
"{name}, забери ЗП, {amount} тугриков"

Но
"Петрович, забери ЗП, 900 тугриков"
"Петрович, отчитайся о командировочных, 1900 тугриков"
отвечает шаблону
"Петрович, {action}, {amount} тугриков
ИМХО алгоритм может быть таким:
1) Составить словарь. Для этого из всех текстов выделить все встречающиеся в них слова, отсортировать в алфавитном порядке, подсчитывая, сколько раз встречается каждое слово (убирая дубликаты).
2) Убрать из словаря служебные слова (предлоги, союзы и т.д.).
3) Убрать из словаря редкие слова. Для этого задать порог. Можно исходить из желаемого размера словаря. А можно убирать слова, которые встречаются только один раз, но тогда словарь может получиться слишком большим.
5) Сгруппировать оставшиеся в словаре слова по смыслу (вручную). Убрать группы из одного слова. Остальным группам дать название: {name}, {amount} и т.д.
6) Заменить в исходных текстах слова словаря на названия групп. Получим список возможных шаблонов.
7) Отсортировать полученный список по именам групп, исключая дубликаты. Получам список шаблонов. При этом можно учитывать, сколько раз применяется каждый шаблон, для исключения редких шаблонов...

Похожий алгоритм я применял в программе для составления предметных указателей книг. (Там еще запоминались номера страниц). В случае русского языка может понадобиться усложнение для падежных окончаний, но принцип останется. Еще один не сильно усложняющий момент - цифры.

[lexand]

текстов сразу нет, они есть потом, но их нет сейчас ))
обрабытвать их нужно в потоке, статистику и прочие данные собирать в потоке, так сказать online.

я согласен что если рассматривать за большой промежуток времени то может получится что 100% будут попадать под шаблон
{someText1}он{someText2}открыл{someText3}

но тут есть определенное временной окно за который мы можем собрать статистику и считать, что она правильная/валидная
и в период этого окна, с очень малой вероятностью (какой не скажу, просто визуальная оценка)
могут идти тексты типа
"Петрович, забери ЗП, 900 тугриков"
"Петрович, отчитайся о командировочных, 1900 тугриков"

более обычно при таких рассылках используются (для примеров выше) два разных шаблона
в котором, по примерам, бухгалтер выбирает нужный и производит рассылку выбранным получателям.

но даже при всех этих ограничениях все равно возможны ложные срабатывания
и имхо не реально будет их побороть

НО, все это лирика, проза оказалась немного сложнее
первый камень о который я реально споткнулся уже, это даже на поиск похожих подстрок
а банальное разбиение текста на токены для сжатия... оказалось не тривиальным, быстро парсить заменители со спец информацией: почтовые адреса, дата/время....
судя по всему придется либо делать автомат для парсинга сроки что медленно с учетом доступного языка, либо...

---
расстояние по Левентштайну отпало
на длинных текстах, гдето около >120 символов, его оценка уже не показательна, на тестовой выборке текстов, мешает в кучу очень много