Методы и алгоритмы семантического информационного поиска в печатных текстах на языках тибето-бирманской группы (на примере бирманского языка) тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Нэй Лин

• Нэй Лин
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Нэй Лин

ВВЕДЕНИЕ

Глава1. Информационный поиск (ип) и онтология

1.1 Модели информационного поиска

1.1.1 Информационный поиск на бирманском языке

1.1.2 Кластеризация документов в информационном поиске

1.1.3 Оценки эффективности ИП-модели

1.2 Проблемы автоматического создания словарного файла для бирманского языка

1.3 Онтология

1.3.1 Модель интеллектуальной информационно-поисковой системы на основе онтологии

1.3.2 Онтологические ресурсы

1.4 Обзор существующих методов кластеризации документов и подходов к бирманскому информационному поиску

1.5 Постановка задачи созданиямодели и алгоритмов информационного поиска на основе лингвистических онтологий

1.6 Вывод по главе

Глава 2. Использование wikipediaкак онтологии для обработки текста

2.1 Создание иерархической онтологии на основе Википедии (ВИО)

2.2 Кластеризации документов на основе онтологии

2.3 Разрешение лексической многозначности (Word Sense Disambiguation -WSD) и семантические отношения между текстами, которые используют Википидеа и WordNet

2.4 Вывод по главе

Глава 3. Использование метода сжатия информации в семантическом

информационном поиске

3.2 Байт-ориентированный метод Хаффмана

3.3 End Tagged Dense Code (ETDC)

3.4 Использование метода сжатия в семантическом информационном поиске

3.6 Вывод по главе

Глава 4. Сжатие текста длябирманскогоинформационого поиска на основе

лингвистической онтологии

4.1 Бирманский языки сегментация

4.1.1 Сегментация слогов

4.1.2 Слова и их разделение

4.2 Предлагаемая модель для автоматического генерирования файла словаря

4.3 Оценка автоматическогогенерирования файла словаря для бирманского информационного поиска

4.4 Проблемы словарногофайла для бирманского информационного поиска

4.5 Оптимизация словаря для бирманского информационного поиска

4.6. Оценка результатов оптимизации словаря

4.7 ПрименениеETDC к информационному поиску на бирманском языке

4.8 Результаты эксперимента

4.9 Проблемы семантического информационного поиска на бирманском языке

100

4.9.1 Расширение запросов с использованием WordNet

4.10 Применение сжатия информационного поиска для бирманского языка на основе онтологии

4.11 Экспериментальные результаты

4.12 Выводы по главе

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

Введение диссертации (часть автореферата) на тему «Методы и алгоритмы семантического информационного поиска в печатных текстах на языках тибето-бирманской группы (на примере бирманского языка)»

ВВЕДЕНИЕ

Актуальность темы. В настоящее время в связи с огромными объемами электронных документов имеется все возрастающая потребность в обработке неструктурированной текстовой информации, повышении качества и эффективности имеющихся методов обработки текстов с целью принятия решений в различных областях. В число активно развивающихся направлений обработки неструктурированной текстовой информации входят такие задачи, как собственно поиск информации, фильтрация, рубрикация и кластеризация документов, поиск ответов на вопросы, автоматическое аннотирование документа и группы документов, поиск похожих документов и дубликатов, сегментирование документов, машинный перевод многое другое. Кластеризация документов и информационный поиск осуществлябтся обычно на основе синтаксической, а не семантической информации. Для решения этой проблемы возможно использовать онтологии. Но трудно найти всеобъёмлющую онтологию, охватывающую всё области человесеских знаний и деятельности.

Язык Мьянмы (бирманский язык) является официальным языком Республики Союза Мьянмы. Его используют 53 миллиона жителей Мьянмы. Бирманский язык относится к тибето-бирманским языкам. Слова бирманского языка округлой формы и пишутся слева направо. Между словами нет интервалов, которые могли бы использоваться для разделения фраз и слов. Но для бирманского языка в настоящее время доступно малое число инструментов компьютерной обработки текста.

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

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

В работах Aye Myat Mon, Soe Lai Phyue, Myint Myint Thein, Su Su Htay and Thinn Thinn Win, Pann Yu Mon and Yoshiki Mikami, W.P. Pa, Y.K. Thu, Thet Tun-Thura, Jin-Cheon Na и многих других обсуждались вопросы улучшения качества сегментации слов бирманского языка. Все авторы используют словарь или учебный набор данных для сегментации, что приводит к снижению точности при поиске информации.

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

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

Область исследования. Содержание диссертации соответствует паспорту специальности 05.13.17 - «Теоретические основы информатики» по следующим областям исследования:

3. Исследование методов и разработка средств кодирования информации в виде данных. Принципы создания языков описания данных, языков манипулирования данными, языков запросов. Разработка и исследование моделей данных и новых принципов их проектирования.

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

Предмет исследования: методы и алгоритмы семантического информационного поиска.

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

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

Для решения научной задачи и достижения цели исследования были определены задачи диссертационного исследования:

1. Разработка методов кластеризация документов по семантическому значению на бирманском языке.

2. Разработка метода информационного поиска для бирманского языка с использованием сжатия.

3. Разработка алгоритма автоматического создания словаря для информационного поиска на бирманском языке.

4. Разработка метода сегментации бирманских слов с помощью локального набора статических данных без использования какой-либо дополнительной информации.

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

что позволяет осуществлять кластеризацию документов, уменьшая время на поиск.

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

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

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

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

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

Практическая значимость работы определяется в доведении предложенных теоретических и алгоритмических конструкций информационного поиска до уровня программных средств, что подтверждается свидетельством о государственной регистрации программы для ЭВМ «Программа для информационного поиска на бирманском языке с использованием сжатия текста» (Свидетельство о государственной регистрации программы для ЭВМ № 2019613510. Нэй Лин (18.04.2019)).

Научные положения, выносимые на защиту:

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

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

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

4. Метод расширения запросов на бирманском языке, основанный на технологии WordNet, что позволило построить семантическую модель информационного поиска на бирманском языке.

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

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

Апробация результатов диссертационного исследования. Результаты диссертационных исследований обсуждались на следующих научно-технических конференциях: 2019 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (2019 EICONRUS) (Санкт Петербург, 2019 г.), 3rd International Conference on Natural Language Processing and Information Retrieval (Tokushima, Japan, 2019 г.), 2020 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (2020 EICONRUS) (Санкт Петербург, 2020 г.), II Международной научно-практической конференции «Передовые научно-технические и социально-гуманитарные проекты в современной науке» (Москва, 2018 г.), V Международной научно-практической конференции «Наука России: Цели и задачи» (Москва, 2017 г.), Международной научно-практической конференции «Воздействие научно-технической революции на характер связи

науки с производством» (Уфа, 2017), Международной научно-практической конференции «Проблемы разработки перспективных технологических систем» (Уфа, 2017), Международной научно-практической конференции «Физико-математические и технические науки как постиндустриальный фундамент эволюции информационного общества» (Уфа, 2017), XIV Международной научно-практической конференции «Российская наука в современном мире» (Москва 2018 г.).

Публикации. По теме диссертационного исследования опубликовано 14 печатных работ (из них 4 - в рецензируемых журналах из перечня, рекомендованного ВАК РФ, и 3 в SCOPUS), в том числе получено свидетельство Роспатента РФ о государственной регистрации программы для ЭВМ.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения и приложений. Работа изложена на 174 страницах машинописного текста, включая 51 рисунка, 28 таблиц и список литературы из 86 наименований.

Глава 1. Информационный поиск (ип) и онтология

Дисциплина, которая занимается поиском неструктурированных данных, называется информационным извлечением. ИП - это процесс поиска всех соответствующих документов, отвечающих на запрос и состоящих в основном из неструктурированных текстовых данных (в работе T. Berners-Lee [1]). Информационный поиск касается релевантных информационных позиций, учитывая конкретные информационные потребности пользователей, поскольку проблемы с поиском присутствуют в различных средах, таких как всемирная паутина, корпоративные базы знаний или даже персональные рабочие столы, P. Sorg [2].

Информационный поиск фокусируется на извлечении документов на основе содержания их неструктурированных компонентов. Запрос ИП может содержать желаемые характеристики как для структурированных, так и для неструктурированных компонентов документа, подлежащих извлечению, например, «документы должны быть об «Информационном поиске», а их автором должно быть «Smit». В этом примере запрашиваются документы, чье содержание (неструктурированная часть) является схожим с заданной темой, а автор (структурированная часть) соответствует заданному значению» [3].

Рисунок 1.1 - Модель информационного поиска

На рисунке 1.1 показаны различные компоненты ИП-процессов: индексирование, обработка запросов и сопоставление. Информационный поиск является одним из приложений обработки естественного языка (МЬР). Он имеет три основных процесса: индексирование, обработка запросов и сопоставление (поиск и ранжирование). На первом этапе документы индексируются с использованием ключевых слов, которые соответствуют каждому документу в коллекции (в работе М. р. БЬаШаш [4]). На втором этапе запросы реконфигурируются, чтобы соответствовать модели подхода к поиску информации [5]. Наконец, на третьем этапе запрос будет сопоставляться с индексом, а согласованный документ извлекается и оценивается на основе его сходства с запросом. На рисунке 1.2 показан ИП-процесс, а именно два основных процесса (индексирование и поиск). В процессе индексирования термин будет извлекаться из документов и храниться в инвертированном индексе [6]. В процессе поиска пользователь создает запрос и извлекает термины из полученного запроса. Таким образом, для проведения поиска в иформационной системе необходимо провести индексирование. Наконец, результаты сопоставления между инвертированным индексом и запросом будут сортироваться на основе алгоритмов ранжирования.

Информационные символы, извлеченные из коллекций алгоритмами анализа, хранятся и управляются модулем индексации. Построение индекса из коллекции документов включает в себя несколько шагов: от сбора и идентификации фактических документов до создания окончательного индекса (в работе КВ.Оопга^ [7]).

Сегментация слова

Рисунок 1.2 - Процесс информационного поиска

Основным элементом механизма индексирования является инвертированный индекс, в котором перечислены информационные символы и все документы, содержащие этот символ. На эффективность индексов влияют несколько аспектов дизайна: сжатие индекса, уменьшающее использование памяти; структурированные индексы дерева или индексы на основе хэшей, позволяющие более быстрый поиск таблицы индексов; сортировка документов ввода индекса ограничивает количество анализируемых документов (в работе J. Magalhaes [8]).

Не все части информационного поиска одинаково важны для представления его значения. Например, в письменном языке некоторые слова несут больший смысл, чем другие. Поэтому обычно считается целесообразным предварительно обработать информационные элементы, чтобы выбрать такие, которые будут использоваться в качестве объектов индекса. Индексы представляют собой структуры данных, которые создаются для ускорения поиска. Целесообразно построить и поддерживать индекс, когда коллекция предметов большая и полустатическая. Наиболее распространенной структурой индексирования для поиска текста является инвертированный файл. Словарь -это набор всех слов в тексте. Для каждого слова в словаре сохраняется список всех текстовых позиций, где отображается слово. Набор все х этих списков называется вхождениями (в работе R.B. González [7]).

Пользовательские запросы сопоставляются с условиями индексирования. В результате этой операции пользователю возвращается набор информационных элементов (в работе P. Pathak [9]). Согласование происходит на основе набора ролей между потребностями пользователя и информационными технологиями. Таким образом, набор информационных элементов, возвращаемых сопоставлением, является неточным. Поэтому на этапе согласования нужны некоторые алгоритмы для сортировки результата, этот шаг называется ранжированием.

1.1 Модели информационного поиска

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

13

проблему ИП в вероятностной структуре. Основная идея заключается в следующем. Учитывая запрос q и набор документов D, предполагается, что существует подмножество R из D, которое содержит точно соответствующие документы для q (идеальный набор ответов). Затем вероятностная модель поиска ранжирует документы в порядке убывания вероятности принадлежности к этому множеству (т. е. относится к информационной потребности), которая обозначается как

Р (R | q,dj), (1.1)

где dj - документ в D.

Булевы модели рассматривают пользовательский запрос ввода как выражение, описанное булевой логикой. В случае логической модели поиска релевантность является двоичной и вычисляется путем сопоставления двоичных векторов, представляющих появление термина в запросе [2]. Булевы модельные алгоритмы (AND-И) описываются следующим образом:

Для каждого термина запроса t:

• Получить запись лексики для t

• Примечание и адрес этого It (перевернутый список)

• Сортировать условия запроса, увеличив/с

• Инициализировать набор кандидатов C с помощью It термина с наименьшим ft

Для каждого оставшегося t:

• Читать/С

• Для каждого d Е С, ifd £It,C < — С-{d}

• IfC = {}, return... не существует релевантных документов

• Посмотреть каждый dc^ вернуться к пользователю [7].

Модели векторного пространства основаны на представлении векторных пространств документов. Термины хранятся в матрице терминальных

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

• Временная частота tf в документе^ (t).

• Частота документа df, условия запроса df (t).

• Количество документов в коллекциях D.

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

Нечеткая модель, или вероятностная модель. Хотя модель вероятностной индексации была предложена и проверена Мароном и Кунсом (1960), основная вероятностная модель, используемая сегодня, была разработана Робертоном и Спарком Джонсом (1976) (в работе W.B Croft [11]).

Рбжиншык докумкшш

+ -

+ г n-r N

- R-r N- n- R + г N-n

R N-R N

Рисунок 1.3 - Индекс в нечеткой модели (Ы - количество документов в

коллекции, Я - количество соответствующих документов

для запроса q, п - количество документов с термином ^г -количество соответствующих документов, имеющих срок ^

Эта модель основана на предположении, что ранее полученные релевантные документы для данного запроса должны иметь больший вес, чем если бы они не появились в соответствующих документах. В частности, Робертон и Спарк Джонсон представили следующую таблицу, показывающую распределение термина t в соответствующих и не относящихся к делу документах для запроса q .

Затем они используют эту таблицу для получения четырех формул, которые отражают относительное распределение терминов в соответствующих и не относящихся к делу документах, и предлагают использовать эти формулы для взвешивания (журналы связаны с фактическим использованием формул в терминах) (в работе Капта Мейо^ [12]).

1.1.1 Информационный поиск на бирманском языке

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

Мьянма (Бирма) - это страна с населением около 53 миллионов человек, в которую входят 135 этнических групп, говорящих на своем родном языке или диалектах. Среди них язык мьянма (бирма), на котором говорят более 30 миллионов человек в качестве их первого языка, который также является официальным языком, используемым в административной, судебной и

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

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

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

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

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

В отличие от этого при поиске слов бирмы в общем поисковике он ведет себя, как «поиск по фразе» в поиске на английском языке. То есть помещение двойных кавычек («») вокруг запроса предлагает поисковым системам рассматривать точные слова в точном порядке без каких-либо изменений. Например, документ «А» содержит составное слово бирмы XYZ, а документ «В» содержит все компоненты слова XYZ непоследовательным образом, например, «X... Y... Z». Если пользователь ищет запрос XYZ, поисковая система извлекает документ А, но не извлекает документ В, поскольку поисковая система не выполняет сегментацию слов. Вот почему необходим особый подход для поисковой системы бирмы, что, в свою очередь, требует ввести процесс сегментации слова как на этапе индексации, так и на этапе обработки входного ключевого слова.

Рисунок 1.4 - Архитектура информационного поиска на бирманском языке

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

1.1.2 Кластеризация документов в информационном поиске

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

Список литературы диссертационного исследования кандидат наук Нэй Лин, 2020 год

список

Подкате гогия

footballers Association football forwards

cateyocics: pyei births Living people People fiom Funchai Portuguese Roman Catholics I Assoc uniorl football wingers Pnmrtra Liga player* Sporting CP footballers Premier League players Manchester United F.C. players La Uga players

Real Madrid C.F. players Portugal youth international footballers Portugal urtder-21 international footballers Portugal international footballers UEFA Euro 2004 players

Рисунок 2.1 - Фрагмент страницы CristianoRonaldo из Википедии

Википедия имеет иерархическую структуру, то есть состоит из категорий и подкатегорий, которые могут включать в себя другие подкатегории и статьи. Например, статья про Криштиано Роналдо включается в категорию Portuguese-Footballer, которая является подкатегорией PortugueseSportsPeople.

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

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

«CristianoRonaldodissentsAveiro [[orderofprinceHenry| GOIH]], [[orderof-merit(Portugal) | ComM] isaPortugueseprofessional [[footballer]].»

В этом предложении слова «orderofprinceHenry» и «orderofmerit (Portugal)» создают ссылку на соответствующие статьи. Если значение идентификатора статьи совпадает со словом-ссылкой, то слово указывается в двойных скобках, например, [[footballer]]. Если название статьи не совпадает с названием ссылки, то тогда связь указывается с помощью разделителя, например, «GOIH» связывается со статьей «OrderofprinceHenry» с помощью следующего значения: [[orderofprinceHenry| GOIH]].

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

Read Edit View history | search Wikipedia

WikipediA

Ihe free EjuucIo pedia

Main page Contents Featured content Current events Random article Donate to Wikipedia Wikipedia store

Interaction Help

About Wiki pedia Community pcrtal Recent changes Contact page

Tools

What li nlks here Related changes

Burma

From Wikipedia, the free encyclopedia Redirect page

Myanmar

L—». This page is a redirect:

» From a page move: This is a redirect from a page that has been moved (renamed). This page was kept as a redirect to avoid breaking links, both internal arid external, that may have been made to the old page name.

» From historic name: This is a redirect from a title that is another name, a pseudonym, a nickname, or a synonym that, more than just a "former name", has a significant historic past. For example, a region, state, principate's holding, city, city-state or such, and the subject has been subsumed into a modem era municipality, district or state, or otherwise has experienced a name change.

• This redirect leads to its target in accordance with the naming conventions for common names and can help writing. However, do not replace this type of redirected link with a piped link unless the page is updated for another reason.

• From a printworthy page title: This is a redirect from a title that would be helpful in a printed or CD/DVD version of Wikipedia.

Men appropriate, protection levels are automatically sensed, described and categorized.

Рисунок 2.2 - Перенаправление на страницу «Мьянма»

В Wikipedia имеется возможность устранения неоднозначности страницы (disambiguation page) для неоднозначных слов. На этой странице представляются списки других определений неоднозначных слов. Для того чтобы посмотреть другие определения неоднозначных слов возможен переход через ссылку. Например, machine(disambiguation) - это неоднозначная страница, на которой существует список разных определениях машины. Уникальные идентификаторы для disambiguation page представляет disambiguation слово в скобках. Например - Machine (disambiguation) page -это уникальный идентификатор для страницы disambiguation of Machine (рисунок 2.3).

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

На страницах статей существуют ссылки на остальные языки, поэтому можно перейти от статьи на одном языке к другому. Например, можно перейти от страницы «Machine» на английском к русской странице «Машина».

Article Talk

WikipediA

Hí Free E»it yclopedia

Main page Contents Featured content Current events Random article Donate to Wikipedia Wikipedia store

Interaction Help

About Wikipedia Community portal Recent changes Contact page

Tools

What Jinks here Related changes Upload fi le Special pages Permanent link Page information Wikidata item Cite this page

Print/export

Machine (disambiguation)

From Wikipedia, the free encyclopedia

A machine is a device that uses energy to perform some activity or task. Machine, Machines, Machinery, The Machine, or The Machines may also refer to:

Term of art [ edit ]

More specific applications of the general term

• Machine (mechanical) using mechanical energy

• Machine (patent), one of the four statutory categories of patent-eligible subject matter under United States patent law

Computing [ edit ]

> "machine", slang for computer or Server

• Abstract machine, a theoretical model of a computer hardware or software system used in automata theory

• Turing machine, an abstract model of a computer

• Internet bot, a computer program that does automated tasks

• virtual machine, a computing machine implemented in software rather than directfy in hardware

• Machine-generated data

■ Machines (video game), a 1999 real-time strategy game for Microsoft Windows

> The Machine (computer architecture), a computer architecture project announced in 2014 by Hewlett Packard

Personal nickname [edit]

The following are nicknamed 'The Machine":

Рисунок 2.3 - Страница «Machine (disambiguation)»

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

Таблица 2.1 - Первые 13 языков и их количество статей и пользователей на конец 2017 г.

1 ООО 000+ articles

№ Î Language * Language (local) ; Wild * Articles - Total : Edits t Adinins - Uséis ' Active Uséis - Files t Depth i

1 English English á5 en 5,475,6060 43,056,862 909,392,697 1,247 31,740,332 122,052 854,420 995

2 Cebuano Sinugboanong Binisayaiá5 ceb 5,266,4320 8,840,105 15,692,661 4 3B.77B 656 0 1

3 Swedish Svenska^ sv 3,788,6430 7,604,524 40,727,823 67 56B.503 4Д0В 0 5

4 German Deutsche de 2,099,520» 5,934,207 173,552,440 197 2,71B,225 19,982 123,797 98

5 Dutch Nederlandsii? ni 1,910,7310 3,843,416 51,013,959 46 861,306 5,357 21 14

6 French Français^ fr 1,907,6180 8,957,972 143,046,169 161 2,882,897 17,167 52,452 218

7 Russian Русский <§> ru 1.420,0490 5,38B,96B 99,927,302 85 2,15B,802 12,069 202,396 145

8 Italian Italianos it 1,381,8040 4,896,725 96,443,304 112 1,552,224 9,916 137,645 127

9 Spanish Españolé? es 1,353,4340 5,994,666 101,526,319 71 4,737,296 16,530 0 199

10 Waray-Waray Winarayá1 war 1,262,8840 2,874,151 6,298,150 2 33,102 427 46 4

11 Polish Pclskiá> pi 1,240,0190 2,686,301 50,259,940 104 837,892 5,690 32 25

12 Vietnamese Tiêng Viêtiá5 vi 1,160,8130 7,262,119 30,863,056 22 563,112 2,565 23,787 117

13 Japanese пш® ja 1,075,5090 3,143,517 66,447,344 47 1,246,847 14,818 84,318 78

Это описывает основную идею процесса создания Википедической иерархической онтологии.Процесс создания ВИО состоит из следующих шагов: Первым шагом в создании ВИО является построение дерева онтологии. Мы используем категории Википедии для представления концепций ВИО. На самом деле, Википедия имеет сложную структуру категорий, организованных иерархически. Эта структура не является древовидной, а скорее представляет собой ориентированный граф. Хотя у каждой категории есть связь с категорией верхнего уровня, некоторые категории наследуются от двух разных родительских категорий. Мы использовали эту структуру категорий для построения дерева ВИО.

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

• Очищение статьи: мы удаляем все виды форматирования, найденные в этой статье, такие как HTML и XML-тэги и разделяли документ на предложения.

• Удаление стоп-слов: мы удаляем стоп-слова из входных статей, используя одно из стандартных стоп-слов.

• Морфологический поиск: мы используем алгоритм генерации Porter [78] для преобразования входного текста в его основную или корневую форму. Таким образом, термины неявно преобразуются в стандартную семантическую форму, которая отражает их смысл.

2.2 Кластеризации документов на основе онтологии

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

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

Рисунок 2.4 - Кластеризация документов на основе Википидии

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

В Википидеи каждая статья имеет единственный заголовок. Таким образом, имеется сходство между ^шкьзаголовком и понятием в онтологии. Эквивалентность этих понятий позволяет использовать их для перенаправленных ссылок. Это средство структуры представляет собой иерархическую систему категоризации. Чтобы сравнивать термины текстов и понятия онтологии, надо применять строгие методы согласования. При точном

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

Xiao Hua [29] утверждает, что трудно найти комплексную онтологию, которая представляет все понятия онтологии. Другой проблемой является то, что замена и добавление свойства происходит достаточно сложно. Когда понятие онтологии заменяет исходное слово, это может привести к потере знаний. Кроме этого, добавление свойства приводит к искажению данных в базе данных.

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

При группировании документов и представлении документов [29] с использованием понятия онтологии применяются два метода.

Для группирования документов надо создать матрицу сходства между документами и понятиями категории Википедии:

• создать отношения между wiki-понятиями и wiki-категориями;

• установить вектор соответствия каждого документа с wiki-понятием;

• определить совпадающие документы и набор wiki-категорий.

Для отношения понятия - категории используют отношения между понятиями и категориями, представленными в Wiki, для отношения документ -понятие матрицы используют метод строгого согласования и метод связанное

согласования понятий в базе знаний. Для отношения документы -категории используют отношения понятие - категория и документ - категория.

При использовании метода строгого согласования сначала анализируется каждый документ и выявляются wiki-понятия. Затем строится вектор из wiki-понятий, комбинируя wiki-понятия и соответствующие документы. Главная проблема строгого согласования - синонимы. Как совпадают синонимы фраз и одиночные понятия? Когда wiki-понятия появляются в документах и дают релевантные результаты?

*ЛЛ1<1 Сй1:едагу Сопоерт""-^ САТ 1 САТ 2

С01 А А

СО 2 В А

Concept СЮситеп!: ■ , СО! СО 2

Г>1 АН А12

Е}2 Б21 А22

\Л/|к1 С^едогу Ооситег^ САТ1 САТ 2

О! VII \/\2

02 V21 422

Рисунок 2.5 - Отображение документов в концепции Wikipedia

Метод согласования связанных понятий в базе знаний работает в два шага. На первом шаге строятся матрицы wiki-статья - wiki-понятие (таблица 2.2). Каждое слово представляется как вектор понятия. Связывающее значение TF-IDF [30, 31] между wiki-понятиями и wiki-термами статьи представляет значение этого вектора. Для того чтобы уменьшить время обработки, необходимо убрать незначимые слова с помощью TF-IDF знания. Таблица 2.2 - Wikipedia термин-концепция (статья) матрица

\ Wiki-\понятия Wiki-понятия Со

\ С01 со2 С03 СОм

Wiki- \

статья \

ЖС11 ^12 ЖС13

^21 ^22 ЖС23

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

к*7' = ■ , (21)

где-йу - документы в наборе документов, Ск — понятии на Вики понятии^М-понятие ^ — каждое слово в йу .

Результат вычисления называют связанностью между документами и понятиями. Метод связанности используется, когда в wiki-понятии у слов отличные синтаксисы и одинаковые семантики.После сопоставления документов для каждых наборов документов создается матрица «документ-понятия». Применяя эту матрицу и иерархическую концепцию, создается матрица «документ - категория». Если использовать точный метод создания отношения документ - понятие, то вместо понятия осуществляем замену соответствующей категорией и затем получаем матрицу «категории -документ». Поэтому частота понятия - частота документа. Если бы документ включал более одного понятия, то сумма частот понятий представляла бы собой частоту категории.

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

характеристика документа зависит от однозначности терма и не представляет дополнительные характеристики.

В хорошем кластеревсё объекты отличаются от других объектов других кластеров. Группирование документов называется обработка данных. Кластер документов можно использовать в базе данных. Подобные документы находятся в подобном кластере. Пользователямиизвлекаются документы из похожих кластеров. Это является лучшим результатом информационного поиска.

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

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

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

Чтобы группировать подобные документы, надо определить величину различия документов. Здесь считают каждый документ, как кластер и подобные документы объединяются к единому документу. Измерение различий между двумя кластерами может быть реализовано с единой связью, полной связью и

средней связью. Когда используется полная связь и средняя связь, возникают проблемы. Максимум различия - это расстояние между документами одного кластера и другого кластера. Подобие между документами можно определить с помощью следующей формулы:

Sim(dm, dn) = sim(dm, dn)word + a. sim(dm, dn)concept + ß. sim(dm, dn)cate^ory . (2.2)

Она вычисляет подобие между документами a,ß, представленными векторами понятий и категорий.Для кластеризации на основе слово-понятие ß устанавливается на 0 и а устанавливается равным 0,1, 0,2 ... 1,0 соответственно. Мы принимаем средний результат десяти порогов в качестве окончательной кластеризации результатов для схемы слово-понятие. Для кластеризации на основе слова-категории а устанавливается на 0 и ß устанавливаются равными 0,1, 0,2 ... 1,0 соответственно. Средний результат десяти порогов используется в качестве окончательной кластеризации результатов для слова-категории. Для слова-понятия-категории а устанавливается равным значению лучшего результата для слова-понятия на основе кластеризации, и ß устанавливается на значении лучшего результата для кластеризации на основе слова-категории.

2.3 Разрешение лексической многозначности (Word Sense

Disambiguation - WSD) и семантические отношения между текстами, которые используют Википидеа и WordNet

В современном мире каждый человек использует Интернет, и увеличивается объеминформации,в которой проявляется семантическая неоднозначность слов по причине лексическоймногозначности.Это становится проблемой, когда производится поиск релевантных документов по запросу пользователей. Для решения этой проблемы существует множество методов устранения неоднозначностей, в частности Word Sense Disambiguation method, включающий 3 этапа. Первый - разработка семантических аннотаций слова и обработка на основе метода SENSEVAL [37] (http://www.senseval.org/). Этот один из известных методов устранения неоднозначностей использует WordNet

49

как семантические аннотации. Второй этап - представление предложения-документа вектором с целью вычисления семантических связей между словами.И третий этап - использование связанности между семантическими предложениями для вычисления семантической связанности между текстами.Мысчитаем, что Википидеа и WordNet можно использовать как надёжные семантические источники данных.

Предлагаемый метод для измерения семантических связностей между WSD и текстами состоит из следующих шагов.

1) предварительная обработка текста, извлечение предложений и понятий как N-gram;

2) семантическая аннотация слов из Википедии;

