Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,916

SOFTWARE FOR PROCESSING LARGE TEXT ARRAYS ON THE EXAMPLE OF THE NATIONAL CORPORA OF THE CHUVASH LANGUAGE

Zheltov P.V. 1
1 FGBOU VPO «ChGU of I.N. Ulyanov»
При создании национальных лингвистических корпусов требуется обработка больших текстовых массивов с целью лингвистического и экстралингвистического анализа и организации быстрого поиска в создаваемой базе данных. В статье рассматривается организация быстрого поиска, реализуемая с помощью создания индексных файлов и хэширования. Создание индексных файлов требует наличия ключевых полей в таблицах базы данных. При поиске по индексным файлам используется один из алгоритмов быстрого поиска. Для технологии хэширования, разработанной для национального корпуса чувашского языка, создана структура хэш-массива на языке Object Pascal в среде программирования Delphi. Хэширование производится по первым двум буквам. Оптимальным для лингвистических корпусов является комбинированный способ организации поиска, когда словарь лингвистического корпуса хранится в хэш-массиве, а остальные таблицы базы данных, на которые он ссылается, индексируются.
The creation of national linguistic corpora needs processing of large text arrays for the purposes of the linguistic and extralinguistic analysis and the organization of quick search in the created database. The organization of the quick search is realized by means of creation of index files and hashing. Creation of index files requires existence of key fields in the tables of a database. For the search in the index files one of the algorithms of the quick search is used. For the technology of hashing for the national corpora of the Chuvash language by us was developed a structure of a hash array in the Object Pascal language in the environment of programming of Delphi. Hashing is made by the first two letters. For linguistic corporas the combined way of the organization of search when the dictionary of the linguistic corpora is stored in a hash array, and other tables of a database on which it refers are indexed is optimal.
hashing
quick search
index file
national corpara of the chuvash language
hash array
linguistic corpora

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

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

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

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

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

Таблица 1

«Словарь»

Слово

Текст

Позиции

книга

1,2,3,…

1,2,100,104,105,200

о книге

1,2,3,…

7,8,100

Таблица 2

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

Текст

Информация

1

 
   

Таблица 3

«Текст 1»

Позиция

Тип

1

1

2

3

Таблица 4

«Тип»

Тип

МорфИнформация

1

<сущ., од., с.р., им.п.,ед.ч.> ед.ч.>

2

<сущ., од., с.р., им.п.,ед.ч.>

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

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

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

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

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

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

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

Опишем теперь технологию хэширования, разработанную для национального корпуса чувашского языка. Для этого разработана структура хэш-массива следующего вида на языке 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.