Введение в формальный анализ естественных языков - Ляпунова А.А.
Скачать (прямая ссылка):
The good candy came anyway,
The good can decay many ways
.(«Хорошая конфета все-таки появилась», «Хорошее может испортиться многими способами»), В этих примерах цепочку фо-иетических элементов можно прочесть нейтрально, так что для слушателя возникает эффект, который можно сравнить с визуальным явлением обратной перспективы. Неоднозначная сегментация гораздо более обычна во французском языке; так, следующий куплет хорошо известен как случай полной рифмы:
Qal1 amant de la Reine, alia (tour magnartime),
Qalamment de Гагёпе a la Tour Magne1 a Nimes
[«Галь, любовник королевы, уехал (великодушный жест!) галантно с арены в башню Мань, в Ниме»),
Рассмотрение примеров такого рода показывает, что производство и восприятие речи есть нечто гораздо большее, чем про* изводство и идентификация последовательных фонетических свойств, и что на разных уровнях организации происходят различные процессы переработки информации. Эти проблемы более подробно рассматриваются в применении к естественным языкам в разд. 6.
Разумеется, трудности сегментации могут быть устранены. Изучение способов их устранения приводит к простой Maccnj фикации кодов (Шютценберже, в частной беседе). Общими .кодами можно называть все коды, которые обеспечивают различное написание для всех различных цепочек слов. Особым видом общих кодов являются древовидные коды, в которых пра-
Формальный анализ естественных языков
241
вила написания могут быть представлены графически, как на ,рис. 1, где каждому слову соответствует отдельная цепь в дереве. Древовидные коды мої'ут относиться к одному из следующих днух типов: леводревовидными называются такие коды, в которых никакой код данного слова не является начальным (левым) сегментом кода какого-либо другого слова; праводревовидными называются соответственно такие коды, в которых пи одно слово не является конечным (правым) сегментом какого-либо другого слова; праводревовидный код можно лолучить, переписав в обратном порядке все слова, записанные в леводревовидном коде. Особую разновидность в классе древовидных кодов составляют коды, которые являются одновременно право- и леводревовидными; Шютценберже называет их анаграмматическими. Простейшим случаем анаграмматического кода являются равномерные коды, в которых все слова имеют .одинаковое число букв и разделение сообщения на слова производится а воспринимающем устройстве просто на основе подсчета. Равномерные коды часто используются в инженерных приложениях теории информации; однако они не имеют большого значения для описания естественных языков.
Другим важным видом кодов являются неравномерные коды. Они обладают тем свойством, что если одиночная помеха или ошибка вызвала смещение границы слова, то эта ошибка ¦не будет продолжать смещать границы слов до бесконечности; в течение конечного интервала времени ошибка будет поглощена и восстановится правильная синхронизация. Код Ci обладает этим свойством, равномерные коды им не обладают. В неравномерном коде границы слов всегда отмечаются появлением какой-либо определенной цепочки букв. Если имеется цепочка, которая заканчивает написание • каждого слова, получается лево-неравномерный древовидный код. Если эта цепочка состоит из одной буквы (которая в этом случае не может встречаться ни в какой другой позиции), то получается натуральный код. В письменной речи синхронизация принимающего устройства осуществляется с помощью пробела между словами. В устной речи процесс сложнее; обсуждение вопроса о том, каким образом цепочки слов (морфем) отображаются в цепочки знаков фонетической транскрипции, см. в разд. 6.
Чтобы удостовериться в том, что некоторое отображение действительно является кодом, достаточно в соответствии с инженерной практикой убедиться в том, что оно является леводревовидным кодом, т. е. в том, что нет такого слова, запись которого является начальным сегментом записи некоторого другого слова. Существуют, однако, общие коды, которые не являются древовидными. Шютценберже (Schiitzenberger1 1956)
242
Н. Хомский, Дж. Миллер
предлагает в качестве простейшего нетривиального примера код C2:
,4=(0,1), V=\vi..........vs],
»(«,)-00,
0(«2) = 001,
O(D3) = Oll1 6(w4) = 01,
O(B6)=Il.
Отметим, что O(CZ1) является начальным сегментом 6(?), так что этот код не является леводревовидным; кроме ТОГО, 0(у<)
Общие коды
Рис. 2. Классификация кодирующих систем.
является конечным сегментом O(O2), так что он не является праводревовидным.
При построении искусственных кодов возникает вполне понятное желание сделать длину закодированных слов как можно меньшей. В этой связи можно показать выполнение для древовидных кодов следующего интересного неравенства (Kraft, .1949). Пусть дан словарь V={vv vn], алфавит A =
Формальный анализ естественных языков
243
-Jai, aD] и отображение G, которое является леводревовидным кодом. Пусть Ci есть длина O(^1). Тогда
(4)
Это неравенство выводится следующим образом. Пусть Wj — число закодированных слов длины /; тогда, поскольку б есть древовидный код, получаем
