Алгоритм поиска текста Рабина на Delphi 7 выходит ошибка

[Des]

Здравствуйте! В книге нашел метод Рабина, но он приведен для Turbo Pascal...

Function Search (S: String; X: String; var Place: Byte): Boolean;
{ Функция возвращает результат поиска в слове S }
{ подслова X. Place - место первого вхождения }
Var Res: Boolean; i: Byte; h,NowH,LenX:Integer; HowMany:Integer;
  Begin
   Res:=FALSE;
   i:=1;
   h:=Hash(x); {Вычисление хеш-функции для искомого слова}
   NowH:=Hash(Copy(S,1,Length(x)));
   HowMany:=Length(S)-Length(X)+1;
   LenX:=Length(X);
    While (i<=HowMany) And Not(Res) do
     If (h=NowH) and (Copy(S,i,Length(X))=X) then
      Begin
         Res:=TRUE;
       	 Place:=i
      End
     else
      Begin
       i:=i+1;
       NextHash(s,i,NowH,LenX); {Вычисление следующего значения хеш-функции}
      End;
       Search:=Res
  End;

Собственно Delphi 7 не понимает вот этот участок кода

h:=Hash(x)

и вот этот

NextHash

Подскажите пожалуйста что можно сделать?

[Jeni]

А где находятся подпрограммы Hash и NextHash?

[Des]

Jeni
1.2.2. Алгоритм Рабина.
Алгоритм Рабина представляет собой модификацию линейного алгоритма; он основан на весьма простой идее, которую изложим, следуя книге [13 ,172-173].
«Представим себе, что в слове A, длина которого равна m, мы ищем образец X длины n. Вырежем "окошечко" размером n и будем двигать его по входному слову. Нас интересует, не совпадает ли слово в "окошечке" с заданным образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую числовую функцию на словах длины n, тогда задача сведется к сравнению чисел, что, несомненно, быстрее. Если значения этой функции на слове в "окошечке" и на образце различны, то совпадения нет. Только если значения одинаковы, необходимо проверять последовательно совпадение по буквам.» (Листинг 2)

Function Search (S: String; X: String; var Place: Byte): Boolean;
{ Функция возвращает результат поиска в слове S }
{ подслова X. Place - место первого вхождения }
Var Res: Boolean; i: Byte; h,NowH,LenX:Integer; HowMany:Integer;
  Begin
   Res:=FALSE;
   i:=1;
   h:=Hash(x); {Вычисление хеш-функции для искомого слова}
   NowH:=Hash(Copy(S,1,Length(x)));
   HowMany:=Length(S)-Length(X)+1;
   LenX:=Length(X);
    While (i<=HowMany) And Not(Res) do
     If (h=NowH) and (Copy(S,i,Length(X))=X) then
      Begin
         Res:=TRUE;
       	 Place:=i
      End
     else
      Begin
       i:=i+1;
       NextHash(s,i,NowH,LenX); {Вычисление следующего значения хеш-функции}
      End;
       Search:=Res
  End;

Этот алгоритм выполняет линейный проход по строке (n шагов) и линейный проход по всему тексту (m шагов), стало быть, общее время работы есть O(n+m). При этом мы ...

Это все что есть. Что за Hash :'(

[soleil@mmc]

а в чем прикол? можно же просто заюзать старый-добрый pos()
или нужно реализовать это вот таким извратом?

[Des]

soleil@mmc
Это требование Института :D

Вот еще немножко инфы к ознакомлению, но нового ничего я так и не нашел. http://ru.wikipedia.org/wiki/Алгоритм_Рабина_—_Карпа

[Jeni]

Сообщение от Des

Это все что есть. Что за Hash

Мне совершенно всё-равно что это за алгоритм и как он описывается математически. Я хотел сказать, что в твоем коде присутствует вызов подпрограмм Hash и NextHash. Т.к. самих этих подпрограмм нет, то естественно что

Delphi 7 не понимает вот этот участок кода

Среда программирования не знает ни о каких Hash. Нужно или вставить код этих подпрограмм или реализовать их самому.

[soleil@mmc]

странно:

Только если значения одинаковы, необходимо проверять последовательно совпадение по буквам

а в коде видим, что

If (h=NowH) and (Copy(S,i,Length(X))=X) then

т.е. сравнение хешей и подстрок делается на одном уровне и при этом высчитывается каждый раз длина подстроки Length(X) вместо уже имеющейся переменной LenX

и еще интересно - а процесс вычисления хешей не дольше будет чем получение подстроки?!

З.Ы.: собсна про хеш-функу там есть описание (лучше смотри оригинал на вики, а то тут степень поплыла):

Используемая хеш-функция

Ключом к производительности алгоритма Рабина-Карпа является эффективное вычисление хэш-значения последовательных подстрок текста. Одна популярная и эффективная кольцевая хэш-функция интерпретирует каждую подстроку как число в некоторой системе счисления, основание которой является большим простым числом. Например, если подстрока "hi" и основание системы счисления 101, хэш-значение будет 104 Ч 1011 + 105 Ч 1010 = 10609 (ASCII код 'h' — 104 и 'i' — 105)

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

Например, если мы имеем текст "abracadabra" и ищем образец длины 3, мы можем рассчитать хэш подстроки "bra" из хэша подстроки "abr" (предыдущая подстрока), вычитая число добавленное для первой буквы 'a' из "abr", т.е. 97 Ч 1012 (97 — ASCII для 'a' и 101 — основание, которое мы используем), умножение на основание и наконец добавляя последнее число для "bra", т.е. 97 Ч 1010 = 97. Если подстроки в запросе длинны, этот алгоритм достигает большой экономии сравнимо с многими другими схемами хэширования.

Теоретически, существуют другие алгоритмы, которые могут обеспечить сравнимый объём вычислений, например, умножая ASCII-значения всех символов, в результате сдвиг подстроки будет влечь за собой только деление на первый символ и умножение на последний. Ограничением, однако, является размер типа данных целого числа и необходимость использовать модульную арифметику для уменьшения результатов хэширования, см. статью хэш-функция; тем не менее, эти простые хэш-функции, которые быстро не производят большие числа, такие как просто добавление ASCII-кодов, наболее вероятно генерируют большое количество хэш-коллизий и следовательно — замедляют алгоритм. Из этого следует, что описанная хэш-функция является предпочитаемой для алгоритма Рабина-Карпа.

[Des]

А ммм допустим самому сделать. Что посоветуете почитать по этому поводу ?

[Des]

PS: перерыл пару тонн учебников по турбо паскалю. Может плохо рыл конечно но там вот этого хеша я не нашел. Значит вышепредоставленный код скорее всего не работоспособен. т.е. идею типа дали, а дальше жувайте еще пару тонн учебников о всяких хешированиях :D...
Чуеться мне я встрял :-o

[Jeni]

Сообщение от Des

перерыл пару тонн учебников по турбо паскалю. Может плохо рыл конечно но там вот этого хеша я не нашел.

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