3) WSD (senseval);

4) использование WordNet и Википедии для расчета семантической связности между однозначеными словмип-grams;

5) для создания семантической матрицы для предложений используется модель векторного пространства и рассчитывается семантическая связь между ними;

6) использование отношений между предложениями для расчета семантической связи между текстами (абзацами).

На первом этапе производится удаление знаков пунктуации. После удаляются незначимые слова (the, a, is, and и т. д.) и специальные знаки (#, %, @ и т.д.). После этого производится синтаксический разбор слов и извлечение их как n-grams. Эти n-grams [81] имеют только фиксированную длину, но не обозначают понятия. Здесь n=1,2, 3.

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

английском языке - также мяч. Посмотрим следующие предложенные примеры из Википедии:

1. Мыши (лат.Muridae) - семействомлекопитающихотрядагрызунов;

2. Компьютерная мышь - одно изустройств вводаинформации вкомпьютер;

3. «Мышь» - сверхтяжёлый немецкий танк.

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

1. У неоднозначных слов при устранении неоднозначности на страницах не указаются отношения между синонимами. Поэтому они не могут быть связаны с другими статьями по значению. То же самое для определений терминов. Например, электронно-вычислительная машина (ЭВМ) - комплекс технических средств. Хоть в этом предложении есть прямая связь со словом «машина», это никак не связано с настоящей машиной, поэтому между этими словами в статьях не указана связь.

2. Трудно реализовать автоматическую систему устранения неоднозначностей на страницах. Потому что на страницах разные значения слов отличаются уникальной ссылкой на значение данного термина. Например, определением слова «paper» является: «Paper is a thin material produced by pressing together moist fibers of cellulose pulp derived from wood, rags or grasses, and drying them into flexible sheets», иприустранениинеоднозначностейполучается «Paper is a thin, flat material produced by the compression of fibers».

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

Для вычленения неоднозначных семантических составляющих слова выполняются следующие шаги:

• Извлекаются образы от Wiki как ссылка или гиперссылка, или ссылка, в которую включаются неоднозначные слова. На основе этихсегментов выбираются абзацы. Создается список строк по абзацам.

• Извлекаются самые левые компоненты ссылок от слов, оформленные абзацами, и собираются метки для неоднозначных слов. Например, гиперссылка [[mathematicaljball]] -слово «mathematical» - это метка для слова «ball». У некоторых слов нет гиперссылки [ball]. Таким образом, для слова [ball] само служит меткой.

• Собираются метки как семантические слова и присоединяются к одинаковым семантическим термам. Затем производится согласование метки и его соответствующих значений в WordNet, чтобы создать семантический отмеченный корпус. В таблице 2.3 показано согласование Wiki аннотации и значении WordNet для слова «ball». Но здесь еще существуют некоторые сложности. Некоторым метки нельзя прямо использовать как значение,потому что некоторые слова неоднократно используются в метках.Например, метки «at-mosphereofearth» и «atmosphereofMars». У них есть общее значение «atmosphere». Но в разных метках. Поэтому надо заниматься кластеризацией метки, чтобы уменьшить семантическое искажение данных. В приведенном выше примере метки «atmosphereofearth» ^atmosphereofMars» нельзяпоставить под метками «atmosphere», потому что у них имеется общее знание.

Таблица 2.3 - Значение для слова «ball», на основе Wiki-аннотации и WordNet

□ Значение СЛОЕ Метка Wikipedia ф редел eHMeWiki n Определение Wordnet

Ball [mathematics) Closed balljOpen ball, n-ball, hyper ball The space bounded by a sphere sphere -- (a solid figure bounded by a spherical surface (including the space it encloses))

Ball [Anatomy) BallJAnatomy) The ball of the foot is padded portion of the sole between the toes and arch, underneath the heads of the metatarsal bones a more or less rounded anatomical body or mass; "the ball at the base of the thumb"; "he stood on the balls of his feet"

