خوارزمية Boyer-Moore

خوارزمية Boyer-Moore

تستخدم هذه الخوارزمية للبحث في السلاسل النصية

حيث تعتبر من أسرع الخوارزميات في هذا المجال

تستخدم هذه الخوارزمية من قبل العديد من محررات النصوص

طرحت هذه الخوارزمية في العام 1975

من قبل Bob Boyer و Strother Moore

أظن أن أفضل من يشرح كيفية عمل هذه الخوارزمية هو الذي ألفها Strother Moore

http://www.cs.utexas.edu/users/moore/best-...os-example.html

إليكم الخوارزمية بالديلفي

{Public-domain demo of Boyer-Moore search algorithm.
 Guy McLoughlin - May 1, 1993.}

 program DemoBMSearch;

 {Boyer-Moore index table data definition}
 type
   BMTable = array[0..127] of byte;

   {Create a Boyer-Moore index table to search with.}

 procedure Create_BMTable(Pattern: string; var BMT: BMTable);
 var
   Index: byte;
 begin
   fillchar(BMT, sizeof(BMT), length(Pattern));
   for Index := 1 to length(Pattern) do
     BMT[ord(Pattern[Index])] := (length(Pattern) - Index)
 end;

 {Boyer-Moore Search function. Returns 0 if string is not found. Returns 65,535 if
 BufferSize is too large, ie: greater than 65,520 bytes.}

 function BMsearch(var Buffer; BuffSize: word; var BMT: BMTable; Pattern: string): word;
 var
   Buffer2: array[1..65520] of char absolute Buffer;
   Index1, Index2, PatSize: word;
 begin
   if (BuffSize > 65520) then
   begin
    BMsearch := $FFFF;
   exit
   end;
   PatSize := length(Pattern);
   Index1 := PatSize;
5  Index2 := PatSize;
   repeat
     if (Buffer2[Index1] = Pattern[Index2]) then
    begin
       dec(Index1);
       dec(Index2)
    end
    else
     begin
       if (succ(PatSize - Index2) > (BMT[ord(Buffer2[Index1])])) then
         inc(Index1, succ(PatSize - Index2))
       else
         inc(Index1, BMT[ord(Buffer2[Index1])]);
       Index2 := PatSize
     end;
   until
     (Index2 < 1) or (Index1 > BuffSize);
   if (Index1 > BuffSize) then
     BMsearch := 0
   else
     BMsearch := succ(Index1)
 end;

 type
   arby_64K = array[1..65520] of byte;

 var
   Index: word;
   st_Temp: string[10];
  Buffer: ^arby_64K;
   BMT: BMTable;

 begin
   new(Buffer);
   fillchar(Buffer^, sizeof(Buffer^), 0);
   st_Temp := 'Gumby';
   move(st_Temp[1], Buffer^[65516], length(st_Temp));
   Create_BMTable(st_Temp, BMT);
   Index := BMSearch(Buffer^, sizeof(Buffer^), BMT, st_Temp);
   writeln(st_Temp, ' found at offset ', Index)
 end.