Введение в формальный анализ естественных языков - Ляпунова А.А.
Скачать (прямая ссылка):
Рассмотрим в качестве простого примера код C1. Пусть Л = {0, 1}, a V = {vi, Ci4). Отображение 0 определим так:
0 (Ui)= 1,
0 (г)2) = 011,
0(?) = 010,
0 (и4) = 00.
Это отображение может быть представлено графом вида дерева, см. рис. 1 (о формальном описании графов вида дерева см. Berge1 1958). Узлы дерева соответствуют точкам выбора; путь вниз влево от узла соответствует выбору 1; путь вниз вправо — выбору 0. Каждое слово имеет единственную запись, соответствующую цепи (последовательности ребер) кодового
238
Н. Хомский, Дж. Миллер
дерева. Когда достигнут конец цепи и записано целое слово, система возвращается к вершине, готовая записать следующее слово.
Чтобы праиилыю декодиропать сообщение, необходимо, конечно, обеспечить синхроииня пит, Ta к, цепочка слои VtViV^VlV, лаиисмваеіся как 0010011; на если первая буква записи будет утрачена, то цепочка будет декодирована как у3у2. Чтобы показать, что первая буква в цепочке является началом сообщения, мы будем писать в начале цепочки символ tt. В противном случае ставится многоточие.
Рис. 1. Граф кодового дерева кода C1.
В каждой данной точке последовательности букв, записывающей некоторое допустимое сообщение, имеется фиксированное множество возможных продолжений. Различные начальные цепочки могут допускать в точности одни и те же продолжения. В коде Cl, например, два сообщения, которые начинаются с Д000... и Д10..., могут быть закончены цепочками ...ОД и ... IOtt, ... Iltf, или же этими цепочками плюс новое слово. Введем бинарное отношение R, которое имеет место между любыми двумя ..ачальными цепочками, допускающими одинаковое продолжение. Непосредственно видно, что R рефлексивно, симметрично и транзитивно; иначе говоря, У? есть отношение эквивалентности. Две начальные цепочки, которые допускают в точности одинаковые продолжения, будут в дальнейшем называться эквивалентными справа. В терминах этого отношения можно определить важное понятие состояния: мно*
Формальний анализ естественных языков
239
жество всех цепочек, эквивалентных справа, образует состояние кодирующей системы.
Состояние кодирующей системы — это ее память о том, что ,уже произошло. Каждый раз, когда к кодовой цепочке прибавляется одна буква, система может перейти в иовое состояние. У кода Ci имеется три состояния: I) S0, когда только что было записано полностью какое-то слово; 2) Si— после ДО... И 3) S2— после В01. Эти состояния соответствуют трем неконечным узлам дерева на рис. 1.
Следуя Шютценберже (Schutzenberger, 1956), мы можем записывать переходы из одного состояния в другое в виде матриц— такая матрица существует для каждой цепочки букв. Пусть строки соответствуют состоянию после п выданных букв, а столбцы — состоянию после п +1 буквы. Если переход возможен, в клетку ставится 1; в противном случае — 0. Для того чтобы задать код Cl, требуются две матрицы: одна показывает, каков результат добавления цифры 0, другая — результат добавления 1 (в общем случае это соответствует разделению кодового дерева на три подграфа, по одному на каждую букву из -4). Каждой цепочке букв х сопоставлена матрица Мх\ элементы этой матрицы rtiij определяют число возможных путей между состояниями Si и Sj при появлении цепочки х в закодированном сообщении. Для кода Ci матрицы, сопоставленные элементарным цепочкам 0 и 1, таковы:
'0 1 0" '1 0 0'
Ma = 1 0 0 , M1 = 0 0 1
л 0 0. -1 0 0.
Матрица для более длинной цепочки есть упорядоченное побуквенное произведение матриц. Произведение ЛЯ матриц А а Я интерпретируется следующим образом: из St система переходит В Sj в соответствии с переходом, допустимым в Л, затем она переходит из Sj в Ss в соответствии с переходом, допустимым в Я ¦ Число различных путей от Si через Sj к Sk есть dijbjk. Общее число путей ОТ Si K Ss, суммируя по всем промежуточным состояниям Sj1 есть т- е- обычное произ-
J
ведение матриц «строка на столбец», которое дает элементы матрицы ЛЯ. В том случае, если некоторая буква вообще не может появиться в данном состоянии, строка ее матрицы, соответствующая этому состоянию, будет состоять целиком из ну» лей. Цепочке в А, которая не является частью записи никакой цепочки слов из V, будет соответствовать нулевая матрица. В общем случае для этих матриц не обязательно должны
240
Н. Хомский, Дж. Миллер
существовать обратные. Матрицы не образуют группы-, но изоморфно отображаются на элементы полугруппы.
Если функция, отображающая цепочки в V на цепочки в Л, яе является имимимАштіичіюй, ти и мптрипих пли их прона-ведениях !юнішої мементм, большие единицы; это будет означат!», что одна и та же цепочка из п буки является кодовой записью для более чем одной цепочки слов. Когда такая ситуация имеет место, полученное сообщение неоднозначно и не может быть понято, даже если оно было передано без помех и искажений. В этом случае нет никакого способа узнать, какая из возможных цепочек слов имелась в виду.
Поскольку между словами в нормальном потоке речи нет никаких фонетических показателей границы, неоднозначность такого рода возникает в естественных языках довольно часто. Миллер (Miller, 1958) приводит следующий пример для английского языка:
