Описание структурного парсера и планы
Восходящий структурный парсер, оценка "О большого"
По плану развитие нисходящего структурного парсера закончено, почти вся необходимая математика есть в коде. Остался нереализованным один пункт - "named entry extraction", учет "дискурса" и динамический словарь. Все это тесно завязано на идею с упрощенной пролог-машиной, то есть будет работать на исчислении предикатов. Но реализацию я отложил до окончания п.2. Само собой, добавление новых правил в грамматику будет продолжаться - там еще много что надо сделать. Например, разбор всяких новостных заголовков с обилием англоязычных названий и всевозможных представлений чисел, дат, масс и так далее.
В документации все, что касается собственно восходящего структурного парсера, на минимальном уровне отражено. Надо, конечно, поподробнее описать работу алгоритма на более сложном примере с конкретными правилами, а также описать механизм взвешивания графов и работы с базой фактов.
Возникла еще одна мысль - попробовать сделать грубую оценку O(?) сложности алгоритма.
Примерно так, как делает Кормен для алгоритмов сортировки. Восходящий парсер сам по себе - исключительно строгий в математическом плане рекурсивный процесс , поэтому вроде бы общий подход должен быть похож на получение оценки для сортировки слияниями. Но дальше возникают непонятности, как оценивать сложность для некоторых теоретико-множественных операций, которые неявным образом возникают при сопоставлении, поэтому задумку пришлось отложить. А вообще говоря, было бы идеально, если компилятор словаря после трансляции всех правил сам проводил оценку сложности и выдавал ее. Ну раз этот путь, с помощью бумажки и карандаша, не получается пройти, то надо попробовать другой вариант, чисто инженерный - сделать вероятностную оценку по экспериментальным данным. То есть вот допустим есть у нас эталонный корпус из 15 тысяч предложений разной длины. Они примерно покрывают некоторое подмножество синтаксических конструкций письменного русского языка. Можно прогнать их через парсер и получить гистограмму распределения времени разбора в зависимости от числа слов. А потом по ней прикинуть асимптотику, хотя бы даже элементарной аппроксимацией полиномом и набором неких "типичных" функций - n*log(n) и так далее. Выбираем лучшее приближение и выдаем его. Для аппроксимирующего полинома смотрим самый старший член с кожффициентов больше заданного порога, отбрасываем все младшие члены. И вот она экспериментальная средняя (даже наверное среднестатистическая) оценка "о большое".
Итерационный алгоритм и приблизительный разбор
А вот эта часть будет самая горячая. Если нисходящий парсер отлично подходит для разбора коротких предложений, то этот алгоритм должен работать с произвольно длинными предложениями-бегемотами. Конечно, обеспечить 100% связывание не всегда удасться, поэтому я сразу снял это требование. Главная идея - пусть парсер выделяет в предложении некоторое синтаксическое ядро (набор ядер для сложных предложений или если имеется какой-то автономный клоз), а затем итерациями детализирует свою догадку, привязывая второстепенные фрагменты.
Для опробования сделал программку-эскиз на C#. Заодно попробовал реализовать одну идею - обучение по образцам. То есть на вход парсера сначала дается последовательность слов, словосочетаний и предложений с таким расчетом, чтобы примеры шли от простых к сложным и показывали обычное употребление слов. Парсер анализирует эти примеры, по возможности выполняется эмпирическую индукцию для обобщения. В итоге получается грамматика всего с двумя базовыми концепциями - есть наборы похожих слов, и есть образцы разбора. Никакой морфологии, вводимых вручную абстрактных концепций типа переходности глаголов или правил согоасования. Интересный бонус - можно разбирать текст, зашумленный лишними пробелами, со слипшимися словами и прочими ошибками. И это без дополнительных сложных механизмов, только сопоставление с имеющимися образцами разбора и использование списков похожести слов.
Отсюда и планирую стартовать. Некоторые вещи пока не буду трогать - так как морфлогия у нас все равно есть, то отказываться от нее как-то не с руки. Возможностью разбора сильно зашумленного текста пока пожертвует. А вот идею с заданием образцов употребления слов, на основании которых парсер может искать в предложении "знаковые слова", можно реализовать с минимальными доработками. Даже не так. Сейчас уже сделана часть нужного кода - есть "sparse" режим разбора, но в нем надо добавить эффективную работу с образцами. Образцов должно быть очень много, поэтому образцы и правила нужно подгружать из базы только по необходимости.
По плану развитие нисходящего структурного парсера закончено, почти вся необходимая математика есть в коде. Остался нереализованным один пункт - "named entry extraction", учет "дискурса" и динамический словарь. Все это тесно завязано на идею с упрощенной пролог-машиной, то есть будет работать на исчислении предикатов. Но реализацию я отложил до окончания п.2. Само собой, добавление новых правил в грамматику будет продолжаться - там еще много что надо сделать. Например, разбор всяких новостных заголовков с обилием англоязычных названий и всевозможных представлений чисел, дат, масс и так далее.
В документации все, что касается собственно восходящего структурного парсера, на минимальном уровне отражено. Надо, конечно, поподробнее описать работу алгоритма на более сложном примере с конкретными правилами, а также описать механизм взвешивания графов и работы с базой фактов.
Возникла еще одна мысль - попробовать сделать грубую оценку O(?) сложности алгоритма.
Примерно так, как делает Кормен для алгоритмов сортировки. Восходящий парсер сам по себе - исключительно строгий в математическом плане рекурсивный процесс , поэтому вроде бы общий подход должен быть похож на получение оценки для сортировки слияниями. Но дальше возникают непонятности, как оценивать сложность для некоторых теоретико-множественных операций, которые неявным образом возникают при сопоставлении, поэтому задумку пришлось отложить. А вообще говоря, было бы идеально, если компилятор словаря после трансляции всех правил сам проводил оценку сложности и выдавал ее. Ну раз этот путь, с помощью бумажки и карандаша, не получается пройти, то надо попробовать другой вариант, чисто инженерный - сделать вероятностную оценку по экспериментальным данным. То есть вот допустим есть у нас эталонный корпус из 15 тысяч предложений разной длины. Они примерно покрывают некоторое подмножество синтаксических конструкций письменного русского языка. Можно прогнать их через парсер и получить гистограмму распределения времени разбора в зависимости от числа слов. А потом по ней прикинуть асимптотику, хотя бы даже элементарной аппроксимацией полиномом и набором неких "типичных" функций - n*log(n) и так далее. Выбираем лучшее приближение и выдаем его. Для аппроксимирующего полинома смотрим самый старший член с кожффициентов больше заданного порога, отбрасываем все младшие члены. И вот она экспериментальная средняя (даже наверное среднестатистическая) оценка "о большое".
Итерационный алгоритм и приблизительный разбор
А вот эта часть будет самая горячая. Если нисходящий парсер отлично подходит для разбора коротких предложений, то этот алгоритм должен работать с произвольно длинными предложениями-бегемотами. Конечно, обеспечить 100% связывание не всегда удасться, поэтому я сразу снял это требование. Главная идея - пусть парсер выделяет в предложении некоторое синтаксическое ядро (набор ядер для сложных предложений или если имеется какой-то автономный клоз), а затем итерациями детализирует свою догадку, привязывая второстепенные фрагменты.
Для опробования сделал программку-эскиз на C#. Заодно попробовал реализовать одну идею - обучение по образцам. То есть на вход парсера сначала дается последовательность слов, словосочетаний и предложений с таким расчетом, чтобы примеры шли от простых к сложным и показывали обычное употребление слов. Парсер анализирует эти примеры, по возможности выполняется эмпирическую индукцию для обобщения. В итоге получается грамматика всего с двумя базовыми концепциями - есть наборы похожих слов, и есть образцы разбора. Никакой морфологии, вводимых вручную абстрактных концепций типа переходности глаголов или правил согоасования. Интересный бонус - можно разбирать текст, зашумленный лишними пробелами, со слипшимися словами и прочими ошибками. И это без дополнительных сложных механизмов, только сопоставление с имеющимися образцами разбора и использование списков похожести слов.
Отсюда и планирую стартовать. Некоторые вещи пока не буду трогать - так как морфлогия у нас все равно есть, то отказываться от нее как-то не с руки. Возможностью разбора сильно зашумленного текста пока пожертвует. А вот идею с заданием образцов употребления слов, на основании которых парсер может искать в предложении "знаковые слова", можно реализовать с минимальными доработками. Даже не так. Сейчас уже сделана часть нужного кода - есть "sparse" режим разбора, но в нем надо добавить эффективную работу с образцами. Образцов должно быть очень много, поэтому образцы и правила нужно подгружать из базы только по необходимости.