.

Пошук зразка в рядку (реферат)

Язык: украинский
Формат: реферат
Тип документа: Word Doc
0 1929
Скачать документ

Реферат на тему:

Пошук зразка в рядку

1. Оцінка кількості порівнянь

Задача. У рядку відшукати всі позиції, починаючи з яких інший рядок
(зразок) входить в рядок, тобто є його підрядком. Наприклад, у рядку

ABRACADABRA

зразок ABR входить як підрядок з позицій 1 і 8, зразок A – з позицій 1,
4, 6, 8 і 11, а зразок ARA не входить.

Позначимо через s рядок, у якому шукається зразок x. Нехай m і n –
довжини рядків s і x. Можна порівняти з x усі підрядки s довжини n, які
починаються з позицій 1, 2, … , m-n+1. У разі рівності друкується
відповідна позиція:

for k:=1 to m-n+1 do

if copy(s, k, n)=x then writeln(k).

Нагадаємо, що з виклику copy(s, k, n) повертається підрядок рядка s, що
починається в його позиції k та має довжину n. Дуже просто, але дуже
нерозумно! Адже загальна кількість порівнянь символів є (m-n+1)? n.
Наприклад, за m=255, n=128 порівнянь символів буде 1282=16384, хоча
більшість їх насправді зайва. Ми переконаємося в цьому, розглянувши далі
зовсім інші способи пошуку зразка.

Але спочатку оцінимо зверху кількість порівнянь символів. Зафіксуємо
довжину рядка m. Нехай довжина зразка n довільна в межах між 1 та m.
Тоді (m-n+1)? n0 s[k]? x[k], то серед x[k-1], … , x[1] треба
відшукати найближчий до x[k] символ x[j]=s[k]. Ця рівність означає, що
зразок, можливо, має кінець у рядку в позиції k+(n-j), тобто n+(k-j).
Тоді можна знову починати все з кінця зразка, порівнюючи x[n] із
s[n+(k-j)].

Нехай змінна last позначає позицію кінця зразка в рядку s. Спочатку
last=n, а його наступним значенням може бути лише, як показує попередній
аналіз, або n+1, або n+(n-p[s[n]]), або n+(k-j). За будь-якого з цих
значень змінної last наступним її значенням буде так само або last+1,
або last+(last-p[s[n]]), або last+k-j. На основі цих міркувань
записується такий спрощений варіант алгоритму Бойєра-Мура:

last:=n;

while last<=m doif x[n]<>s[last] then last:=last+(n-p[s[n]])

else

begin

k:=n-1; ok:=true;

while (k>0) and ok do

if x[k]=s[last-n+k] then k:=k-1 else ok:=false;

if k=0 then {s[last-n+1]…s[last]=x}

begin

повідомити про те, що з last-n+1 починається зразок;

last:=last+1

end else

begin

відшукати серед x[1]…x[k-1] найближчий до x[k]

символ x[j], рівний s[last-n+k]; якщо такого немає, то j:=0

last:=last+(k-j)

end

end.

Зауважимо, що цей спрощений варіант в деяких випадках не рятує від
необхідності здійснювати O(m? n) порівнянь символів. Справжній алгоритм
Бойєра-Мура забезпечує, що кількість порівнянь символів за будь-яких
рядків довжини m і n оцінюється як O(m+n), тобто її можна вважати
пропорційною сумі довжин рядка й зразка. Ідея цього методу приблизно
така сама, як і методу з наступного підрозділу.

3. Метод Кнута-Морріса-Пратта

Цей метод уперше описано Моррісом і Праттом у [MorPr]. Він наведений
також у книзі [АХУ].

Почнемо порівнювати символи зразка x=x[1]…x[n] із символами рядка
s=s[1]…s[m] із початку. Нехай s[1]=x[1], … , s[j-1]=x[j-1], s[j]? x[j],
де j? n. Зрозуміло, що зразок не входить у рядок із першої позиції.
Можна, звичайно, спробувати почати перевірку з другої позиції, але
зовсім не обов’язково. Наприклад, за зразка x=’ababb’ й рядка
s=’ababababbab’ після того, як виявилося, що s[5]=’a’? ‘b’=x[5], є сенс
починати наступну перевірку лише з s[3], оскільки саме там є входження
початку зразка. Символами s[3]s[4]=’ab’ водночас закінчується й
починається частина зразка x[1]x[2]x[3]x[4], і наступне входження зразка
можливе, коли x[1]x[2] займуть місце x[3]x[4], тобто зразок “зсунеться”
відносно рядка одразу на дві позиції. Після цього можна продовжити
перевірку від символу s[5], тобто без повернення назад у рядку s.

Далі виявляється s[7]? x[5], і зразок можна зсунути одразу на дві
позиції, щоб x[1]x[2] знову зайняли місце x[3]x[4], збігаючися при цьому
з s[5]s[6]. Тепер s[7]=x[3], s[8]=x[4], s[9]=x[5], і входження починаючи
з позиції 5 знайдено.

Отже, нехай перевіряється входження зразка від позиції i-j,
x[1]…x[j]=s[i-j]…s[i-1], а x[j+1] не збігається з черговим символом
рядка s[i]. У такому разі треба відшукати такий найдовший початок
x[1]…x[k] зразка, що водночас є кінцем підрядка x[1]…x[j]. Він є також і
кінцем підрядка s[1]…s[i-1]!

