Индексирование текста для поиска с учетом орфографических ошибок - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
О компьютерной коррекции психологически обусловленных ошибок правописания... 2 292.49kb.
1. Исправление ошибок (орфографических, пунктуационных, грамматических) 1 235.37kb.
Название секции 2 424.63kb.
Эффективность поиска в Интернете сведений по тематике 1 90.27kb.
Материалы для подготовки контрольной работы по дисциплине «История... 1 157.42kb.
Материалы для подготовки контрольной работы по дисциплине «История... 1 175.68kb.
Всероссийский марафон «Моря, озера, реки, океаны» Задания 1 47.9kb.
Всероссийский марафон «Моря, озера, реки, океаны» Ответы 1 52.92kb.
Формирование орфографических умений и навыков на уроках русского... 1 63.25kb.
Н. Н. Ташатов Использование избыточности для защиты от ошибок 1 103.59kb.
Лекции №17, №18 08. 11. 2011. Реализация на Лиспе и Плэнере алгоритма... 1 59.29kb.
Перечень вступительных испытаний по общеобразовательным предметам... 1 93.78kb.
Направления изучения представлений о справедливости 1 202.17kb.

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

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

Искандер Акишев


Михаил Дворкин
СПбГУ ИТМО
Ноябрь 2006 г.


1. Введение 1

1.1 Область применения 1

1.2 Постановка задачи 2

1.3 Пример 2

1.4 Имеющиеся результаты 3

2. Необходимые знания 3

2.1 Расстояние Левенштейна 3

2.2 Функция minpref 4

2.3 Бор 4

2.4 Сжатый бор 5

2.5 l-слабый бор 5

3. Алгоритм Маасса-Новака 5

3.1 Старые подходы 5

3.2 Случай d = 1 5

3.3 Общий случай 6

3.4 Оценка времени поиска 6

3.5 Оценка времени индексирования 7

4. Заключение 7





1.Введение

1.1 Область применения


  • Поиск документов в Интернете

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

  • Автоматическое исправление орфографических ошибок

Можно попытаться найти некоторую последовательность букв в словаре, содержащем все слова некоторого языка. Найденное таким образом слово – возможно, ровно то, что имел в виду пользователь, сделавший в слове опечатку или орфографическую ошибку. Таким образом можно автоматически предлагать замену, если пользователь ввел слово, отсутствующее в словаре.

  • Вычислительная биология:

    • Поиск образца в неточных экспериментальных данных

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

    • Поиск похожих участков ДНК

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

1.2 Постановка задачи


Пусть T – коллекция документов (возможно, один документ), суммарный размер всех документов равен n.

Пусть P – образец, который (в точности или с некоторыми отклонениями) требуется найти в документах из коллекции. Обозначим длину образца m.

В образце могут содержаться ошибки, а именно он может отличаться от искомого участка текста следующими изменениями:


  • Пропущенный символ

  • Лишний символ

  • Измененный символ

Максимальное допустимое число ошибок равно d.

ВАЖНО: d – заранее зафиксированная константа, она не участвует в оценке асимптотики времени работы алгоритма и размеров структур данных.

Кроме того, все описанные результаты переносятся на случай метрики Хэмминга, а именно, на случай, когда единственной допустимой ошибкой является измененный символ. В частности, именно этот случай – наиболее осмысленный в случае поиска по базам данных ДНК.

Постановка задачи: требуется найти одно из следующих множеств:



  • Все вхождения образца в коллекцию документов

  • Все начальные позиции вхождений образца

  • Все документы, содержащие образец

1.3 Пример


Рассмотрим пример – коллекцию документов T, состоящую из четырех генетических кодов:

  1. GACTCAAAACGGGTGC

  2. GTGACCGACGGATGAC

  3. CCTACAAACATGTTCG

  4. TAAACCTGAGACCAAC

В этих документах будем искать образец P = 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)




  • Начальные позиции вхождений:

1-й документ: 6, 7

3-й документ: 4, 6

4-й документ: 2, 11, 12, 13




  • Документы, содержащие образец: 1, 3, 4


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


Число ошибок

Время запроса

Размер структуры данных

Время индексирования

Источник

d = 0

O(m + occ)

O(n)

O(n)

Weiner 1973

d = 1

O(m + log n log log n + occ)

O(n log2 n)

O(n log2 n)

Amir et al. 2000

d = 1

O(m log log n + occ)

O(n log n)

O(n log n)

Buchsbaum et al. 2000

d = 1

O(m + occ)

