При создании национальных лингвистических корпусов требуется обработка больших текстовых массивов с целью лингвистического и экстралингвистического анализа и организации быстрого поиска в создаваемой базе данных. Организация быстрого поиска реализуется с помощью создания индексных файлов или хэширования. Создание индексных файлов требует наличия ключевых полей в таблицах базы данных. Если их нет, то необходима либо реорганизация таблицы, т.е. реорганизация существующих полей таким образом, чтобы поля в каждой записи имели бы уникальную информацию, либо добавление новых полей [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.
Библиографическая ссылка
Желтов П.В. ПРОГРАММНЫЕ СРЕДСТВА ОБРАБОТКИ БОЛЬШИХ ТЕКСТОВЫХ МАССИВОВ НА ПРИМЕРЕ НАЦИОНАЛЬНОГО КОРПУСА ЧУВАШСКОГО ЯЗЫКА // Современные наукоемкие технологии. – 2015. – № 12-5. – С. 786-789;URL: https://top-technologies.ru/ru/article/view?id=35371 (дата обращения: 20.04.2024).