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

Реферат з програмування: ПОШУК ЗРАЗКА В РЯДКУ 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) n<m n. Як бачимо, різниця n2-n між m n та (m-n+1) n мала за значень n, близьких до 1, і велика за n, близьких до m. За малих значень n величиною n2-n можна нехтувати. Таким чином, наша оцінка (m-n+1) n = O(m n) є досить точною за малих значень n і грубою – за великих. Припустивши, що зразки з великою довжиною – явище дуже рідкісне, можна вважати цю оцінку цілком прийнятною. 2. Метод Бойєра-Мура (спрощений варіант) Один із способів суттєво зменшити кількість порівнянь належить Бойєру та Муру [BoMo]. Розглянемо спрощений варіант їх алгоритму. Нехай символи рядка й зразка належать деякому алфавіту. Нехай зразок x=x[1]x[2]…x[n]. Спочатку для кожного символу Z алфавіту визначається номер позиції p[Z] його останньої появи в рядку x. Якщо символ Z відсутній в x, то p[Z]=0. Наприклад, у зразку ‘ababc’ p[‘a’]=3, p[‘b’]=4, p[‘c’]=5, а для решти символів Z алфавіту p[Z]=0. Обчислення масиву p очевидне: Для всіх символів Z алфавіту p[Z]:=0; for k:=1 to n do p[x[k]]:=k. Інформація про останню появу символів у зразку використовується так. Порівняємо одразу s[n] та x[n]. Якщо s[n]  x[n], то найближчим до кінця зразка символом, якому рівний s[n], є символ x[p[s[n]]]. Таким чином, можна не порівнювати s[n] із жодним із символів зразка між x[p[s[n]]] та x[n]. А це означає, що можна не перевіряти рівність зразка з підрядками, що починаються з позицій 2, 3, … , n-p[s[n]]. Наприклад, якщо x=’ababc’, а рядок s починається символами aaaba, то p[s[5]]=3 підказує, що зразок не може починатися в рядку з позиції 5-3=2. Отже, за s[n] x[n] можна перейти одразу до порівняння x[n] із s[n+(n-p[s[n]])]. Якщо s[n]=x[n], то можна порівняти попередні символи рядка з відповідними символами зразка, рухаючися від його кінця до початку. Якщо всі відповідні символи рівні, то зразок є підрядком, що починається з першої позиції рядка. Після цього можна переходити до аналізу другої позиції s, порівнюючи x[n] із s[n+1]. Якщо за деякого k>0 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 do if 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)<j такого початку зразка x[1]…x[f(j)], що збігається з кінцем x[1]…x[j], то перше входження зразка знаходиться без повернень у рядку s. Для визначення можливого початку наступного входження треба знати лише f(n) і продовжувати пошук знову-таки без повернень у рядку! Саме відсутність повернень у рядку дозволяє оцінити загальну кількість порівнянь як O(m+n), що суттєво менше, ніж O(m n). Ми доведемо це далі. Функція f(j), що виражає довжину такого найдовшого початку рядка x[1]…x[j], що є водночас його кінцем, називається функцією відступів. Вона показує, до якого символу x[f(j)] треба відступити в зразку, коли x[j+1] не збігається з черговим символом рядка, щоб продовжувати пошук із порівняння чергового символу з символом x[f(j)+1]. Цей відступ рівносильний зсуву рядка на найменшу можливу кількість позицій j-f(j). Займемося тепер обчисленням цієї функції за зразком. Очевидно, f(1)=0. Нехай всі значення f(1), … , f(j-1) уже обчислено, причому f(j-1)=k. Якщо x[j]=x[k+1], то кінець рядка x[1]…x[j-1]x[j] збігається з його ж початком довжини k+1, тому f(j)=k+1. Якщо x[j] x[k+1], то "наступним кандидатом у кінці" рядка x[1]…x[j-1]x[j] є рядок x[1]…x[f(k)]x[f(k)+1], оскільки саме x[1]…x[f(k)] є найдовшим кінцем x[1]…x[k]. Якщо й він не годиться, то наступним є x[1]…x[f(f(k))+1] тощо. Отже, ми або знайдемо початок довжини p, такий, що x[1]…x[p] є кінцем x[1]…x[j], і тоді f(j)=p, або не знайдемо, і f(j)=0. Наведені обчислення описуються таким алгоритмом (подамо функцію f масивом): f[1] := 0; for j := 2 to n do begin k := f[j-1]; while (x[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). Якщо ж j<n, то переходимо до наступної пари символів, збільшивши t і j на 1. За нерівності s[t] і x[j] при j>1 міняємо значення j на f[j-1]+1, а при j=1 збільшуємо t на 1. Втім, зміни j не мають сенсу, коли t=m. Ось і все. Наведемо цей алгоритм також і в мові Паскаль: t:=1; j:=1; while t<=m do begin if x[j]=s[t] then if j=n then begin writeln(t-j+1); j:=f[j] end else begin t:=t+1; j:=j+1 end else { x[j]<>s[t] } if t<m then if j>1 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). ДОДАТОК Службові слова стандарту мови Паскаль and false mod set array file nil then begin for not to case forward of true const function or type div goto packed until do if procedure var downto in program while else label record with end maxint repeat Додаткові слова в Турбо Паскаль absolute implementation object unit constructor inline shl uses destructor interface shr virtual external interrupt string xor СПИСОК ЛІТЕРАТУРИ [Аб] Абрамов А.С. Элементы анализа программ.- М., 1986. [АГКС]Абрамов С.А., Гнездилова Г.Г., Капустина Е.Н., Селюн М.И. Задачи по программированию.- М., 1988. [Ан] Андерсон Р. Доказательство правильности программ.- М.:, 1982. [Арс] Арсак Ж. Программирование игр и головоломок.- М., 1990. [АУ] Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1.- М., 1978. [АХУ] Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.- М., 1979. [БаГо] Бауэр Ф., Гооз Г. Информатика.- М., 1990. [Белл] Беллман Р. Динамическое программирование. М., 1960. [БВК] Бородич Ю.С., Вальвачев А.Н., Кузьмич А.И. Паскаль для персональных компьютеров.-Минск., 1991. [Бу] Бублик В.В. Методические указания и задания к лабораторным занятиям по курсу "Вычислительные машины и программирование".- Киев, 1986. [Ви77] Вирт Н. Систематическое программирование. Введение.- М., 1977. [Ви85] Вирт Н. Алгоритмы + Структуры данных = Программы.- М., 1985. [Григ] Григорьев В.Л. Микропроцессор i486.- М., 1993. [Грис] Грис Д. Наука программирования.- М., 1984. [Гро] Грогоно П. Программирование на языке Паскаль.- М., 1982. [ГД] Гэри М., Джонсон Д. Вычислительные алгоритмы и труднорешаемые задачи. – М., 1982. [ЙеВи]Йенсен К., Вирт Н. Паскаль. Руководство для пользования.- М., 1993. [КаСа] Касьянов В.Н., Сабельфельд В.К. Сборник заданий по практикуму на ЭВМ.- М., 1986. [Кнут] Кнут Д. Искусство программирования для ЭВМ. Основные алгоритмы.- М., 1976. Т. 1. Получисленные алгоритмы.- М., 1977. Т. 2. Сортировка и поиск.- М., 1978. Т. 3. [М80] Майерс Г. Надежность программного обеспечения.- М., 1980. [М82] Майерс Г. Искусство тестирования программ.-М., 1982. [ПоКр]Поляков Д.Б., Круглов И.Ю. Программирование в среде Турбо Паскаль. Версия 5.5. М., 1992. [Пи] Пильщиков В.Н. Сборник упражнений по языку Паскаль.-М., 1989. [ПрЧС]Проценко В.С., Чаленко П.Й., Ставровський А.Б. Техніка програмування мовою Сі.- К., 1993. [РНД] Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. М., 1980 [Сл] Слэйгл Дж. Искусственный интеллект. М.: Мир, 1973. [СтКо] Ставровський А.Б., Коваль Ю.В. Вступний курс програмування.- К., 1998. [Фар] Фаронов В.В. Турбо Паскаль 7.0. Начальный курс.- М., 1997. [Фор] Форсайт Р. Паскаль для всех.- М., 1987. [BoMo]Boyer R.S., Moore J.S. A fast string searching algorithm.- Comm.ACM, 1977.- № 10 [MorPr]Morris J.H. Jr, Pratt V.R. A linear pattern matching algorithm.- Tech.Rept. 40, Comput. Centre, University of California, Berkeley.- 1970