Skip to content

OOmnik

Sections
Personal tools
You are here: Home » Теория » Объектно-ориентированная грамматика » Токенизация линейного потока
 

Токенизация линейного потока

Document Actions

Символьная токенизация электронного текста

Электронный способ кодирования текста состоит в последовательной записи числовых кодов, соответствующих определенным буквенным и иным символам, на информационный носитель (память компьютера, жесткий диск, съемные накопители типа CD/DVD/USB и др. Направление письма в данном способе хранения не имеет значения, поскольку вся информация сохраняется на цифровых носителях, а не на бумаге. Вывод на экран или бумагу осуществляется программными средствами и может быть каким угодно.
Мельчайшей единицей электронного текста является символ, которому в компьютере соответствует определенный числовой код. Анализ текста, хранящегося в электронном виде, начинается с анализа числовых кодов, нахождения соответствующих им символов и разбиения непрерывного символьного потока на составные последовательности символов, которые можно интерпретировать как знаки более высокого уровня (морфемы, слова, числа, знаки пунктуации и т.д.).
Для корректной интерпретации цифрового содержимого текстового файла важно понимать разницу между числовыми кодами, символами и токенами. Числовой код–это всего лишь число, кодируемое одним или несколькими байтами памяти в компьютере. Различают однобайтовые и многобайтовые кодировки исходя из того, сколько байтов памяти отводится на хранение отдельного символа в таблице. В однобайтовых кодировках присутствует всего лишь 256 кодов, которых не всегда хватает для записи языковых и иных символов.
Для решения проблем с кодированием большого числа символов были приняты стандарты Unicode (http://www.unicode.org), использующие в качестве единиц хранения символов 2 и более байтов памяти. Благодаря Unicode мы имеем сегодня возможность хранить в одном файле текстовое содержание, использующее самые разные системы письменности, включая иероглифические. Вместе с тем на сегодняшний день остаются еще достаточно распространенными и однобайтовые кодировки, что создает проблемы интерпретации унаследованных документов, поскольку приходится каждый раз определять кодировку документа. В разных системах кодировки известные нам символы (например, кириллические буквы) могут иметь разные соответствия числовым кодам. Многим приходилось сталкиваться с абракадаброй странных символов: часто это случается при получении электронных писем или чтении веб-страниц. Это происходит из-за несоответствия кодировки электронного текста и экранного шрифта.
Аналогичная ситуация имеет место и с использованием символов, т.е. собственно графических знаков письменности, которой мы пользуемся. Символы могут использоваться для образования разных знаков, имеющих совершенно разные интерпретации. Так, символ «I» может использоваться для записи слов в различных языках, имеющих в качестве письменной системы латиницу (например, английское «I», т.е. «я»). Этот же символ может применяться в римской системе записи чисел, где он уже будет использован в качестве цифры и числа 1. Говоря о различном применении символов, мы вводим понятие символьного токена, т.е. последовательности символов, которая может иметь ту или иную лексическую интерпретацию. Минимальный токен–это 1 символ. Для перехода на более высокий уровень анализа электронного текста мы должны разбить непрерывный поток символьных токенов на лексические токены.

Лексическая токенизация

Ключевые термины и формализмы

Лексическим токеном мы назовем любую последовательность символов, которая может быть истолкована как лексема. Лексема–это единица следующего уровня, способная участвовать в формировании синтаксических объектов.
Рассмотрим несколько примеров. Лексический токен «начала», представляющий собой последовательность кириллических символов, может быть проинтерпретирован следующими способами.
  1. Лексема естественного языка (в виде конкретной словоформы):
    1. глагол «начать»: личная форма глагола, прошедшее время, единственное число, женский род;
    2. существительное «начало»: средний род, единственное число, родительный падеж;
    3. существительное «начало»: средний род, множественное число, именительный падеж;
    4. существительное «начало»: средний род, множественное число, винительный падеж.
Лексический токен «зпт», представляющий собой также последовательность кириллических символов, получает интерпретацию как знак препинания (запятая), используемый в телеграфных сообщениях.
Лексический токен «:)», представляющий собой последовательность символов, которые в изолированном положении используются в качестве знаков пунктуации, получает интерпретацию как эмотивный знак (смайлик) для выражения позитивных эмоций автора текста.
Основываясь на этих особенностях интерпретации символьных последовательностей, мы можем спроектировать программный класс Токен. Базовой частью Токена будет контейнер символов, представляющий собой линейную последовательность символов (self.symbols). Эта последовательность может быть проинтерпретирована по-разному, т.е. распознана как объект других классов. Все возможные интерпретации данного Токена размещаются в особом контейнере интерпретаций, который ранжирует их по принадлежности к различным классам. Так, все интерпретации Токена как слова естественного языка будут храниться в особом массиве, доступ к которому осуществляется по ключу 'Word'. Все интерпретации этого же Токена как знака другого класса будут храниться в отдельных массивах со своими ключами. Единая хеш-таблица self.types хранит соответствующие массивы других объектов: self.types['Word'] хранит Слова, self.types['Punctuation']–знаки препинания, self.types['Number']–числа и т.п. Главное условие помещения различных объектов внутрь Токена состоит в том, чтобы они соответствовали строго данной последовательности символов.

Рисунок 4 – Лексическая токенизация: основные компоненты анализатора

 

Процесс токенизации символьного потока или процесс разбиения символьного потока на объекты класса Токен осуществляется динамически. Заранее мы не знаем границ Токенов и не можем с уверенностью сказать, например, что такой границей является пробел. Пробел может ошибочно быть пропущен или добавлен, а может и использоваться в качестве разрядки, в целях эмфазы. Пробел также может являться полнозначным Токеном, когда он используется для отбивки красной строки, для табуляции строк программы и в других случаях.
Токен как программный объект создается в момент начала считывания символьного потока и получает на вход свой первый символ. Мы помним, что символ может входить в состав знаков различных классов, поэтому нам потребуется запросить различных программных экспертов, которые подтвердят или отвергнут принадлежность текущего символа к тому или иному классу. Все возникшие интерпретации символа должны быть сохранены в хеш-словаре self.types.
Каждый раз, когда на вход Токена подается очередной новый символ, Токен должен предъявить его всем имеющимся у него интерпретациям и решить, оставаться ли единым Токеном или быть разбитым на несколько. Основным условием сохранения текущего Токена является то, что все текущие интерпретации, имеющие одинаковый состав self.symbols, признают новый символ своим (легитимным).
Если же хотя бы одна интерпретация заявит о том, что такой символ ей не подходит, она выделяется в отдельный Токен и изымается из текущего Токена. Таким образом, происходит ветвление версий разбиения строки на Токены, и поэтому необходимо сообщить об этом вызывающему Токенизатору, чтобы он создал новый массив Токенов с учетом происшедших изменений.
Например, при анализе символьной последовательности «снами» может возникнуть несколько вариантов членения ее на Токены:
  1. «с» (предлог) и «нами» (местоимение)
  2. «снам» (существительное в дательном падеже) и «и» (союз)
  3. «снами» (существительное в творительном падеже)
Все эти интерпретации могут действительно иметь место в различных контекстах, если предположить, что знак пробела мог быть пропущен по ошибке.
Каждый класс интерпретаций представлен массивом экземпляров, представляющих разные трактовки текущей цепочки символов в пределах одного класса. Например, в классе Word (слово естественного языка) трактовки могут отличаться друг от друга различным составом формантов. Возвращаясь к примеру с Токеном «начала», мы видим, что различные его интерпретации в качестве слова естественного языка имеют различный морфологический состав:
  1. корень «нач» + формант «а» + формант «л» + формант-флексия «а»
  2. корень «начал» + формант-флексия «а» (сущ., ед.ч., ср.род., род. падеж)
  3. корень «начал» + формант-флексия «а» (сущ., мн.ч., ср.род, им.падеж)
  4. корень «начал» + формант-флексия «а» (сущ., мн.ч., ср.род, вин.падеж)
Каждая трактовка получает на вход 1 символ. Если у гипотезы это первый символ, то она начинает сразу же анализировать его возможную семантику. Делается запрос к словарю формантов. Если в словаре есть форманты, совпадающие с этим символом, то первый из них заносится в список формантов текущей гипотезы, а для остальных создаются новые гипотезы и в каждую заносится соответствующий формант. Помимо этого создается трактовка, в которой текущий символ присоединяется к строке нераспознанных символов, поскольку мы предполагаем, что нынешние гипотезы могут быть ошибочными и более правильная трактовка будет возможна при дальнейшем увеличении числа символов.
Если в трактовке уже имеются форманты, то берется остаток неприсоединенных символов и к нему присоединяется текущий символ. Получившаяся строка анализируется тем же образом, как было указано выше.
Токен должен отслеживать текущее состояние своих трактовок. Когда какая-нибудь трактовка заявляет о том, что ее состояние представляет собой законченную легитимную словоформу, Токен должен создать новый экземпляр Токена, поскольку появилась легитимная граница между Токенами.
Когда поток символов заканчивается, Токен рассматривает имеющиеся гипотезы. Например, речь может идти о незаконченной словоформе (обрыв текста), и в таком случае необходимо выдать хотя бы текущие гипотезы интерпретации.

Лексическая токенизация иероглифического текста

Рассмотрим более подробно алгоритм лексической токенизации на примере пошагового разбора иероглифического текста на китайском языке. На вход анализатора будет подан следующий набор иероглифов:

Рисунок 5 – Текст на китайском языке (guójiāyínháng «государственный банк»)

 

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

Рисунок 6 – Начало работы лексического токенизатора: считывается первый символ

 

Применяя доступные ему эвристики, токенизатор должен решить, может ли данная последовательность (пока лишь 1 символ) образовать единицу лексического уровня, т.е. слово. Для этого он обращается к собственным экспертам, ответственным за конкретные языки. Эксперты снабжены словарными базами и динамическими правилами построения сложных лексических единиц. В данном случае эксперт по китайскому языку ответит, что согласно его данным, данный символ может восприниматься как законченное слово китайского языка. Словарные значения иероглифа (в фонетической транскрипции пиньин: guó) будут включать такие понятия, как «государство», «страна», «империя» и др. Кроме того, токенизатору будет сообщено, что этот иероглиф может быть началом других слов. Исходя из полученных данных токенизатор создаст две гипотезы прочитанного потока данных. Первый вариант означает наличие завершенного токена, являющегося словом. Второй вариант означает поступление символов незавершенного токена, остаток которого ожидается далее. В иллюстрации незавершенность токена обозначается отсутствием правой границы у рамки, обводящей весь токен.

Рисунок 7 – Первые гипотезы лексического токенизатора

 

Лексический токенизатор запрашивает у символьного токенизатора следующую единицу и получает 2 символ. Этот иероглиф (пиньин: jiā) в изолированном употреблении имеет значения «семья», «дом» и др. Таким образом, версия раздельного восприятия этих иероглифов разветвляется на две: согласно варианту 1.1 перед нами два отдельных слова, а согласно варианту 1.2 перед нами одно завершенное слово и начало какого-то другого.

Рисунок 8 – Лексическая токенизация: фокус внимания на 2 символе

 

Согласно другой версии, необходимо попытаться связать вместе 1 и 2 символы, поэтому токенизатор фокусируется на этой комбинации.

Рисунок 9 – Лексическая токенизация: фокус внимания на 1 и 2 символе

 

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

Рисунок 10 – Текущие гипотезы после прочтения 2 символа

 

Запрашивается следующий символ и расширяются те версии анализа, которые на данный момент содержали лишь завершенные токены.

Рисунок 11 – Лексическая токенизация: фокус внимания на 3 символе

 

Данный иероглиф (пиньин: yín) имеет значение «серебро», «серебряный», «серебристый» и др., что позволяет рассматривать его как самостоятельное слово в этой последовательности токенов. Также лексический эксперт сообщает, что имеются слова, которые начинаются с этого иероглифа, поэтому добавляется вариант с ожиданием правого контекста.

Рисунок 12 – Увеличение гипотез

 

Рассмотрение иероглифа как продолжения открытого токена с началом во 2 символе не дает словарного подтверждения, такой комбинации не зафиксировано, однако ничто не мешает лексическому эксперту по китайскому языку воспринять это сочетание как свободное (например, в смысле «семейное серебро») или же трактовать это сочетание как имя собственное, поскольку иероглифы могут использоваться в качестве фонетических слогов для создания уникальных имен собственных или транслитерации иностранных имен.

Рисунок 13 – Лексическая токенизация: фокус внимания на 2 и 3 символе

 

Таким образом, число вариантов увеличивается: каждая версия разветвляется на 2.

Рисунок 14 – Увеличение гипотез

 

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

Рисунок 15 – Лексическая токенизация: фокус внимания на 1, 2 и 3 символе

 

Состояние версий, учитывающих максимально длинную цепочку символов:

Рисунок 16 – Увеличение гипотез

 

Наконец, поступает последний символ из входного потока. Он имеет очень много значений и обладает огромным потенциалом к образованию значений. Ряд значений простирается от глаголов «ходить, передвигаться» до существительных «предприятие, фирма, банк» и др.

Рисунок 17 – Лексическая токенизация: фокус внимания на 4 символе

 

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

Рисунок 18 – Увеличение гипотез

 

Рассмотрение 3 и 4 символа вместе дают нам вариант, подтверждаемый лексическим экспертом, согласно которому перед нами слово «банк».

Рисунок 19 – Лексическая токенизация: фокус внимания на 3 и 4 символе

 


Рисунок 20 – Увеличение гипотез

 

Трактовка символов со 2 по 4 даст только свободные сочетания, не зафиксированные словарями. Однако эти версии также имеют право на существование.

Рисунок 21 – Лексическая токенизация: фокус внимания на 2, 3 и 4 символе

 

Передав лексическому эксперту все 4 символа, мы получаем ответ, что это сочетание означает «государственный банк».

Рисунок 22 – Лексическая токенизация: фокус внимания на 1, 2, 3 и 4 символах

 


Рисунок 23 – Увеличение гипотез

 

Как можно понять из вышеприведенного алгоритма токенизации, лексический эксперт не может принять самостоятельное решение о выборе той или иной версии. Конечно, можно предположить, что наиболее длинные цепочки всегда будут предпочтительнее, чем сочетания коротких слов. Однако в китайском языке эта ситуация усложняется тем обстоятельством, что имена собственные, особенно иностранные наименования в китайской фонетической записи, всегда будут самыми длинными. Это не значит, что при выборе, скажем, между раздельными 3 одиночными иероглифами и их слитным восприятием в качестве имени собственного длина будет иметь значение. Более определяющим является синтаксический и семантический контекст, который контролируется другими экспертами. Только совместная работа всех уровней экспертной оценки может привести к убедительному заключению о правильности той или иной интерпретации текста.

Лексическая токенизация арабского текста

Рассмотрим в качестве примера многозначной токенизации варианты разбора арабского арабского знака "ﺏﺬﻠﻛ". Входной поток состоит из морфем. Связка работает с версиями разбиения входного символьного потока на морфемы.

Рисунок 24 – Входной символьный поток

 

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

Рисунок 25 – Версии разбора: первый токен

 

Когда поступает следующий символ, количество версий удваивается за счет наличия в словаре двух морфем, начинающихся с слога, согласным в котором является этот символ, а также двух морфем, согласные первых двух слогов которой–оба прочитанных символа.

Рисунок 26 – Версии разбора: второй токен

 

На данный момент во всех версиях есть только один законченный токен. Однако с приходом следующего символа подтверждаются все версии о незаконченных морфемах: в трех версиях из четырех поступивший символ оказывается последним согласным, а в одной–вторым. В первых трех случаях токен оказывается незавершенным, так как нет информации об огласовке последнего слога: она не входит в эти морфемы, а является отдельной флексией. В этом случае эксперт, тем не менее, выстраивает версии, готовые к приему новых заполнителей. Затем экспертом осуществляется попытка связать каждую полученную морфему с предыдущей, однако модификационной связи между ними нет. Это означает, что связаны они будут только на вышестоящих уровнях анализа.

Рисунок 27 – Версии разбора: третий токен

 

Когда поступает последний символ, количество вычислений достигает максимума. Во-первых, последний символ оказывается согласным, а предшествующий слог все еще неогласован. Поэтому токенизатор вынужден предположить наличие в морфемной цепочке некой морфемы, на письме не выраженной никак, а в произнесении выраженной гласным звуком. Чтобы определить, какая именно морфема могла иметься в виду, приходится запрашивать у нижестоящего токенизатора все варианты морфем, состоящих только из гласного. Далее, как только такая морфема возникает, эксперт пытается связать ее с предыдущим контекстом. На сей раз это увенчивается успехом, так как морфема оказывается либо падежным окончанием, либо окончанием глагольной формы. Далее, если токенизатор работает в связке с вышестоящим экспертом, то на уровне последнего обнаруживается связанность имени с предлогом. Эта связанность отметает для данного имени версии о винительном и именительном падежах, так как предлоги в арабском языке присоединяют к себе только родительный падеж (информация об этом хранится в поле 'needs_gram' синтаксического класса 'предложный аргумент'). Затем токенизатор переходит к поступившему символу, на который нижестоящий эксперт выдает сразу две версии (последний символ может соответствовать двум слитным местоимениям). Эксперт снова осуществляет попытку связать его с левым контекстом, но и эта попытка терпит неудачу. Тогда, если токенизатор работает в связке с вышестоящим, то уже вышестоящий эксперт пытается их связать. В итоге на данном уровне выстраиваются следующие версии:

Рисунок 28 – Итоговые версии разбора

 
Created by oomnik
Last modified 2007-04-16 13:32
« May 2012 »
Mo Tu We Th Fr Sa Su
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      
 
 
Powered by Plone

This site conforms to the following standards: