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

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

Наприклад,

  1. Перетворення числівників у число«десять» -> 10:Int)
  2. і назад (10:Int -> «десять» («десятий», «десяток» ...))
  3. Перетворення числівників разом з одиницею виміру («десять рублів» <-> NumberWithMeasurement(10, RUB))
  4. Неповний адресу («вул. Яблучна» <-> Address(street=«Яблучна»))
  5. Адреса в межах міста («вулиця Яблучна будинок сто двадцять три квартира сорок п'ять» <-> Address(street=«Яблучна», building=123, flat=45))
  6. Телефон (256-00-21 («двісті п'ятдесят шість нуль нуль двадцять один») <-> 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 Failure class[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(лема:LemmaInfo, left:Option[LemmaInfo], right:Option[LemmaInfo]):WordFormAssociation

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

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

  • числівники,
  • адреси,
  • телефони,
  • різні буквено-числові коди,
  • час, дати, інтервали часу/дат,
  • і т.п.
За декларативним опису будується аналізатор і генератор, які здійснюють пряме перетворення тексту в семантики та семантики тексту на природній мові.

P.S. Код до статті

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.