Создание списка всех длинных общих подстрок и список изменений

Question

высокого уровня

Я пытаюсь свернуть общие подстроки в списке предложений и представить только те области, которые они отличаются. Так что, это:

Please don't kick any of the cats 
Please do kick any of the cats 
Please don't kick any of the dogs 
Please do kick any of the dogs 
Please don't kick any of the garden snakes 
Please do pet any of the garden snakes 

И возвращение этого:

Please [don't|do] [kick|pet] any of the [cats|dogs|garden snakes] 

Подробнее

• Я смотрел на алгоритмах Серия общей подстроки, но это, кажется, только сравнить две строки.
• Меня интересует только целые слова в строчке.
• Только хотите оценить строки слева направо.
• Длина необычных подстрок не будет одинаковое количество слов («кошка» против «сад змеи»)

Я ищу помощи по алгоритму. Я считаю, что это вариант проблемы LCS, я думаю, что какая-то обработка дерева суффикса. Псевдокод, который может объяснить и реализовать, был бы идеальным.

Другой пример

Please join thirteen of your friends at the Midnight Bash this Friday 
Don't forget to join your friend John at the Midnight Bash tomorrow 
Don't forget to join your friends John and Julie at the Midnight Bash tonight 

превращается в:

[Please|Don't forget to] 
join 
[thirteen of your friends|your friend John|your friends John and Julie] 
at the Midnight Bash 
[this Friday|tomorrow|tonight] 

Может быть, этот подход

Что об этом подходе ...

for an array of sentences 
    loop with the remaining sentence 
    find the "first common substring (FCS)" 
    split the sentences on the FCS 
    every unique phrase before the FCS is part of the set of uncommon phrases 
    trim the sentence by the first uncommon phrase 
    end loop 

Answer 1

Интересно, что я думал о кре что-то вроде твоего долгого времени, пока я не понял, что на самом деле это своего рода ИИ. Слишком много факторов, которые необходимо учитывать: грамматика, синтаксис, ситуации, ошибки и т. Д. Но если ваш вход всегда настолько фиксирован, как «Please [A1 | A2 | ..]] [B1 | B2 | ..], любой из [C1 | C2 | ..] ", тогда может быть простой шаблон Regex:«^Please \ s * (? (Do not | do)) \ s * (? \ W +) + \ s * любой из \ s * (?). * $».

Answer 2

Сопоставьте каждое уникальное слово с одним объектом. Затем постройте условную таблицу вероятностей (см. Markov chains), чтобы подсчитать количество раз, сколько слов следует за каждой последовательностью.