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



На правах рукописи

./¿г '

Черепицкий Андрей Анатольевич

ИССЛЕДОВАНИЕ И РАЗРАБОТКА СТРУКТУР ПОСТРОЕНИЯ И АЛГОРИТМОВ УПРАВЛЕНИЯ БАЗОЙ ДАННЫХ КОМПЬЮТЕРНЫХ СЛОВАРЕЙ.

Специальность: 05.13.06 - Автоматизированные системы

управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

\

Санкт-Петербург - 1999

Работа выполнена в Санкт-Петербургском государственном электротехническом университете «ЛЭТИ».

Научный руководитель -

кандидат технических наук, профессор Солодовников А.И.

Официальные оппоненты:'

доктор технических наук, профессор Никифоров В.В., кандидат технических наук, доцент Дубенецкий В.А.

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

университета «ЛЭТИ» по адресу: 197376, Санкт-Петербург, ул. Проф. Попова, 5.

С диссертацией можно ознакомиться в библиотеке университета.

Защита диссертации состоится < на заседании диссерта: .

Санкт-Петербургского государственного

1999г. совета К 063.36.03 электротехнического

на

Автореферат разослан «

ГРЯ 1999

г.

Ученый секретарь диссертационного совета

Кутузов О.И.

2 ¿3-/. £<я>. 4 О

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Динамичное развитие рынка программного обеспечения в области Desktop Publishing (настольное издательство) внесло существенные коррективы в традиционные методы подготовки текстов, обусловив тем самым появление и развитие компьютерных словарей (КС) как неотъемлемой части любой издательской или информационно-справочной системы.

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

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

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

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

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

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

Для достижения поставленной цели в работе были поставлены и решены следующие задачи исследования:

1) анализ и выделение основных функций компьютерного словаря;

2) анализ эффективности реализации функций поиска на структурах данных компьютерного словаря;

3) разработка принципов построения компьютерного словаря на основе печатного прототипа;

4) разработка алгоритмов преобразования текста и структуры исходного печатного словаря при формировании базы данных компьютерного словаря.

Методы исследования. При проведении исследований в работе использовались элементы теории баз данных, теории множеств, теории вероятностей, теории анализа алгоритмов и теории построения трансляторов.

Научная новизна.

В диссертационной работе были получены следующие научные результаты:

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

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

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

Практические результаты заключаются в том, что:

1) Разработаны основные принципы и алгоритмы построения компьютерных словарей на основе исходного печатного прототипа.

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

Внедрение результатов работы. Работа выполнялась в рамках договора о сотрудничестве между СПбГЭТУ и фирмой Р01ЛЕТ (г.Варшава, республика Польша). Разработанные методы и алгоритмы легли в основу разработки следующих компьютерных словарей:

1996г. - большой толковый словарь польского языка (издательство РИН);

1998г. - словари синонимов польского языка (автор СТ. С±епко>гзк1) ;

1999г. - большой польско-русский словарь (издательство Пхейга РомегесЬпа).

Апробация результатов работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на научно-технической конференции СПГЭТУ в 1999 гг., а также на международной конференции „Ksi^zki multimedialne i elektroniczne w edukacji i biznesie" -Instytut Maszyn Maternatycznych, Warszawa, 29.X.1998.

Публикации. По теме диссертации опубликовано 3 печатные работы (статьи).

Структура и объем диссертации. Работа состоит из введения , четьдэех глав с выводами, заключения, списка литературы, включающего 48 наименований, и одного приложения. Основная часть работы изложена на 105 страницах машинописного текста. Работа содержит 2 6 рисунков и 5 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность исследований, определены объект исследования и основные цели диссертационной работы, кратко раскрыто их содержание.

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

Сформулирована проблема построения КС на основе ПС, заключающаяся в комплексном решении следующих задач (рис.1):

- анализ существующих КС с целью определения множества типичных функций управления, на основе которых формируется набор функций поиска (ФП) как основы системы управления (СУ) ;

- построение модели структуры исходного ПС на основе описания, приведенного авторами;

- преобразование текста ПС в компьютерную запись с сохранением исходной структуры ПС;

- разработка структуры представления данных КС на основе структуры ПС для эффективной реализации ФП;

- преобразование компьютерной записи текста ПС в рамки разработанной структуры;

- разработка алгоритмов реализации ФП и соответствующих им структур.

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

Модификации исходного словаря

ПЕЧАТНЫЙ СЛОВАРЬ

Преобразование данных

Преобразование структуры

Текстовый

файл на компьютере

Анализ

исходной

структуры

Запись в формате базы данных

Разработка Функций управления

РАЗРАБОТЧИК

Разработка структур данных

Анализ функций словарных модулей

КОМПЬЮТЕРНЫЙ СЛОВАРЬ

Система управления

База данных

Применение

ДИАЛОГОВЫЕ ИНФОРМАЦИОННО-ПОИСКОВЫЕ СИСТЕМЫ Системы машинного перевода Текстовые процессоры (орфография, синонимы)

Область применения компьютерных словарей

Рис.1. Объект и задачи исследования

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

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

На основе проведенного исследования строится классификация основных ФП по различным критериям (табл.1).

Таблица 1. Классификация основных ФП

ПАРАМЕТР КЛАССИФИКАЦИЯ

Форма запроса по содержанию (точный) по смыслу (тематический)

Область поиска по заголовку (индексный) по определению (полнотекстовый)

Объект поиска слово (известно все слово) шаблон (известна часть слова)

Условие поиска простой (один объект) логический (два и более объектов)

Запрос на поиск может формироваться путем комбинации основных ФП.

В завершение главы рассматривается концептуальная модель КС в виде иерархической структуры, на основе которой определяется взаимосвязь основных элементов КС и в дальнейшем строится его математическое описание на языке множеств .

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

Сначала на основе теории анализа алгоритмов определяются критерии сравнения эффективности алгоритмов и структур, которыми являются среднее А(п) и худшее №'(") время вы-

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

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

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

Идея построения ДП основана на представлении слов wt и Wj , имеющих общий префикс w [1: ni] - w^l: т], в виде узла дерева , расположенного на расстоянии т от его корня. Обобщив это правило на случай, когда несколько слов могут иметь общий префикс, получаем дерево следующего вида (рис.2) (в качестве примера были выбраны слова ЪаЪа, Ьасас, bacd, badb, ЬЬс, bad из алфавита А ~ {a,b,c,d}) .

Рис.2. Пример построения дерева префиксов

В классическом варианте построения ДП узел дерева представляет собой массив указателей общим числом г , где г-размер алфавита А . Основным достоинством этого варианта является то, что время поиска линейно зависит от длины ис-

комого слова к и не зависит от размера словаря, т.е. W{k) = А(к) = к . Оценим количество памяти, необходимое для реализации такой структуры. Пусть к - средняя длина слова. Обозначим через г усредненное число ветвей, выходящих из каждого узла, 1 < г < г . Оценить значение г можно, исходя из общего числа слов п и средней длины слова к-, п = , отсюда г «log,_, п , т.е. г <г . Тогда число всех узлов в дереве

* !

можно оценить как N(n,k) = = ^(log4_, и)' . Соответственно

ï-0

объем занимаемой памяти составляет

1=0

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

В работе предложены два варианта улучшения характеристик ДП.

1) Динамическое формирование узла. Модифицируем структуру узла, добавив к каждому указателю символ из алфавита А, согласно которому осуществляется переход. Таким образом, в узле могу' храниться только те пары значений «символ» - «указатель», которые реально присутствуют в словаре. Несмотря на то, что в структуру узла добавился новый элемент, объем занимаемой памяти снижается за счет уменьшения средней длины узла:

= - ¿(log, ,«)' .

1-0 1-1

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

W(n) = А(п) = Цlog2 г +1) = A(log2 log,,, п +1) .

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

2) Перегруппировка элементов узла по частоте.

Определим вероятность /(а,) появления символа я, в тексте словаря на произвольной позиции. Из множества символов алфавита А построим новый алфавит А таким образом, чтобы выполнялось соотношение /(а[)>/(а'2)>.. >/(а'г) , т.е. на первом месте находился наиболее часто встречающийся в тексте символ, на втором - следующий по частоте и т.д. Размер узла в данном случае определяется номером элемента а, , имеющего минимальную вероятность /(я,) из числа присутствующих в узле. Время поиска в такой структуре минимально и совпадает с классическим вариантом, тогда как объем занимаемой памяти в общем случае определяется видом функции распределения /-'(О случайной величины /, определенной на

диапазоне [1;г]. Обозначив через / математическое ожидание г

/, получим У%(г,к,п) = — и)' . Таким образом, предлагаемый

' 1=0

вариант позволяет уменьшить объем ДП при сохранении его основного достоинства - минимального времени поиска.

Приведенные выше оценки времени поиска справедливы для поиска точно Заданного слова. Если же в качестве объекта поиска выступает шаблон, алгоритм поиска усложняется и, соответственно, снижается скорость его работы. Однако, как показали исследования, и в этом случае ДП является оптимальной структурой.

Для определения местонахождения искомого слова в тексте словаря используется линейный поиск в последовательном файле, который представляет собой текст словаря, кодированный предложенным в работе статическим частотным кодом:

1} Определим понятие веса слова как произведение частоты его выступления в тексте на длину: /(») = /ге<](\у;) х ) .

2) Упорядочив все /00 по убыванию, получим распределение весов слов от 1 до ш, где т- число всех слов(рис.3).

3) Каждому слову м>1 поставим в соответствие двоичный код, длина которого обратно пропорциональна весу /ОО .

Заметим, что похожий механизм используется в различных вариантах алгоритма компрессии данных Лемпела-Зива. Разница заключается в том, что при компрессии данных в реальном времени сложно построить таблицу всех слов, поэтому в Ьй-алгоритмах используется окно размером 2-16 КБ, перемещаемое по тексту.

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

код, в котором для обозначения кодируемого слова испольЗу-

И

Рис.3. Принцип кодирования текста словаря

Оценка характеристик алгоритма поиска слова в этом случае выглядит следующим образом:

I= £ + ^ , Л(М,*) = *г + 2у ,

где 1Т- длина текста словаря, к- средняя длина слова. Для того, чтобы оценить расход памяти для предложенной структуры, определим коэффициент сжатия исходного текста а как отношение разности длин исходного Ыь и полученного Иа

N -Я

текстов к длине исходного текста: а-—^—-х100%. Если

.у — число разных слов в тексте словаря, получим следующие соотношения:

= £/(и, Ма = ¿/О,) + 2 £ /К) + 3 ¿/Ю 1 = 1 1=1 !=27+1 ( = 2"+1 Общий объем памяти, занимаемый словарем после преобразования текста, складывается из объема дерева префиксов

к

и длины компрессированного текста: У(к,п) = /))' +Ая(1-а) ,

1=1

где и- общее число слов в тексте словаря, к- средняя длина слова в тексте словаря, а-коэффициент сжатия.

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

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

Основное внимание уделено проблеме построения БД словаря, которая разделяется на следующие основные этапы:

- преобразование текста ПС в компьютерную форму;

- построение и преобразование структуры статьи;

В настоящее время наиболее эффективным способом переноса большого объема печатного текста на компьютер является ввод текста при помош?! сканера. Учитывая специфический характер обрабатываемого материала, в работе предложен алгоритм решения этой задачи, характерными особенностями которого являются:

- обучение системы нетипичным символам, используемым в ПС для обозначения частей статьи;

- введение в базу лингвистического модуля системы распознавания списка сокращений, используемых в данном ПС;

- пакетный режим обработки, заключающийся в последовательном автоматическом выполнении этапов сканирования, распознавания с последующей коррекцией;

- применение методов групповой обработки (МГО) текстов для исправления ошибок.

Остановимся подробнее на последнем этапе. Стандартные последовательные методы проверки текстов, реализуемые в большинстве современных текстовых редакторов и систем распознавания, предназначены в первую очередь для проверки текстов небольшого объема. Если же речь идет о проверке десятков тысяч страниц, такой способ является неэффективным, поэтому в работе предложен другой подход к решению этой задачи путем применения МГО, основная концепция которых изложена ниже (рис.4).

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

и

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

Рис.4. Алгоритм проверки текста методом групповой обработки

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

Общее время проверки текста Гк при применении последовательного метода коррекции равно времени участия в нем оператора Т'0Ри составляет Т +/*) . Очевидно, что при

равномерном распределении ошибок в тексте его проверка в

данном случае требует постоянного вмешательства оператора в течении всего процесса.

Обозначив через к число ошибок в группе (к>\), оценим

временные показатели для МГО: Т' = 7," + Т" = ^ —пе1к . Заме-

к

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

Сравним теперь время работы оператора Т'ср и

Г" =—и,?* с целью оценки границ применимости метода груюто-

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

Т / I

'к 'к

Обозначив а = —, получим следующий вид зависимости

Ч

Е = /(к) = к (а +1) , представленный на рис. 5.

Е(Ю

и,(а+1)

га+1

1 „, к

Рис.5. Зависимость эффективности метода групповой обработки от параметров текста

Итак, эффективность МГО определяется двумя основными факторами:

- соотношением времени поиска ошибки машиной I, и времени исправления этой ошибки оператором Iк. Если ¡к », эффективность определяется только лишь группировкой ошибок;

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

Следует отметить, что наряду с количественным аспектом эффективности МГО, Заключающимся в уменьшении времени ручной проверки, присутствует качественный, определяемый меньшей утомляемостью оператора, что в свою очередь снижает вероятность допущения ошибки.

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

- построение структуры статьи исходного словаря;

- проверка полученной структуры;

- модификации этой структуры.

Структурой статьи словаря $={Р,К,Р} будем называть совокупность следующих множеств: основных полей словаря F, разделителей полей Я и правил построения Р . Для построения и отображения структуры используется множество вспомогательных обозначений .

Первоначальный вариант структуры Я строится на основе анализа описания структуры, приведенного авторами исходного ПС. В работе предложен способ задания 5 в виде синтаксической диаграммы (СД) - графа, узлами которого являются элементы множеств полей статьи и разделителей К, порядок соединения которых задается множеством правил Р . (рис. б) .

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

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

Представление структуры статьи словаря в виде СД используется не только для ее построения и модификации, но и позволяет эффективно реализовать функции тематического поиска, задавая в качестве области поиска определенное поле. Следует Заметить, что машинный формат представления статьи словаря также определяется на основе СД.

<СТАТЬЯ>:

<ЗДГШЮВ0К>:

О- ЧлНнамоР Г

ОКОНЧАНИЕ

а

I—[ Иасга речи |

ТЬ---МТ

1—| Квалификатор —1

<ОПРЕДЕЛЕШЕ>:

значение

Вжер

]-—I ЗНАЧЕНюГ

-о-

г

<ОКОНЧЙНИЕ>:

Слово

-СИ

ОКОНЧАНИЕ

Рис.6. Представление структуры статьи в виде синтаксической диаграммы

Итак, СД являются эффективным и гибким способом задания структуры словаря, ее проверки и модификации, а также позволяют реализовать поиск по заданным полям и построить низкоуровневый формат записи БД.

Четвертая глава содержит экспериментальную проверку предложенных методов и алгоритмов на примере разработки компьютерной версии большого польско-русского словаря, основные характеристики которого представлены в табл.2.

На рис.7 приведена зависимость объема памяти, занимаемого деревом префиксов, от способа его построения и числа слов, а также распределение весов слов в тексте словаря.

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

Таблица 2. Основные характеристики исследуемого словаря_

ИСХОДНЫМ ПЕЧАТНЫЙ СЛОВАРЬ

Название Большой польско-русский словарь

Объем 80 ООО статей

Число и объем печатных страниц Том I - 635 стр., том II - 835 стр. 2 колонки на стр., 45 симв. х 65 строк

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

ТЕКСТ ПОСЛЕ ПРЕОБРАЗОВАНИЯ В КОМПЬЮТЕРНУЮ ФОРМУ

Объем файла 15,6 МБ (чистый текст, без атрибутов)

Число слов 276500 (143675 русских и 132825 польских)

Число ошибок в оригинале орфографических: > 500 структурных: > 200

Эффективность обработки с применением МГО время проверки одного тома классическим способом - 1 месяц, с применением МГО - 8 дней, эффективность Е~4

Коэффициент сжатия текста предложенным способом: 55% (методом сжатия LZW: 62%)

Отношение времени поиска обычный текст/кодированный текст > 12

Рис.7. Экспериментальные характеристики словаря

В завершение главы обсуждаются возможные направления дальнейших исследований.

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

ОСНОВНЫЕ НАУЧНЫЕ И ПРАКТИЧЕСКИЕ РЕЗУЛЬТАТЫ

1) Разработаны основные принципы и алгоритмы построения компьютерных словарей на основе исходного печатного прототипа.

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ РАБОТЫ

