Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:


Алгоритм Рабина-Карпа

Поиск:
Идея, предложенная Рабином и Карпом, подразумевает поставить в соответствие каждой строке некоторое уникальное число, и вместо того чтобы сравнивать сами строки, сравнивать числа, что намного быстрее. Проблема в том, что искомая строка может быть длинной, строк в тексте тоже хватает. А так как каждой строке нужно сопоставить уникальное число, то и чисел должно быть много, а стало быть, числа будут большими (порядка 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<m) and (S[j+1]=T[i-m+j]) do
    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 достаточно невелико, так что сложность работы почти линейная. Понятно, что простое число следует выбирать большим, чем больше это число, тем быстрее будет работать программа. Этот алгоритм значительно быстрее предыдущего и вполне подходит для работы с очень длинными строками.

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






Просмотров: 11240

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную