Введение 4
1. Расширяемый язык разметки XML. Язык разметки MathML. ОБЗОР 6
1.1. XML - язык мета-разметки 6
1.2. Средства и основные приложения языка XML 16
1.3. Средства и основные приложения языка MathML 24
2. Деревья математических выражений языка MathML: их сходство и
различие 32
2.1 Преобразования математических выражений в Presentational MathML 32
2.2. Основные меры схожести между деревьями, а также
алгоритмы, вычисляющие их 36
2.3. Модель приложения языка MathML 39
2.4. Выбор средства разработки программного модуля 41
3. Разработка программного модуля, предоставляющего средства
поиска документов по математическим формулам 43
3.1. Создание консольного приложения на платформе .NET Core 44
3.2. Разработка прикладного программного интерфейса деревьев 45
3.3. Отображение XML-документов в деревья 64
3.4. Простой генератор лексиколизированных деревьев 69
3.5. Строковое представление деревьев 70
3.6. Интеграция внешних программ в приложение: парсер формул
MathML и программа реализующая алгоритм AP- TED 71
3.7. Сортировка данных и реализация словаря 74
3.8. Собираем всё вместе: простая поисковая машина ... 92
Заключение 104
Список использованных источников
Попытки найти информацию, удовлетворяющую основным потребностям пользователя, были ещё до появления первых ЭВМ. Первым шагом к построению целой системы поиска были библиотеки с их картотеками и каталогами. Затем, с появлением ЭВМ, появились новые возможности в организации поиска данных. Стали создаваться первые информационные поисковые системы. Сначала информационные поисковые системы выполняли поиск научной информации и литературы. Многие университеты и библиотеки использовали такие системы для обеспечения доступа к их журналам, научным статьям и книгам. Далее, в связи с появлением интернета и развитием вебтехнологий поисковые системы получили широкое распространение. Благодаря развитию технологий в области вычислительных сетей, стали возможными хранение и обработка больших данных. Из-за быстрого роста и громадного объема данных задача информационного поиска становится всё более востребованной. Появляются задачи семантического поиска, т.е. поиска документов не по ключевым словам и метаданным, а по содержимому [11].
Целью моей работы является изучение специального вида языка разметки XML - MathML, его приложения в сфере информационного поиска, а именно: поиск документов по формулам. Также анализ модели векторного поиска среди документов языка XML и возможности её применения для языка MathML.
Объектом исследования является информационный поиск в коллекции документов, написанный на специальном виде языка разметки XML - MathML. Предметом исследования являются сам язык MathML, модели векторного поиска XML-документ ов [6] и построенная на их основе система информационного поиска, её приложение к поиску по математическим формулам, а также алгоритмы определения меры схожести между содержимым двух XML-документов [1, 7, 8].
Для достижения обозначенной цели поставлен ряд задач:
1. Изучить спецификацию языка XML, затем MathML.
2. Ознакомиться с основной структурой поисковой системы.
3. Найти и проанализировать определения схожести между двумя документами.
4. Найти для каждого такого определения эффективный алгоритм.
5. Выбрать подходящее определение.
6. Смоделировать систему поиска на основе векторной модели поиска MathML документов по математическим формулам и выбранного определения схожести, и на её основе разработать программный модуль.
7. Выбрать подходящее средство разработки.
8. Оценить производительность и эффективность программного модуля.
В результате было реализовано приложение, использующее средство языка MathML, в частности, его древовидную форму. Приложение представляет из себя простую поисковую машину на основе векторной модели поиска, которая ищет документы в коллекции не по словам, а по математическим выражениям. В рамках разработки приложения были разработаны типы для решения ряда подзадач (LinkedTree, ArrayTree - представляющие структуру дерева для решения множества ряд задач на них, а также тип ArrayHeap, выполняющий сортировку данных по переданному ему делегату, инкапсулирующий указатель на функцию, и тип Counter, представляющий счётчик).
Сложность по времени для постройки индекса благодаря текущей реализации алгоритма AP-TED, занимает O(n2 * А), где N = количество документов в коллекции. В текущей реализации для представления разницы используется тип данных float. Кроме того, для определения стоимости операций вставки, удаления, переименования узлов дерева используется реализация интерфейса CostModel - StringUnitCostModel, возвращающая 1 для вышеупомянутых операций. Можно определить собственный тип (на языке Java), задающий свою модель стоимости операций, главное, чтобы он реализовывал интерфейс CostModel. Для этого понадобится модифицировать скачанный исходный код библиотеки и построить новый архив jar, заменяющий предыдущий.
Второе узкое место приложения - конвертация дерева в его строковое представление, занимающее сложность O(n). Если брать каждый узел дерева в качестве нового, то преобразование их всех в строку займёт O(n2).
Также из-за того, что тип ключа словаря (индексатора) является строкой и для реализации словаря используется нагруженное дерево, время обработки также пропорционально длине ключа.
Рекомендуется разработать хеш-функцию, создающую уникальное множество ключей для словаря.
На данный момент тип IndexBuilder, строящий индекс, возвращает конкретный тип индексатора - Trie. Для большей гибкости, можно создать интерфейс, определяющий методы класса Trie (собственные методы), указать, что тип Trie реализует данный интерфейс, и заменить возвращаемое значение метода ReadData экземпляра класса IndexBuilder на тип интерфейса (также потребуется изменить код класса Program).
Методы API деревьев нормально работают, если принимают в качестве параметра узел текущего экземпляра класса дерева (сами методы также являются методами экземпляра). Если им передать узел другого объекта дерева, то возможны ошибки в работе программы. Поэтому, для предотвращения подобных коллизий следует определить абстрактный класс AbstractTree, реализующий интерфейс IPositionalTree, задача которого всего лишь при вызове соответствующих методов API проверить, что переданный узел принадлежит текущему экземпляру класса (для проверки надо воспользоваться унаследованным методом GetHashCode (который можно переопределить)). Затем, всем неабстрактным классам, реализующих API деревьев, надо наследоваться от класса AbstractTree.
Что касается релевантности документов, то её значение получалось одинаковым для тех документов, у которых одинаковая древовидная структура (вложенность узлов). А те документы, у которых была большая разница в структуре по сравнению с деревом формулы введённой пользователем имели нулевую релевантность.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
