|
Автореферат на выпускную работу магистра
"Исследование способов фильтрации информации в текстовых документах"
Введение
Развитие индустрии систем электронного документооборота, сопровождающееся ростом полнотекстовых документов, требует новых средств обработки информации, так как возникают все новые и новые проблемы фильтрования текста.
Основной задачей, возникающей при работе с полнотекстовыми базами данных, является задача поиска шаблона по его содержанию. Однако, ставшие традиционными средства контекстного поиска по вхождению слов в документ и его обработки, представленные, в частности, поисковыми машинами в интернет, программами-модераторами и электронными словарями, зачастую не обеспечивают адекватного выбора информации.
Существуют проблемы, заключающиеся в сложности точной формулировки запроса программы – подбора ключевых слов и словосочетаний, которые предстоит искать в текстах, и выбор должного алгоритма, отвечающего заданному поиску. Это может быть связано с рядом причин, как то: недостаточным знанием пользователем терминологии предметной области, наличием в языке многозначных и синонимичных слов, различного контекста, наличием орфографических ошибок в написании искомых слов, которые могут встречаться в текстах, а так же, быстродействием поиска и его контекстной обработке.
Таким образом в данной работе сделаны попытки найти «золотую середину» в фильтрации текстовых документов, так как любое словосочетание, похожее или идентичное шаблону, не всегда является на самом деле искомым.
Анализ алгоритмов текстового поиска
В современном мире множество проблем работы с текстом связаны с поиском строк. Поиск строк используется в электронных словарях, программах-модераторах и в обычном текстовом редакторе. Алгоритмы, которые будут рассматриваться далее, лучшие из перечисленных ниже и работают примерно одинаково. Пара секунд не играет значения при небольших размерах текста, но при его росте – могут складываться в достаточно большие промежутки времени.
Рассмотрим задачи анализа строк, возникающие при разработке предлагаемой системы обработки текстовой информации. На данный момент не ставится цель – дать очень точные решения всех возможных задач, а скорее рассмотреть и проанализировать существующие алгоритмы.
Термин “анализ строк” используется в довольно общем смысле и обозначает целый класс задач – таких как поиск заданных шаблонов и приближенных (охватывающих диапазон подобных слов) шаблонов. Под подобными словами будем понимать слова, имеющие одинаковую заданную структуру (например, однокоренные слова). Трудность заключается в выборе оптимального алгоритма поиска. Под оптимальным будем понимать алгоритм с достаточно высокой скоростью выполнения предварительных вычислений и дальнейшего поиска.
1 Формулировка задачи
Последовательность - цепочка символов.
Рассматриваемые последовательности – одномерные и составлены из символов. Используется алфавит символов, в том числе и пробел.
Образец. Поиск всех имеющихся повторений внутри заданной строки для использования любой внутренней избыточности при разработке нужной схемы кодирования, что позволяет увеличить эффективность представления информации. В этом случае может оказаться, что образцом удобно считать подстроку. С другой стороны, если требуется проанализировать входную последовательность для выделения синтаксических структур.
Данные - количество образцов длины n в последовательности длины m (m>=n).
О подстроках.
Из последовательности можно выделить ровно (m – n + 1) подстрок длины n. Общее число подстрок вычисляется суммированием, что приводит нас к формуле 2.1
Формула 2.1 – Вычисление общего числа подстрок
Где m –длина последовательности, n – количество символов в шаблоне (1..n). При n=const, общее число подстрок вычисляется - (m-n+1).
В шаблонах обнаруживаем, что верхняя граница их количества является степенной. Это выводится следующим образом. Каждый из символов исходной последовательности находится в одном из двух состояний относительно данного шаблона - входит в него или нет. Отсюда получаем 2n шаблонов, включая пустую строку ?.
Формулировка задачи.
Строка x длины |x| = n записывается как x1x2...xn, где xi представляет i-й символ x.
Подстрока xixi+1 … xj строки x, где i?j?n, будет обозначаться x(i,j). В случае, когда i>j подстрока обозначается так xR(i,j).
Обычно x будет обозначать искомый образец (шаблон), а y – текстовую строку, в которой идет поиск; |x| = n, |y| = m и, конечно, m<=n.
Для данной текстовой строки - y, следует найти максимально пересекающиеся с шаблоном (шаблон найден полностью, а не только его часть) и имеющие повторы в тексте строки x.
2 Описание алгоритмов
В ходе проделанной работы были рассмотрены алгоритмы [1][2]:
* Наивный подход; * Кнута-Морриса-Пратта; * Бойера-Мура; * Бойера-Мура-Хорспула; * Сандея; * Хьюма и Сандея; * Харрисона; * Карпа и Рабина.
Из анализа данных алгоритмов Грэхэмом Стефаном были сделаны выводы об относительной эффективности[1]:
* алгоритм Бойера-Мура-Хорспула является наилучшим; * эффективность Хорспула примерно равна исходному алгоритму Бойера-Мура, но лучше, чем наивный подход; * алгоритм Кнута-Морриса-Пратта не дает на практике значительного преимущества в скорости к наивному подходу, и алгоритм Бойера-Мура.
Метод Карпа-Рабина сильно уступает остальным; * Вариант Сандея (быстрый поиск) совместно с упрощенным алгоритмом Бойера-Мура очень эффективен; * Хьюм и Сандей более эффективны по сравнению с исходным алгоритмом Бойера-Мура,но они не учитывают громоздких и медленных предварительные вычислений.
Далее рассмотрим только эффективные алгоритмы поиска.
Алгоритм Бойера-Мура
В алгоритме Бойера-Мура образец движется вдоль строки текста слева на-право, однако фактические сравнения символов выполняются справа налево. Первыми, таким образом, сравниваются символы xm и ym. Если они не совпадают и ym не встречается нигде в x, мы можем спокойно сдвинуть образец на m симво-лов вправо, так как можем быть уверены, что ни одна из начинающихся с одной из первых m позиций подстрок не совпадает с образцом. Следующими сравнива-ются xm и y2m.
Пусть отвергающими оказались символы xm и yi. Как уже говорилось, если yi не содержится нигде в образце, шаблон можно сдвинуть на m позиций вправо. С другой стороны, если yi присутствует в образце, и xm-s – его самое правое вхождение, то образец можно сдвинуть лишь на s позиций вправо, совмещая xm-s с yi. Проверку можно продолжить сравнением xm с yi+s, то есть текстовый индекс мы увеличиваем на s.
Если xm и yi совпадают, нужно сравнивать предшествующие им символы в образце и тексте, пока вся подстрока текста не будет сопоставлена с образцом или пока не встретится несовпадение. Если отвергающим оказался, скажем, символ xj, то мы знаем, что суффикс x(j+1,m)равен подстроке текста y(i-m+j+1, i),и xj<>yi-m+j. Теперь, если самым правым вхождением yi-m+j в образец снова является, скажем, xm-s, образец можно сдвинуть на j-m+s мест вправо, так что xm-s окажется на одной позиции с yi-m+j. Процедуру можно продолжить сравнением xm с соответствую-щим символом, в данном случае с yi+j-m+s. Приращение индекса текста с позиции несовпадения до следующей пробной позиции равно, таким образом, (i+j-m+s)-(i-m+j) = s.
Если xm-s находится правее xj, то значение j-m+s отрицательно, так что со-вмещение xm-s с yi-s+j ничего не даст, поскольку повлечет за собой шаг назад. В этих обстоятельствах образец лучше сдвинуть на одно место вправо и сравнивать xm с yi+1. Для этого нужно увеличить индекс текста на (i+1)-(i-m+j) = m+1-j.
Приращения s, используемые во вхождении, вычисляются заранее до нача-ла самого поиска и хранятся в таблице skip. В процессе поиска таблица индекси-руется неподходящими символами текста, поэтому требуется таблица размером с используемый алфавит символов.
Вход для символа алфавита w равен m-j, где xj – самое правое вхождение w в x, и равен m, если w не содержится в x, то есть:
skip[w] = min {s : s = m или (0?s < m и x[m-s] = w)}
Таблица skip для алфавита ? инициализируется следующим образом:
for w = 1 to |?|
skip[w] = m
for j = 1 to m
skip[xj] = m – j
Где xj – элемент строки-шаблона.
Вот пример, иллюстрирующий работу skip-таблицы для образца ABCDB (найден символ А, так как он 1-й, а символов шаблона 5 – идет сдвиг на 4 симво-ла, то есть предполагается, что повторений А нет в ближайших пяти символах; затем следует символ В – он повторяется в шаблоне, следовательно может повториться - ставим сдвиг 0; потом символ С, являющийся третьим, по анало-гичному пути А – получает сдвиг на 2 символа; D таким же образом, как А и С получает сдвиг на 1; отсутствующие в шаблоне символы получают сдвиг на 5 – количество символов в шаблоне).
w A B C D E F G H ...
skip[w] 4 0 2 1 5 5 5 5 ...
Несовпадение возникает при yi = A (символ шаблона А не совпадает с сим-волом текста L, следовательно по предыдущим вычислениям в таблице skip – идет сдвиг по тексту на 4 символа).
образец A B C D B
текст . . . L M N A B C D B . . .
i
Следующими сравниваются символы xm и yi+skip[A] (то есть yi+4). При нахож-дении первого символа шаблона – проверяем последний символ.
X A B C D B
Y . . . L M N A B C D B . . .
i i+4
Особый интерес представляет ситуация, когда часть образца содержится в текущей части текста, т.е. x(j+1, m) = y(i-m+j+1, i) и xj<>yi-m+j. Если суффикс x(j+1, m) входит также в x как подстрока x(j+1-t, m-t), причем xj-t<> xj, и это самое правое из подобных вхождений, то образец можно сдвинуть на t мест вправо. При этом мы совмещаем x(j+1-t, m-t) с y(i-m+j+1, i) и процесс поиска можно возобно-вить, сравнивая xm с yi+t. Таблица shift, содержащая информацию о сдвиге t, вычисляется заранее на основании образца и индексируется той позицией образ-ца, в которой встретилось несовпадение. Значение shift[j] равняется сдвигу t образца плюс дополнительный сдвиг, требуемый для того, чтобы возобновить сравнения от правого края образца. Значение i – это минимум, такой что, если xj<>yi-m+j, то x(j+1-t, m-t) совпадет с y(i-m+j+1, i) [2]. Итак, входы таблицы shift определяются следующим выражением:
shift[j] = min{t + m - j : t<>1 и
(t>=j или xj-t<>xj) и
((t>=k или xk-t = xk) для j < k<=m)}
Таким образом, значение shift[j] равно требуемому приращению для индекса текста с текущей позиции yi-m+j до позиции следующего сравнения yi+t, то есть (i + t) - (i - m + j) = t + m - j. Вот пример, иллюстрирующий значения shift для образца ABCDABC.
xj A B C D A B C
j 1 2 3 4 5 6 7
m - j 6 5 4 3 2 1 0
t 4 4 4 4 7 7 1
shift[j] 10 9 8 7 9 8 1
Из определения shift[j] можно углядеть, что shift[j]<>m+1-j. Так, в указан-ном выше случае, где индекс текста следует увеличить на m+1-j, вместо соответ-ствующего значения shift, так как последнее вызывает сдвиг образца назад, достаточно использовать соответствующее значение таблицы shift. Таким обра-зом, в случае несовпадения следует использовать максимальное из двух значений, взятых из описанных выше таблиц. Алгоритм для этого метода представлен на рисунке 2.1. Конечное значение i возвращает позицию вхождения образца в тексте, или 0, если образец в тексте не встретился.
i = m
j = m
while (j > 0) and (i<>n)
if yi = xj
i = i – 1;
j = j - 1
else
i = i + max{skip[yi], shift[j]}; j = m
if j < 1
i = i + 1
else
i = 0
Рисунок 2.1 - Сопоставление строк по Бойеру-Муру
Для локализации всех вхождений образца в текст алгоритму Бойера-Мура требуется O(n+rm) сравнений символов, где r – число вхождений. Он показал также, что в случае отсутствия в тексте образца требуется всего 6n сравнений символов. Для больших алфавитов средняя эффективность алгоритма Бойера-Мура является сублинейной, и в среднем требует n/m сравнений символов.
Алгоритм Бойера-Мура-Хорспула
Существует множество других вариантов подхода Бойера-Мура к сопостав-лению строк. Один из наиболее известных, алгоритм Бойера-Мура-Хорспула, с упрощенными предварительными вычислениями, описан далее.
Хорспул разработал упрощенную версию алгоритма Бойера-Мура, в кото-рой отказался от вычисления сопоставления и использует только вычисление вхождения. Это сокращает объем предварительных вычислений, а также снижает требования к памяти с O(m+|summa|) до O(|summa|), где summa– алфавит. Поскольку алфавит, как правило, фиксирован, то и размер запрашиваемой памяти тоже, как правило, постоянен. В худшем случае эффективность его подхода равна O(mn), но на практике такие ситуации редки и средняя эффективность сравнима с эффективно-стью алгоритма Бойера-Мура.
Таблица skip в версии Хорспула слегка отличается от используемой в вер-сии Бойера-Мура: в ней skip[xm] присваивается значение m, так что остается инициализировать только элементы с x1 до xm-1. В таблице Бойера-Мура значение skip для xm равно 0, а ненулевой сдвиг определяется взятием максимума из значений двух вычислений – сопоставления и вхождения.
Хорспул отметил также, что, в случае несовпадения, скажем, в xj, в качестве следующей пробной позиции можно взять такую-любой из m-j сопоставляемых символов текста совмещается с самым правым вхождением этого символа в образце. Всегда используя для индексации таблицы skip символ текста, соответ-ствующий последнему символу образца (xm), можно избежать описанной выше ситуации с обратным сдвигом образца. Иначе данная ситуация потребовала бы явной проверки. В алгоритме Бойера-Мура для борьбы с этой ситуацией предна-значена вычисление сопоставления. Алгоритм Бойера-Мура-Хорспула представ-лен на рисунке 2.2. И снова, окончательное значение i содержит первую позицию вхождения образца, или равно 0, если образец в тексте не обнаружен.
for w = 1 to |C|
skip[w] = m
for j = 1 to m - 1
skip[xj] = m - j
i = m;j = m
while (j>m) and (i<=n)
k = i
while (j>m) and (yk = xj)
k = k - 1; j = j - 1
if j>0
i = i + skip[yi]; j = 1
if j<1
i = k + 1
else
i = 0
Рисунок 2.2 - Сопоставление строк по Бойеру-Муру-Хорспулу
Алгоритм “Быстрый поиск”
Сандей обнаружил, что в алгоритме Бойера-Мура при обнаружении несовпадения, когда xm совмещен с i-м символом текста, для обращения к таблице эвристики сопоставления вместо yi можно использовать следующий символ, то есть yi+1. Основанием для этого является то, что при минимальном сдвиге образца, то есть на один символ вправо, yi+1 является частью следующей проверяемой подстроки текста. Сандей утверждает, что на практике в среднем это дает сдвиг, больший или равный сдвигу на значение skip Бойера-Мура плюс один, что показано на рисунке 2.3. Однако, даваемое этим фактом преимущество в скорости уменьшается с увеличением длины образца.
for w = 1 to |C|
skip[w] = m + 1
for j = 1 to m
skip[xj] = m + 1 - j
i = 1;j = 1
while (j<=m) and (i<=n - m + 1)
k = i
while (j<=m) and (yk = xj)
k = k + 1; j = j + 1
if j<=m
i = i + skip[yi+m]; j = 1
if j<=m
i = 0
Рисунок 2.3 - Быстрый поиск по Сандею
И опять and во внутреннем цикле while является `условным’.
Выводы по алгоритмам четкого поиска
Для объективной оценки метода поиска выбирались такие шаблоны, которые давали одинаковое количество вхождений (такими являлись шаблоны, которые ни разу не встречались в тексте, то есть давали 0 вхождений). При росте обрабатываемых массивов текста и шаблона – алгоритмы становятся все более одинаковы по быстроте и качеству поиска, что представлено на рисунках 2.4 и 2.5:
Рисунок 2.4 – Зависимость времени поиска от длины шаблона
Рисунок 2.5 – Зависимость времени поиска от длины текста
При различной длине строк файла отношение эффективности работы алгоритмов Бойера-Мура-Хорспула и Сандея остается неизменным.
Заключение
В ходе данной работы были рассмотрены алгоритмы текстового поиска.
При рассмотрении алгоритмов текстового поиска, экспериментально было определено, что алгоритм Сандея «Быстрый поиск» является наиболее оптимальным. По графику зависимости времени поиска от длины шаблона и длины текста, алгоритм Сандея «Быстрый поиск» превосходит в быстродействии алгоритм Бойера-Мура-Хорспула приблизительно на 6%.
|
