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

Известные ParserCombinator'ы и Parboiled предназначены исключительно для разбора формальных языков. Мы же решаем задачу разбора естественного языка и при этом хотим, чтобы с помощью той же грамматики можно было осуществлять синтез фраз на естественном языке, отражающих требуемую нам семантику. Было бы удобно иметь возможность описывать языковые конструкции вместе с правилами абстрагирования/конкретизации.

Например,

1. Преобразование числительных в число («десять» -> 10:Int)
2. и обратно (10:Int -> «десять» («десятый», «десяток» ...))
3. Преобразование числительных вместе с единицей измерения («десять рублей» <-> NumberWithMeasurement(10, RUB))
4. Неполный адрес («ул. Яблочная» <-> Address(street=«Яблочная»))
5. Адрес в пределах города («улица Яблочная дом сто двадцать три квартира сорок пять» <-> Address(street=«Яблочная», building=123, flat=45))
6. Телефон [phone] («двести пятьдесят шесть ноль ноль двадцать один») <-> NumericalSequence(256,0,0,21))

Причём хотелось бы иметь следующие системные свойства:

• единственность описания правил абстрагирования/конкретизации
• строго типизированное представление семантики на всех уровнях абстракции
• наличие альтернативных форм представления семантики и возможность повлиять на выбор формы представления семантики
• согласование словоформ для получения фразы на чистом русском языке
• возможность формирования вторичных структур на основе исходных правил. В частности, мы бы хотели формировать грамматики разбора, соответствующие правилам.

Под катом — описание подхода, реализованного в библиотеке synapse-typed-expressions. Рассмотрены только числительные, но подход естественным образом распространяется на другие вышеупомянутые формальные языковые конструкции.

Уровни абстракции

Одна и та же семантика (содержательная информация) представляется в разных формах на разных уровнях абстракции. Рассмотрим для примера, как может выглядеть число 1234 на разных уровнях абстракции:

1. 1234:Int — на уровне бизнес-логики приложения
2. Number(1234L)
3. TwoClassNumber(Number(1L), Order(1000), Number(234L)) — разбиение числа на два класса — тысяч и единиц
4. Seq(Number(1L), Order(1000), Number(234L)) — цепочка компонентов
5. Seq(Number(1L), Order(1000), TwoRangesNumber(Number(200L),100,Number(34L)))
6. Seq(Number(1L), Order(1000), TwoRangesNumber(Number(200L),100,TwoRangesNumber(Number(30L),10,Number(4L)))) — свели до структуры числительного
7. Seq(Word(1L), Word(1000L), Word(200L), Word(30L), Word(4L)) — цепочка идентификаторов слов
8. Seq(одна, тысяча, двести, тридцать, четыре) — цепочка слов после применения правил согласования словоформ
9. «одна тысяча двести тридцать четыре» — текст.

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

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

Следует заметить, что собственно содержание или семантика на всех уровнях остаётся неизменной. Меняется только форма представления семантики. При этом мы совершенно чётко определяем направление на оси абстрагирования/конкретизации.

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

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

Грамматические правила для числительных

Опишем правила конкретизации для различных диапазонов чисел:

"Число от 1 до 9"                    := ID1   или ID2   или ... ID9
"Число от 10 до 19"                  := ID10  или ID11  или ... ID19
"Число от 1 до 19"                   := ID1   или ID2   или ... ID19
"Десятки от 20 до 90"                := ID20  или ID30  или ... ID90
"Сотни от 100 до 900"                := ID100 или ID200 или ... ID900
"Число, представленное одним словом" := "Сотни от 100 до 900" или "Десятки от 20 до 90" или "Число от 1 до 19"

Вышеприведённые правила позволяют конкретизировать число из множества (1, 2,… 20, 30,… 100, 200,… 900) в виде одного идентификатора русского слова. Идентификаторы обозначены также числами, а форма слова пока не конкретизируется. Наши правила пока работают не для всех чисел. При попытке работы с неподходящим числом нас ждёт неуспех. Также наши правила не позволяют распознать больше одного слова.

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