1. А.А.Черепицкий. Применение методов групповой обработки текстов для поиска и исправления ошибок // С-Петербургск. гос. электротехн.ун-т. - СПб, 1999. - 9с.: ил. - Деп.в ВИНИТИ 2389-В99.

2. Алексеев A.A., Кноте К., Солодовников А.И., Спива-ковский А.М., Черепицкий A.A. Алгоритм формирования диагностических признаков нечетких экспериментальных сигналов // Известия ГЭТУ: «Информационные технологии в технических и организационных системах». Вып.514.-СПб,1997г.-с.76-80.

3. А.Czerepicki, O.Dyczkowska-Uss. Przygotowanie tekstów do siowników komputerowych // Materialy konferencji „Ksiazki multimedialne i elektroniczne w edukacji i biznesie". Prace Instytutu Maszyn Matematycznych. - Warszawa, wrzesieñ 1998.

ВВЕДЕНИЕ

1. АНАЛИЗ СОВРЕМЕННЫХ КОМПЬЮТЕРНЫХ СЛОВАРЕЙ И ВЫДЕЛЕНИЕ ЗАДАЧ ИССЛЕДОВАНИЯ

1.1. Предварительные замечания.

1.2. Определение предметной области и объекта исследования.

1.3. Обзор литературы по предметной области.

1.4. Анализ современных компьютерных словарей.

1.5. Выделение и классификация функций поиска.

1.6. Концептуальная модель общей структуры словаря.

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

Динамичное развитие рынка программного обеспечения в области DTP (DeskTop Publishing - настольное издательство) внесло существенные коррективы в традиционные методы подготовки текстов, обусловив тем самым появление и развитие компьютерных словарей как неотъемлемой части любой издательской или информационно-справочной системы.

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

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

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

Популярные текстовые редакторы зачастую обладают возможностью проверки правописания, поиска синонимов, а иногда даже помогают проверять грамматику [3] . Однако они не в состоянии заменить истинного словаря, то есть программы или книги), которая давала бы объяснения слов, примеры их использования или правила написания. Именно поэтому в настоящее время возрос интерес к построению компьютерных словарей, имеющих в своей основе накопленный столетиями опыт создания печатных словарей.

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

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

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

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

Определим требования, которым ■ должны удовлетворять исходные данные. В нашем случае это словарь, отпечатанный типографским способом на бумаге хорошего качества, с четким разделением текста на статьи, структура которых описана авторами издания.

Выделим основные направления исследований: анализ и выделение основных функций компьютерного словаря;

- разработка элементов системы управления компьютерного словаря;

- разработка структуры компьютерного словаря

- разработка методов и алгоритмов построения компьютерного словаря на основе печатного прототипа.

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

4.5, Основные выводы

В данном разделе была проведена экспериментальная проверка предложенной концепции и основных методов построения компьютерных словарей на примере разработки системы управления и базы данных компьютерной модели большого польско-русского словаря.

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

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

1) Модификации структур и алгоритмов, основанных на дереве префиксов.

Хотя вариант с построением дерева префиксов обладает лучшими временными характеристиками, объем занимаемой памяти все еще остается достаточно большим, чтобы применять этот метод во всех словарях без исключения. Каковы возможности по уменьшению этого объема? Заметим, что большинство слов в таких флективно-богатых языках, как русский, имеют одинаковые окончания. Выделив эти окончания в таблицу, можно убрать нижние уровни дерева префиксов, заменив их ссылками на номер окончания в таблице, что может дать существенную экономию памяти.

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

2) Совершенствование существующих печатных словарей

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

3) Построение обратных словарей

Если исходный словарь является двуязычным, возможно полуавтоматическое построение на его основе словаря, обратного заданному (в нашем случае на основе польско-русского словаря может быть построен зеркальный ему русско-польский) .

4) Построение подсловарей на основе универсального словаря

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

ЗАКЛЮЧЕНИЕ

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

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

В заключение перечислим основные результаты, выносимые на защиту.

1) Разработаны основные принципы и алгоритмы построения компьютерных словарей на основе исходного печатного прототипа.

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

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

4) Разработана концепция методов групповой коррекции как сочетания автоматического распознавания ошибок, их классификации на базе сортировки в более крупные группы,

1. Ашманов И. С. Грамматический и стилистический корректор для текстов на русском языке. «Мир ПК», 1995, №1, с.51-61.

2. А.Беленький. Внимание! Переводит компьютер. «КомпьютерПресс», 1995, №11, с.50-51.

3. А.Соколов. Парадоксы в мире компьютерной обработки текстов. «Компьютер-Пресс», 1996, №4, с.37-39.

4. Першиков В.И, Савинков В.М. Толковый словарь по информатике. М.: Финансы и статистика, 1991.

5. Розенталь Д.Э., Теленкова М.А. Словарь-справочник лингвистических терминов. М.: Просвещение, 1976.

6. Atkins В. Bilingual Dictionaries: Past, Present and Future. Euralex 96 Proceedings. Part I, Goteborg: University Press, s.515-546.

7. Catford J.C. A Linguistic Theory of Translation: An Essay in Applied Linguistics. Oxford: University Press, 1965.

8. А.Блинов. Общеобразовательные продукты. Энциклопедии. «Компьютер-Пресс», 1995, №11, с.126-131.

9. P.Wimmer. Slowniki i nie tylko. PC Kurier, 1996, №24, s. 84 .

10. E.Golachowska. J^zykoznawstwo na CD. PC Kurier, 1997, №26, s.116.

11. А.Федоров. Что бывает на CD. «Компьютер-Пресс», 1995, №4, с.143-150.

12. Р.Гадас. Какой словарь самый-самый? «Компьютер-Пресс», 1996, №11, с.14-18.

13. Старизный А.Е. Автоматическое построение указателей к словарям словосочетаний с учетом парадигматических отношений между понятиями: Автореферат диссертации на соискание ученой степени канд.техн.наук: 05.25.05 . М. , 1991, 27 с.

14. Ситняковская Е.И. Исследование и разработка эффективных словарных методов сжатия данных для систем цифровой связи: Автореферат диссертации на соискание ученой степениканд.техн.наук: 05.12.02. Новосибирск, 1995, 27 с.

15. D.Angluin. Finding Patterns Common to a Set of Strings. SIAM Journal of Computing, 1980, v. 21, p.46-62.

16. R.M.Karp, M.O.Rabin. Efficient randomized, pattern-matching algorithms. IBM Journal of Research and Development, 1987, v.32, p.249-260.

17. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 519с.

18. L.Banachowski, K.Diks, W.Rytter. Algorytmy i struktury danych. Warszawa, WNT, 1996. 290 s.

19. D.E.Knuth. The art of Computer Programming. Volume 3: Sorting and Searching. Addison-Wesley Publishing Company, 1975 .

20. P.Wroblewski. Algorytmy: struktury danych i techniki programowania. Warszawa, Helion, 1997. 350 s.

21. Crochemore M., Rytter M. Text algoritms. Oxford University Press, 1994.

22. D.E.Knuth, J.H.Morris, V.R.Pratt. Fast pattern matching in strings. SIAM Journal of Computing, 1977, v.6, p.323-350.

23. Ziv J., Lempel A. Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theory.- 1978, T24, №5, p.530-536.

24. Huffman D.A. A method for the construction of minimum-redundancy codes. Proc. Inst. Electr. Radio Eng. 1952, T.40, №9, p.1098-1101.

25. Н.Никольский. Автоматический ввод сложных документов. «Компьютер-Пресс», 1996, №4, с.18-20.

26. Н.Никольский. Системы ввода информации вчера, сегодня, завтра. «Компьютер-Пресс», 1996, №11, с.52-54.

27. Горский Н., Анисимов В., Горская JI. Распознавание рукописного текста: от теории к практике. СПб.: Политехника, 1997. - 126 с.

28. Зайцев-Зотов В.И., Савин A.A. Методы распознавания машинописных и рукописных знаков в оптических читающих устройствах. Сб.статей: Электронная вычислительная техника. Вып.З/под ред.В.В.Пржиялковского. М.: Радио и связь, 1989.- с.170-184.

29. Байков A.M., Кузин Е.С., Шамис A.C. Целостное целенаправленное распознавание изображений в ЭВМ / Вопросы кибернетики. М.: 198 7. - с.78-90.

30. Фурман Я., Юрьев А., Яншин В. Цифровые методы обработки и распознавания бинарных изображений. Красноярск, 1992.

31. Д.Тин, Б.Прасада. Методы цифровой обработки для кодирования графической информации. ТИИЭР,т.68, 1980, №7, с.6-40 .

32. Прикладные нечеткие системы // под ред. Т.Тэрано и др. -Перев. с японского. М.: Мир, 1993. - 368 с.

33. Алексеев A.A., Кноте К., Солодовников А.И., Спиваковский A.M., Черепицкий A.A. Алгоритм формирования диагностических признаков нечетких экспериментальных сигналов // Известия

34. ТЭТУ. Информационные технологии в технических и организационных системах. Вып.514. СПб., 1997, с.7б-80.

35. Алексеев A.A., Кундышев С.Б., Солодовников А.И., Спиваковский A.M., Черепицкий A.A. Метод спектрально-фрактального преобразования изображений // Известия СПбГЭТУ. Управление, информатика и вычислительная техника. Вып.1. СПб., 1998, с.29-33.

36. Русин Б.П. Структурно-лингвистические методы распознавания изображений в реальном времени. Киев, 1986.

37. Лингвистическое обеспечение информационных систем. М.: ИНИОН АН СССР, 1987. 219 с.

38. С.Dolçga. Pecet uczy siç czytac. CHIP,1998,№11,s.228-233.

39. А.А.Черепицкий. Применение методов групповой обработки текстов для поиска и исправления ошибок// С-Петербургск.гос. электротехн.ун-т. -СПб.-1999.-9с.: ил.- Деп.в ВИНИТИ 2389-В99.

40. A.Czerepicki, О.Dyczkowska-Uss. Przygotowanie tekstów do slowników komputerowych // Materialy konferencji „Ksiazki multimedialne i elektroniczne w edukacji i biznesie". Prace Instytutu Maszyn Matematycznych. Warszawa, wrzesieñ 1998.

41. E.Golachowska, К.Golachowski. Zadnej pewnosci. PC Kurier, №7. Warszawa, 1997. s.64-71

42. Совпель И.В. Инженерно-лингвистические принципы, методы и алгоритмы автоматической переработки текста. Минск: ВШ, 1991.

43. Wielki slownik polsko-rosyjski/Большой польско-русский словарь. Warsawa, Wiedza Powszechna, 1998. Tom I,II.

44. A.Majkowski, A.Pajak. Skanowanie nie jest trudne. Enter, №10. Warszawa, 1999. s. 60-72.

45. J.Banasiak, J.Turyñski. Scanocerowanie. PC Kurier, 1997, №19, s.94-100.

46. Slownik Jçzyka Polskiego. Warszawa, PWN, 1996. Tom I-III.

47. W.Cienkowski. Praktyczny Slownik Wyrazów Bliskoznacznych. Warszawa, WNT, 1995.