O(n log n)

O(n log2 n)
(в среднем)

Maaß Novak 2004

d = O(1)

O(m + logd n log log n + occ)

O(n logd n)

O(n logd n)

Cole et al. 2004

d = O(1)

O(d nε log n)

O(n)

O(n)

Myers 1994

d = O(1)

O(nε)

O(n)

O(n)

Navarro et al. 2000

d = O(1)

O(m log2 n + m2 + occ)
(в среднем)


O(n log n) (в среднем)

O(n log2 n)
(в среднем)


Chávez et al. 2002

d = O(1)

O(m min{n, md+1} + occ)

O(min{n, md+1} + n)

O(min{n, md+1} + n)

Cobbs 1995 (Ukkonen 1993)

d = O(1),

Hamming

O(logd+1 n)
(в среднем)


O(n)

O(n)

Maaß 2004

d = O(1)

O(m + occ)

O(n logd n) (в среднем)

O(n logd+1 n)
(в среднем)


Maaß Novak 2005

d = O(1)

O(m + occ)
(в среднем)


O(n logd n)

O(n logd+1 n)

Maaß Novak 2005

2.Необходимые знания

2.1 Расстояние Левенштейна


Пусть u и v – две строки над некоторым алфавитом.

Определение Операцией редактирования называется одно из следующих действий со строкой:

  • Добавление символа в произвольную позицию

  • Удаление символа

  • Замена одного символа другим

Определение Расстоянием Левенштейна d(u, v) между строками u и v называется наименьшее количество операций редактирования, необходимое, чтобы перевести u в v.

Из соображений обратимости операций редактирования, имеем d(u, v) = d(v, u).

Расстояние Левенштейна также называют редакционным расстоянием (по-английски – Lowenstein distance/edit distance).
Расстояние Левенштейна между строками u и v вычисляется методом динамического программирования за время O(|u| * |v|) с использованием следующей формулы:



d(u[1..i],v[1..j]) = min

d(u[1..i],v[1..j-1])+1
d(u[1..i-1],v[1..j])+1
d(u[1..i-1],v[1..j-1])+δu[i],v[j]

Например, d(”АВТОР”, ”АФФТАР”) = 3, поскольку для приведения одной строки к другой необходимы три операции редактирования:

АВТОР – заменяем 2-ю букву на «Ф»

АФТОР – добавляем после 2-й буквы букву «Ф»

АФФТОР – заменяем 5-ю букву на «Ф»

АФФТАР
Важным достижением является алгоритм, предложенный Эско Укконеном в 1985 г., позволяющий за время O(|u|*k) определить следующие данные:


  • Если d(u, v) > k, вывести соответствующее уведомление

  • Если d(u, v) ≤ k, вывести d(u, v)

Заметим, что время работы алгоритма не зависит от |v| по следующей причине: если |v| > |u| + k, то есть длины строк отличаются больше, чем на k, то никакие k операций редактирования не сравняют эти две строки, следовательно, можно сразу сообщать, что d(u, v) > k.

2.2 Функция minpref


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

minpref u (v) = наименьшее 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

2.3 Бор


Бор – классическая структура данных для хранения набора строк. Размер бора линейно зависит от суммы длин всех строк, а поиск в бору занимает время, пропорциональное длине образца. Вот пример бора для небольшого набора слов:


2.4 Сжатый бор


Сжатый бор – структура данных для хранения набора строк, отличающаяся от бора следующим улучшением: если у некоторой вершины исходящая степень равна 1, то эту вершину, ребро, входящее в нее, и ребро, исходящее из нее, можно объединить в одно ребро с более чем одним символом. Сжатый бор для вышеприведенного набора слов выглядит так:


НС

2.5 l-слабый бор


l-слабый бор – это улучшение сжатого бора, применимое в данной области. Напомним, что глубиной вершины называется длина пути от корня до этой вершины, так глубина корня равна 0.

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

2-слабый бор для набора слов из предыдущих примеров выглядит так:




3.Алгоритм Маасса-Новака

3.1 Старые подходы


Приведем два подхода, каждый из которых можно назвать «лобовым». Оба подхода в некоторым смысле используются в алгоритме Маасса-Новака.

Подход №1. Выберем любую строку s из T. За время O(md) ее можно сверить с образцом P.

Конечно же, старый подход плох тем, что приходится перебирать все строки из коллекции T. Это совершенно недопустимо в плане времени поиска образца.



Подход №2. Построим словарь всех слов, отличающихся от слов из коллекции T, не более чем d ошибками. Тогда поиск образца будет занимать O(m) времени.

Легко оценить, что словарь всех слов со всеми возможными ошибками занимает непозволительно много места.


3.2 Случай d = 1


Пусть S – сжатый бор, содержащий все подстроки Т. Обозначим h0 высоту S.

Поскольку, d = 1, есть лишь два варианта нахождения образца в тексте:



  • Если P встречается в T как подстрока (без ошибок), то P найдется в S.

  • Если P встречается в T с одной ошибкой, возможны два важных случая:

    • Ошибка после h0-го символа, т.е. minprefs(P) > h0

    • Ошибка до h0-го символа (включительно), т.е. minprefs(P) ≤ h0,

где s – подстрока T, похожая на P.
Итак, пусть minprefs(P) > h0, то есть ошибка не в первых h0 символах. Тогда последовательность действий не сложна: она представляет собой «старый подход №1».

  • Ищем P в боре S

  • Доходим до листа

  • Сверяем метку на этом листе с оставшимся суффиксом P

Теперь рассмотрим случай minprefs(P) ≤ h0.

Чтобы отлавливать такие вхождения образца, заранее предпосчитаем отличающиеся от строк из T ровно одной ошибкой, и эта ошибка в позиции, не большей h0.

Оценим количество таких строк. В каждой позиции можно добавить символ |∑| различными способами, изменить символ |∑| - 1 способами и, наконец, удалить символ одним способом. Итого, 2|∑| возможных ошибок в каждой позиции. Таким образом, для каждой строки из S порождается O(h0) новых строк.

Все такие строки сложим в сжатый бор S’ высоты h1.

Теперь при обработке строки P необходимо найти все вхождения строки P в бор S’. Таких вхождений может быть несколько – в этом случае для выдачи ответа необходимы интервальные запросы.


3.3 Общий случай


Предположим, что P совпадает некоторой строкой s из S с d ошибками.

  • Случай I: prefh0(P)=prefh0(s).

В таком случае в боре S следует дойти до листа, далее – «старый подход №1». Обработка такого случая занимает O(md) времени.

  • Случай II: prefh0(P)≠prefh0(s).

Тогда в боре S’ присутствует строка r, являющаяся строкой P с исправленной первой ошибкой. Рассмотрим, где находится первая ошибка в строке r относительно s.

    • minprefs(r)>h1

В таком случае по строке r дойдем в боре S’ до соответствующего листа, и далее применим «старый подход №1».

    • minprefs(r)≤h1

Чтобы обрабатывать такие ситуации, предподсчитаем все строки, отличающиеся от строк из S’ одной ошибкой в первых h1 символах. Аналогично приведенным выше рассуждениям, при этом бор разрастется в O(h1) раз, и получится бор S’’.

В боре S’’ находим строчку P и так далее.


3.4 Оценка времени поиска


В процессе обработки строки P могли возникнуть следующие случаи:

  • В боре не оказалось строки P

Такая ситуация обрабатывается за O(m) времени.



  • Пройдя бор, мы дошли до листа


Обработка этой ситуации требует в общем случае O(d+md)=O(m) времени.

  • При обходе бора кончилась строка P

При аккуратной реализации интервальных запросов этот этап обрабатывается за время O(m + occ), где occ – стандартное обозначение для размера ответа (от англ. occurences).


3.5 Оценка времени индексирования


Во-первых, оценим суммарный размер всех боров.

Он асимптотически растет как O(h0h1...hd-1n).

Напомним, что d и |∑| считаются константами и в асимптотическую оценку не входят.

Однако построение последнего, самого большого бора, занимает большее время, поэтому, время создание индекса оценивается следующей величиной: O(h0h1...hdn).

Маассом и Новаком были оценены величины hi в случае, если строки коллекции P порождаются постоянным эргодическим источником. В таких предположениях они показали, что hi=O(log n), во-первых, в среднем, а во-вторых, с высокой вероятностью.

4.Заключение


Алгоритм Маасса-Новака – есть первый алгоритм с приемлемым временем создания и размером индекса, который позволяет обрабатывать запрос за наилучшее возможное время – O(m + occ).

К сожалению, в имеющемся алгоритме за всеми асимптотическими оценками скрываются огромные константы, экспоненциально зависящие от d и |∑|. Для практического применения необходимо коренным образом улучшить эти оценки.



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




Божьи жернова мелют медленно, но муку дают превосходную. Секст Эмпирик
ещё >>