'

Индексирование текста для поиска с учетом орфографических ошибок

Понравилась презентация – покажи это...





Слайд 0

Индексирование текста для поиска с учетом орфографических ошибок Искандер Акишев Михаил Дворкин СПбГУ ИТМО Ноябрь 2006 г.


Слайд 1

Часть 0 – Предисловие


Слайд 2

Часть I - Введение Область применения Постановка задачи Примеры Имеющиеся результаты


Слайд 3

Область применения Необходимость поиска с учетом ошибок: Поиск документов в Интернете Автоматическое исправление орфографических ошибок Вычислительная биология: Поиск образца в неточных экспериментальных данных Поиск похожих участков ДНК


Слайд 4

Постановка задачи (1) Коллекция документов Т суммарного размера n Образец P длины m Предполагается не более d ошибок: Пропущенный символ Лишний символ Измененный символ Можно также сузить на метрику Хэмминга


Слайд 5

Постановка задачи (2) Требуется найти Все вхождения Все начальные позиции вхождений Все документы, содержащие образец


Слайд 6

Пример Документы: GACTCAAAACGGGTGC GTGACCGACGGATGAC CCTACAAACATGTTCG TAAACCTGAGACCAAC Образец: ACAAC Разрешенное число ошибок: d = 1


Слайд 7

Пример Документы: GACTCAAAACGGGTGC GTGACCGACGGATGAC CCTACAAACATGTTCG TAAACCTGAGACCAAC Образец: ACAAC Разрешенное число ошибок: d = 1 Различные вхождения: 1-й документ: (6, 10), (7, 10) 3-й документ: (4, 7), (4, 8), (4, 9), (6, 9) 4-й документ: (2, 5), (11, 16), (12, 16), (13, 16)


Слайд 8

Пример Документы: GACTCAAAACGGGTGC GTGACCGACGGATGAC CCTACAAACATGTTCG TAAACCTGAGACCAAC Образец: ACAAC Разрешенное число ошибок: d = 1 Начальные позиции вхождений: 1-й документ: 6, 7 3-й документ: 4, 6 4-й документ: 2, 11, 12, 13


Слайд 9

Пример Документы: GACTCAAAACGGGTGC GTGACCGACGGATGAC CCTACAAACATGTTCG TAAACCTGAGACCAAC Образец: ACAAC Разрешенное число ошибок: d = 1 Документы, содержащие образец: 1, 3, 4


Слайд 10

Имеющиеся результаты (1)


Слайд 11

Имеющиеся результаты (2)


Слайд 12

Часть II – Необходимые знания Расстояние Левенштейна Функция minpref Бор Сжатый бор l-слабый бор Интервальные запросы


Слайд 13

Расстояние Левенштейна d(u,v) = наименьшее количество операций редактирования, необходимое, чтобы перевести u в v. Вычисляется методом динамического программирования: d(u[1..i],v[1..j]) = d(u[1..i],v[1..j-1])+1, =min d(u[1..i-1],v[1..j])+1, d(u[1..i-1],v[1..j-1])+?u[i],v[j]


Слайд 14

Расстояние Левенштейна (2) Пример: d(”АВТОР”, ”АФФТАР”) = 3 АВТОР АФТОР АФФТОР АФФТАР За время O((|u|+|v|)*k) можно найти min(d(u,v),k) [Укконен 1985]


Слайд 15

Функция minprefu(v) minprefu(v) = min l: d(prefl(u),prefl+|u|-|v|(v)) = d(u,v) suffl+1(u) = suffl+|u|-|v|+1(v) Пример: minpref”АВТОР”(”АФФТАР”) = 4 AВТО?Р AФФТА?Р d(”АВТО”,”АФФТА”)=3


Слайд 16

Лемма о minpref Пусть d(u,v)=k Обозначим за u(i) строку u после i из k операций редактирования Если minprefu(i)(u) > h + 1, то для некоторого j > h prefj(v)=prefj(u(i-1)) Например: АВТОР АФТОР АФФ?ТОР АФФТАР i = 2 minprefu(2)(u)=3 h = 1 j = 2 pref2(v)=pref2(u(1))


Слайд 17

Бор Структура данных для хранения набора слов А В А Н С Т О Р А Т Р А Т Р Ф Ф


Слайд 18

Сжатый бор Структура данных для хранения набора слов А В А НС ТОР ТАР ФФТАР


Слайд 19

l-слабый бор Вершины глубины менее l имеют структуру сжатого бора После l-го уровня – никакого ветвления Пример 2-слабого бора: А В АНС ТОР АТАР ФФТАР


Слайд 20

Интервальные запросы Дан массив A длины n с целыми числами. Поступают запросы про числа в позициях с i по j. Время работы <f(n),g(n)> обознает Один запрос обрабатывается за время f(n) Предобработка занимает время g(n)


Слайд 21

Интервальные запросы (2) RMQ – Range Minimum Query Запрос (i, j) – найти индекc l, такой что A[l] = min{A[k], i?k?j} Алгоритм Фарака-Колтона и Бендера позволяет решать RMQ за наилучшее возможное время: <O(1),O(n)>


