Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Текстовые базы данных

Содержание

Текстовые базы данныхСодержат текстовую информацию/текстовые документыНаиболее распространенные на сегодняшний день«Зрелый» уровень развития; «первые шаги» в 60-70-х годахСуществует условное разбиение:Структурированные (structured) бд: форматированные записи, объект задается структуройНеструктурированные (unstructured) бд: например, полные тексты статейПолуструктурированные (semi-structured) данные: (веб-страницы, XML-документы)«Зрелый»
Текстовые базы данныхСодержат текстовую информацию/текстовые документыНаиболее распространенные на сегодняшний день«Зрелый» уровень развития; Документ?  В зависимости от контекста, книга, одна глава, один параграф, одна Поиск без использования индексаПоследовательное полнотекстовое сканирование текстаДостоинства:Не требуется дополнительное место для индексаБыстрые Алгоритмы1 для нахождения точного соответствия (exact matching) в общей памяти:Knuth-Morris-Pratt: алгоритм линейной Инвертированный индексТрадиционный способ, широко используется в поисковых машинахИнвертированный?   Каждый документ «Разрешение» индекса:Степени детализации индекса (granularity of the index) – «разрешение» индекса: разрешение Плюсы и минусы крупноструктурного индекса:Маленький размерЛегко поддерживать (обновлять, вносить изменения)Требует значительного полнотекстового Сжатие:Инвертированные файлы - ориентировочно 50-100% от размера суммарного текстаЛучшее сжатие, если:Индекс без Составные запросы:AND: выполняется путем извлечения для каждого термина списка документов и нахождения Алгоритм построения индекса:Для каждого документа в коллекции, сформировать список терминов, где для Битово-матричное индексирование Еще один способ представления инвертированного индекса: в матричной формеКрупноструктурная или Иерархическое сжатие битовых строк:Разбиваем строку на блоки символов одинакового размераДля каждого Матрица обычно разреженная, большинство листьев - блоки нолейСжатие происходит за счет того, Сигнатурное индексированиеВероятностная техникаСигнатура – битовый массив, генерируемый путем хеширования терминов в массив Достоинства сигнатурных файлов:Меньший размер (в сравнении с мелко-структурным инвертированным индексом); типичный размер Пример:Есть три документа со следующими терминами:    D1:	база данных, объект, Организация сигнатурного файла:Основные принципы:Неизбыточный размер файлаМинимизация операций ввода/вывода при выполнении запросовПростая поддержка (2) Транспонированный сингулярный файл:Сингулярный файл – матрица (таблица) в которой число строк Один из найденных сравнением сигнатур документов нерелевантен запросу Сигнатурное индексирование (3) Двухуровневые сигнатурные файлы:Два уровня (типа) сигнатур: высшего и низшего уровняСигнатура высшего Многоуровневые сигнатурные файлы (multi-level signature file)Обобщение двухуровневых сигнатурных файлов: сигнатуры в каждом Пример: S(4,2,3)0011111011100011Указатели на документыS-деревья Выполнение запросов с помощью S-деревьев:Сгенерировать сигнатуру запроса путем суперпозиционного кодирования терминовОбход дерева Переполнение узла:Узел разбивают на два, стараясь при этом минимизировать весы новых получающихся Расширенный информационный поискОсновные принципы:Результаты поиска не обязательно точно соответствуют запросуРанжирование (ranking) документов, Расширенный информационный поискВажные понятия: Синонимия (synonymy): различные термины имеют одинаковое илиблизкое значениеПолисемия Коллекцию документов можно представить в виде матрицы D (обобщение битово-матричного индекса).Dt,i = Сложности:Если вес термина задается как количество экземпляров данного термина в документе, то Если какое-то слово встречается часто, то это слово хорошо передает смысл документа Геометрические расстояния в векторном пространстве:Евклидово расстояние (Euclidean distance): Латентное семантическое индексированиеМатрица, которая ставится в соответствие коллекции документов, обычно разреженная (большинство Сингулярное разложение:Широко используется во многих областяхДля любой матрицы D существует разложение Сингулярное разложение:Эффект: удаление «шума», выявление скрытых (неявных) семантических связейВектор запроса подвергается следующей УпражненияОбъясните более подробно почему число false drops уменьшается, если ноли и единицы
Слайды презентации

Слайд 2 Текстовые базы данных
Содержат текстовую информацию/текстовые документы
Наиболее распространенные на

Текстовые базы данныхСодержат текстовую информацию/текстовые документыНаиболее распространенные на сегодняшний день«Зрелый» уровень

сегодняшний день
«Зрелый» уровень развития; «первые шаги» в 60-70-х годах
Существует

условное разбиение:
Структурированные (structured) бд: форматированные записи, объект задается структурой
Неструктурированные (unstructured) бд: например, полные тексты статей
Полуструктурированные (semi-structured) данные: (веб-страницы, XML-документы)
«Зрелый» уровень развития; «первые шаги» в 60-70-х годах
Области применения:
Электронный документооборот (автоматизация офиса)
Цифровые библиотеки
Юридические и патентные системы
Электронные словари/энциклопедии/справочники
Электронные газеты/журналы/книги
Библиотеки исходников программного обеспечения (source program libraries)

Слайд 3 Документ?
В зависимости от контекста, книга, одна

Документ? В зависимости от контекста, книга, одна глава, один параграф, одна

глава, один параграф, одна статья, одни тезисы к статье,

письмо, исходный код какой-нибудь программы, поле типа VARCHAR или TEXT в бд и т.д.
Задача: поиск в коллекции документов по их содержимому - ассоциативный поиск (associative search)
Используются ключевые слова (keywords) или термины (terms)
Поисковый запрос: совокупность ключевых слов, объединенная булевыми (или логическими) выражениями AND, OR, NOT
Индекс: механизм для нахождения заданного термина в тексте

Текстовые базы данных


Слайд 4 Поиск без использования индекса
Последовательное полнотекстовое сканирование текста
Достоинства:
Не требуется

Поиск без использования индексаПоследовательное полнотекстовое сканирование текстаДостоинства:Не требуется дополнительное место для

дополнительное место для индекса
Быстрые изменения/обновления (не нужно вносить изменения

в индекс)
Нахождение частично совпадающих строк относительно простое (при помощи wildcard-символов: таких как *,? и т.д.)
Возможно приближенное сравнение (approximate matching) (путем задания порогового значения для расстояния Левенштейна (Levenshtein distance или edit distance)

Слайд 5 Алгоритмы1 для нахождения точного соответствия (exact matching) в

Алгоритмы1 для нахождения точного соответствия (exact matching) в общей памяти:Knuth-Morris-Pratt: алгоритм

общей памяти:
Knuth-Morris-Pratt: алгоритм линейной сложности (O(n) time); основан на

предварительной обработке строки поиска (строка поиска – образец который ищется в тексте)
Boyer-Moore: поиск происходит быстрее для более длинных строк; на практике скорость работы сублинейна; основан на предварительной обработке строки поиска
Aho-Corasick: одновременный поиск нескольких терминов; основан на теории конечных автоматов (finite automata)
Rabin-Karp: используется специальная хеш-функция – хеш-значения последовательно вычисляются для всех подстрок текста и потом сравниваются с хеш-значением строки поиска



1 Более подробно описаны здесь:
Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы. Построение и анализ, 2-ое издание, Вильямс, 2005
http://en.wikipedia.org/wiki/String_searching_algorithm (с текстами исходников)

Поиск без использования индекса


Слайд 6 Инвертированный индекс
Традиционный способ, широко используется в поисковых машинах
Инвертированный?

Инвертированный индексТрадиционный способ, широко используется в поисковых машинахИнвертированный?  Каждый документ


Каждый документ - это список терминов (index

terms), а инвертированный индекс каждому термину ставит в соответствие список документов в которых встречается данный термин; т.е. получаем обратное (инвертированное) соответствие – у каждого термина есть список документов
Лексикон: термины, используемые в документе(-ах)
Правила построения лексикона:
Все символы переводятся в нижний регистр (case folding);
Удаление суффиксов, в индекс идут корневые формы слов (stemming)
В индекс не включаются так называемые стоп-слова: (например, для английского языка не включаются the, is, as, that, и ряд других)

Слайд 7 «Разрешение» индекса:
Степени детализации индекса (granularity of the index)

«Разрешение» индекса:Степени детализации индекса (granularity of the index) – «разрешение» индекса:

– «разрешение» индекса: разрешение с которым индекс определяет местоположение

термина в документе
Три степени детализации индекса:
Крупноструктурный индекс (coarse-grained index): каждый термин указывает на блок(-и) текста (а блок включает в себя несколько документов);
Среднеструктурный индекс (moderate-grained): указывает на документы, содержащие термин (список id-номеров документов);
Мелкоструктурный индекс (fine-grained): может указывать на предложение, в котором есть данный термин, или порядковый номер термина внутри документа или даже точную байтовую позицию термина.

Инвертированный индекс


Слайд 8 Плюсы и минусы крупноструктурного индекса:
Маленький размер
Легко поддерживать (обновлять,

Плюсы и минусы крупноструктурного индекса:Маленький размерЛегко поддерживать (обновлять, вносить изменения)Требует значительного

вносить изменения)
Требует значительного полнотекстового сканирования
Нерелевантен при поиске нескольких терминов

одновременно (например, искомые слова могут находиться в одном и том же блоке, но необязательно в одном и том же документе)
Плюсы и минусы мелкоструктурного индекса:
Позволяет находить слова, расположенные рядом (proximity queries)
Большой размер индекса
Тяжело поддерживать
Если запросов в которых ищут близко расположенные слова немного, то используют среднеструктурный индекс

Инвертированный индекс


Слайд 9 Сжатие:
Инвертированные файлы - ориентировочно 50-100% от размера суммарного

Сжатие:Инвертированные файлы - ориентировочно 50-100% от размера суммарного текстаЛучшее сжатие, если:Индекс

текста
Лучшее сжатие, если:
Индекс без потери общности можно задать в

виде целых чисел; например, лексикон сортируется в алфавитном порядке, и затем каждому термину из лексикона ставится в соответствие число - номер по списку; указатели на документы - id-номера документов
Храним неполные id-номера документов; например, <8: 3, 5, 19, ...> , где 8 – это номер термина в лексиконе, а 3, 5, 19 – id-номера документов, можно упростить до <8: 3, 2, 14, ...>
Располагаем термины лексикона в алфавитном порядке, тогда общие префиксы расположенных рядом терминов можно представлять более компактно
Для мелкоструктурного индекса: вместо сохранения полных указателей на термины в документе, можно хранить интервалы между последовательно встречающимися терминами

Инвертированный индекс


Слайд 10 Составные запросы:
AND: выполняется путем извлечения для каждого термина

Составные запросы:AND: выполняется путем извлечения для каждого термина списка документов и

списка документов и нахождения пересечения
OR: аналогично, но возвращаем объединение

списков
NOT: обычно сочетается с оператором AND, затем вычисляется логическая разность между списками
Структуры данных для инвертированного индекса:
B+-дерево, где термины являются ключами, а списки указателей листьями
Организация в виде хеша, обычно динамическая версия:
Линейный хеш (linear hash)
Расширяемый хеш (extendible hash)
Бор-структура или трай-структура («trie-structure» от retrieval, «бор» от выборка: на каждый узел приходится только один символ, термин находится движением по бору (дереву) с вершины до соответствующего листа
Список документов находится в структуре данных либо локально, либо (предпочтительно) от нее обособлен

Инвертированный индекс


Слайд 11 Алгоритм построения индекса:
Для каждого документа в коллекции, сформировать

Алгоритм построения индекса:Для каждого документа в коллекции, сформировать список терминов, где

список терминов, где для каждого термина есть список указателей

на месторасположение данного термина(-ов) в документе. Итог - большой последовательный файл S.
Отсортируем S, с помощью например mergesort (сортировка слиянием).
Объединим последовательные элементы, представляющие один и тот же индекс-термин.
На основе выбранной структуры данных (B+-дерево, хеш, ...) сформировать индекс. При этом пусть листья содержат указатели на хранящиеся обособлено списки id-номеров документов (и указателей на месторасположение терминов в документах, если строится мелкоструктурный индекс). Сами же списки хранятся как записи переменной длины.
Резюме:
Очень эффективный и популярный метод извлечения данных
Несмотря на минусы (большой размер и сложность поддержки индекса) широко используется для коллекций статичных документов

Инвертированный индекс


Слайд 12 Битово-матричное индексирование
Еще один способ представления инвертированного индекса:

Битово-матричное индексирование Еще один способ представления инвертированного индекса: в матричной формеКрупноструктурная

в матричной форме
Крупноструктурная или среднеструктурная степень детализации
Битовая матрица –

матрица, в которой число строк соответствует числу терминов в индексе (размер лексикона), число столбцов = число документов в коллекции. равен 1, если термин i встречается в документе j, иначе равен 0.
Эффективно для запросов с логическими выражениями: AND, OR, NOT могут быть реализованы в «железе» (например, с параллельной обработкой по 64 бита)
Проблема: индекс занимает много места (размер матрицы = число терминов*число документов, матрица разреженная (нолей много больше чем единиц)
Комбинация индексов: инвертированный индекс для не часто встречающихся терминов и бинарная матрица для более часто встречающихся терминов
Сжатие индекса: кодирование с переменной длиной строки (или метод RLE); заменяет последовательности нолей на их количество

Слайд 13 Иерархическое сжатие битовых строк:
Разбиваем строку на блоки

Иерархическое сжатие битовых строк:Разбиваем строку на блоки символов одинакового размераДля

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

блока операцию дизъюнкции (OR - операция логического сложения), результат даст нам бит следующего уровня; операция OR примененная к блоку со одними нулями даст ноль, если в блоке имеется хоть одна единица, то получим единицу
Рекурсивно повторяем процесс на всех уровнях иерархии

Каждый бит легко определяется построением
соответствующего пути от вершины дерева

Битово-матричное индексирование


Слайд 14 Матрица обычно разреженная, большинство листьев - блоки нолей
Сжатие

Матрица обычно разреженная, большинство листьев - блоки нолейСжатие происходит за счет

происходит за счет того, что блоки нолей можно не

хранить совсем

Битово-матричное индексирование


Слайд 15 Сигнатурное индексирование
Вероятностная техника
Сигнатура – битовый массив, генерируемый путем

Сигнатурное индексированиеВероятностная техникаСигнатура – битовый массив, генерируемый путем хеширования терминов в

хеширования терминов в массив индексов (о генерации ниже); длина

сигнатуры обычно как минимум несколько сотен бит
Сигнатуры хранятся в отдельном (сигнатурном) файле; его размер меньше чем размер всей коллекции документов
Сигнатурный файл - фильтрующий механизм, уменьшающий количество данных, которые просматриваются во время поиска
Возможен поиск по частичному совпадению
Поисковый запрос рассматривается как самостоятельный документ (состоящий из терминов, заданных в запросе); у запроса есть своя сигнатура; при поиске сигнатура запроса Q сравнивается с сигнатурами документов Di; если единичные биты Q есть в сигнатуре документа Dj, то Dj является возможным результатом (candidate result)
Сигнатура приблизительное описание документа; документы нерелевантные запросу (их называют false drops) должны быть устранены

Слайд 16 Достоинства сигнатурных файлов:
Меньший размер (в сравнении с мелко-структурным

Достоинства сигнатурных файлов:Меньший размер (в сравнении с мелко-структурным инвертированным индексом); типичный

инвертированным индексом); типичный размер – 10-20% от общего размера

коллекции документов
Более удобны чем многомерные индексы (о них будет рассказано позже)
Два основных метода генерации сигнатур:
Метод сигнатур слов (word signature method): каждому термину хеш-функция ставит в соответствие определенную битовую комбинацию (bit pattern) заданной длины; получившиеся композиции соединяют вместе, что дает сигнатуру документа; метод сохраняет информацию о последовательности с которой термины встречаются в документе; в тоже время, дает более высокую вероятность появления нерелевантных запросу документов
Суперпозиционное кодирование (superimposed coding): каждому термину ставится в соответствие битовая комбинация такой же длины, что и полная сигнатура; получившиеся комбинации логически складывают (выполняют OR), получая итоговую сигнатуру; метод по умолчанию далее
Как уменьшить число false drops?
Количество нолей и единиц в сигнатуре должно быть примерно одинаковым (вес сигнатуры - количество битовых единиц в ней)
Ноли и единицы должны быть однородно распределены по сигнатуре

Сигнатурное индексирование


Слайд 17 Пример:
Есть три документа со следующими терминами:

Пример:Есть три документа со следующими терминами:  D1:	база данных, объект, программирование,

D1: база данных, объект, программирование, схема

D2: алгоритм, компьютер, программирование
D3: алгоритм, структура данных, программирование
Длина сигнатуры 8 бит, хеш-функция возвращает позицию бита с единицей (остальные семь бит – 0)
hash(“алгоритм ”) = 3 (т.е. 00100000);
hash(“компьютер”) = 1 (10000000);
hash(“база данных”) = 7 (00000010);
hash(“структура данных”) = 5;
hash(“объект ”) = 6;
hash(“программирование”) = 4;
hash(“схема”) = 1.
Сигнатура D1 – 10010110, сигнатура D2 – 10110000, D3 – 00111000
Запрос: найти документы с «алгоритм» и «программирование»
Запрос Q задается сигнатурой 00110000; единичные биты Q есть у D2 и D3 (технически, выполняется побитовая операция AND);
для получения окончательного результата нужно проверить D2 и D3 на наличие «алгоритм» и «программирование»

00000010
00000100
00010000
10000000
-----------
10010110

Сигнатурное индексирование


Слайд 18 Организация сигнатурного файла:
Основные принципы:
Неизбыточный размер файла
Минимизация операций ввода/вывода

Организация сигнатурного файла:Основные принципы:Неизбыточный размер файлаМинимизация операций ввода/вывода при выполнении запросовПростая

при выполнении запросов
Простая поддержка (изменение, удаление, добавление) индекса

(1) Сингулярный

файл:
Составлен из списка сигнатур для всех документов из коллекции
Выполнение запроса: генерирование сигнатуры запроса; ее сравнение (выполнение побитовой операции AND) с каждой сигнатурой, имеющейся в сигнатурном файле (т.е. приходится сканировать весь сигнатурный файл); найденные документы (возможные результаты) затем просматриваются полностью, чтобы исключить false drops
Скорость выполнения запросов невелика
Замечание: для физического представления сигнатурного файла B-деревья не подходят

Сигнатурное индексирование


Слайд 19 (2) Транспонированный сингулярный файл:
Сингулярный файл – матрица (таблица)

(2) Транспонированный сингулярный файл:Сингулярный файл – матрица (таблица) в которой число

в которой число строк равно числу сигнатур (= числу

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

Сигнатурное индексирование


Слайд 20 Один из найденных сравнением сигнатур документов нерелевантен запросу

Один из найденных сравнением сигнатур документов нерелевантен запросу Сигнатурное индексирование


Сигнатурное индексирование


Слайд 21 (3) Двухуровневые сигнатурные файлы:
Два уровня (типа) сигнатур: высшего

(3) Двухуровневые сигнатурные файлы:Два уровня (типа) сигнатур: высшего и низшего уровняСигнатура

и низшего уровня
Сигнатура высшего уровня является фильтром для низшего

уровня
Генерация сигнатуры высшего уровня:
а) Разбить документы на группы и генерировать сигнатуры для групп; сигнатуры больше в длину, но суммарный размер меньше
б) Генерировать сигнатуры путем логического сложения (OR) сигнатур низшего уровня; недостаток - в силу OR будет расти число единиц и, значит, количество false drops

Сигнатурное индексирование


Слайд 22 Многоуровневые сигнатурные файлы (multi-level signature file)
Обобщение двухуровневых сигнатурных

Многоуровневые сигнатурные файлы (multi-level signature file)Обобщение двухуровневых сигнатурных файлов: сигнатуры в

файлов: сигнатуры в каждом узле получаются логическим сложением (OR)

сигнатур, содержащихся в дочерних узлах (см. «двухуровневые сигнатурные файлы», способ б)
S-деревья:
S-деревья и B-деревья имеют несколько общих свойств
S-дерево - сбалансированное по высоте дерево с множественным ветвлением (height balanced multiway tree)
Каждый узел соответствует странице (page) (блоку данных)
У корня дерева (корневого узла) не менее двух и не более K (= емкость страницы) дочерних узлов (если корень не является листом (leaf) дерева)
Все узлы за исключением корневого имеют не менее k и не более K дочерних узлов (1 <= k <= K, например k=K/2)
Каждый узел (за исключением возможно корневого) содержит не менее k сигнатур
Листья дерева содержат указатели на документы
Отличия S-дерева от B-дерева:
Сигнатуры в узлах не упорядочены
Одна и та же сигнатура может присутствовать в нескольких местах (сигнатуры разных документов могут совпадать)
Запросу вполне может соответствовать несколько путей движения по дереву

S-деревья


Слайд 23 Пример: S(4,2,3)
00111110
11100011
Указатели на документы
S-деревья

Пример: S(4,2,3)0011111011100011Указатели на документыS-деревья

Слайд 24 Выполнение запросов с помощью S-деревьев:
Сгенерировать сигнатуру запроса путем

Выполнение запросов с помощью S-деревьев:Сгенерировать сигнатуру запроса путем суперпозиционного кодирования терминовОбход

суперпозиционного кодирования терминов
Обход дерева начнем с вершины
Для каждого узла

просматриваем содержащиеся в нем сигнатуры; если 1-биты сигнатуры запроса совпадают с 1-битами сигнатур узла, то переходим к соответствующим дочерним узлам
Дойдя до листьев дерева, получим указатели на документы, которые нужно просмотреть для устранения false drops
Вставка сигнатуры в S-дерево:
Основная идея: логическое сложение (OR) всех сигнатур в узле должно иметь как можно меньший вес; тогда достигается наивысшая избирательность (selectivity)
Для определения подходящего узла для вставки осмотр начинают с вершины дерева, переходя на наиболее «близкие» дочерние узлы; под наиболее «близким» узлом может пониматься:
Узел, сигнатуры которого, имеют наименьшее расстояние Хемминга (Hamming distance) с сигнатурой вставляемого документа, или
Узел, имеющий наименьшее увеличение веса (weight increase), когда сигнатуры узла и добавляемую сигнатуру логически складывают (OR)
После вставки нужно внести изменения во все выше лежащие узлы

S-деревья


Слайд 25 Переполнение узла:
Узел разбивают на два, стараясь при этом

Переполнение узла:Узел разбивают на два, стараясь при этом минимизировать весы новых

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

ними
Используют следующий эвристический алгоритм для разбиения узла S-дерева:
(1) Выбирается сигнатура имеющая наибольший вес; она добавляется в группу 1; в группу 2 добавляется та сигнатура, что имеет наибольшее увеличение веса по отношению к сигнатуре из группы 1
(2) Каждая из оставшихся сигнатур добавляются в ту группу в которой достигается наименьшее увеличение веса при логическом сложении сигнатур уже добавленных в группу и рассматриваемой сигнатуры
В равнозначных случаях используется следующие правила (по порядку):
а) добавить в меньшую группу;
б) добавить в группу с меньшим весом;
в) добавить в случайно выбранную группу.
Если на каком-то шаге в одной из групп K-k сигнатур, добавить остающиеся сигнатуры в другую группу
Распространение:
Как и у B-деревьев, разбиение узлов может быть распространено на выше
лежащие узлы вплоть до вершины
После разбиения узла все выше лежащие узлы должны быть
соответствующим образом изменены
Обновление документа: индекс обновляется путем последовательного удаления и вставки сигнатуры

