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

Высокий уровень

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

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

c# algorithm longest-substring set-theory
person theChrisMarsh    schedule 24.01.2014    source источник
comment
... что именно вы спрашиваете?   -  person JNYRanger    schedule 24.01.2014
comment
Отредактировано, чтобы было более понятно, о чем я прошу... помогите с алгоритмом.   -  person theChrisMarsh    schedule 24.01.2014

Ответы (2)


arrow_upward
0
arrow_downward

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

person Superbest    schedule 24.01.2014

arrow_upward
-1
arrow_downward

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

person Johnny    schedule 24.01.2014