"Число, представленное двумя словами" :=  ("Сотни от 100 до 900" затем "Десятки от 20 до 90") 
                                      или ("Сотни от 100 до 900" затем "Число от 1 до 19") 
                                      или ("Десятки от 20 до 90" затем "Число от 1 до 9")
"Число, представленное тремя словами" := "Сотни от 100 до 900" затем "Десятки от 20 до 90"  затем "Число от 1 до 9"

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

1. `[100..900/100]` будет обозначать числа из диапазона от 100 до 900 с шагом 100.
2. Вместо «или» мы будем использовать значок |, а вместо «затем» будем использовать значок ~.
3. Перед именем правила будем писать ключевое слово val, а само определение правила будем записывать после знака равенства.
4. Вместо ID20 будем использовать функциональную запись id(20)

Такой способ записи позволяет нам записать правила более компактно.

	val `[0]`            = id(0L)
	val `[1..9]`         =   (1L to 9).map(id)
	val `[0..9]`         =  `[1..9]` | `[0]`
	val `[1..19]`        =   (1L to 19).map(id)
	val `[10..19]`       =   (10L to 19).map(id)
	val `[20..90/10]`    =   (20L to 90 by 10).map(id)
	val `[100..900/100]` =   (100L to 900 by 100).map(id)
	val singleWordNumber =  `[100..900/100]` | `[20..90/10]` | `[1..19]`

Как представить числительные, составленные из двух слов? С синтаксической точки зрения такие числительные представлены двумя выражениями, связанными оператором следования ~. С точки зрения повышения уровня абстракции мы имеем два способа связи — сложение («двадцать» и «один» = 20+1 = 21) и умножение («пять» «тысяч» = 5*1000=5000). А при понижении уровня абстракции деление с остатком (21%10 = 1, 21-1=20) и просто деление (5000/1000 = 5). Будем представлять способ преобразования между уровнями абстракции дополнительным оператором ^^, который сообщает, что между уровнями присутствует указанное преобразование. Например, мы можем представить числительные, представляемые двумя словами в диапазоне от 20 до 99 таким образом:

	val `[20..99] без 20..90/10` = `[20..90/10]` ~ `[1..9]` ^^ ModSplit(10L)

В это выражение не попадают однословные числительные. Они отличаются тем, что вторая составляющая пары (единицы) пропущена, а с математической точки зрения представлена нулём. Грамматически такую ситуацию можно представить с помощью символа Epsilon, который сопоставляется с пустым потоком, а на верхнем уровне абстракции представляется константой. Будем обозначать такое явление с помощью специального значка |?:

	val `[20..99]` = `[20..90/10]` ~ (`[1..9]` |? 0L) ^^ ModSplit(10L)

Это выражение при разборе позволяет сопоставляется с любыми числительными в диапазоне от 20 до 99, а при синтезе позволяет получить пару чисел — десятки и единицы, или только десятки.

Чтобы представить диапазон от 1 до 99, мы можем объединить два выражения с помощью оператора |. Для обеспечения однозначного выбора в ходе конкретизации, добавим селектор LessThanSelector(20L), выбирающий правое выражение, в случае, если число меньше порога.

	val `[1..99]` = `[20..99]` | `[1..19]` selectBy LessThanSelector(20L)

Аналогичным образом представляются числа в диапазоне от 1 до 999.

	val `[100..999]` = `[100..900/100]` ~ (`[1..99]` |? 0L) ^^ ModSplit(100L)
	val `[1..999]`   = `[100..999]` | `[1..99]` selectBy LessThanSelector(100L) labelled "1..999"

Для представления чисел свыше тысячи, необходимо использовать преобразование OrderSplit(1000), которое при восходящем движении произведёт умножение количества тысяч на тысячу, а при нисходящем движении выполнит деление, тем самым осуществив разбиение числа на старший класс и остаток:

	val `[1 000..999 000/1000]` = `[1..999]` ~ `[1 000]` ^^ OrderSplit(1000L)
	val `[1 000..999 999]`      = `[1 000..999 000/1000]` ~ (`[1..999]` |? 0L) ^^ ModSplit(1000L)
	val `[1..999 999]`          = `[1 000..999 999]` | `[1..999]` selectBy LessThanSelector(1000L)

