Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,916

ПРОГРАММНЫЕ СРЕДСТВА ОБРАБОТКИ БОЛЬШИХ ТЕКСТОВЫХ МАССИВОВ НА ПРИМЕРЕ НАЦИОНАЛЬНОГО КОРПУСА ЧУВАШСКОГО ЯЗЫКА

Желтов П.В. 1
1 ФГБОУ ВПО «ЧГУ им. И.Н. Ульянова»
При создании национальных лингвистических корпусов требуется обработка больших текстовых массивов с целью лингвистического и экстралингвистического анализа и организации быстрого поиска в создаваемой базе данных. В статье рассматривается организация быстрого поиска, реализуемая с помощью создания индексных файлов и хэширования. Создание индексных файлов требует наличия ключевых полей в таблицах базы данных. При поиске по индексным файлам используется один из алгоритмов быстрого поиска. Для технологии хэширования, разработанной для национального корпуса чувашского языка, создана структура хэш-массива на языке Object Pascal в среде программирования Delphi. Хэширование производится по первым двум буквам. Оптимальным для лингвистических корпусов является комбинированный способ организации поиска, когда словарь лингвистического корпуса хранится в хэш-массиве, а остальные таблицы базы данных, на которые он ссылается, индексируются.
хэширование
быстрый поиск
индексный файл
национальный корпус чувашского языка
хэш-массив
лингвистический корпус
1. Желтов В.П., Желтов П.В., Губанов А.Р. Морфологический стандарт национального корпуса чувашского языка // Современные проблемы науки и образования. – 2015. – № 2; URL: www.science-education.ru/122-20578 (дата обращения: 19.11.2015). Публикация подготовлена в рамках поддержанного РГНФ научного проекта № 15-04-00532.
2. Желтов П.В. Лингвистические процессоры, формальные модели и методы: Теория и практика. – Чебоксары: Издательство Чувашского университета, 2006. – 208 с.
3. Желтов П.В. Лингвистические сети для представления схем следрвания аффиксов. // Вестник чувашского университета. – 2006. – № 2. – С. 297–303.
4. Желтов П.В. Модели и алгоритмы в лингвопроцессорах. // Вестник чувашского университета. – 2005. – № 2. – С. 297–303.
5. Желтов П.В. Моделирование причинно-следственных отношений в тексте с помощью сетей Петри // Современные проблемы науки и образования. – 2015. – № 2; URL: www.science-education.ru/122-21173 (дата обращения: 19.11.2015). Публикация подготовлена в рамках поддержанного РГНФ научного проекта № 15-04-00532.
6. Желтов П.В. Создание национального корпуса чувашского языка: проблемы и перспективы // Современные проблемы науки и образования. – 2015. – № 1; URL: www.science-education.ru/121-19046 (дата обращения: 19.11.2015). Публикация подготовлена в рамках поддержанного РГНФ научного проекта № 15-04-00532.
7. Желтов П.В., Семенов В.И., Трофимова А.И., Шурбин А.К. Алгоритмы идентификации фонем и формирования слова в системах распознавания речи на основе вейвлет-преобразования / Вестник чувашского университета. – Чебоксары, 2014. – № 2.
8. Pavel Zheltov. Morphological markup system for the national body of the Chuvash language. Processings of the International Conference «Turkic Languages Processing: Turklang-2015». – Kazan: Academy of Sciences of the Republic of Tatarstan Press, 2015. – 488 c. (328 стр.) имеется ссылка на грант Публикация подготовлена в рамках поддержанного РГНФ научного проекта № 15-04-00532.
9. Zheltov P., Fomin E., Luutonen J. Reverse Dictionary of Chuvash. Обратный словарь чувашского языка. Societe Finno-Ougrienne, 344, 2009.

При создании национальных лингвистических корпусов требуется обработка больших текстовых массивов с целью лингвистического и экстралингвистического анализа и организации быстрого поиска в создаваемой базе данных. Организация быстрого поиска реализуется с помощью создания индексных файлов или хэширования. Создание индексных файлов требует наличия ключевых полей в таблицах базы данных. Если их нет, то необходима либо реорганизация таблицы, т.е. реорганизация существующих полей таким образом, чтобы поля в каждой записи имели бы уникальную информацию, либо добавление новых полей [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: http://www.top-technologies.ru/ru/article/view?id=35371 (дата обращения: 03.06.2020).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074