S-деревья


Слайд 26 Расширенный информационный поиск
Основные принципы:
Результаты поиска не обязательно точно

Расширенный информационный поискОсновные принципы:Результаты поиска не обязательно точно соответствуют запросуРанжирование (ranking)

соответствуют запросу
Ранжирование (ranking) документов, т.е. все документы из коллекции

могут быть расставлены в определенном порядке на основе ранга каждого документа; ранг документа определяется на основе «расстояния» от документа до запроса
Учитываются семантические связи между терминами

Слайд 27 Расширенный информационный поиск
Важные понятия:
Синонимия (synonymy): различные термины

Расширенный информационный поискВажные понятия: Синонимия (synonymy): различные термины имеют одинаковое илиблизкое

имеют одинаковое или
близкое значение
Полисемия (многозначность) (polysemy): один термин имеет

несколько значений
Вес (weight) термина: указывает на важность термина в документе
Добротность (качество) поиска:
Точность (precision) поиска: отношение количества извлеченных документов, релевантных (удовлетворяющих условиям поиска) поиску, к общему количеству извлеченных документов
Полнота (recall) поиска: отношение количества извлеченных документов, релевантных поиску, к общему количеству релевантных документов
Часто происходит объединение этих двух понятий в одно – релевантность; релевантность поискового запроса - степень соответствия искомого (запроса) и найденного (результатов запроса), уместность результата; релевантность - субъективное понятие

