Поиск в больших массивах информации
| Вид материала | Документы |
- Отчет По реализации алгоритма Боуэра-Мура по поиску фрагмента текста в больших массивах, 113.85kb.
- Рабочей программы дисциплины Поиск и обработка экономической информации средствами, 22.35kb.
- Урок по теме: "Поиск информации во Всемирной паутине", 96.8kb.
- Поиск в Интернет (индексный), 171.95kb.
- Тема: Разработка методики и программы выявления в массивах цифровых сигналов шумовых,, 193.45kb.
- Вучебниках информатики в общем виде информационный процесс, 1336.12kb.
- Роль поисковых технологий в крупных информационных системах и системах документооборота, 205.97kb.
- Перечень учебных курсов с краткими аннотациями, 170.84kb.
- Реферат по дисциплине «Поиск и обработка экономической информации» на тему: «Автоматизированных, 153.2kb.
- 1 Введение, 63.55kb.
Министерство образования Российской Федерации
Уральский государственный технический университет
кафедра молекулярной физики
ПОИСК В БОЛЬШИХ МАССИВАХ ИНФОРМАЦИИ
по курсу « Теория информационных систем»
Выполнили:
Студенты группы Фт-23024
Комарова М.А., Пушкина А.А.
Руководитель:
Кандидат физико-математических наук, доцент Александров О.Е.
Екатеринбург 2004
Введение.
Проблемы поиска информации возникли еще задолго до появления вычислительных машин. Ещё в докомпьютерную эру начали рассматриваться способы облегчения доступа к информации и ее максимально быстрого извлечения. С появлением вычислительных средств стало возможным автоматизировать поиск. Поэтому в конце 40-ых впервые проводятся исследования в области автоматических методов поиска.
В эпоху глобальной компьютерной сети с проблемой поиска информации пользователи сталкиваются постоянно. Это одно из наиболее часто встречающихся в программировании действий и обычно является наиболее «времяёмкой» частью многих программ. Замена плохого метода поиска хорошим может значительно увеличить скорость работы программы. Естественно, очень важно подобрать наиболее эффективный алгоритм поиска.
Постановка задачи.
Вначале об используемой нами терминологии. Введем понятие массива.
Массив - это упорядоченная совокупность элементов некоторого типа, адресуемых при помощи одного или нескольких индексов. Частным случаем является одномерный массив.
Пусть мы имеем некоторый текст. Будем рассматривать его как набор из N записей. Причем необходимо сделать принципиальное допущение: набор записей фиксирован.
Теперь можно рассматривать текст в виде массива.
Пример:
s: array [1..N] of char;
В приведенном примере описан массив s, состоящий из элементов текстового типа. Элементы могут быть адресованы при помощи индекса в диапазоне значений от 1 до N.
Тогда s[i] – i-ый элемент массива.
Хотелось бы отметить важную деталь: что вообще понимается под «поиском информации»? Задача поиска состоит в нахождении необходимой записи заданном тексте. Поэтому для любого алгоритма поиска неотъемлемой частью является понятие ключа, как некоторой искомой записи. Данный термин удачен, т.к., несомненно, отражает тот печальный факт, что ежедневно миллионы людей тратят время и силы на поиски собственных неизвестно куда запропастившихся ключей…
Существует несколько основных вариантов поиска, для которых создано много различных алгоритмов:
1. Поиск элемента в массиве:
1.1.Линейный поиск.
1.2.Поиск делением пополам (двоичный поиск).
1.3.Поиск в таблице.
2. Поиск массива в массиве.
2.1.Прямой поиск строки.
2.2.Алгоритм Рабина.
2.3.Алгоритм Кнута, Мориса и Пратта.
2.4.Алгоритм Боуера и Мура.
Все эти методы имеют свои особенности, свои характерные черты и модернизации. Чем сложнее структура алгоритма поиска, тем эффективней (быстрее) его работа. Алгоритмы 1.2. и 1.3. можно выделить особо, так как они имеют существенное отличие от остальных. Данные методы рассматривают поиск в упорядоченной структуре. Поэтому эти алгоритмы в работе разобраны не будут.
Результатом любого поиска может быть одно из двух:
- поиск завершился успешно, и запись являющаяся ключом найдена;
- поиск оказался неудачным и запись с ключом не найдена.
Поэтому мы считаем задачу выполненной, когда находим ключ (или убеждаемся в её отсутствии).
Варианты алгоритмов поиска
1.1.Линейный поиск
«Начать с начала и продолжать, пока не будет найден искомый ключ; а затем остановиться.» Это последовательная процедура представляет собой очевидный путь поиска, т.е. метод поиска «в лоб».
Если нет никакой дополнительной информации о необходимой записи, то можно использовать простой просмотр текста с каждым шагом сравнивая искомый ключ с элементом текста до нахождения совпадения. Такой метод называется линейным поиском.
Пример1:
Заданный текст: Мама мыла раму.
Искомый элемент (ключ): р
Алгоритм выполнения поиска:
A – сравниваемые элементы совпали
A – сравниваемые элементы не совпали
Мама мыла раму.
р // Не совпал, переходим к следующему символу;
Мама мыла раму.
р // Не совпал, переходим к следующему символу;
… // …
Мама мыла раму.
р // Удачное завершение поиска.
Данный алгоритм очень прост в исполнении:
Program Lin;
const
N = 10000;
var
i, N: integer;
x: char; //ключ
s: array[0..N-1] of char; //текст
begin
/*Ввод текста s*/
Write('N:'); Readln(N);
Write('s:'); Readln(s);
/*Задание ключа х*/
Write('х:'); Readln(х);
i:=0;
while (i
/*Вывод результата поиска*/
if s[i]=x then Writeln('Yes') //найден
else Writeln('No'); //не найден
Readln;
End.
Следует обратить внимание, что если элемент найден, то он найден вместе с минимально возможным индексом, т. е. это первый из таких элементов. Равенство i=N свидетельствует, что совпадения не существует.
Очевидно, что окончание цикла гарантировано, поскольку на каждом шаге значение i увеличивается, и, следовательно, оно достигнет за конечное число шагов предела N; фактически же, если совпадения не было, это произойдет после N шагов. Легко видеть, что, если текст состоит из N значений, то среднее число сравнений с ключом равно N/2. Это можно объяснить следующим образом: искомый элемент может оказаться и первым (один просмотр), и последним (N просмотров), а в среднем и получится N/2.
Казалось бы, тут "ни прибавить, ни убавить". Однако есть средство сделать такой алгоритм существенно более быстрым. Обратите внимание, что в заголовке цикла WHILE проверяются два условия: совпадение ключа и выход за границы массива. Можно сделать следующее: добавить к концу массива еще один элемент (барьер) и перед поиском занести в него искомое значение ключа. Тогда в цикле останется проверять только условие совпадения с ключом, поскольку ключ в массиве гарантированно есть – это или "настоящая" запись, которую мы и ищем, или "фиктивная", добавленная в конец. Программа изменится следующим образом:
s[N]:=x; i:=0;
while s[i]<>x do i:=i+1;
Ясно, что равенство i=N свидетельствует о том, что совпадения (если не считать совпадения с барьером) не было.
Представленный выше алгоритм наиболее подходит для исследования небольших массивов.
2.1. Прямой поиск строки.
Рассмотренный метод поиска не имеет достаточной практической ценности. Реально приходится искать некоторое слово, а не один конкретный символ. Т.е. это можно определить следующим образом. Пусть задан массив s из N элементов и массив p из M элементов, причем 0
s: array[0..N–1] of char; //текст
р: array[0..M–1] of char; //ключ
Разберем алгоритм поиска, который будем называть прямым поиском строки.
Пример:
Заданный текст: Сегодня вернулся Сережа
Ключ: Сережа
Алгоритм выполнения поиска:
A – сравниваемые элементы совпали
A – сравниваемые элементы не совпали
Сегодня вернулся Сережа //находим совпадение первого символа ключа с
Сережа символом текста
Сегодня вернулся Сережа //проверяем совпадение следующих символов
Сережа
Сегодня вернулся Сережа //ищем совпадение первого символа ключа с
Сережа символом текста
…
Сегодня вернулся Сережа //находим совпадение первого символа ключа с
Сережа символом текста
…
Сегодня вернулся Сережа //поиск успешно завершен
Сережа
Program Poisk;
const
N = 10000; M=100;
var
i, j, N, M: integer;
p: array[0..M-1] of char; // ключ
s: array[0..N-1] of char; // текст
begin
/* Ввод текста s*/
Write('N:'); Readln(N);
Write('s:'); Readln(s);
/* Задание ключа p */
Write('M:'); Readln(M);
Write('p:'); Readln(p);// вложенный цикл с предусловием
i:=-1;
repeat
i:=i+1; j:=0;
while (j
until (j=M) or (i=N-M);
/* Вывод результата поиска */
if i=M then Writeln('Yes') // найден
else Writeln('No'); // не найден
Readln;
End.
Вложенный цикл с предусловием начинает выполняться тогда, когда первый символ слова p совпадает с очередным, i-м, символом текста s. Этот цикл повторяется столько раз, сколько совпадает символов текста s, начиная с i-го символа, с символами слова p (максимальное количество повторений равно M). Цикл завершается при исчерпании символов слова p (перестает выполняться условие j
2.2.Метод Рабина
Этот алгоритм основан на простой идее. Представим себе, что в слове длины m мы ищем образец длины n. Вырежем окошечко размера n и будем двигать его по входному слову. Нас интересует, не совпадает ли слово в окошечке с заданным образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую функцию, определенную на словах длины n. Если значения этой функции на слове в окошечке и на образце различны, то совпадения нет. Только если значения одинаковы, нужно проверять совпадение по буквам. В чем выигрыш при таком подходе. Казалось бы, ничего - ведь чтобы вычислить значение функции на слове в окошечке, все равно нужно прочесть все буквы этого слова. Так уж лучше их сразу сравнить с образцом. Тем не менее выигрыш возможен, и вот за счет чего. При сдвиге окошечка слово не меняется полностью, а лишь добавляется буква в конце и убирается в начале. Хорошо бы, чтобы по этим данным можно было рассчитать, как меняется функция.
Решение: Заменим все буквы в слове (m) и образце (n) их номерами, представляющими собой целые числа. Тогда удобной функцией является сумма номеров букв. (При сдвиге окошечка нужно добавить новое число и вычесть пропавшее.)
| А | 123 |
| Л | 234 |
| Ж | 312 |
| У | 451 |
| Ц | 155 |
| И | 165 |
Ужа ужалила ужица
1. Начинаем сравнение
1.1 Вычислим сумму для образца длины n в нашем случае это “уж”:
Nom(“у”)= 451 и Nom(“ж”) = 312, тогда сумма “уж” равна 763, обозначим ее как nSum(“уж”)
1.2 Вычислим сумму первых двух символов в слове m, в нашем случае это “Уж”: Nom(“у”)= 451 и Nom(“ж”) = 312, тогда сумма “уж” равна 763, обозначим ее как mSum(“уж”)
1.3 Сравниваем значения nSum(“уж”) и mSum(“уж”):
Ужа ужалила ужица
Уж // получаем полное совпадение значений.
1.4 Вычислим сумму следующих двух символов в слове m, в нашем случае это “жа”: Nom(“ж”)= 312 и Nom(“а”) = 123, тогда сумма “жа” равна 435, обозначим ее как mSum(“жа”)
1.5 Сравниваем значения nSum(“уж”) и mSum(“жа”):
Ужа ужалила ужица
Уж // Значения не совпали.
…
Далее алгоритм повторяется.
ИТОГ: при рассмотрении данной строки получаем три совпадения, результат поиска окажется таким же как в линейном поиске.
Превосходство данного алгоритма перед простым поиском:
- при сравнении кодов слов требуется меньше времени и занимается меньшее количество памяти, т.к ЭВМ значительно легче сравнить цифровые коды чем буквенные.
- функция, пробегая по всему тексту, лишь при совпадении сравнивает образец с искомым элементом по буквам.
2.3. Алгоритм Кнута, Мориса и Пратта.
Приблизительно в 1970 г. Д. Кнут, Д. Морис и В. Пратт изобрели алгоритм, фактически требующий только N сравнений даже в самом плохом случае. Новый алгоритм основывается на том соображении, что после частичного совпадения начальной части слова с соответствующими символами текста фактически известна пройденная часть текста и можно “вычислить” некоторые сведения (на основе самого слова), с помощью которых потом можно быстро продвинуться по тексту.
Основным отличием КМП-алгоритма от алгоритма прямого поиска является осуществления сдвига слова не на один символ на каждом шаге алгоритма, а на некоторое переменное количество символов. Таким образом, перед тем как осуществлять очередной сдвиг, необходимо определить величину сдвига. Для повышения эффективности алгоритма необходимо, чтобы сдвиг на каждом шаге был бы как можно большим.
Если j определяет позицию в слове, содержащую первый несовпадающий символ, то величина сдвига определяется как j-D. Значение D определяется как размер самой длинной последовательности символов слова, непосредственно предшествующих позиции j, которая полностью совпадает с началом слова. D зависит только от слова и не зависит от текста. Для каждого j будет своя величина D, которую обозначим dj. Так как величины dj зависят только от слова, то перед началом фактического поиска можно вычислить вспомогательную таблицу d; эти вычисления сводятся к некоторой предтрансляции слова. Соответствующие усилия будут оправданными, если размер текста значительно превышает размер слова (M<
Алгоритм отыскания d:
1. ABCABD ABCABD ABCABD ABCABD ABCABD d=2
2. AAAAAB AAAAAB AAAAAB AAAAAB AAAAAB d=4
3. ABCDEA ABCDEA ABCDEA ABCDEA ABCDEA d=0
Процесс сдвига:
- ABCABE j=5; dj=2; наибольший сдвиг 3; АBCABE
ABCABD ABCABD
- AAAAAC j=5; dj=4; наибольший сдвиг 1; AAAAAC
AAAAAB AAAAAB
3. ABCDEF j=5; dj=0; наибольший сдвиг 5; ABCDEF
ABCDEA ABCDEA
Приведенный пример поиска слова ABCABD показывает принцип работы такого алгоритма. Символы, подвергшиеся сравнению, здесь подчеркнуты. Обратите внимание: при каждом несовпадении пары символов слово сдвигается на все пройденное расстояние, поскольку меньшие сдвиги не могут привести к полному совпадению.
ABCABCABAABCABD
ABCABD j=5; dj=2; наибольший сдвиг 3;
ABCABD j=5; dj=2; наибольший сдвиг 3;
ABCABD j=2; dj=0; наибольший сдвиг 2;
ABCABD j=1; dj=0; наибольший сдвиг 1;
ABCABD полное совпадение
Program KMP;
const
Mmax = 100; Nmax = 10000;
var
i, j, k, M, N: integer;
p: array[0..Mmax-1] of char; // слово
s: array[0..Mmax-1] of char; // текст
d: array[0..Mmax-1] of integer;
begin
/* Ввод текста s и слова p */
Write('N:'); Readln(N);
Write('s:'); Readln(s);
Write('M:'); Readln(M);
Write('p:'); Readln(p);
/* Заполнение массива d*/
j:=0; k:=-1; d[0]:=-1;
while j<(M-1) do
begin
while(k>=0) and (p[j]<>p[k]) do k:=d[k];
j:=j+1; k:=k+1;
if p[j]=p[k] then
d[j]:=d[k]
else
d[j]:=k;
end;
/*Поиск слова p в тексте */
i:=0; j:=0;
while (j
begin
while (j>=0) and (s[i]<>p[j]) do j:=d[j]; //Сдвиг слова
i:=i+1; j:=j+1;
end;
/* Вывод результата поиска */
if j=M then Writeln('Yes') // найден
else Writeln('No'); // не найден
Readln;
end.
Точный анализ КМП-поиска, как и сам его алгоритм, весьма сложен. Его изобретатели доказывают, что требуется порядка M+N сравнений символов, что значительно лучше, чем M*N сравнений из прямого поиска. Они так же отмечают то положительное свойство, что указатель сканирования i никогда не возвращается назад, в то время как при прямом поиске после несовпадения просмотр всегда начинается с первого символа слова и поэтому может включать символы, которые ранее уже просматривались. Это может привести к негативным последствиям, если текст читается из вторичной памяти, ведь в этом случае возврат обходится дорого. Даже при буферизованном вводе может встретиться столь большое слово, что возврат превысит емкость буфера.
2.4. Алгоритм Боуера и Мура
КМП-поиск дает подлинный выигрыш только тогда, когда неудаче предшествовало некоторое число совпадений. Лишь в этом случае слово сдвигается более чем на единицу. К несчастью, это скорее исключение, чем правило: совпадения встречаются значительно реже, чем несовпадения. Поэтому выигрыш от использования КМП-стратегии в большинстве случаев поиска в обычных текстах весьма незначителен. Метод же, предложенный Р. Боуером и Д. Муром в 1975 г., не только улучшает обработку самого плохого случая, но дает выигрыш в промежуточных ситуациях.
БМ-поиск основывается на необычном соображении – сравнение символов ведется с начала текста, но с конца слова (помещаемого в начало текста) и продолжается по направлению к его началу. Кроме того, рассматриваемый алгоритм делает то, что на первый взгляд кажется невозможным: в типичной ситуации он читает лишь небольшую часть всех букв слова, в котором ищется заданный образец.
Если проверяемый элемент в слове не совпадает с соответствующим элементом текста, то слово двигается вправо относительно этой позиции, которую будем называть опорной, до тех пор, пока какой-нибудь элемент снова не совпадет с элементом текста в этой позиции. Если этого не произойдет, то слово сдвигается таким образом, чтобы его первый элемент искомого слова отстоял от опорной позиции на один интервал.
Сразу же возникает вопрос, как находят следующий совпавший элемент, - ведь если для этого нужно сравнивать элементы по одному, то никакого выигрыша нет. Существует другой способ! Программа должна содержать таблицу расстояний от конца слова до каждой буквы (из одинаковых букв выбирается ближайшая к концу слова, т.е. самое правое совпадение); если буква в слово не входит, в соответствующей позиции таблицы указывается длина всего слова. Конечно, нужно потратить определенное время на построение такой таблицы, но сделать это необходимо только один раз; если текст достаточно длинный, дело того стоит!
| A | B | C | D | E | … |
| 2 | 1 | 3 | 0 | 6 | 6 |
Значения не совпали.
Вот пример, иллюстрирующий этот процесс:
ABCABCABEAABCABD // A - сравниваемый элемент не совпал
ABCABD // A – сравниваемый элемент совпал
ABCABD
ABCABD
ABCABD
Ниже приводится программа с упрощенной стратегией Боуера-Мура, построенная так же, как и предыдущая программа с КМП-алгоритмом. Обратите внимание на такую деталь: во внутреннем цикле используется цикл с repeat, где перед сравнением s и p увеличиваются значения k и j. Это позволяет исключить в индексных выражениях составляющую -1.
Program BM;
Const
Mmax = 100; Nmax = 10000;
Var
i, j, k, M, N: integer;
ch: char;
p: array[0..Mmax-1] of char; // cлово
s: array[0..Nmax-1] of char; // текст
d: array[' '..'z'] of integer;
begin
/* Ввод текста s и слова p */
Write('N:'); Readln(N);
Write('s:'); Readln(s);
Write('M:'); Readln(M);
Write('p:'); Readln(p);
/* Заполнение массива d */
for ch:=' ' to 'z' do d[ch]:=M;
for j:=0 to M-2 do d[p[j]]:=M-j-1;
/* Поиск слова p в тексте s */
i:=M;
repeat
j:=M; k:=i;
repeat
/* Цикл сравнения символов слова, начиная с правого */
k:=k-1; j:=j-1;
until (j<0) or (p[j]<>s[k]); // Выход, если сравнили все слово или несовпадение
i:=i+d[s[i-1]];// Сдвиг слова вправо
until (j<0) or (i>N); // Вывод результата поиска
if j<0 then Writeln('Yes') // найден не найден
else Writeln('No'); //
Readln;
end.
Почти всегда, кроме специально построенных примеров, данный алгоритм требует значительно меньше N сравнений. В самых же благоприятных обстоятельствах, когда последний символ слова всегда попадает на несовпадающий символ текста, число сравнений равно N/M.
Авторы алгоритма приводят и несколько соображений по поводу дальнейших усовершенствований алгоритма. Одно из них – объединить приведенную только что стратегию, обеспечивающую большие сдвиги в случае несовпадения, со стратегией Кнута, Морриса и Пратта, допускающей “ощутимые” сдвиги при обнаружении совпадения (частичного). Такой метод требует двух таблиц, получаемых при предтрансляции: d1 – только что упомянутая таблица, а d2 – таблица, соответствующая КМП-алгоритму. Из двух сдвигов выбирается больший, причем и тот и другой “говорят”, что никакой меньший сдвиг не может привести к совпадению. Дальнейшее обсуждение этого предмета приводить не будем, поскольку дополнительное усложнение формирования таблиц и самого поиска, кажется, не оправдывает видимого выигрыша в производительности. Фактические дополнительные расходы будут высокими и неизвестно, приведут ли все эти ухищрения к выигрышу или проигрышу.