Слайд 22

Интервальные запросы (3) BVRQ – Bounded Value Range Query Запрос (i, j, k) – найти множество всех индексов l, таких что i?l?j и A[l]?k CRQ – Colored Range Query Запрос (i, j) – найти множество всех различных значений A[l] при i?l?j


Слайд 23

Часть III – Алгоритм Маасса-Новака Подход Маасса-Новака Случай d = 1 Общий случай Оценка времени поиска Оценка времени индексирования Использование интервальных запросов


Слайд 24

Подход Маасса-Новака Старый подход №1: Выберем строку s из T. За время O(|P|d) можно сравнить ее с P. Старый подход №2: Построим словарь всех слов, отличающихся от слов из T не более чем на d. Тогда поиск P будет занимать O(|P|).


Слайд 25

Подход Маасса-Новака Чем плохи старые подходы? Старый подход №1: Перебор всех строк из T - ВРЕМЯ Старый подход №2: Индекс всех слов со всеми возможными ошибками – ПАМЯТЬ


Слайд 26

Подход Маасса-Новака Иногда: обнаружим один подходящий вариант и проверим его за O(|P|). Иногда: будем искать P в предпосчитанном дереве строк, мало отличающихся от строк из T.


Слайд 27

Случай d = 1 Пусть S – сжатый бор, содержащий все подстроки Т, h0 – высота S. Если P встречается в T как подстрока (без ошибок), то P найдется в S. Если P встречается в T с одной ошибкой, возможны два важных случая: Ошибка после h0-го символа, т.е. minprefs(P) > h0 Ошибка до h0-го символа (включительно), т.е. minprefs(P) ? h0 где s – подстрока T, похожая на P.


Слайд 28

Случай d = 1 minprefs(P) > h0 Ищем P в боре S Доходим до листа Сверяем метку на этом листе с оставшимся суффиксом P (” старый подход №1”)


Слайд 29

Случай d = 1 minprefs(P) ? h0 Предподсчитаем все строки, отличающиеся от строк из T ровно одной ошибкой, и эта ошибка в позиции, не большей h0. В каждой позиции бывает 2|?| разных ошибок Для каждой строки из S порождается O(h0) новых строк Эти строки положим в сжатый бор S’ высоты h1 В боре S’ найдем все вхождения строки P Их может быть несколько Здесь пригодятся интервальные запросы


Слайд 30

Общий случай Пусть P совпадает некоторой строкой s из S с d ошибками Если prefh0(P)=prefh0(s), дойдем в S до листа, далее ”старый подход №1”, на этот раз O(|P|d) времени. Иначе: в боре S’ есть строка r, являющаяся строкой P с исправленной первой ошибкой.


Слайд 31

Общий случай (2) Снова два случая: minprefs(r)>h1 Дойдем в боре S’ до соответствующего листа, далее ”старый подход №1” minprefs(r)?h1 Предподсчитаем все строки, отличающиеся от строк из S’ одной ошибкой в первых h1 символах. При этом бор разрастется в O(h1) раз. В боре S’’ находим строчку P и так далее.


Слайд 32

Оценка времени поиска В боре не оказалось строки P O(m) Пройдя бор, мы дошли до листа O(m + dm)


Слайд 33

Оценка времени поиска (2) При обходе бора кончилась строка P O(m + occ) Итого: O(m + occ) d и |?| считаются константами Интервальные запросы


Слайд 34

Оценка времени индексирования Суммарный размер вспомогательных боров: O(h0h1…hd-1|S|) Время построения индекса: O(h0h1…hd|S|) hi=O(log n) В среднем С высокой вероятностью Доказано Маассом и Новаком в модели постоянного эргодического источника


Слайд 35

Использование интервальных запросов Необходимо за время O(occ) находить все первые позиции вхождений все документы, содержащие образец Обойдем все листья боров в лексикографическом порядке Для каждого вхождения в массив A запишем первую позицию вхождения/номер документа Для внутренних узлов бора, поддеревьям соответствуют интервалы в массиве A В массиве A необходимо за время O(occ) обрабатывать запросы CRQ


Слайд 36

Использование интервальных запросов (2) СRQ сводится к BVRQ Заведем массив B: B[i] = предыдущая позиция в массиве A числа A[i], либо -1, если оно ранее не встречалось CRQ-запрос (i,j) сводится к BVRQ-запросу (i,j,i-1) для массива B. A B


Слайд 37

Использование интервальных запросов (3) BVRQ решается за время <O(occ),O(n)> сведением к RMQ: Запрос (2,7,6): 2 4 4


Слайд 38

Часть IV - Заключение Алгоритм Маасса-Новака - первый алгоритм, обрабатывающий запрос за O(m+occ) Важно улучшить размер и время создания индекса (в данном алгоритме огромные константы) Неизвестен алгоритм, с приемлемой оценкой размера индекса в худшем случае Вопросы ?


×

HTML:





Ссылка: