Детали реализации Jardic Pro

Структура файла словаря Jardic Pro

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

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

  • Тип 1. Записи словарных статей. Одна запись содержит весь текст одной словарной статьи. Формат записи обычно соответствует формату исходного словаря (Jardic, EDICT, DSL и т.д.).
     
  • Тип 2. Не используется.
     
  • Тип 3. Записи хитов слов. Используются для полнотекстового поиска. Одна запись соответствует одному слову Лексикона (см. ниже). Она перечисляет все документы и все места документов, в которых встречается это слово. Запись имеет следующую структуру:
     
         <Указатель_статьи_1><Количество_хитов><Хит><Хит>...<Хит>
         <Указатель_статьи_2><Количество_хитов><Хит><Хит>...<Хит>
     
    Каждый элемент <Хит> имеет структуру:
     
         <Приоритет><Порядковый_номер_слова_в_тексте_статьи>
     
    Приоритеты хитов используются для сортировки результатов полнотекстового поиска.

Индексы используются для хранения отсортированных списков ключей (с точки зрения пользователя - списков слов), содержащих указатели на конкретные записи словарных статей. Ключи являются составными и могут содержать несколько сегментов, например: <произношение><слово><приоритет>.

В Jardic Pro предусмотрены следующие индексы:

  • Тип 1. Индекс служебных записей
         Ключ: <тип_записи>
         Данные: <указатель_служебной_записи>
     
  • Тип 101. Индекс чтений (кана или пиньин)
         Ключ: <чтение_слова><слово_в_записи_иероглифами>
         Данные: <указатель_записи_словарной статьи>
     
  • Тип 102. Индекс иероглифических слов
         Ключ: <слово_в_записи_иероглифами><чтение_слова>
         Данные: <указатель_записи_словарной статьи>
     
  • Тип 106. Индекс слов алфавитных языков
         Ключ: <слово><вес>
         Данные: <указатель_записи_словарной статьи>
     
  • Тип 110. Лексикон. Список всех слов и иероглифов
         Ключ: <слово_или иероглиф>
         Данные: <номер_в_лексиконе>
     
  • Тип 111. Список использования всех слов и иероглифов  
         Ключ: <номер_в_лексиконе>
         Данные: <указатель_записи_хитов_слова>
Элементы индексов имеют переменную длину. Индексы организованы в виде многоуровневых сбалансированных деревьев. Особенностью индекса Jardic Pro является возможность быстрого поиска документа по порядковому номеру значения ключа в индексе. На основе порядковых номеров значений ключей реализованы показ и прокрутка списков слов в программе Jardic Pro, а также работа с виртуальными индексами множества словарей.

Физическая организация файла словаря

Файл словаря Jardic Pro имеет страничную организацию. Предусмотрены следующие типы страниц:

  • Головная страница
  • Страницы таблицы распределения страниц
  • Страницы данных
  • Страницы индексов
Страницы файла идентифицируются их номерами. Соответствие номера страницы и ее физического положения внутри файла устанавливается через Таблицу Распределения Страниц (Page Allocation Table, PAT). В пределах одного файла страницы имеют фиксированный размер. Страницы данных и страницы индексов могут сжиматься. Из-за сжатия реальные позиции страниц внутри файла не кратны фиксированной величине. Номера страниц файла вместе с таблицей PAT используются для преобразования указателей адресного пространства файла в пару значений: позицию сжатой страницу и смещение данных внутри страницы.

 

Система управления данными Jardic Pro

Система управления данными Jardic Pro, называемая далее DMS (Data Management System) выполняет функции, типичные для систем индексного доступа к данным.

Доступ к страницам словарных файлов

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

  • Расчет физического положения страниц в файле
  • Распаковка сжатых страниц
  • Кеширование страниц в оперативной памяти
  • Поиск свободного места

Внешние функции DMS

Внешние функции DMS Jardic Pro обеспечивают поиск информации в словаре и заполнение его данными. Они делятся на следующие группы:

  • Управление
  • Поиск в индексе
  • Чтение данных
  • Вставка ключей в индекс
  • Массовая вставка ключей в индекс
  • Обновление индекса и данных
  • Сравнение ключей

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

Функции управления: Connect, Disconnect, CreateCursor, DestroyCursor, UseRecord, UseIndex, Compress, SetProgressProc и другие.

Функции поиска в индексе: FindEQ, FindGE, FindLE, FindLT, FindGT, FindFirst, FindLast, FindNext, FindPrevious, FindByCounter, FindByPercentage. В качестве результатов выполнения этих функций возвращаются указатель на запись (статью словаря) и порядковый номер найденного ключа в индексе.

Функции чтения данных: GetRecord.

Функции вставки в индекс: InsertRecord, InsertKey, BeginBulkInsertKey, EndBulkInsertKey, StopBulkInsertKey.

Функции сравнения ключей CompareKeys, GetCollator, GetCollatorVersion, CreateCollator0, CreateCollator1. Функции сравнения ключей экспортируются для внешнего приложения т.к. оно должны использовать тех же алгоритмы сравнения строк, что и DMS.

