Я обычно довольно хорошо разбираюсь в алгоритмах, но здесь у меня есть довольно абстрактный вопрос, который, возможно, является чьим-то PhD-проектом и граничит с полнотой NP. Но, возможно, это более распространенная проблема, чем я думаю.
У меня есть список из 25000 строк, созданный с использованием нескольких раскрывающихся списков и текстовых полей. Итак, чтобы упростить обсуждение, допустим, что это однонаправленный граф:
{Мой кот / Моя собака} имел {котята, щенки} .
Итак, это похоже на древовидную структуру, 4 пути которой представляют 4 возможных предложения.
Как можно было бы реконструировать древовидную структуру из (возможно, неполного) списка предложений?
т.е.
Так что с
у моего кота были котята
У моего кота были щенки
У моей собаки были котята ,
Вы все еще можете воссоздать исходное синтаксическое дерево.
Очевидно, что с 25000 строк это займет некоторое время. Но есть ли какое-нибудь программное обеспечение, которое делает это? Или это достаточно распространенная проблема, что для этого существуют известные алгоритмы?
В природе это похоже на анализатор регулярных выражений, но я не знаю, с чего начать. Я имею дело с этой проблемой на работе, и делаю свой собственный анализ предложений, чтобы разобрать еще 500 или около того, каждый раз, когда я нахожу новый шаблон. Но я считаю, что если бы у меня была древовидная структура, я мог бы сделать это порубить отбивную.
Есть идеи?
Спасибо