Слайд 28 Коллекцию документов можно представить в виде матрицы D

Коллекцию документов можно представить в виде матрицы D (обобщение битово-матричного индекса).Dt,i

(обобщение битово-матричного индекса).
Dt,i = значение веса термина t в

документе i (вес термина может задаваться как количество раз, которое термин встречается в документе).
Столбцы матрицы (векторы) характеризуют документы.
Запрос – документ: запрос -> вектор (при построении веса входящих в запрос терминов как правило не учитываются).
Задача информационного поиска: Найти k документов, вектора которых наиболее «близки» к вектору запроса.
Вопрос: как измерять «расстояние» между документами (между запросом и документом)?
Первой попытка: меры похожести (similarity), скалярное произведение векторов запроса и документа:
similarity(Q, Di) = Q • Di = tTermsQtDt,i.

Расширенный информационный поиск


Слайд 29 Сложности:
Если вес термина задается как количество экземпляров данного

Сложности:Если вес термина задается как количество экземпляров данного термина в документе,

термина в документе, то широко используемые термины (слова) будут

иметь избыточный вес
Длинные документы (содержат больше терминов) будут в более привилегированном положении чем короткие
Закон Ципфа (Zipf’s law): Формулировка закона - если все слова некоторого языка (или достаточно длинного текста) упорядочить по убыванию частоты их использования, то частота n-го слова в таком списке окажется приблизительно обратно пропорциональной его порядковому номеру n. Можно записать: f * r = c, где f – частота слова в документе, r – ранг слова, c – константа.
Следствия: небольшое количество слов встречается очень часто; среднее количество слов встречается со средней частотой; большинство слов встречается очень редко

