Scientific journal

Modern high technologies

ISSN 1812-7320

"Перечень" ВАК

ИФ РИНЦ = 0,940

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

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

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

Морфологические характеристики, которые соответствуют каждому конкретному типу, содержатся в табл. 4 «Тип» в поле «МорфИнформация». Табл. 2 «Текст-Информация», табл. 3 для каждого текста содержит экстралингвистическую информацию, такую как фамилия, имя и отчество автора, название книги/текста, том, год издания, место издания, название издательства, количество страниц книги/текста [1, 6].

Единственной проблемой, которая возникает при индексировании табл. 1 «Словарь» по полю «Слово», является омонимия, когда в поле «Слово» могут быть две одинаковые записи, например слова «лук» (растение) и «лук» (оружие). Эта проблема, однако, разрешима, если омонимы относятся к одной и той же части речи (как в упомянутом примере). В этом случае в словарь можно включать только один из омонимов, точнее просто слово, общее для обоих значений.

Таблица 1

«Словарь»

Таблица 2

«Текст-Информация»

Таблица 3

«Текст 1»

Таблица 4

«Тип»

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

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

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

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

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

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

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

Опишем теперь технологию хэширования, разработанную для национального корпуса чувашского языка. Для этого разработана структура хэш-массива следующего вида на языке Object Pascal в среде программирования Delphi [2, 9].

type

ArrayofLength Pointer=array[1..36] of array [1..36] of array [1..20] of array [0..1000] of string;

Хэширование производится по первым двум буквам, общее число букв в чувашском алфавите равно 36, максимальная длина слова не превышает 20 символов, а число слов, если произвести их сортировку по длине по спискам, для самого большого по объему современного словаря чувашского языка (таковым является 17-томный словарь чувашского языка Н.И. Ашмарина) не будет превышать 1000 слов для каждого из списка.

Хэш-массив типа ArrayofLength Pointer может вмещать 36×36×20×1000 = = 25 млн 920 тыс. слов. Такая избыточность необходима потому, что словарь лингвистического корпуса содержит слова в измененном виде, т.е. все парадигмы того или иного слова обычного словаря, в котором существительные, прилагательные, числительные, местоимения и послелоги приведены в основном падеже, так же как и причастия, а глаголы представлены в виде глагольных основ.

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

В настоящее время в чувашском языкознании до сих пор нет единого мнения относительно правил слитного или раздельного написания словосочетаний типа арçын ‘мужчина’ (букв. ар ‘муж’ + çын ’человек’).

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

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

Однако на практике в живом языке их количество меньше в два-три раза, поэтому подобная размерность хэш-массива для практических целей вполне обоснована [3, 4].

Опишем функции, созданные для хэширования. Функция Ord-Char, которая возвращает порядковый номер буквы по алфавиту и нужна для хэширования словаря и быстрого поиска в словаре, выглядит следующим образом:

function Ord_Char(ch: char): integer;

// алфавит чувашского языка

const Alphabet: array [1..36] of char=('а', '?', 'б', 'в', 'г', 'д', 'е', '?', 'ж', 'з', 'и', 'й', 'к', 'л', 'м', 'н', 'о', 'п', 'р', 'с', 'ç', 'т', 'у', 'ÿ', 'ф', 'х',' ц', 'ч', 'ш', 'щ', 'ъ', 'ы', 'ь', 'э', 'ю', 'я');

var i: byte;

begin // по умолчанию, в случае отсутствия символа в алфавите

Ord_Char:=-1; //поиск символа в алфавите

for i:=0 to length(Alphabet)-1 do

begin if Ch=Alphabet[i] then begin //символ найден

Ord_Char:=i; break;

end; end; end;

Функция Ord-Char возвращает значение – 1, если символ ch не является символом алфавита, в противном случае, если символ найден в словаре, возвращает его порядковый номер.

Процедура ProcessDictionary, которая распределяет хэш-адреса и создает из таблицы словаря DictionaryTable хэш-массив LengthPointe,r выглядит следующим образом:

procedure ProcessDictionary(var DictionaryTable: TTable;

var LengthPointer: ArrayofLengthPointer);

var lexem: string;

L,lexemLength,OrdCharl1,OrdCharl2,c: integer;

l1,l2: char;

begin ClearLengthPointer(LengthPointer);

DictionaryTable.First;

while not(DictionaryTable.Eof) do

begin lexem:=DictionaryTable.FieldValues[‘LEXEM’];

if lexem<>’’ then

begin l1:=lexem[1]; l2:=lexem[2];

lexemLength:=length(lexem);

OrdCharl1:=Ord_Char(l1);

OrdCharl2:=Ord_Char(l2);

Val(LengthPointer[Ord_Char(l1)][Ord_Char(l2)][lexemLength] [0],L,c);

Str(L+1,LengthPointer[Ord_Char(l1)][Ord_Char(l2)][lexemLength][0]);

LengthPointer[Ord_Char(l1)][Ord_Char(l2)][lexemLength][L+1]:=lexem; end;

DictionaryTable.Next; end; end;

Функция быстрого поиска в словаре, который уже загружен в хэш-массив LengthPointer, называется QuickFoundDictionary и выглядит следующим образом:

function QuickfoundDictionary (s: string; var LengthPointer: ArrayofLengthPointer):boolean;

var i,l,k,c: integer; lexem: string;

begin QuickfoundDictionary:=false;

DictionaryTable.First; l:=1;

Val(LengthPointer[Ord_Char(s[1])][Ord_Char(s[2])][length(s)][0],k,c);

for i:=1 to k do

begin

lexem:=LengthPointer[Ord_Char(s[1])][Ord_Char(s[2])][length(s)][i];

if s=lexem then begin QuickfoundDictionary:=true;

break;

end; end; end;

Процедура очищения хэш-массива ClearLengthPointer выглядит следующим образом:

procedure ClearLengthPointer(var LengthPointer: ArrayofLengthPointer);

var i,j,k: integer;

begin for i:=0 to 32 do

begin for j:=0 to 32 do

begin for k:=1 to 20 do

begin Str(0,LengthPointer[i][j][k][0]);

end; end; end; end;

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

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

Публикация подготовлена в рамках поддержанного РГНФ научного проекта № 15-04-00532.