Выражение для чисел в произвольном диапазоне можно представить с помощью рекурсивной функции

  def range1To999Order(order:Long):NE = order match {
    case 1L => `[1..999]`
    case o if o>= 1000 =>
      val lower = range1To999Order(order/1000)
      val ordNE = order:NE
      val upper = `[1..999]` ~* ordNE
      ((upper ~+ lower) | upper selectBy OrderSplit(order)) | lower selectBy RangeSelector(order)
  }

в качестве order здесь указывается миллион, миллиард и т.д.

Описание правил связи между уровнями абстракций

Разные формы семантики могут быть представлены на языке программирования разными типами данных. Поэтому переход между уровнями абстракции необходимо снабдить двумя типами — типом более конкретной формы (L — Lower) и типом более абстрактной формы (U — Upper):

	sealed trait Expression[L, U]

Тип Expression описывает грамматику, соответствующую части входного потока L с одной стороны, и объекту U с другой стороны. Можно считать этот объект синтаксическим компонентом правил. Дальнейшее преобразование объекта к более высокому уровню абстракции осуществляется некоторой функцией, которая может быть представлена одним из потомков Transformer'а:

	sealed trait Transformer[M, U]

А в целом грамматическое выражение вместе с функциональным преобразованием также является выражением:

	case class Transformed[L, M, U](e: Expression[L, M], t: Transformer[M, U]) extends Expression[L, U]

Функция преобразования уже привносит некоторую семантическую интерпретацию сопоставившемуся выражению. Поэтому Transformer — это семантический компонент правил.

Конвертация форм с помощью одного из правил может оказаться неудачной. Поэтому функция конвертации должна иметь возможность сообщить о том, что правило не подошло. Для этих целей подходит один из вариантов паттерна Result/Option/Try/Either:

	sealed trait ParseResult[T]
	case class Success[T](value: T, tail:LemmaStream) extends ParseResult[T]
	case class Failure[T](reason: String) extends ParseResult[T]

Сами правила представляются с помощью набора Case-классов, которые конструируются вышеописанным DSL — Pair, BooleanAlternative, MapAlternative, ConstExpr

Представление словаря

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

Вообще говоря, для задачи согласования форм числительных необязательно описывать морфологическую форму слова с помощью стандартных грамматических категорий. Так как фактически используется только ограниченный набор комбинаций грамматических категорий, то можно вполне обойтись суррогатной грамматической категорией — «группа согласования». Таких групп оказывается всего 3: единица, от 2 до 4, и больше 4. Все числительные внутри «группы согласования» ведут себя одинаково с точки зрения выбора формы слова.
Однако, так как мы рассматриваем задачу несколько шире, чем преобразование числительных, и включаем формальные языковые конструкции типа адреса и телефона, то удобнее будет, всё-таки, придерживаться стандартной грамматической класификации.

Как грамматическую категорию, так и её значения («граммемы») мы представляем объектами, чтобы было удобно использовать их как ключ-значение.

	case object Gender extends GrammarCategory {
	  val default = Masculine
	  case object Masculine extends Grammem
	  case object Femini extends Grammem
	  case object Neuter extends Grammem
	}

Тип Grammem объявлен внутри GrammarCategory, что обеспечивает проверку совместимости типа граммемы с типом грамматической категории на этапе компиляции. В частности, если нам требуется граммема грамматического рода (например, средний Neuter), то мы можем объявить тип как Genger.Grammem. И, в то же время, мы можем использовать объект Gender как ключ в списке значений грамматических категорий.

