Лексический анализатор в распознавании последовательных образов

Холоденко А. Б.
Кафедра Математичекой теории интеллектуальных систем

Использование лексических и семантико-синтаксических анализаторов в системах распознавания речи позволяет повысить качество их работы. Как правило, системы распознавания речи позволяют получить набор возможных вариантов распознавания вместе с информацией относительно их правдоподобности.

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

Множество слов D над алфавитом A назовем словарем. Задача коррекции ошибок сводится к следующему: для цепочки G и словаря D определить, существует ли ориентированный путь, ведущий из начальной вершины в конечную, такой, что строка символов вдоль пути допускает разбиение на участки из словаря. Если он существует, то выдать наиболее правдоподобный вариант этого пути или все варианты, суммарные штрафы по которым не превосходят некоторого порогового значения.

Для решения задачи предполагается, что словарь D является регулярным множеством, т.е. задается конечным детерминированным автоматом (теорема Клини). Это позволяет достичь высокой скорости поиска: время поиска слова в словаре равно его длине и не зависит от размеров словаря. Кроме того, операции добавления и удаления слова выполняются за время, равное его длине и также не зависящее от размеров словаря (все свойства словаря при этом сохраняются автоматически).

Разработанные автором алгоритмы позволяют решать задачу о нахождении наиболее правдоподобного варианта распознавания за время const*n², где n - длина обобщенной цепочки, а const - величина, характеризующаяся только словарем и не зависящая от распознаваемой цепочки. Требуемая для этого память также является квадратичной относительно длины цепочки.

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

Алгоритм реализован для случая распознавания введенных сканером текстов с известной тематикой и показал качество работы лучшее, чем оператор.

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

Работа выполнена на кафедре математической теории интеллектуальных систем механико-математического факультета МГУ им. М. В. Ломоносова.

Литература

1.     Yu. Kosarev, I. Machovicova, A. Machovicov, S. Tseitlin. Language Perception Modeling Based on Analysis of Children Speech // 'SPECOM'98' International Workshop Proceedings. 26-29 October 1998 г. St.-Petersburg. -St.-Petersburg, 1998. Pp. 161-168.

2.     I. Zitouni, K. Smaili, J.-P. Haton. Variable-length class sequences based on a hierarchical approach: MCnv// 'SPECOM'98' International Workshop Proceedings. 26-29 October 1998 г. St.-Petersburg. -St.-Petersburg, 1998. Pp. 191-196.

3.     S. Furui. Perspectives of Speech Processing Technologies// 'SPECOM'98' International Workshop Proceedings. 26-29 October 1998 г. St.-Petersburg. -St.-Petersburg, 1998. Pp. 1-6.

4.     Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. ¾ М.: Наука, 1985.

Информационные технологии в инновационных проектах: Материалы докладов. Международная конференция, 20-22 апреля 1999 г. - Ижевск: ИжГТУ, 1999, С. 43-44.