Алгоритми пошуку в тексті

Андрій Боровський

Напевно, кожному, хто багато працює за комп'ютером, знайома така ситуація: гортаючи сторінки книги в пошуках потрібного фрагмента, мимоволі починаєш думати про те, як викликати команду «пошук по всьому тексту». Дійсно, сучасні програми обробки тексту привчили нас до такої зручної можливості, як пошук і заміна фрагментів, і якщо ви розробляєте подібну програму, користувач має право очікувати, що ви надасте в його розпорядження відповідні команди. Цю проблему не можна ефективно вирішити за допомогою стандартних функцій Delphi/Kylix, оскільки більшість засобів розробки включає тільки малоефективні кошти. По-перше, в стандартних функціях не завжди використовуються найефективніші алгоритми, а по-друге, цілком можливо, що вам знадобиться змінити стандартну поведінку цих функцій (наприклад, передбачити можливість пошуку за шаблоном).

У цій статті розглядаються два варіанти найбільш ефективного алгоритму пошуку в тексті - алгоритму Бойєр-Мура. Ми також розглянемо деякі корисні розширення цього алгоритму.

Алгоритм грубої сили і простий варіант алгоритму Бойєр-Мура.

Перш, ніж приступити до розгляду алгоритму Бойєр-Мура, наведемо найпростіший (і самий повільний) алгоритм пошуку, що називається «методом грубої сили ».        

function Find (const S, P: String): Integer;   

var   

i, j: Integer;   

begin   

Result: = 0;   

if Length (P)> Length (S)   then Exit;   

for i: = 1 to Length (S) --   Length (P) + 1 do   

for j: = 1 to Length (P) do   

if P [j] <> S [i + j-1]   then Break   

else if j = Length (P) then      

begin   

Result: = i;   

Exit;   

end;   

end;     

Функція Find шукає підрядок P в рядку S і повертає індекс першого символу рядка або 0, якщо підрядок не знайдено. Хоча в загальному випадку цей метод, як і більшість методів грубої сили, малоефективний, в деяких ситуаціях він цілком прийнятний. Ми самі скористаємося схожим алгоритмом при побудові таблиці зміщень для методу Бойєр-Мура.

Алгоритм Бойєр-Мура, розроблений двома вченими -- Бойєр (Robert S. Boyer) і Муром (J. Strother Moore), вважається найбільш швидким серед алгоритмів загального призначення, призначених для пошуку підрядка в рядку. Перш ніж розглянути роботу цього алгоритму, уточнимо деякі терміни. Під рядком ми будемо розуміти всю послідовність символів тексту. Власне кажучи, мова не обов'язково повинна йти саме про тексті. У загальному випадку рядок - це будь-яка послідовність байтів. Пошук підрядка в рядку здійснюється за заданим зразком, тобто деякої послідовності байтів, довжина якої не перевищує довжину рядка. Наше завдання полягає в тому, щоб визначити, чи містить рядок заданий зразок.

Найпростіший варіант алгоритму Бойєр-Мура складається з наступних кроків. На першому кроці ми будуємо таблицю зміщень для шуканого зразка. Процес побудови таблиці буде описано нижче. Далі ми поєднуємо початок рядка і зразка і починаємо перевірку з останнього символу зразка. Якщо останній символ зразка та відповідний йому при накладенні символ рядка не збігаються, зразок зсувається щодо рядка на величину, отриману з таблиці зміщень, і знову проводиться порівняння, починаючи з останнього символу зразка. Якщо ж символи збігаються, проводиться порівняння передостаннього символу зразка і т. д. Якщо всі символи зразка співпали з накладеними символами рядки, то ми знайшли підрядок і пошук закінчено. Якщо ж якийсь (не останній) символ зразка не збігається з відповідним символом рядка, ми Зрушуємо зразок на один символ вправо і знову починаємо перевірку з останнього символу. Весь алгоритм виконується до тих пір, поки або не буде знайдено входження шуканого зразка, або не буде досягнуто кінець рядка.

Величина зрушення у разі неспівпадання останнього символу обчислюється виходячи з таких міркувань: зсув зразка повинен бути мінімальним, таким, щоб не пропустити входження зразка в рядку. Якщо даний символ рядка зустрічається у зразку, ми зміщуємо зразок таким чином, щоб символ рядка збігся з самим правим входженням цього символу у зразку. Якщо ж зразок взагалі не містить цього символу, ми Зрушуємо зразок на величину, рівну його довжині, так що перший символ зразка накладається на наступний за перевіряла символ рядка.

Величина зміщення для кожного символу зразка залежить тільки від порядку символів у зразку, тому зміщення зручно вирахувати заздалегідь і зберігати у вигляді одновимірного масиву, де кожному символу алфавіту відповідає зсув щодо останнього символу зразка. Пояснимо все вищесказане на простому прикладі. Нехай у нас є набір символів з п'яти символів: a, b, c, d, e і ми хочемо знайти входження зразка "abbad" у рядку "Abeccacbadbabbad". Наступні схеми ілюструють всі етапи виконання алгоритму:

Таблиця зсувів для зразка "abbad".

Початок пошуку. Останній символ зразка не збігається з накладеним символом рядка. Зрушуємо зразок вправо на 5 позицій:

Три символи зразка співпали, а четвертий - ні. Зрушуємо зразок вправо на одну позицію:

Останній символ знову не збігається з символом рядка. Відповідно до таблиці зміщень Зрушуємо зразок на 2 позиції:

Ще раз Зрушуємо зразок на 2 позиції:

Тепер, відповідно до таблиці, зрушує зразок на одну позицію, і отримуємо шукане входження зразка:

Реализуем вказаний алгоритм на мові ObjectPascal. Перш за все слід визначити тип даних «таблиця зсувів». Для кодової таблиці, що складається з 256 символів, визначення цього типу буде виглядати так:        

type   

TBMTable = array [0 .. 255] of   Integer;     

Далі наводиться процедура, обчислює таблицю зміщень для зразка P.        

procedure MakeBMTable (var BMT: TBMTable; const P: String);   

var   

i: Integer;   

begin   

for i: = 0 to 255 do BMT [i]: =   Length (P);   

for i: = Length (P) downto 1   do   

if BMT [Byte (P [i])] =   Length (P) then   

BMT [Byte (P [i])]: =   Length (P) - i;   

end;     

Тепер напишемо функцію, що здійснює пошук.        

function BMSearch (StartPos: Integer; const S, P: String;   

const BMT: TBMTable):   Integer;   

var   

Pos, lp, i: Integer;   

begin   

lp: = Length (P);   

Pos: = StartPos + lp -1;   

while Pos   

if P [lp] <> S [Pos]   then Pos: = Pos + BMT [S [Pos]]   

else for i: = lp - 1 downto   1 do   

if P [i] <> S [Pos --   lp + i] then   

begin   

Inc (Pos);   

Break;   

end   

else if i = 1 then   

begin   

Result: = Pos - lp + 1;   

Exit;   

end;   

Result: = 0;   

end;     

Функція BMSearch повертає позицію першого символу перше входження зразка P в рядку S. Якщо послідовність P в S не знайдено, функція повертає 0 (нагадаю, що в ObjectPascal нумерація символів у рядку String починається з 1). Параметр StartPos дозволяє вказати позицію в рядку S, з якої слід починати пошук. Це може бути корисним у тому випадку, якщо ви захочете знайти всі входження P в S. Для пошуку з самого початку рядка слід задати StartPos рівним 1. Якщо результат пошуку не дорівнює нулю, то для того, щоб знайти наступний збіг P в S, слід поставити StartPos рівним значенню «попередній результат плюс довжина зразка».

Більш ефективний варіант

Хоча розглянутий спрощений алгоритм цілком придатний з практичної точки зору (і часто застосовується), не можна не помітити, що результати порівнянь використовуються недостатньо ефективно. Дійсно, на другим кроком, коли у нас збіглися три символи, ми, знаючи, що послідовність "Bad" зустрічається у зразку тільки один раз, могли б відразу змістити зразок на всю його довжину, а не на один символ. Тепер ми розглянемо другий, трохи більше складний варіант алгоритму Бойєр-Мура, що дозволяє врахувати результати попередніх порівнянь у випадку часткового збігу зразка та підрядки. Перш за все змінимо принцип побудови таблиці зміщень. У цьому варіанті алгоритму таблиця - Двовимірна, кожному символу зразка відповідає один стовпчик таблиці, а кожній букві алфавіту - один рядок. У клітинках таблиці містяться значення зсувів, на які потрібно зрушити зразок, якщо при перевірці цього символу зразка виявлена розбіжність і замість шуканого символу отриманий символ алфавіту, що відповідає деякої рядку в таблиці. Наприклад, таблиця послідовності "Abdab" для нашого пятібуквенного алфавіту буде виглядати наступним чином:

Заповнення таблиці починається з останнього стовпця. Самий правий стовпець таблиці фактично відповідає масиву, який використовується в спрощеному варіанті алгоритму. Наступні стовпці містять значення зсуву для зразка за умови, що попередні (при русі справа наліво) символи збіглися. Проводячи пошук за допомогою цієї таблиці, ми послідовно переглядаємо значення комірок, що лежать на перетині стовпця, відповідного символу зразка і рядка, що відповідає символу тексту. Перегляд починається з останнього стовпця. Якщо в кожному стовпці обрана комірка містить 0, значить, підрядок знайдено. Якщо значення комірки відрізняється від нуля, ми Зрушуємо зразок на відповідне значення.

Певні труднощі можуть виникнути при роботі з кодуванням Unicode. Очевидно, що таблиця, число рядків якої дорівнює числу символів двобайтового кодування, буде занадто громіздкою. На щастя, у такій таблиці немає необхідності, адже у випадку двобайтового кодування будь-який зразок містить лише невелику частину символів алфавіту. Для всіх символів, які не містяться у зразку, значення зміщення в кожному стовпці таблиці будуть однаковими. Ця особливість дозволяє розробити скорочені варіанти таблиці для Unicode. Звичайно, Unicode-рядок можна розглядати як послідовність байтів, де кожен Unicode-символ представлений двома байтами. Однак цей підхід менш ефективний і не дозволяє скористатися тими додатковими можливостями алгоритму, про які буде сказано нижче.

Далі наводяться функції і визначення, що реалізують алгоритм для 256-символьного набору.        

type   

TIntVect = array [0 .. 255] of   Integer;   

TBMTable = array [0 .. 0] of   TIntVect;   

PBMTable = ^ TBMTable;   

function FindRightmost (const S, P: String;   

n: Integer): Integer;   

var   

i, j, lp: Integer;   

begin   

Result: = 0;   

lp: = Length (P);   

if lp> n then Exit;   

for i: = n - lp + 1 downto 1   do   

for j: = 1 to lp do   

if P [j] <> S [i + j-1] then   Break   

else if j = lp then   

begin   

Result: = i;   

Exit;   

end;   

end;   

procedure MakeBMTable (var BMT: PBMTable; const P: String);   

var   

i, j, lp, MaxShift, CurShift,   SufPos: Integer;   

Suffix: String;   

begin   

lp: = Length (P);   

GetMem (BMT,   SizeOf (TIntVect) * lp);   

for i: = 0 to 255 do   BMT ^ [lp-1] [i]: = lp;   

for i: = lp downto 1 do   

if BMT ^ [lp-1] [Byte (P [i])] = lp   then   

BMT ^ [lp-1] [Byte (P [i])]: = lp --   i;   

MaxShift: = lp;   

for i: = lp - 1 downto 1 do   

begin   

SetLength (Suffix, lp - i);   

Move (P [i +1], Suffix [1], lp --   i);   

if Pos (Suffix, P) = 1 then   MaxShift: = i;   

for j: = 0 to 255 do   

begin   

CurShift: = MaxShift;   

SetLength (Suffix, lp - i +   1);   

Suffix [1]: = Char (j);   

Move (P [i + 1], Suffix [2],   lp - i);   

SufPos: = FindRightmost (P,   Suffix, lp - 1);   

if SufPos <> 0 then   CurShift: = i - SufPos;   

BMT ^ [i-1] [j]: = CurShift;   

end;   

BMT ^ [i-1] [Byte (P [i])]: = 0;   

end;   

end;   

function BMSearch (StartPos, lp: Integer; const S: String;   

BMT: PBMTable): Integer;   

var   

Pos, i: Integer;   

begin   

Pos: = StartPos + lp -1;   

while Pos   

for i: = lp downto 1 do   

if   BMT ^ [i-1] [Byte (S [Pos-lp + i])] <> 0 then   

begin   

Pos: = Pos +   BMT ^ [i-1] [Byte (S [Pos-lp + i])];   

Break;   

end   

else if i = 1 then   

begin   

Result: = Pos - lp + 1;   

Exit;   

end;   

Result: = 0;   

end;     

Службова функція FindRightmost повертає саме останнє входження зразка P серед n перших символів рядка S. Формат виклику функції BMSearch відрізняється від попереднього. У параметрі lp передається довжина рядка зразка, сама ж рядок не потрібна, так як таблиця зсувів однозначно описує зразок. Слід також врахувати, що функція MakeBMTable динамічно виділяє пам'ять для таблиці зміщень, і після закінчення використання функції BMSearch цю пам'ять необхідно звільнити за допомогою функції FreeMem. Наступний фрагмент коду ілюструє пошук всіх входжень зразка P в рядку S.        

MakeBMTable (BMT, P);   

PatPos: = BMSearch (1, Length (P), S, BMT);   

while PatPos <> 0 do   

begin   

...   

PatPos: = BMSearch (PatPos + 1,   Length (P), S, BMT);   

end;   

FreeMem (BMT);     

Додатковою перевагою даного варіанту алгоритму є можливість організувати «регістронезавісімий» пошук, тобто пошук слова незалежно від контексту. Для цього досить у таблиці зсувів зіставити однакові рядки одним і тим же буквах різного регістра. Можна навіть ввести пошук за шаблоном, який містить символи підстановки. Нижче наводяться функції формування таблиці зміщень для шаблонів, в яких символ «?» Відповідає будь-якому символу використовуваного набору.        

function WCBeginsWith (const P, S: String): Boolean;   

var   

i, lp: Integer;   

begin   

Result: = False;   

lp: = Length (P);   

if lp> Length (S) then   Exit;   

for i: = 1 to lp do   

if (P [i] <> S [i]) and   (P [i ]<>'?') and (S [i ]<>'?') then Exit;   

Result: = True;   

end;   

function WCFindRightmost (const S, P: String;   

l: Integer): Integer;   

var   

i, j, lp: Integer;   

begin   

Result: = 0;   

lp: = Length (P);   

if lp> l then Exit;   

for i: = l - lp + 1 downto 1   do   

for j: = 1 to lp do   

if (P [j] <> S [i + j-1]) and   (P [j ]<>'?') and (S [i + j-1 ]<>'?')      

then Break   

else if j = lp then   

begin   

Result: = i;   

Exit;   

end;   

end;   

procedure WCMakeBMTable (var BMT: PBMTable;   

const P: String);   

var   

i, j, lp, MaxShift, CurShift,   SufPos: Integer;   

Suffix: String;   

begin   

lp: = Length (P);   

GetMem (BMT,   SizeOf (TIntVect) * lp);   

if P [lp] = '?' then   

for i: = 0 to 255 do   BMT ^ [lp-1] [i]: = 0   

else   

begin   

for i: = 0 to 255 do   BMT ^ [lp-1] [i]: = lp;   

for i: = lp downto 1 do   

if BMT ^ [lp-1] [Byte (P [i])] =   lp then   

BMT ^ [lp-1] [Byte (P [i])]: = lp   - I;   

end;   

MaxShift: = lp;   

for i: = lp - 1 downto 1 do   

begin   

SetLength (Suffix, lp - i);   

Move (P [i +1], Suffix [1], lp --   i);   

if WCBeginsWith (Suffix, P)   then MaxShift: = i;   

if P [i] = '?' then for j: =   0 to 255 do BMT ^ [i-1] [j]: = 0   

else for j: = 0 to 255 do   

begin   

CurShift: = MaxShift;   

SetLength (Suffix, lp - i +   1);   

Suffix [1]: = Char (j);   

Move (P [i + 1], Suffix [2], lp - i);   

SufPos: =   WCFindRightmost (P, Suffix, lp - 1);   

if SufPos <> 0 then   

CurShift: = i - SufPos;   

BMT ^ [i-1] [j]: = CurShift;   

end;   

BMT ^ [i-1] [Byte (P [i])]: = 0;   

end;   

end;     

Наприклад, якщо в якості шаблону функції WCMakeBMTable передати рядок «кинув? Ть», і передати отриману таблицю функції BMSearch, в тексті S будуть знайдені всі входження слів «кидати» і «кинути» (а також «закидати», «закинути», «кидатися» і тому подібне, оскільки не вказані випереджає і завершальний пробілами).

На закінчення розглянемо питання про те, чи завжди слід застосовувати алгоритм Бойєр-Мура, і який варіант цього алгоритму краще вибрати. Перевага алгоритму Бойєр-Мура перед методом грубої сили найбільш відчутно проявляється зі збільшенням довжини зразка. Хоча алгоритм Бойєр-Мура виробляє менше порівнянь, ніж примітивний алгоритм при довжині зразка більше двох символів, велика складність цього алгоритму і необхідність заздалегідь обчислювати таблицю зміщень може звести нанівець його переваги, якщо пошук проводиться в короткому тексті, і довжина зразка невелика.

Перевага у швидкодії складнішого варіанта алгоритму Бойєр-Мура перед більш простим варіантом позначається, тільки якщо довжина зразка велика, і в тексті часто зустрічаються окремі послідовності символів, що містяться у зразку. Головне ж достоїнство складнішого варіанту алгоритму полягає у можливості реалізації регістронезавісімого пошуку і пошуку за шаблоном.

Список літератури

Для підготовки даної роботи були використані матеріали з сайту http://www.rsdn.ru/