Собственно словарь представляет собой коллекцию пар — (строковое представление слова, грамматическая характеристика). Словарь формируется с помощью небольшого DSL, позволяющего компактно записать все детали:

  lazy val allWordForms = {
    associate("три четыре пять шесть семь восемь девять",
      3L to 9, new WordFormDescription(Masculine, Cardinal, Nominative, Ones)) :::
      associate("ноль",
        List(0L), new WordFormDescription(Cardinal, Nominative, Ones)) :::
      associate("одна две",
        List(1, 2), new WordFormDescription(Femini, Cardinal, Nominative, Ones)) :::
      associate("один два",
        List(1, 2), new WordFormDescription(Masculine, Cardinal, Nominative, Ones)) :::
      associate("одно",
        List(1), simpleNumericalWordForm(Ones, Neuter)) :::
      associate("десять одиннадцать двенадцать тринадцать четырнадцать " +
        "пятнадцать шестнадцать семнадцать восемнадцать девятнадцать",
        10L to 19, simpleNumericalWordForm(Teens)) :::
   ...
      associate("нулевого первого второго третьего четвёртого пятого шестого седьмого восьмого девятого",
        0L to 9, new WordFormDescription(Masculine, Ordinal, Genetive, Ones)) :::
   ...
      associateOrder("миллион миллиона миллионов", 1000000L) :::
   ...
      associate("минус", List(-1L), WordFormDescription.empty)

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

На основе описанной грамматики можно либо непосредственно выполнять разбор с помощью какого-либо интерпретатора, либо сконструировать парсер путём конвертации исходной грамматики. Для разбора естественного текста, в котором допустимы ошибки, необходим вероятностный парсер, например, CKY.

1. Backtracking
   

   Участок текста в процессе разбора сопоставляется с шаблоном, заданным вышеприведёнными правилами. В случае, если правило возвращает Success, считаем, что сопоставление прошло успешно, и можно продолжать разбор дальше. Если правило не подошло, то мы выполняем backtracking для поиска альтернативных способов сопоставления. При использовании immutable структур данных шаг отсечения неудачного варианта и возврата к точке выбора альтернативного пути реализуется очень просто — достаточно проигнорировать результат и продолжать разбор. Данные не требуется корректировать к исходному состоянию.
   

   
   
2. CKY-парсер
   

   Для использования вероятностного CKY-парсера, необходимо вначале сконвертировать правила в грамматику в нормальной форме Хомского. Так как грамматика в этом случае будет представлять собой бинарное дерево, то можно систематически перебрать все возможные способы сопоставления этой грамматики с исходной цепочкой слов. При этом разным вариантам разбора будет присваиваться некоторая вероятность (что, в частности, сразу же позволяет выполнять разбор текстов с ошибками замены). В ходе такого преобразования полезным оказывается объединить эквивалентные с точки зрения алгоритма разбора терминалы в разновидность нетерминалов — preterminals.
   

   
   

Конструирование backtracking-парсера

Для целей настоящей статьи вполне достаточно backtracking-алгоритма («алгоритм отсечений и возврата»). Парсер представляет собой функцию, принимающую на вход поток лемм (LemmaStream), и, в случае успеха, возвращающую некоторое значение и хвост потока. Хвост может использоваться для дальнейшего разбора. В случае неудачи алгоритм «отсечений и возврата» отбросит этот парсер и будет пробовать альтернативный вариант. «Возврат», таким образом, осуществляется за счёт использования immutable структур и наличия хвоста потока лемм на каждом уровне.
Результат работы парсера можно представить типом ParseResult[T] с двумя потомками — Success и Failure.

Конвертация выражений в парсер осуществляется с помощью функции backTrackingParser:

  def backTrackingParser[U](e: Expression[LemmaStream, U]): Parser[U] = {
    implicit def uncheckedGenerics[T[_], O](t: T[_]): T[O] = t.asInstanceOf[T[O]]
    implicit def uncheckedGenerics2[T[_, _], O, P](t: T[_, _]): T[O, P] = t.asInstanceOf[T[O, P]]

    def backTrackingParser0(e: Expression[_, _]): Parser[_] = e match {
      case Epsilon(u) => s => Success(u, s)
      case ConstExpression(l: LemmaStream, u) => (s: LemmaStream) => startsWithAndTail(l, s).map(t => u)
      case Labelled(_, expr) => backTrackingParser0(expr)
      case Alternatives(expressions) =>
        val parsers = expressions.map(backTrackingParser0)
        (s: LemmaStream) =>
          parsers.
            map(parser => parser(s)).
            dropWhile(_.isFailure).
            headOption.getOrElse(Failure())
      case Pair(e1, e2) =>
        val parsers = List(e1, e2).map(backTrackingParser0)
        (s: LemmaStream) =>
          val res = parsers.foldLeft(Success[List[U]](Nil, s): ParseResult[List[U]])(_.next(_))
          res.map { lst => val list = lst.reverse; (list.head, list.tail.head).asInstanceOf[U]}
      case Transformed(innerExpression: Expression[_, _], t) =>
        val innerParser = backTrackingParser0(innerExpression)
        val converter = defaultSequencerHandler(t)
        (s: LemmaStream) =>
          innerParser(s).map(converter)
      case _ => throw new IllegalArgumentException(s"backTrackingParser0 is not implemented for expression $e")
    }
    uncheckedGenerics(backTrackingParser0(e))
  }

Возвращённый парсер принимает на вход поток лемм. Чтобы разбирать обычные строки, его надо преобразовать в парсер строк с помощью такого метода:

  implicit def toSimpleParser[T](p:Parser[T]):SimpleParser[T] = (text:String) => {
    val res = p(text.split(" ").map(wordToLemma))
    if(res.tail.nonEmpty)
      throw new IllegalArgumentException(s"Cannot parse \"$text\"")
    res.value
  }

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

	assert(parse("двадцать семь миллионов три тысячи двести сорок пять") === 27003245L)

Конструирование генератора текста

Для порождения текста с использованием тех же правил необходимо преобразовать правила в генератор текста. Мы опять-таки генерируем не конечный текст, а поток лемм, а затем уже по этому потоку подбираем подходящие слова с учётом правил выбора морфологической формы слова (согласование, управление).

Генератор представляет собой функцию, преобразующую значение какого-либо типа U в цепочку лемм. Конвертация разбирающих выражений в генератор осуществляется с помощью pattern matching:

  def constructGenerator[U](tGen: TransformerGenerator[U], selGen: BooleanSelectorGenerator[U])(e: Expression[LemmaStream, U]): Generator[U] = {
    implicit def uncheckedGenerics[T[_], O](t: T[_]): T[O] = t.asInstanceOf[T[O]]
    implicit def uncheckedGenerics2[T[_, _], O, P](t: T[_, _]): T[O, P] = t.asInstanceOf[T[O, P]]
    def constructGenerator0(e: Expression[_, _]): Generator[Any] = e match {
      case ConstExpression(l: LemmaStream, u) => (t) => l
      case Labelled(_, e1) => constructGenerator0(e1)
      case Epsilon(_) => (t) => Iterable()
      case Pair(e1, e2) =>
        val g1 = constructGenerator0(e1)
        val g2 = constructGenerator0(e2)
        (u:(_, _)) => g1(u._1) ++ g2(u._2)
      case BooleanAlternative(sel: SemanticSelector[U], e1, e2) =>
        val selector = selGen(sel).asInstanceOf[Any => Boolean]
        val g1 = constructGenerator0(e1)
        val g2 = constructGenerator0(e2)
        (u) =>
          if (selector(u))
            g2(u)
          else
            g1(u)
      case MapAlternative(lst) =>
        val map = lst.map(c => (c.upper, c.lower)).toMap: Map[Any, LemmaStream]
        (u) =>
          map.getOrElse(u, throw new IllegalArgumentException(s"Cannot generate text for $u by $e"))
      case Transformed(innerExpression, t) =>
        val innerGen = constructGenerator0(innerExpression)
        val transformer = tGen(t)
        (u: U) => innerGen(transformer(u))
      case _ => throw new IllegalArgumentException(s"constructGenerator is not implemented for expression $e")
    }
    constructGenerator0(e)
  }

Выбор формы слова

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

	def betterForm(lemma:LemmaInfo, left:Option[LemmaInfo], right:Option[LemmaInfo]):WordFormAssociation

Сами правила задаются с помощью pattern-matching'а над тройкой — текущая лемма, контекст слева, контекст справа.

Заключение

Декларативное представление грамматики позволяет описывать формальные языковые конструкции, такие как

• числительные,
• адреса,
• телефоны,
• различные буквенно-числовые коды,
• время, даты, интервалы времени/дат,
• и т.п.

По декларативному описанию строится парсер и генератор, которые осуществляют прямое преобразование текста в семантику и семантики в текст на естественном языке.

P.S. Код к статье