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

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

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

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

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

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

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

Пример
Документы:
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)

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

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

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

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

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

Расстояние Левенштейна
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]

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

Функция 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

Лемма о 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))

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

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

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

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

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

Интервальные запросы (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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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