Автор работы: Пользователь скрыл имя, 21 Июня 2014 в 12:50, курсовая работа
Проблема взаимодействия человека с компьютером существует с момента появления вычислительной техники. На начальном этапе непосредственное взаимодействие с ЭВМ осуществляли только программисты, а специалисты других областей – потребители результатов, полученных на компьютере, выступали в роли косвенных конечных пользователей, т. е. общались с компьютером через программистов. По мере расширения сферы использования компьютера и увеличения масштабов их применения конечные пользователи стали вовлекаться в процесс непосредственного взаимодействия с компьютером, что привело к появлению массовой категории пользователей – прямых конечных пользователей, работающих в диалоговом режиме.
Методы решения задач, основанные на сведении этих задач к поиску, зависят от особенностей предметной области, в которой решается задача и от требований, предъявляемых к решению. Особенности проблемной области определяются следующими параметрами:
Требования пользователя к результату задачи, решаемой с помощью поиска, можно определить количеством решений и свойствами результата и (или) способом его получения. Так, задача может иметь одно решение, несколько решений, все решения. Свойствами решения задают ограничения, которым должен удовлетворять полученный результат или способ его получения. Например, для системы, выдающей рекомендации ремонту машин, пользователь может указать требование не использовать детали некоторых производителей ценовой категории или свойств металлов. Параметр "свойства" может определять и такие особенности, как время, отведенное для решения, объем памяти, занимаемой для получения результата, указание об обязательности использования каких-либо знаний и т.п.
В настоящее время наиболее распространены поисковые системы, использующие два базовых принципа информационного поиска: поиск по ключевым словам (терминам) документов и поиск на основе кластерных методов и векторных моделей. Однако многие информационно-поисковые системы используют кластерные методы в качестве дополнения к поиску по ключевым словам, что позволяет существенно повысить эффективность и точность информационного поиска, а также удобочитаемость результатов поиска. К системам, использующим поиск по ключевым словам можно отнести большинство широко распространенных поисковых систем, среди них такие системы Web поиска как: Яндекс, Google, AstaVista, Yahoo. В подобных системах процесс поиска сводится к поиску во множестве документов вхождений каждого из заданных ключевых слов, с последующей сортировкой этих документов по степени релевантности.
Для систем осуществляющих последовательный поиск, поисковым индексом являются сам набор исходных документов. И на сравнительно небольших объёмах, данных, методы последовательного поиска являются наиболее быстрыми, хотя скорость поиска у такого рода систем жёстко ограничена и по определению и будет всегда не лучше, чем O(n), где n - суммарный размер исходных документов. Однако благодаря простоте реализации, и высокой эффективности на небольших объёмах данных, алгоритмы последовательного поиска нашли свою нишу и широкое применение. Сканирующие алгоритмы полнотекстового поиска могут применять и для решения задач нечёткого поиска где при сканировании вычисляется функция близости между терминами запроса и терминами документов.
Задачу поиска сформулируем следующим образом: пусть существует некоторый текст {} n T t1 t2Kt =, и требуется найти все вхождения в него подстроки (шаблона) {} m P p1, p2Kp =, где m ≤ n. Простейшее решение задачи состоит в последовательном сравнении и заключается в следующем: начиная с 1 t и 1 p, символов T и P до тех пор, пока не будет обнаружено совпадение или несовпадение. В последнем случае следует вернуться к началу сравнения 1 t, сдвинуться на один символ по тексту т.е. до 2 t и повторить попытку. Этот алгоритм требует выполнения не менее n-m+1 сравнений и работает медленно. Вместе с тем он весьма прост в реализации и позволяет проводить поиск с использованием шаблонов любой длинны.
В большинстве случаев при решении задач точного поиска, методом последовательного сканирования алгоритм Бойера-Мура работает быстрее, и широко применяется в программах редактирования текста. Сравнение терминов происходит с права на лево и начинается, между последним символом шаблона P и m -им символом текста T, где P = m - длинна шаблона. Далее, если обнаруживается несовпадение на некоторой паре терминов i p и j t, соответственно шаблона и текста, тогда определяем в каких позициях шаблона содержится несовпадающий символ j t, и на основе этого принимаем решение о сдвиге шаблона относительно текста. Реализация данного алгоритма требует предобработки поискового шаблона перед началом поиска за время O(m). И сам поиск происходит за время O (m⋅ n) , но в лучшем случае поиск алгоритмом Бойера-Мура может производиться за время O(n /m) .
Стоит отметить ещё один сканирующий алгоритм поиска по тексту, так называемый алгоритм СДВИГ-И. Его опубликовали в 1991 году два исследователя из Аризонского университета и Bell Labs - Уди Манбер (Udi Manber) и Сан Ву (Sun Wu). Данный алгоритм так же используется в свободно-распространяемой утилите полнотекстового поиска agrep.
Основные характеристики алгоритма СДВИГ-И:
• Предобработка поискового шаблона P за время O(m).
• Время поиска порядка O(n), не зависимо от размера алфавита и длины поискового шаблона P.
• Существуют очень эффективная реализация данного алгоритма, если длинна шаблона P будет умещаться в машинное слово вычислительной машины.
• Легко расширяем для решения задач нечеткого поиска.
Большинство современных информационно-поисковых систем, для осуществления поиска строят на основе исходной информации, логические и физические структуры данных, представляющие собой поисковый индекс, который позволяет реализовать некоторую заданную модель информационного поиска. Преобразование информации в информационно-поисковых системах строящих поисковый индекс, обычно состоит из следующих базовых этапов:
1) Анализ данных исходного
множества текстовых
2) Анализ данных полученных в пункте 1. и последующее построение поискового индекса. В данном случае индекс является представлением данных, логическая модель которого определяет способ обработки и интерпретации данных и позволяет осуществлять информационный поиск.
3) Преобразование поисковых запросов в формат позволяющий использовать поисковый индекс для вычисления функции релевантность запросов и документов и выборки релевантных запросу документов.
При обработке информации и построении поискового индекса потенциально можно использоваться достаточно широкий спектр методов анализа текстовой информации документов, как например методы статистического, семантического, синтаксического и лингвистического анализа текста. Наибольшее распространение получили методы, использующие статистический анализ документов. Статический анализ уже давно получил широкое применение в задачах информационного поиска. Впервые этот подход был рассмотрен в работах Луна, где в качестве меры значимости отдельных фраз, являлась частота их появления в документах. И при этом наиболее значимые слова находятся в середине частотного диапазона их появления в документах, т.е. значимые слова не входят не входят в число ни наиболее часто, ни наиболее редко встречающихся слов. В настоящее время эти простые идеи Луна лежат в основе большинства современных информационно-поисковых систем. Определим исходное представление любого документа как список слов с учётом порядка их
следования в документе. Процесс выделения значимого информационного содержимого документов обычно состоит из следующих шагов:
1) Удаление очень часто и редко встречающихся слов
2) Выделение общих языковых словоформ, слов текста документов.
3) Определение эквивалентных (синонимичных) словоформ, т.е. построение тезауруса.
В ходе данного процесса, текстовая информация документов нормализуется в список ключевых словоформ, которые служат для классификации документов в ходе поисковых запросов и используются для построения текстового индекса документов. Стоит отметить, что на этапе преобразования исходной текстовой информации в поисковый индекс при использовании стемминга текста, некоторая часть содержательной информации безвозвратно теряется, поскольку при стемминге, к одной словоформе могут быть приведены два и более разных по семантике слова, однако даже при использованием чисто алгоритмических методов стемминга, удаётся получить удовлетворительную точность поиска.
Идея, заключающаяся в основе хеширующих методов поиска состоит в следующем: пусть на множестве ключевых терминов документов задана функция (хеш-функция) () i H w, отображающая множество исходных терминов документов в конечный отрезок целых чисел [nKm], и пусть n ≤ m. Выделим множество ячеек памяти для m − n +1 терминов и для каждого термина i w будем помещать его в ячейку под номером () i H w. Если () () i j H w ≠ H w для всех i ≠ j, то для поиска произвольного термина i w потребовалось бы только одно обращение к элементу массива под номером () i H w. Но поскольку построение хеш-функции на множестве терминов довольно сложная задача, на практике допускаются коллизии хеширования, когда () () i j H w = H w, для некоторых пар i ≠ j. Существую два способа разрешения таких коллизий:
1. При хешировании нового термина, если возникает коллизия, то помещаем термин в ближайшую свободную ячейку или ячейку с номером, вычисляемым по некоторому правилу.
2. Хранить в ячейке ссылку на список терминов с одинаковыми значениями хеш-функции.
Простота реализации, и высокая скорость поиска на достаточно небольших объёмах данных, являются основными преимуществами хеширующих методов поиска.
Логически, инвертированные файлы устроены подобно указателю в конце книги. А точнее в виде списка ключевых терминов, где каждому термину сопоставлен список его вхождений в документы. Каждое вхождение ключевого термина, определяется ссылкой на исходный документ содержащий данное ключевое слово. Инвертирование является полным, если в списке вхождений терминов помимо ссылок на документы содержится информация о точном местоположении каждого термина, однако в этом случае размер индекса может быть очень велик, и в несколько раз превышать суммарный размер исходных документов. Поэтому в большинстве систем, термины в инвертированном списке ссылаются на документы как таковые, где не указывается точное местоположение термина в документе. Поиск происходит посредством сканирования инвертированного списка ключевых слов для нахождения соответствующих терминов запроса и документов, и последующего объединения или пересечения результатов полученных для каждого термина поискового запроса. Для уменьшения размеров инвертированного индекса обычно применяют неполное инвертирование, когда вместо ссылок на точный адрес термина, хранятся только ссылки на документы или на блоки данных некоторого фиксированного размера в которых содержится данный термин.
В современных поисковых системах, основанных на ИФ применяются также методы сжатия инвертированного индекса и в настоящее время размер индекса сжатых инвертированных файлов может составлять лишь 4-10% от общего объёма исходных документов. Для ускорения поиска инвертированный словарь ключевых слов документов может быть представлен в виде дерева или хеш-таблицы. В системах, работающих с большим объёмом исходных текстовых данных инвертированные файлы организованы в виде иерархических структур.
К сожалению полнотекстовые индексы, базирующиеся на структурах, данных, основанных на списках не могут обеспечить время поиска по текстовым данным лучше, чем O (log n). К тому же списки ключевых терминов, позволяющие осуществлять поиск с логарифмическим временем, должны быть отсортированы, ведь только тогда по ним можно осуществлять бинарный поиск за логарифмическое время. Но в свою очередь отсортированные списки, трудно модифицировать, вставлять и удалять ключевые термины, количество операций необходимых для этого обычно не меньше чем O(n).
Бинарные деревья могут применяться в качестве структуры данных, для инвертированных файлов. Для этого необходимы бинарные лексиграфические отношения между ключевыми терминами инвертированного списка, т.е. два любых термина i w и j w должны быть лексикографически сравнимы, для того чтобы построить бинарное дерево терминов. В этом случае время поиска по шаблону будет логарифмическим и ограничено величиной O (m⋅ log n).
Множество разных задач, начиная от задач поиска наибольшей общей подстроки, комплементарных пар в последовательностях ДНК и заканчивая задачами сжатия информации, нечёткого поиска и кластеризации можно эффективно решить с помощью суффиксных деревьев.
Суффиксным деревом T для строки n S s1s2 s3Ks =, называется структура данных, обладающую следующими свойствами:
Рисунок 3 - суффиксное дерево для строки S = BANANAS
Очевидно, что данная структура данных обеспечивает поиск за O (m + k) операций сравнения, где k − число всех вхождений искомой подстроки в исходной строке. Суффиксное дерево, построенное для некоторого набора строк {} m S1S2S3KS, позволяет решить задачу на нахождение наибольшей общей подстроки данного набора строк. Однако существуют и слабые стороны данной структуры данных, в частности занимаемая ими память. Её можно оценить, посчитав количество узлов, необходимых для построения суффиксного дерева строки длинной n. Поскольку каждый узел дерева имеет как минимум два потомка, и при этом каждый потомок порождает уникальный путь до одного и n суффиксов строки S , то это значит что всего внутренних узлов будет не меньше чем n , и прибавим сюда количество внешних узлов (листьев дерева), получаем в итоге 2n узлов, из этого следует, что можно построить суффиксное дерево, занимающее O(n) дискового пространства.
Информация о работе Понятие естественно-языкового интерфейса