Перехід від перевіреного початку зразка довжини j до перевіреного
початку довжини k означає зсув зразка відносно рядка s одразу на j-k
позицій. Але на меншу кількість позицій зсувати зразок немає сенсу,
оскільки x[1]…x[k] – це найдовший початок зразка, що збігається з кінцем
підрядка s[1]…s[i-1].

Якщо x[k+1]=s[i], то можна продовжувати порівняння від символу s[i+1].
Якщо x[k+1]? s[i], то треба відшукати найдовший початок x[1]…x[k1]
зразка, що збігається з кінцем x[1]…x[k] (і з кінцем s[1]…s[i-1]), і
порівняти x[k1+1] із s[i] тощо.

Наприклад, якщо s=’abababc’, а x=’ababc’, то при спробі “прикласти”
зразок починаючи з першого символу рядка маємо x[1]=s[1], x[2]=s[2],
x[3]=s[3], x[4]=s[4], x[5]? s[5], тобто j=4. Відповідним значенням k
буде 2, оскільки ‘ab’ є найдовшим початком рядка ‘abab’, що є водночас
його кінцем. Звідси випливає, що немає сенсу пробувати “прикласти”
зразок до рядка, починаючи з його другої позиції, а слід “пересунути”
його одразу на j-k=2 позиції. При цьому гарантується рівність x[1]…x[k]
і s[i-k]…s[i-1], тобто назад від позиції s[i] в рядку можна не
повертатися.

Отже, якщо для кожної позиції j зразка відома найбільша довжина f(j) x[k+1]) and (k>0) do

k := f[k];

if (x[j] <> x[k+1] ) and (k=0) then f[j] := 0

else f[j] := k+1;

end;

Оцінимо загальну кількість порівнянь символів, виконуваних за цим
алгоритмом. Позначимо через w(j) кількість виконань тіла циклу за
відповідного значення j=2, … , n. Помітимо, що кожне виконання тіла
циклу while зменшує значення k не менше, ніж на 1. Звідси
f[j]<=f[j-1]-w(j)+1, тобто w(j)<=f[j-1]-f[j]+1. Тодіw(2)+w(3)+…+w(n) ? f[1]-f[2]+1+f[2]-f[3]+1+…+f[n-1]-f[n]+1 == f[1]-f[n]+n-1 ? n-1.За кожного j порівнянь символів відбувається на 2 більше, ніж виконань тіла циклу – одне додаткове при обчисленні умови в заголовку циклу і одне в умовному операторі. Звідси загальна кількість порівнянь символів не більше 3(n-1), тобто прямо пропорційна n. Таким чином, загальну кількість порівнянь символів при побудові функції відступів можна оцінити як O(n).Тепер, нарешті, наведемо алгоритм пошуку входжень зразка в рядок. Нехай t позначає номер поточної позиції в рядку, j – номер поточної позиції в зразку, спочатку вони рівні 1. Далі, поки t? m, виконуємо наступні дії. Порівнюємо символи x[j] і s[t]. Якщо вони рівні, маємо входження x[1]…x[j] в кінці рядка s[1]…s[t]. Якщо при цьому j=n, то можна повідомити про входження зразка починаючи з позиції t-j+1 і приступати до пошуків наступного входження, поклавши j=f(n). Якщо ж j1 міняємо значення j на f[j-1]+1, а при j=1
збільшуємо t на 1. Втім, зміни j не мають сенсу, коли t=m. Ось і все.
Наведемо цей алгоритм також і в мові Паскаль:

t:=1; j:=1;

while t<=m dobeginif x[j]=s[t] thenif j=n thenbegin writeln(t-j+1); j:=f[j] endelsebegin t:=t+1; j:=j+1 endelse { x[j]<>s[t] }

if t1 then j:=f[j-1]+1 else t:=t+1

else t:=t+1

end.

Оцінимо тепер кількість порівнянь символів при виконанні цього
алгоритму. Помітимо, що при кожному виконанні тіла циклу збільшується t
на 1 або зменшується j принаймні на 1 присвоюванням f[j] чи f[j-1]+1.
Позначимо через b(t) початкове значення j при черговому значенні t=1, 2,
…, m, а через w(t) – кількість зменшень j при відповідному значенні t.
Оскільки при збільшенні t значення j або не міняється, або збільшується
на 1, то маємо, що b(t)? b(t-1)-w(t)+1 за t>1, звідки w(t)?
b(t-1)-b(t)+1. Тоді

w(1)+w(2)+…+w(m) ? 1+b[1]-b[2]+1+b[2]-b[3]+1+…+b[m-1]-b[m]+1 =

= m+b[1]-b[m] ? m+1.

З алгоритму очевидно, що порівнянь символів відбувається рівно стільки,
скільки збільшень t та зменшень j разом. Оскільки t збільшується m-1
разів, загальна кількість порівнянь символів не більше 2m, тобто
пропорційна m, і оцінюється як O(m).

З урахуванням побудови функції відступів загальна кількість порівнянь
символів за будь-яких рядків довжини m і n оцінюється як O(n)+O(m), або
O(m+n).

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Оставить комментарий

avatar
  Подписаться  
Уведомление о
Заказать реферат
UkrReferat.com. Всі права захищені. 2000-2019