Ball(dance party) Ball_(Dance party) The ball is a formal dance party . Social dance forms a large part of the evening dance -- (a party of people assembled for dancing)

Ball(Football) Football, futsal ball, American Football, goals, field of play , Association Football,rules football A Ball inflated with air that is used to play one of the various sports knows as football. football game — (any of various games played with a ball (round or oval) in which two tea ms try to kick or ca rry or propel the ball into each other's goal)

На третьем шаге используется SENSEVAL. Это система устранения семантических неоднозначностей [37]. Для неоднозначных слов создается сементическая аннотация из базы данных Википедии. Задачей системы устранения семантической неоднозначности слов является понимание правильного значения слова, которое зависит от контекста, где появляются такие слова. В статье H.T.Ng[38] рассмотрен подход к обучению машины, управляющей устранением семантической неоднозначности слов. Метод похож на предложенный Ng and Lee [38] и метод Senseval 2 и 3 в [37]. В SENSEVAL для семантических отмеченных корпусов используют сведения из WordNet в работе Strube [39]. Мыпредлагаем метод, использующий Wikipedia (рисунок 2.8) как семантические отмеченные корпусы вместо WordNet.

Рисунок 2.6 - Устранение семантической неоднозначности слов на основе WSD (Senseval)

На четвертом шаге используется Википедия и WordNet для расчета семантической связи между словами с одинаковыми значениями n-grams. Для вычисления семантической связи необходимо рассчитать сходства между n-граммами слов с одинаковым значением. Если у одной пары n-граммов существует семантическая связь, то их надо добавить в семантическую матрицу. Чтобы рассчитать отношение между термами, используется WordNet и Википедия [82]. Метод согласования используется для того, чтобы вычислить связи между извлеченными n-граммами термов и понятий из WordNet, в работе J. Zhang [56]. Чтобы получить базу данных WordNet, его необходимо установить. WordNet состоит из наборов синонимов, которые называются «синсетами». В синсеты включаютсяглоссы, предствляющие семантические понятия. WordNet предоставляет большую базу синонимов, антонимов и т.д. для выбранных слов, поэтому можно использовать WordNet, когда необходимо узнать синтаксическое отношение между понятиями. Поиск синтаксических связей между понятиями в WordNet быстрее, чем в Википедии. Если у n-грамм термов нет связи с понятиями из WordNet, то их нужно искать в базе Википедии. Для поиска связей между термами в статьях, в работе WittenlH [42] необходимо использовать не только ссылки на статьи, но и структуру категорий

(в моей работе [58]) Википедии, так как п-граммы терминов согласуются не только со статьями, но и с категориями. Если п-грамма одного терма совпадает с одной статьей, то он имеет отношение и к этой категории, а соответственно и ко всем статьям в этой категории, так как Википедия имеет иерархическую структуру [58]. Когда семантические связи используются в 'ЬМ-методах [42], то эти п-граммы связываются и с другими статьями, с которыми данная статья соединена гиперссылками (рисунок2.9). Когда производится согласование, используются все подобные ссылки, поэтому качество согласования с помощью Википедии лучше, чем при использовании 'огё№1

Рисунок 2.7 - Гиперссылки между статями в '1к1

На этом шаге используем список однозначности п^гатБ термов и отношения между ними и создаем семантическую матрицу. Чтобы узнать семантические связанности между предложениями, надо создать семантическую матрицу между п^гатБ термами и предложениями. В семантической матрице каждый элемент впервой строке является одним из п-граммов одного предложения, и каждый элемент в любомстолбце является одним из п-граммов другогопредложения. Каждое число в матрице - это семантическая связанность соответствующих понятий. Эти отношения получены из 'огё№1 и '1к1реё1а, поэтому такая матрица называетсяобогащенной семантической матрицей. Здесьнадо обратить внимание на то, что если смысловая взаимосвязь между понятиями, полученными из 'огё№1:, ниже порогаоценки (в этой работе порог

55

0,2), то семантическая связанность принимается равной по вычислениям с Wikipedia. Этот метод делает нашподход быстрым, потому что вычисление семантической связи WordNet происходит быстрее, чем в Wikipedia. В таблице 2.4 показана обогащенная семантическая матрица предложений A и B. K -количество n-gramsв предложении А и w - количество n-gramsв предложении B. щ = (i = 1,......, ^)n-граммAи bj = (j = 1,......, w)n-гpаммB.

Здесь надо внимание на неоднократностьслов в n-grams. Например, Владимир Владимирович и Владимир Владимирович Путин. Один n-grams (Владимир Владимирович) представляет собой части другого n-grams (Владимир Владимирович Путин). Когда создается семантическая матрица, необходимо использовать большие значения по семантическому измерению. Если использованы оба понятия (Владимир Владимирович и Владимир Владимирович Путин), то результат семантического измерения будет больше, чем действительное значение.

Таблица 2.4 - Обогащенная семантическая матрица для предложений А и

В

sentence В Sentence Ä^- NB± NB2 NB3 Сумма средний вес N грам- А к предложению В

SituiNA^, NRX) Sim( NA-l, «Si) Sim (NA-l, NB3) S imiNA1,NBu,)

na2 Sim{NA2. NB,ï ЫВг) Sim(iV,42, NB3) Sim (,NA2.NB„) WANAIJ)

NA3 Sim(NA3. NBit Sim(JVjl3, JVS3) Sim{NA3.NB„1

nak SimiiV/lj, NU, ) sim(ivat, NU.) SimCAM*. NB3Ï Sim (NAk,NB„) WANAtJS

Сумма средний вес ]SI грам- А к предложению В WANBiiA WANBi.a

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

семантическую связь между одним п-граммом одного предложения и другим предложением. Длина любого вектора должна быть равна сумме количества п-граммов предложений (например, длина векторов для предложений А и В равна к + Тогда мы создаем вектор для каждого предложения следующим образом:

А = (]КАма 1,А> ^^ИА2,А> №АМАзА, ...., №АмАк,А, №АМВъА, №АМВ2,а, №АМВз,а, ..., №АМВю,а)

(2.2)

В = 1,в> №АмАз,в> .... > WANAk>в> WANB1>B> WANB2,B> WANB3,B>... > №АмВю,Б)

(2.3)

После этого рассчитывается семантическая связь между векторами как косинус понятия вектора. Уравнение (2.4) представляет собой косинус вектора А и В. Значение косинуса будет в диапазоне между 0 и 1. Если значение косинуса близко к 0, то угол вектора близок к 90 градусом, и это означает, что семантические связи находятся далеко друг от друга. Если значение косинуса приближается к 1, то угол вектора близок к 0 градусам, что означает, что они имеют тесную семантическую связь.

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

После создания семантической матрицы каждый текст представляет собой семантический вектор.

(2.4)