Расширенный информационный поиск


Слайд 30 Если какое-то слово встречается часто, то это слово

Если какое-то слово встречается часто, то это слово хорошо передает смысл

хорошо передает смысл документа (бОльший вес)
Слова, которые часто встречаются

во многих документах, не несут существенную информацию
Правило TF*IDF (TF*IDF rule, TF*IDF – term frequency times inverse document frequency):
Dt,i = tf*idf = ft,i*log(1+N/ft), где tf = ft,i - частота термина t в документе i
tf и idf могут вычисляться по разному – например, частота термина (tf) может быть нормализована

Расширенный информационный поиск


Слайд 31 Геометрические расстояния в векторном пространстве:
Евклидово расстояние (Euclidean distance):

Геометрические расстояния в векторном пространстве:Евклидово расстояние (Euclidean distance):   Выделяет

Выделяет длинные документы; степень

подобия (similarity)
документа и запроса может определяться по мере обратной
евклидовому расстоянию
Определение угла (косинуса угла):



степень подобия –


Вместе с правилом TF*IDF:

Расширенный информационный поиск


Слайд 32 Латентное семантическое индексирование
Матрица, которая ставится в соответствие коллекции

Латентное семантическое индексированиеМатрица, которая ставится в соответствие коллекции документов, обычно разреженная

документов, обычно разреженная (большинство элементов ноли).
Альтернатива: латентное семантическое индексирование

(LSI)
LSI позволяет представить термины и документы в «семантическом пространстве», выявляя скрытые (внутренние) семантические связи между терминами и документами.
Процедура для LSI:
Создать частотную матрицу D для искомой коллекции документов
Вычислить сингулярное разложение (singular value decomposition - SVD) матрицы D; D = A x S x B (см.след.слайд)
Уменьшить размер матриц путем удаления малозначащих строк/столбцов
Сохранить получившиеся матрицы с помощью какого-нибудь метода индексирования
Выполнение запроса: вектор запроса преобразуется в трансформированный вектор; получившийся вектор сравнивается (определяется степень подобия) с векторами одной из уменьшенных матриц разложения

Слайд 33 Сингулярное разложение:
Широко используется во многих областях
Для любой матрицы

Сингулярное разложение:Широко используется во многих областяхДля любой матрицы D существует разложение

D существует разложение
D = A

* S * BT:
Матрицы А размером M*R и B размером N*R ортогональные, т.е. A*AT = I, B*BT = I; матрица S, сингулярная матрица, размером R*R является диагональной, причем диагональные элементы (они также являются сингулярными числами матрицы А) не возрастают (sj,j >= sj+1,j+1)
Базовая идея сингулярного разложения – уменьшить размер матрицы S, c R до k; уменьшив матрицу S до размера k*k (удалив R-k сингулярных значений справа внизу), получим что матрица D может быть представлена в виде произведения матриц Ak (M*k), Sk (k*k), Bk (N*k)

Латентное семантическое индексирование


Слайд 34 Сингулярное разложение:
Эффект: удаление «шума», выявление скрытых (неявных) семантических

Сингулярное разложение:Эффект: удаление «шума», выявление скрытых (неявных) семантических связейВектор запроса подвергается

связей
Вектор запроса подвергается следующей трансформации: Qk = QT *

Ak * Sk-1; затем, вычисляется степень подобия между Qk и векторами матрицы Bk (без доказательства)
Слабая сторона LSI: метод требует значительных матричных преобразований и вычислений
LSI подходит для статичных (или редко обновляющихся) коллекций документов

Латентное семантическое индексирование


  • Имя файла: tekstovye-bazy-dannyh.pptx
  • Количество просмотров: 176
  • Количество скачиваний: 0