Низкая цена
Всего 249a за скачивание одной диссертации
Скидки
75 диссертаций за 4900a по акции. Подробнее
О проекте

Электронная библиотека диссертаций — нашли диссертацию, посмотрели оглавление или любые страницы за 3 рубля за страницу, пополнили баланс и скачали диссертацию.

Я впервые на сайте

Отзывы о нас

Анализ и разработка способов индексирования текстов на основе обобщенных и неплотных суффиксных деревьев : диссертация ... кандидата технических наук : 05.13.11

Год: 2005

Номер работы: 84526

Автор:

Стоимость работы: 249 e

Без учета скидки. Вы получаете файл формата pdf

Оглавление и несколько страниц
Бесплатно

Вы получаете первые страницы диссертации в формате txt

Читать онлайн
постранично
Платно

Просмотр 1 страницы = 3 руб



Оглавление диссертации:

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

Структуры данных и способы организации индексов в информационнопоисковых системах во многом определяют возможности поиска. Важным вопросом при построении ИПС является выбор минимального индексируемого элемента. Наибольшее распространение получили [20]:

- пословная декомпозиция, - декомпозиция на основе подстрок: п-грамм [95] и аффиксов. Согласно [20]: "Выбор минимальной индексирующей единицы зависит от того, насколько полно необходимо реализовать возможность ... поиска и от объема

Рассмотрим некоторую строку з в алфавите Е. Её длину будем обозначать через |з|. Запись 5[1-о] соответствует подстроке з с позиций 1 по], где 1 <Л <} < |з|. Префиксом з называется любая подстрока з вида з[1.л], 1<|з|. В случае 1<|з| мы имеем собственный префикс. Аналогично, суффиксом з называется любая подстрока з вида з[1..|5|], при 1>1 мы имеем собственный суффикс. Определение

1.1 Луч ("Ме") над множеством строк 3 представляет собой дерево, вершины которог

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

В настоящее время многие разработчики используют обычные реляционные СУБД для хранения слабоструктурированных текстовых документов (например, содержимое ^еЬ-сайта [2,6], различная справочная информация, техническая документация и др.). Соответственно, возникает задача удобного и быстрого поиска требуемой информации. Однако, предоставляемые универсальными СУБД средства зачастую не удовлетворяют всем потребностям. Так, одним из удобных способов поиска является использование регулярных выражений

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

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

1.4.2 Алгоритм Укконена Алгоритм Укконена выполняет последовательное построение неявных суффиксных деревьев для подстрок з[1..1], з[1..2],..., з[1..п]. Определение

1.6 Неявное суффиксное дерево — это суффиксное дерево, построенное над строкой, не заканчивающейся терминальным символом. В результате некоторые суффиксы данной строки могут заканчиваться не в листьях (явно), а в позициях внутри дерева (т.е. неявно). На очередном шаге алгоритма у нас имеется дерево Т для з[1.л], и нужно перей

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

Как отмечалось в предыдущей главе, имеются важные отличия между ОСД и обычными СД, что приводит к необходимости пересмотреть существующие схемы компактного хранения деревьев на применимость их для ОСД. Основное отличие в самой структуре дерева состоит в том, что в узлы дерева добавляются номера исходных строк. Как показано в [23], первоначальное построение ОСД можно легко свести к построению СД следующим образом: 1). Дополнить каждую исходную строку справа уникальным символом. Как и для обычн

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

1.5. При "связносписковом" подходе связи дерева представляются достаточно известным способом "

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

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

§(р) раз, и время построения дерева оказывалось равным О(1о

§(р)-п). Дальнейшее уменьшение данной величины может быть достигнуто с использованием кодов переменной длины - в частности, оптимальных префиксных кодов и алгорит

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

Лемма

2.1 Пусть к — длина кодовых последовательностей, в которые преобразуются символы исходного алфавита. Для любой позиции р=<и,1> в дереве Т', соответствующей неравенство: р./ < к-1. Доказательство. Пусть V - внутренний узел в исходном дереве, которому соответствует позиция р в Т\ Из узла V выходят не менее двух дуг, начинающихся внутреннему узлу в дереве Т, справедливо с разных символов исходного алфавита. Поскольку символы различны, то их кодовые представления тоже различа

ГЛАВА 3. Разработка алгоритмов построения и использования обобщенных суффиксы ых деревьев во внешней памяти.

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

Несмотря на применение описанных в предыдущей главе способов компактного представления СД, на практике далеко не всегда возможна работа с СД в оперативной памяти — размер исходных данных может быть слишком велик. При этом рассматриваемый ранее алгоритм Укконена (и его альтернативы) становится неприменимым в связи с резким - на несколько порядков уменьшением скорости его работы. Такое замедление связано с тем, что в процессе работы алгоритма необходим доступ к узлам уже построенной части дер

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

3.3.2 Определение соотношения между размером буфера для исходных данных и памятью для НСД Найдём соотношение между размером кэш-буфера под исходный текст и Ш памятью под поддеревья, которое минимизирует число дисковых операции. Очевидно, чем больше памяти выделено под буфер, тем быстрее будет выполняться построение поддеревьев. Но, вследствие уменьшения размера поддеревьев, возрастёт число проходов по исходному тексту. С другой стороны, на каждом проходе тогда будет считываться меньше страниц

.

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

В работе [60] предлагается другой подход к ускорению поиска по регулярным выражениям. Как замечают авторы этой статьи, для многих практически важных регулярных выражений можно значительно ускорить их поиск, просто выполняя поиск подстрок (так называемых грамм; если подстроки различной длины, используется термин "мультиграммы"), документа нашлось соответствие выражению <а содержащихся в регулярном выражении. Например, для того, чтобы для некоторого НТМЬЬгег=("|')?.*\.трЗ(&quo

Заметим, что вместо структуры, предложенной в [60], вполне можно использовать обобщенное суффиксное дерево. В нашем случае это целесообразно, поскольку ОСД уже применяется для ускорения поиска по расширенным префиксным регулярным выражениям. Следовательно: а). Нет необходимости в памяти под ещё одну индексную структуру. б). Нет необходимости в разработке кода для работы с новой структурой. в). Структура индекса, предложенная в [60], является статической - т.е. не предполагается возможностей м

4.2 Применение индекса на основе ОСД для поиска по сходству в Ф программном коде

Постановка и краткий обзор подходов к решению данной задачи приведены в главе 1. Хотя непосредственно использовать СД для её решения не возможным, следующими но можно поступить следующим образом. некоторыми свойствами современных представляется Воспользуемся Ф" 1). оптимизирующих компиляторов: Генерируемый код не зависит от наименований идентификаторов, форматирования текста и т.п. 2). Альтернативные конструкции во многих случаях компилируются в один и тот же код 3). Избыточный код не

Задача формулируется следующим образом. Дано множество строк Р={Рь...,Рп} и проверяемый документ 8. Требуется определить подмножество Р' с Р строк, которые имеют к или более общих подстрок с 8 длины не менее /. Здесь к и / - некоторые настраиваемые параметры, подбираемые опытным путём. В основе решения лежит алгоритм поиска наибольшей общей подстроки, описанного в [23]. Данный алгоритм основывается на построении вспомогательной структуры данных - статистики совпадений [59]. Определяется она с

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

4.3 Реализация индексного метода доступа для СУБД Ро81

§

Введём сначала основные понятия, качающиеся использования и разработки индексов в СУБД. Механизмы СУБД, реализующие работу с индексами заданного вида, образуют индексный метод доступа. Обычно метод доступа включает в себя процедуры для создания нового индекса, вставки и удаления записей из него, выполнения одного или нескольких видов поиска и некоторые Практически во всех существующих другие. СУБД реализован некоторый набор индексных методов доступа. Наиболее распространены индексы, основанн

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

(1оситеп1а1;1оп // пир://VV\V\V.ро5^

§^е5^1.о^

§/с^ос5/ 97. 8сЫеЬег, В. Оп йп(1т

§ 1о\уез1 с о т т о п апсезШгз: зтрНЁсайопв апё рага11еН2а110П / В. 8сЫеЬег, V. У1зЬкт // 81АМ 5. Сотри1.

- 1988.

- Уо1. 17. Р. 1253-1262. 149 98. 8Ыгаш, Эг. 5. МиШтесНа Соттитсайопз / Бг. 8. 8Ыгат // МсМаз1;ег Цтуегзку. Соигзе питЬег: ЕСЕ 728.

- 2004. п11р:/Лулу\у.есе.тстаз1:ег.са/ ~5Ыгат/тиШ04/тиШ04.п1т 99. 8ту1Ь, ВШ. Сотри1т

§ райегпз т з1гт

§5 / ВШ 8ту1Ь // Мс