Список литературы к выпускной работе.
Вислый А.И. Вступаем в электронную эру // Мир библиографии. –2000 г. – №6 – с.14–19;
Глухов В.А., Лаврик О. Л. Электронная доставка документов. – М.: ИНИОН РАН, 1999 г. – 132с.;
Сюнтюренко О.В Электронные информационные ресурсы: проблемы создания и использования // Научный сервис в сети Интернет: Тезисы докладов Всероссийской научной конференции 20–25 сент. 1999 г., Новороссийск. – М.: Изд-во МГУ , 1999 г.– с.3–9;
Земсков А.И. К проекту программы «Российские электронные библиотеки» // НТБ – 2000 г. – №3 – с.4–9;
Фонотов А. Роль электронных библиотек в передаче технологий // Инф. ресурсы России. – 1999 г. – №4 – с. 22–25;
Хякли Э. Национальная электронная библиотека // Библиотековедение. – 1998 г. – №5 – с. 44–48.
Приложения
Приложение 1
Алгоритмы поиска данных
Пусть у нас есть текст, состоящий из n символов, который в дальнейшем договоримся называть T, а T[i] его i-ый символ. Строку или просто слово, состоящее из m символов, назовем S, где S[i] -i-ый символ строки. Нам нужно проверить, входит ли данная строка в данный текст, и если входит, то начиная с какого символа текста. Мы рассмотрим несколько известных алгоритмов, решающих поставленную задачу.
Простейший алгоритм
Суть метода, о котором пойдет речь ниже, заключается в следующем: мы проверяем, совпадают ли m символов текста (начиная с выбранного) с символами нашей строки, пытаясь примерить шаблон куда только возможно. Естественно, реализовать описанный алгоритм проще всего (код на языке Pascal):
Program SimpleSearch;
Var T : array[1..40000] of char; {выполняет роль текста}
S : array[1..10000] of char; {выполняет роль строки; как и текст, может быть достаточно велика}
i,j: longint;
m,n: longint;
Begin
{Ввод текста и образца}
…
for i:=1 to n-m+1 do
begin
j:=0;
while (j
j: = j+1;
if j=m then {если все символы совпадали}
writeln('Образец входит в текст начиная с ',i,'-ого символа'); {сообщение о нахождении строки в тексте}
end;
End.
Это несложно в исполнении, но и не очень эффективно на практике. В программе присутствуют два цикла (один вложенный), время работы внешнего большей степенью зависит от n, а внутренний в худшем случае делает m операций. Таким образом, время работы всего алгоритма есть O((n-m+1)m). Для маленьких строк поиск проработает быстро, но если в каком-то многомегабайтном файле вы будете искать последовательность длинной 100 Кб, то, боюсь, придется ждать очень долго.
Основной недостаток вышеизложенного метода состоит в том, что приходится выполнять много лишней работы. Например, найдя строку aabc и обнаружив несоответствие в четвертом символе (совпало только aab), алгоритм будет продолжать сравнивать строку, начиная со следующего символа, хотя это однозначно не приведет к результату. Следующий метод работает намного быстрее простейшего, но, к сожалению, накладывает некоторые ограничения на текст и искомую строку.
Алгоритм Рабина-Карпа
Идея, предложенная Рабином и Карпом, подразумевает поставить в соответствие каждой строке некоторое уникальное число, и вместо того чтобы сравнивать сами строки, сравнивать числа, что намного быстрее. Проблема в том, что искомая строка может быть длинной, строк в тексте тоже хватает. А так как каждой строке нужно сопоставить уникальное число, то и чисел должно быть много, а стало быть, числа будут большими (порядка Dm, где D – количество различных символов), и работать с ними будет так же неудобно. Пример: реализация для текста, состоящего только из цифр, и строки длиной до 8 символов.
Program RabinKarpSearch;
Var T: array[1..40000] of 0..9;
S: array[1..8] of 0..9;
i,j: longint;
n,m: longint;
v,w: longint; {v - число, характеризующее искомую строку, w характеризует строку длинны m в тексте}
k: longint;
const D: longint = 10; {количество разных символов (10 различных цифр)}
Begin
{Ввод текста и образца}
…
v:=0;
w:=0;
for i:=1 to m do
begin
v:=v*D+S[i]; {вычисление v, строка представляется как число}
w:=w*D+T[i]; {вычисление начального значения w}
end;
k:=1;
for i:=1 to m-1 do {k нужно для многократного вычисления w и имеет значение Dm-1}
k:=k*D;
for i:=m+1 to n+1 do
begin
if w=v then {если числа равны, то строки совпадают, а значит, образец найден в тексте}
writeln('Образец входит в текст начиная с ',i-m,'-ого символа');
if i<=n then
w:=d*(w-k*T[i-m])+T[i]; {вычисление нового значения w}
end;
End.
Этот алгоритм выполняет линейный проход по строке (m шагов) и линейный проход по всему тексту (n шагов), стало быть, общее время работы есть O(n+m). Это время линейно зависит от размера строки и текста, стало быть программа работает быстро. Но какой интерес работать только с короткими строками и цифрами? Разработчики алгоритма придумали, как улучшить этот алгоритм без особых потерь в скорости работы. Как вы заметили, мы ставили в соответствие строке ее числовое представление, но возникала проблема больших чисел. Ее можно избежать, если производить все арифметические действия по модулю какого-то простого числа (постоянно брать остаток от деления на это число). Таким образом, находится не само число, характеризующие строку, а его остаток от деления на некое простое число. Теперь мы ставим число в соответствие не одной строке, а целому классу, но так как классов будет довольно много (столько, сколько различных остатков от деления на это простое число), то дополнительную проверку придется производить редко.
Var T: array[1..40000] of char;
S: array[1..10000] of char;
i,j: longint;
n,m: longint;
v,w: longint;
k: longint;
const P: longint = 7919; {1000-е простое число}
D: longint = 256; {количество разных символов (количество всех возможных значений символьного типа char)}
Begin
{Ввод текста и образца}
…
v:=0;
w:=0;
for i:=1 to m do {вычисление v и w}
begin
v:=(v*D+ord(S[i])) mod P; {ord преобразует символ в число}
w:=(w*D+ord(T[i])) mod P;
end;
k:=1;
for i:=1 to m-1 do
k:=k*D mod P; {k имеет значение Dm-1 mod P}
for i:=m+1 to n+1 do
begin
if w=v then {если числа равны, то строки принадлежат одному классу, и надо проверить совпадают ли они}
begin
j:=0;
while (j
j:=j+1;
if j=m then {окончательная проверка}
writeln('Образец входит в текст начиная с ',i-m,'-ого символа');
end;
if i<=n then
w:=(d*(w+P-(ord(T[i-m])*k mod P))+ord(T[i])) mod P;
end;
End.
Итак, все-таки приходится производить сравнение строк посимвольно, но так как «холостых» срабатываний будет немного (в 1/P случаях), то ожидаемое время работы малое. Строго говоря, время работы есть O(m+n+mn/P), mn/P достаточно невелико, так что сложность работы почти линейная. Понятно, что простое число следует выбирать большим, чем больше это число, тем быстрее будет работать программа. Этот алгоритм значительно быстрее предыдущего и вполне подходит для работы с очень длинными строками.
Еще один важный метод – алгоритм Кнута-Морриса-Пратта, один из лучших на нынешний момент, работает за линейное время для любого текста и любой строки.
Алгоритм Кнута-Морриса-Пратта
Метод использует предобработку искомой строки, а именно: на ее основе создается так называемая префикс-функция. Суть этой функции в нахождении для каждой подстроки S[1..i] строки S наибольшей подстроки S[1..j] (j
…
var S: array[1..10000] of char;
P: array[1..10000] of word; {массив, в котором хранятся значения префикс-функции}
i,k: longint;
m: longint;
…
Procedure Prefix; {процедура, вычисляющая префикс-функцию}
Begin
P[1]:=0; {префикс строки из одного символа имеет нулевую длину}
k:=0;
for i:=2 to m do {вычисляется для префиксов строки длинной от 2 до m символов}
begin
while (k>0) and (S[k+1]<>S[i]) do
k:=P[k]; {значение функции может быть получено из ранее сделанных вычислений}
if S[k+1]=S[i] then
k:=k+1;
P[i]:=k; {присвоение префикс-функции}
end;
End;
…
Почему же данная процедура вычисляет префикс-функцию правильно? Используется следующая идея: если префикс (он же суффикс) строки длинной i длиннее одного символа, то он одновременно и префикс подстроки длинной i-1. Таким образом, проверяем префикс предыдущей подстроки, если же тот не подходит, то префикс ее префикса, и т.д. Действуя так, находим наибольший искомый префикс. Следующий вопрос, на который стоит ответить: почему время работы процедуры линейно, ведь в ней присутствует вложенный цикл? Ну, во-первых, присвоение префикс-функции происходит четко m раз, остальное время меняется переменная k. Так как в цикле while она уменьшается (P[k]Program KnutMorrisPrattSearch;
…
{Описание процедуры Prefix и связанных с нею переменных}
…
var n: longint;
T: array[1..40000] of char;
Begin
{Ввод текста и образца}
…
Prefix; {Вычисление префикс-функции}
k:=0; {количество символов, совпавших на данный момент}
for i:=1 to n do
begin
while (k>0) and (S[k+1]<>T[i]) do
k:=P[k];
if S[k+1]=T[i] then
k:=k+1;
if k=m then {если совпали все символы}
begin
writeln('Образец входит в текст начиная с ',i-m+1,'-ого символа');
k:=P[k];
end;
end;
End.
Доказать что эта программа работает за линейное время, можно точно так же, как и для процедуры Prefix. Стало быть, общее время работы программы есть O(n+m), т. е. линейное время.
Простейший алгоритм и алгоритм Кнута-Морриса-Пратта помимо нахождения самих строк считает, сколько символов совпало в процессе работы. Алгоритм Кнута-Морриса-Пратта немногим более громоздок, чем простейший, зато работает намного быстрее.
Автор: Владимир Ткачук (mycоmр.cоm.uа).
Приложение 2
1
|