Индексы Jardic Pro могут содержать до нескольких миллионов значений ключей. Поэлементное заполнения индексов такого размера неприемлемо из-за того, что построение индексов одного словаря может потребовать значительного времени. Для построения индексов словарей Jardic Pro используются оптимизированные функции массового заполнения (bulk insert). Для заполнения Лексикона используется предварительная сортировка ключей в оперативной памяти. Для заполнения других индексов используется оптимизация основанная на расчете гистограммы распределения ключей "на лету". При этом шаг гистограммы выбирается таким, что количество попадающих в него ключей соизмеримо с объемом кеша DMS. Используемый в Jardic Pro алгоритм обеспечивает заполнение индекса, сжатие его страниц и запись на диск со скоростью около 0,7 млн ключей в минуту для 1,6 ГГц процессора.

Сортировка

Работа с индексами Jardic Pro, в частности поиск в индексе и вставка ключей в индекс, тесно связана с функциями сортировки ключей. Сортировка текстовых элементов ключей основана на внутренней реализации Unicode Collation Algorithm (UCA) с использованием Default Unicode Collation Element Table (DUCET). Этот алгоритм обеспечивает правильную "словарную" сортировку слов с большими и маленькими буквами, диакритикой, внутренними знаками пунктуации (дефисами, апострофами и т.д.).

В соответствии с UCA сортировка текстовых строк выполняется в 3 этапа:

  • Преобразование строк в массив Unicode Points
  • Построение массивов 3-уровневых элементов сортировки (Collation Elements, CE)
  • Обработка переменных весов
  • Сравнение массивов CE
На этапе преобразования строк в Unicode Points выполняется дополнительная настройка (tailoring). При этом происходит распознавание суррогатов Unicode, замена символов повторения японского языка на кану и иероглифы, декомпозиция корейского хангыля на чамо. Каких либо настроек для европейских языков при этом не делается. т.к. в Jardic Pro используется единый список слов для всех языков, тогда как абсолютно "правильная" словарная сортировка слов для разных европейских языков противоречива и не допускает построения общего многоязыкового индекса.

Построение массивов 3-уровневых элементов сортировки осуществляется с использованием таблицы DUCET.

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

 

Словарная оболочка Jardic Pro

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

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

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

Виртуальными являются следующие списки слов:

  • Список слов по чтению (произношению)
  • Список слов по иероглифам
  • Список обычных слов
  • Лексикон

Некоторые отображаемые списки строятся только в оперативной. Это, в частности:

  • Список результата перевода иероглифического текста [под курсором]
  • Список результатов полнотекстового поиска
  • Список выбранных словарных статей
  • История отображения словарных статей

В отличие от других словарных программ Jardic Pro отображает списки, состоящие из нескольких колонок. Так, например, список слов по их чтению содержит 3 колонки: чтение слова, запись слова иероглифами, начало словарной статьи. Для отображения строк списка программа выполняет поисковые запросы к индексам словаря и запросы на чтение словарных статей. Благодаря эффективной реализации DMS эти запросы выполняются достаточно быстро, так что даже ручная "прокрутка" списка из нескольких миллионов строк с помощью скроллбара выполняется без заметного замедления.

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

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

Jardic Pro может искать переводы слов "на лету" под курсором в окнах MS Word и MS HTML (включая Internet Explorer и т.д.). Доступ к словам MS Word, точнее, к его объектной модели, осуществляется средствами COM Automation через Running Object Table (ROT). Доступ к объектной модели MS HTML осуществляется с помощью интерфейса IHTMLDocument2, полученного через Microsoft Active Accessibility (MSAA).

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

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

Полнотекстовый поиск выполняется следующим образом.

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

  • Определяется индекс каждого поискового слова (иероглифа) в Лексиконе словаря
  • Для первого поискового слова: Через индекс использования всех слов (см.выше Индекс 111) читается запись со списком указателей словарных статей и хитов этого слова (запись типа 3).
  • Для каждого следующего поискового слова: Через индекс использования всех слов читается запись со списком указателей словарных статей и хитов этого слова. Результат чтения "мёрджится" (находится пересечение множества указателей словарных статей) с предыдущим результатом.
  • Рассчитывается приоритет каждой найденной словарной статьи, в котором учитываются:
    • Длина непрерывной последовательности слов или иероглифов в том порядке, в котором они набраны для поиска
    • Приоритеты слов в статьях, указанные в записях хитов

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

Импорт словарей

Импорт одного словаря выполняется в несколько шагов:

  1. Загрузка текстов словарных статей (записей типа 1)
  2. Построение индекса заголовочных слов по чтению (по кане или пиньину) (индекс 101)
  3. Построение индекса заголовочных иероглифических слов (индекс 101)
  4. Построение индекса заголовочных слов алфавитных языков (индекс 106)
  5. Построение в оперативной памяти списка слов Лексикона и записей хитов слов. При этом автоматически рассчитывается приоритет каждого слова в словарной статье, исходя из его положения в этой статье (присутствие в заголовке, в скобках, в записи курсивом и т.д.). Рассчитанный приоритет используется при полнотекстовом поиске.
  6. Загрузка индекса Лексикона (индекс 110)
  7. Загрузка записей хитов слов (записей типа 3)
  8. Загрузка индекса с указателями на записи хитов слов (индекс 111)

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

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

Программы Jardic Pro написаны на C++. Объем исходного текста программ составляет более 90 000 строк.

Copyright © Загребельный В.А., 2007-2013 E-mail: jardic@jardic.ru