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

Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования Национальный исследовательский университет "Высшая школа экономики" Кафедра Управления разработкой программного обеспечения УТВЕРЖДАЮ Зав. кафедрой УРПО ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА по направлению 231000.62 Программная инженерия подготовки бакалавра На тему «Программа анализа текстов на основе модифицированного метода аннотированных суффиксных деревьев»Среди наиболее значимых разработок в этой области назовем использование аннотированных суффиксных деревьев в проблеме классификации текстов [16] и извлечения из них наиболее значимых слов, кроме того, основанный на этой структуре данных подход к иерархической кластеризации текстов, а также использование ее для построения графов связей между ключевыми словосочетаниями на основе анализа входной коллекции текстов [25]. Алгоритм построения такого «концептуального графа» основывается на анализе совместной встречаемости ключевых словосочетаний в текстах данного корпуса (ключевое словосочетание считается встречающимся в некотором тексте, если оценка степени его вхождения в этот текст, вычисленная с помощью соответствующего АСД, превышает некоторый порог). В [24] было показано, что при соблюдении условия окончания каждого из текстов из коллекции уникальным символом (что легко достигается путем предобработки поступающей на вход совокупности текстов) возможно использование этого свойства для адаптации одного из линейных алгоритмов построения обычного суффиксного дерева (например, алгоритма Укконена). Реализация метода АСД с использованием суффиксных массивов Подход к преобразованию алгоритмов, основанных на использовании суффиксных деревьев, к алгоритмам, работающим с суффиксными массивами, излагается в [1] применительно к суффиксным деревьям в их оригинальном виде. После построения собственно суффиксного и двух вспомогательных массивов сами аннотации точно так же, как и ранее, вычисляются за один постфиксный обход дерева в глубину, но дерево на этот раз является лишь уже упоминавшимся нами виртуальным lcp-деревом (работу с которым несложно реализовать с помощью lcp-массива [9]), а обрабатываются только его внутренние узлы (но не листья): Алгtrial LINEAREASACONSTRUCTION(??)Нами разработано и опубликовано программное средство EAST для анализа текстов методом аннотированных суффиксных деревьев, являющееся на сегодняшний день наиболее эффективным среди аналогов по объему потребляемой памяти и времени работы основных алгоритмов. Программное средство поддерживает функции построения аннотированных суффиксных деревьев для входной коллекции текстов и ответа на запросы об оценке степени вхождения в построенное АСД списка ключевых словосочетаний. Тот факт, что разработанное программное средство продемонстрировало десятикратный выигрыш в объеме используемой памяти в сравнении с предшествующими реализациями метода АСД, открывает широкие перспективы для его использования исследователями в своей работе: нетребовательность к ресурсам означает возможность анализа текстовых корпусов больших размеров на доступных большинству исследователей вычислительных мощностях.

Содержание

Реферат........................................................................................................................................................2 Введение......................................................................................................................................................4 Цель работы.............................................................................................................................................6

1. Обзор........................................................................................................................................................8 1.1. Структуры данных и алгоритмы над строками.............................................................................8 1.2. Выделение синонимов...................................................................................................................11

2. Описание алгоритмов.........................................................................................................................13 2.1. Реализация метода АСД с использованием суффиксных массивов..........................................13 2.2. Учет синонимов в методе АСД.....................................................................................................16

3. Программная реализация..................................................................................................................19 3.1. Общее описание .............................................................................................................................19 3.2. Архитектура программного средства...........................................................................................19 3.3. Работа с программным средством................................................................................................22

4. Анализ полученных результатов.....................................................................................................24 4.1. Ресурсная эффективность..............................................................................................................24 4.2. Работа с синонимами.....................................................................................................................26 4.3. Применение ПО к анализу реальных текстов .............................................................................27 Заключение...............................................................................................................................................31 Список использованных источников..................................................................................................33

3