А = (ШАпл1Д, 'МАпа2,Л, ^АПД3,Л......'МАпАк,А, WAпв1,A. WAпв2,A. WAпBз,A.....'^АПВ^А) (2.5)

В = (ЖЛЯЛ1,В, ЖЛпЛ2,В, ^^плз, в......WAПBllв, ЖЛпВ2,в, В.....^^ПВ№,В)(2.6)

Таблица 2.5 - Обогащенная семантическая матрица для текстов А и В

Ге кс 1 В Текст ПВ, пв2 п в3 п В„ Сумма средицй вес редложени А к Текст В

ПЛ, вптКПЛ!, ПВ!) 3{т(ПЛ1, ПВ2) 81т(ПЛ1,ПВ3) пах.в

пл2 81т(ПЛ2, ПВ,) 31т(ПЛ2, ПВг) 31т(ПЛ2,Г1В:1) 31т(ПЛ2,ПВ„)

ПЛ3 511П(ГЪ43, ПВ,) Э1т(;ПЛ3, ПВ2) 81т(ПЛ3,ПВ3) 81т(ПЛ3,ПВ№) МАПАзшВ

П Ак 31т(ПЛ4. ПВ,) Б1т(ПЛ4, ПВ;,) 51т(4.Пе;1) 31Ш(ПЛк,ПВи,)

Сумма средний вес рсдложсни В к Текст А. И'Лпв^л ™АПВз.а

ПА- предложение текста А, ПВ- предложение текста В

Следовательно, в конце любой строки и столбца мы найдем наибольшее соответствие между одним предложением из первого текста и другим из второго. Длина любого вектора равняется сумме количества предложений в тексте. Для вычисления связи между векторами можем использовать косинус между векторами.

Исходные данные

Предварительная обработка

п-граммы

7 'п *

V I *

ft , ■

Семантические

аннотации,

использующие

Wiki pedia

1

WSD

fSENSEVALl

Однозначные n-

граммы

Семантические связи между

предложениями

Семантические

связи между

текстами

Рисунок 2.8 - Семантические связи между одинаковыми термами текстов с использованием SENSEVAL, Википедия и WordNet

2.4. Вывод по главе

В этой главе представлено 2 метода:

• кластеризация документов на основе онтологии

• устранение семантической неоднозначности слов (Word Sense Disambiguation - WSD) исемантические отношения между текстами с использованием Википидии и WordNet.

В первом методе мы представляем общие рамки концепции улучшения кластеризации информации и категорий на базе Википедии. С использованием двух разных методов соответствия: точное соответствие и сопоставимость - мы

можем создать вектор концепции в Википедии и вектор категории Википедии для каждого понятия в статье. Вектор концепции и вектор категории представляют собой поверхностные знания о понятии. Они линейно объединены с текстовым вектором слова дляизмерения сходства документов. Наличие структуры в Википедии положительно влияет на производительность кластеризации. Мы экспериментируем с шестью различными кластерами: схема-концепция, категория, WordConcept, WordCategory, ConceptCategory и WordConceptCategory. На основе эмпирических результатов мы можем сделать следующие выводы:

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

2. Концептуальная информация не так полезна, как информация о категории для повышения производительности кластеризации из-за информационного шума и проблемы неопределенности.

3. Влияние категории и информации о концепции на ^средство кластеризации не так значительно, как на агломерационную кластеризацию. Но в большинстве случае кластеризация на основе WordCategory достигает большую производительность по сравнению с остальными формами кластеризации.

4. Эффективность двух схем отображения зависит от набора данных, показателя качества и используемого кластерного подхода.

Представлен метод, использующий Википедия для поиска семантических аннотаций в SENSEVAL и поиска семантических связей между однозначными текстами с использованием WordNet и Википидея. Для семантических аннотаций значений слова используются термины, имеющие гиперссылки в Wikipedia. WSD-системы на основе Wikipedia могут уменьшать относительную

ошибку на значение от 30 до 44 %. Использование Википидеа для устранения неоднозначности значений слов имеет следующие причины:

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

2. Wikipedia написана на множестве разных языков, и можно реализовывать семантические теги и решать проблемы неоднозначности словдля разных языков.

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

Глава 3. Использование метода сжатия информации в семантическом информационном поиске

3.1. Классификация методов сжатия текста

Свойства хорошей системы информационного поиска (ИП) - это не только высокая точность и полнота, но и высокая скорость поиска информации пользователем. Для улучшения скорости, точности и полноты ИП-системы в работе Н.Н. Кучукова [44] предложены разные методы и модели поиска и ранжирования документов. В этой главе предлагается новая модель семантического информационного поиска, использующая метод сжатия.Среди методов сжатия выделяют методы на основе словарей (Ziv-Lempelfamily, gizp,) и статистические методы (код Хаффмана, арифметический, PPM и так далее) в [45]. В качестве модели сжатия выделяют 3 модели: статистическую, полустатистическую и динамическую модели. Методы Хаффмана (простой Хаффман и помеченный Хаффман [46]) и метод помеченного с конца плотного кода - ETDC (End Tagged Dense Code - ETDC) включаются в полустатистические методы (в работе N.R. Brisaboa [47]). Ziv-lempelметод в работе K. Sharma [48] представляет собой динамическую модель. Полустатистическая модель - это двухпроходный метод (2 passmethod), а динамическая модель - это однопроходный метод (1 passmethod). Полустатистическая модель обеспечивает хороший коэффициент сжатия. Популярные Ziv-Lempel-методы представляют собой динамические методы и обладают хорошим коэффициентом сжатия. Но они реализуются сжатием текста только с самого начала. Посредством Ziv-lempel-метода нельзя реализовать прямой (произвольный) доступ. Поэтому он не подходит к задачам ИП. Коды традиционного метода Хаффмана реализуются на основе букв (символов) и представляют собой последовательности битов. И хотя коэффициент сжатия при этом получается равным 25%, восстановление и поиск информации занимает

много времени (в работе Brisaboa[49]). Поэтому Mouretal [50]. предлагает байт-ориентированный метод Хаффмана (простой Хаффман).

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

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

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

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

Коэффициент сжатия = уХ100. (3.1)

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

I — 0

Степень сжатия = 100 —— Х 100 . (3.2)

• Коэффициент бит на символ (бит/с). Он сравнивает количество бит, необходимое для представления символа источника, против числа бит, используемых для представления кодового слова. Он вычисляется как:

Ьря = у Х ¿¿. (3.3)

Интересно отметить очевидную разницу между абсолютными и относительными мерами при сравнении двух методов сжатия.

3.2. Байт-ориентированный метод Хаффмана

В этом методе последовательность кода - это байты. Поэтому, хотя, согласно методу Хаффмана,коэффициент сжатия получается равным 30%, восстановление и поиск идет быстрее, чем в ранее представленном коде (в работе A. Fariña [51]). Но его недостаток - это невозможность прямого (произвольного) доступа. Так как при восстановлении Хаффман-метод осуществляется с самого начала цельного текста, то он соответствует требованиям ИП. Решением этой проблемы является маркированный код Хаффмана, в котором первый бит первого байта принимается равным 1, а первые биты остальных байтов - 0 (таблица 3.1). В маркированном коде Хаффмана из-за использования первого бита первого байта как флагового разряда (флагового бита) возможен прямой (произвольный) доступ. Благодаря флаговым разрядам обеспечивается возможность распознавать начало кодового слова (в простом коде Хаффмана нет такой возможности). Поэтому в маркированном коде Хаффмана невозможны ошибочные согласования. Кроме того, скорость поиска и восстановления увеличиваются. Код называется помеченным, так как для распознавания начала или окончания кодового слова, для исключения ошибочных согласованийиспользуются метки начала или окончания байта. Коэффициент сжатия помеченного кода Хаффмана получается равным 35%, что хуже, чем у простого кода Хаффмана. Поэтому N. Brisaboa, E. Iglesias, G. Navarro описали новый байт-ориентированный код Хаффмана - код End Tagged Dense Code - ETDC (в работе Brisaboa [49]). Коэффициент сжатия ETDC (5, 6%) - лучше, чем помеченного кода Хаффмана, и хуже (1%) коэффициента сжатия простого кода Хаффмана. Для него не надо строить деревья Хаффмана, что обеспечивает простое и быстрое кодирование. Поэтому время кодирования этого метода сопоставимо с помеченным кодом Хаффмана и

на 40% быстрее простого кода Хаффмана (в работе N.R. Brisaboa [47]). При этом возможен прямой (произвольный) доступ. В сжатом тексте файлы, использующие ETDC, можно искать на основе использования алгоритма boyer moore в [53].

3.3. End Tagged Dense Code (ETDC)

Antonio Farina Martinez [83] предлагает End Tagged Dense Code (ETDC), основойкоторогоявляетсямаркированныйкодХаффмана. Но ETDC совсем не зависит от кода Хаффмана. В отличие от маркированного кода Хаффмана, использующего первый бит первого байта как флаговый разряд (флаговый бит) «1», ETDC использует первый бит последнего байта как флаговый бит, первый бит остальных байтов принимается равным «0» (таблца. 3.1). Благодаря этим флаговым битам ETDC становится префиксным кодом, который однозначно декодируется. В префиксных кодах, в работе ShangXue [54] невозможны ошибочные согласования при реализации поиска. Например, допустим, даны 2 кодовых слова А и В, где длина А короче длины В (|А|<|В|). В этой ситуации «А» не может быть префиксом «В». В начале ETDC[83] осуществляет определение частоты слов и получает файл, в котором находятся отсортированные по частоте слова (терминологический словарь). Затем определяются коды для этих слов. Для осуществления кодирования используют не фактическую частоту слов, а только ранги (индексы) слов по этой частоте. На втором шаге осуществляется сжатие (замена исходных символов их кодами).

Таблица 3.1 - Кодовые слова формат ПФ и ETDC

Байты Помеченный Хаффман ETDC

1 lxxxxxxx lxxxxxxx

2 lxxxxxxx Oxxxxxxx Oxxxxxxx1xxxxxxx

3 lxxxxxxx OxxxxxxxOxxxxx xx OxxxxxxxOxxxxxxx lxxxxxxx

N 1ххххххх0ххххх хх.Оххххххх Оххххххх.. ..Оххххххх 1ххххххх

Таблица 3.2 - Кодовые слова ETDC

Рангслова(i) Назначенное ключевое Слово байт Слова

0 27 — 1 = 127 10000000 11111111 1 1 27

27=128 00000000:10000000 2

256 00000001:10000000 2 2727

2727+27-1=16511 01111111:11111111 2

2727+27=16512 00000000:00000000:1000000 3

(27)3+(27)2 + 27-1=2113663 ,01111111:01111111:1111111 1 3 (27)3

На основе учета исходных символов с убывающими вероятностями №}0 < i < п, соответствующими кодовым словам, используется метод ETDC, и в результате формируется последовательность символов из Ь бит, из которых образуются числа в базе 2Ь-1 (то есть от 0 до 2Ь-1 — 1), за исключением последней, которая имеет значение между 2Ь-1 и2ь — 1, при этом назначение выполняется последовательным образом. В частности, если k - число байтов в каждом кодовом слове (к >1), тогда:

где Ь=8.

Ь-1 2(ь-1)(к-1)-1 ь-1 2(ь-1)к-1

2 2ь-1-1 < 2 2ь-1-1 , (3.4)

На самом деле значение Ь может быть любым, а не только 8. По этой формуле (3.4), когда

к = 1 ,0 < i < 128, илик =2 ,128 < i < 16512, шик = 3 ,16512 < I < 2113664 и т.д.

Эта формула считает только ранг слов <а», а не кодовые слова <а».

Кодирование

Кодовое слово (х) рассчитывается по следующему алгоритму кодирования (рисунок 3.1). Кодирование (i)

1) 0< i < n — 1//вход ранг слова (i)

2) output ((imod 128)+128);//самый правый байт

3) i^i div 128;

4) while i > 0 //остальные байты

5) i^ i-1;

6) output (i mod 128);

7) i ^ i div 128.

Рисунок 3.1 - Алгоритм кодирования ETDC В этом алгоритме output - это кодовое слов «х», а «п» - это количество «i». Этот алгоритм производит однокодовое слово как последовательность байт слева направо и производит самый первый значимый байт (самый правый байт с началом «1»). Для построения файла терминологического словаря нужны только простые тексты, при этом строить кодовое дерево не нужно. Однако в каноническом коде Хаффмана необходимо построить кодовое дерево для кодирования. Поэтому для построения файла терминологического словаря кода ETDC требуется меньше

времени, чем для реализации метода Хаффмана. В сжатых файлах существуют только кодовые слова (рисунок 3.3).

Декодирование

Декодирование реализуется в 2 этапа. На первом осуществляется загрузка файла терминологического словаря, который отсортирован по частоте. На втором получают кодовое слово (х) в сжатом файле, которое совпадает с рангом слова (i) файла терминологического словаря. Оценка времени декодирования для кода (х) байта (К) будет O(K) = O(logx)[49]. Чтобы получить ранг слова «i», выполняется итерация по каждому байту кодовых слов (х). Так как первый бит последнего байта равен «1», то его значение больше, чем 127. Этот помеченный бит «1» указывает на окончание кодового слова. После завершения итерации получается ранг слова «i». Если найти соответствующее слово [i] в файле терминологического словаря, то декодирование завершится. Например, рассмотрим трехбайтовый код x = xxx2x3. Чтобы получить ранг слова (i), нужно произвести вычисления по следующей формуле (3.5):

i = (((xx * 128) + x2) * 128) + (x3 - 128) + base[k], (3 5)

гдек=3.

Допустим, x1 = 1,x2 = 2, x3 = 255

Итак: x=1,2,255. base [3] вычисляется по следующей формуле(3.6):

base[3] = (£3=1128j-1) - 1.

(3.6)

Итак, i=(((1*128)+2)*128)+(255-128)+(16512)= 33279.

В файле терминологического словаря находим соответствующее слово с рангом 33279. Таким образом, декодирование завершено.

Начало

Рисунок 3.2 - Алгоритм декодирования ETDC

Алгоритм декодирования (см. рисунок 3.2) имеет следующий вид: Декодирование(Ьа8е,х)

1) //вход х: кодовое слов для декодирования

2) //выход i: позиция декодированного слова в файле терминологического словаря

3) i^ 0;

4) k ^ 1// б„йт кодового слова 5 128

6) i^ i'128 + x[k];

7) k ^ k+1;

8) i ^i* 128 + x[k]-128;

9) i ^ i+base[k];

10) return i.

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

образцу, то появляются ошибочные согласования. В простом коде Хаффмана невозможно определить начала или окончания соединенных кодовых слов. Поэтому, когда осуществляется поиск, появляются ошибочные согласования. В ETDC определяется «1» первый бит последнего байта каждого кодового слова как флаговый бит. Из-за флагового бита легко распознавать окончание кодовых слов. Поэтому при использовании ЕТЭС невозможны ошибочные согласования. В сжатом файле при осуществлении поиска по принципу соответствия образцу реализуется кодирование образца (рисунок 3.3).Когда появляется полное кодовое слово образца, совпадающее с кодовым словом сжатого текста, то необходимо проверять, имеет ли первый согласованный байт значение в диапазоне [2Ь-1,2Ь — 1]. Это позволяет проверить последний байт предыдущего кодового слова. Здесь основание Ь=8, значение в диапазоне предыдущего кодового слова - [128, 255].Если диапазон предыдущего кодового слова между [128] и [255], то его первый бит «1». Посредством этого текущий согласованный байт обеспечивает правильное согласование. А если предыдущее кодовое слово полного кодового слова образца лежит в диапазоне [0,2Ь-1 — 1] (значит - 0,127), то этот текущий согласованный байт - только часть одного кодового слова, и будет ошибочное согласование.

Рисунок 3.3 - Процесс кодирования и декодирования ETDC

В такой ситуации кодовые слова сжатого текста длиннее, чем кодовые слова образца (рисунок 3.4). Здесь мы предлагаем новую модель семантического информационного поиска.

Слово 2

Последний байт правильнее согласование

предыдущего кодового слова образец

Рисунок 3.4 - Поиск по Boyer Moore принципу соответствия образцу в ETDC

3.4. Использование метода сжатия в семантическом информационном

поиске

Предложенная модель реализуется за 5 шагов (рисунок 3.3).

1) расширение понятия запроса через Wordnet;

2) сжатие онтологии ETDC;

3) поиск в сжатом тексте с алгоритмом Boyer Moore;

4) декодирование;

5) отыскание документов.

Пользователю, чтобы получить соответствующие результаты, необходимо осуществлять расширение понятия запроса. При этом Wordnetв [57] - это всеобъемлющий тезаурус для получения семантической связанности между понятиями и расширениями (в работе Jayant R. Gadge [59]). На этапе предварительной обработки расширения запроса устраняются слова, игнорируемые информационно-поисковой системой, и знаки препинании из запросов, а запрос присоединяется к индивидуальным словам. С помощью

72

<word, POS, POS_NUM>, где POS - часть речи и POS_NUM-H0Mep части речи определяются эти индивидные слова. У слов в синсете имеются семантические связанности с понятиями запросов. Слова в синсете определяются как двухмерный массив. В каждой строке массива определяются понятия одного синсетав [59]. Таким образом, получаются семантически подобные наборы термов, схожие с понятиями одного терма запроса. Расширенные термы запроса для каждой строки массива объединяются в предложения. Семантические значения этих предложений при случайных объединениях являются не подходящими. Чтобы избежать этого, необходимо фильтровать расширенные запросы. Фильтрация похожа на расширение понятий запросов. Получающиеся термы-кандидаты объединяются в тройки <word,POS,POS_NUM> и находят синсеты в WordNet, которые соответствуют этим тройкам.

Рисунок 3.5 - Семантический информационный поиск со сжатием

Термы WordNet сансета определяются как двухмерный массив. Исходное понятие двухмерного массива сравнивается с текущими понятиями двухмерного массива, а расширяются только совпадения с исходными понятиями двухмерного массива. На рисунке 3.4 пунктирная линия - это запрос - кандидат, а сплошная линия - это финальный запрос. №термы исходных запросов соответствуют шштермам слова синсета. WSD - устранение семантической

73

неоднозначности слов.Wikipedia имеет иерархическую структуру и, из-за подобия заголовка статьи Wiki и понятия онтологии, возможно использовать Wiki как онтологию в моей статье [41].

Сжатие статьи Wikipedia осуществляется методом ETDC.На первом этапе определяется частота слов wiki-статьи и создается файл терминологического словаря. В этом файле находятся только простые слова, отсортированные по частоте. На этом этапе кодирования определяется ранг слова, осуществляется их сортировка по частоте и образуются кодовые слова.

Рисунок 3.6 - Расширение запросов через Wordnet

На втором этапе термы статей Wiki заменяются полученнымикодовыми словами. Таким образом, получаются сжатые файлы, в которых находятся только связанные кодовые слова. Запросы пользователей расширяются через WordNet. Получающиеся расширенные запросы согласовываются с термами файла терминологического словаря, и осуществляется кодирование с использованием ETDC. Эти кодовые слова запросов согласовываются с кодовыми словами сжатых файлов с использованием алгоритма Boyre Moore.

Осуществляется декодирование кодовых слов и поиск документов, которые включают кодовые слова, соответствующие кодовым словам запросов.

3.5. Результаты эксперимента

На основе описанных моделей были разработаны алгоритмы и осуществлена их программная реализация. Результаты экспериментальной проверки разработанного программного комплекса представлены на рисунках и в таблицах.

Рисунок 3.7 - Коэфицента Сжатия для русского языка и английского языка

Таблица 3.3 - Скорости кодирование русские Таблица 3.4 - Скорости декодирование руссю

и английский текст

и английский текст

Набор данных объем В1гр2(э) Т.7ЛУ (я) ЕТБС (я)

Английский 124.3 0.039 94 0.69

Русский 1339 1.15 15.1 2.25

Набор данных объем В1гр2(в) 1 ;/.\\ ЕТБС

Английский 124.3 0.034 85 0.578

Русский 1339 0.855 0.578 1.46

3.6. Вывод по главе

Для сжатия статьи Wiki используется метод ETDC, обеспечивающий получение коэффициента сжатия, равный 25%. Для построения файла терминологического словаря необходимы только простые тексты. Кодирование - процесс очень простой и легко реализуется программно. Поэтому время кодирования и декодирования меньше, чем в методе Хаффмана. Главное преимущество метода ETDC - возможность прямого (произвольного) доступа и поиск в сжатом тексте, что невозможно при использовании простых методов Хаффмана и других методов сжатия на основе словарей (Zim-lempelfamily, в работе E. 07Шгк [55], gizp, в работеУ. БЫЬа1а, [84]). Поэтому метод сжатия на основе ETDC можно использовать для решения задач информационного поиска.

Глава 4. Сжатие текста длябирманскогоинформационого поиска на основе лингвистической онтологии

4.1 Бирманский языки сегментация

Язык мьянма (бирманский язык) является официальным языком. Его используют более 53 млн жителей Мьянмы. Бирманский язык относится к тибето-бирманским языкам, подсемейство - сино-тибетская семья языков [13, 14]. Слова бирманского языка округлой формы и пишутся слева направо. Между словами нет интервалов, они обычно используются для разделения фраз. Бирманский язык не поддерживается компьютерами, и для него доступно малое число инструментов естественной обработки. Кодировка бирмы была предоставлена в Unicode (U+1000-U+109F, начиная с версии 3,0 (рисунок 4.1) [14].

Myanmar11' Official Unicode Consortium code charts (PDF)

0 1 2 3 4 5 6 7 8 9 A В С D Е F

U+100x TO Э 0 то с ® эо @ 41 г. e я S Я Ü СЮ

U+101x TO СО 3 Ö f 0 (S о то « со я (X) О 00 ТО

U+102x g зэ го 00 01 si е 9 е е 6 § egs о) со я g "l

U+ЮЗх II 60 ч в g 6 0 \Jo ,r ...t.J £ 41 В о J ОТО

U+104x О 0 J ? 3 g ? m e 1 II с i S eil

U+105x Й а (5 Ü е е 03 OJS e è с г ч @ 3 d- с

U+Юбх L Ol ор Ol 0 V Od 0 OJ ог OJ С1 01 os СЮ

U+107x Uj> 30 с /ч у о 3 00 so ? оэ se иг Of V

U+108x 90 о j с °1 со к д Wo Ла. WQ. 0° О00 - в г-.о WÇ

U+109x 0 г ? h к 6 я z 8 8 Лв ГМГ а 1 ■f

Notes 1 A As of Unicode version 11.0

Рисунок. 4.1 - Таблица кодов

4.1.1 Сегментация слогов

В бирманском языке алфавит состоит из 12 групп, приведенных в таблице 4.1. Есть согласные, ше&аЪ (вспомогательные символы), употребляющиеся вместе с гласными. Для обозначения конца слога в языке бирмы используют ряд различных символов: символ асат (.), большое са, зависимый. В бирманском языке слог может состоять из одного или нескольких согласных и гласных. Таким образом, задача обнаружения слога трудновыполнима для компьютерной программы, в отличие от людей. Алгоритм разделения слога по бирме представлен [23].

Таблица 4.1 - Классификациябирманского языка

Название категории Название алфавитов. Сим бол ипк^е Код

С согласные гоэовос ^испоооою^оовао ¿осероо эзоэ^^э и— 1 ООО____и— 1021

М вспомог агельные СИМЕ ОЛЫ Ч Е ¿9 и-103В... и-ЮЗЕ

V Зависимый гласный симбол ::: 5 .5 у во о и-102В... и-1032

а Симб ол Вир ама - и-1.039

А символ асат £ и-ЮЗА

г Зависимый различньп"! симбол б 5 :! и—1036. ..и—1038

I Независимые глЕсньге симболы и независимые различные симболы U-l.024iU-l.027: и-102А;и-Ш4С; и+104П;и+104Р;

Е Бирманский вышесказанный симбол и-1.02 3:и-102 5: и—1026:и—1029 и—1.04Е:

О большое са и-ЮЗБ

Б Бирманская цифр а и-1040....и-1049

Р Знак пр еиинания 1 и и и— 1.04А... и— 104В

"О/ пробел и—0020

Алгоритм разделения слогов для языка бирмаможет быть записан следующим образом:

ЗуПаЫе: :=С {М}М Ш | {сХм}т/а| С ШНУ> САЩ | Г|П

4.1.2 Слова и их разделение

Существует много методов разделения слова, прежде всего модели CRF, Win PAPA [25], TunTuraTheta Jin-CheonNa [24] и необслуживаемая модель Ye Kyaw Thu [25]. Все эти модели используютсловарь. В нашем методе мы используем знаки препинания бирмы и пробел для разделения слов. Слово не имеет четкого определения в бирме. Слово может содержать один или несколько слогов, но иногда оно состоит из нескольких слов - это «сложные слова». Бирманский язык богат на сложные слова. Два или более простых слова объединяются между собой и образуют сложные слова. Так, в качестве примера можно привести слово (лампа), состоящее из слов (огонь) и □ =■ (дом). Предложение может быть как простым, так и сложным, состоящим из нескольких простых. Несмотря на отсутствие четких правил для использования пробелов в письменности, большинство носителей языка используют пробел для разделения слов в предложении. В качестве примера можно привести официальный веб-сайт Министерства информации (www.moi.gov.mm);