Розробка автоматизованого робочого місця науково-технічної бібліотеки університету (стр. 9 из 15)
Префікс-функція, асоційована із зразком P, несе інформацію про те, де в рядку P повторно зустрічаються різні префікси цього рядка. Використання цієї інформації дозволяє уникнути перевірки свідомо неприпустимих зрушень.
Хай простий алгоритм шукає входження підрядка P = ababaca в текст T. Припустимо, що для деякого зрушення s виявилось, що q перших символів зразків збігаються з символами тексту, а в наступному символі є розбіжність, де q = 5). Отже, ми знаємо q символів тексту, від T[s+1] до T[s+q], і з цієї інформації можна укласти, що деякі подальші зрушення будуть свідомо недопустимі.
У загальному випадку префікс-функція повинна відповісти на таке питання:
Хай P[1..q]= T[s + 1..s + q]; яке найменше значення зрушення s` > s, для якого
P[1..k]= T[s` + 1..s` + до](1.1)
де s` + до = s + q.
Число s` - це найменше значення зрушення, більше s, яке не можна відкинути. Щоб знайти s`, нам не потрібно нічого знати про текст T, достатньо знання зразка P і числа q. Саме, T[s` + 1..s` + до] - суфікс рядка Pq. Тому число до у формулі (1.1) - це найбільше число до < q, для якого Pk є суфіксом Pq. Само значення s` обчислюється за формулою s` = s + (q - до).
Префікс-функцией, що асоціюється з рядком P[1..m], називається функція f:{1,2., m} Ќ {0,1., m - 1}, визначена таким чином:
f[q]= max{k:k < q Pk ] Pq}.(1.2)
Іншими словами, f[q] - довжина найбільшого префікса P, що є (власним) суфіксом Pq. Приведемо псевдокод алгоритму Кнута - Моріса - Пратта.
n = length(T)
m = length(P)
q = 0
for i = 1 to n
while q > 0 and P[q+1]< > T[i]
q = pf[q]
if P[q+1]=T[i]
then q = q+1
if q=m
then print «рядок входить із зрушенням» i-m
q = pf(q)
m = length[P]
pi[1]= 0
до = 0
for q = 2 to m
while до > 0 and P[k+1]< > P[q]
до = pi[k]
if P[k+1]=P[q]
then до = k+1
pi[q]= до
return pi
Час виконання префікс - функції пропорційно довжині рядка m і, отже, є O(m). Аналогічно, час виконання операторів процедури пошуку пропорційно довжині підрядка і є O(n). Отже, загальний час виконання приведеного алгоритму є O(m+n), що дає значний виграш в порівнянні з простий процедурою пошуку.
Проаналізувавши два методи пошуку були виявлені як позитивні так і негативні сторони. Для даної роботи необхідний пошукач який працює з невеликим часом і частковим текстом (див. рис. 1.10)
Рисунок 1.10 – Схема роботи програми пошука
1.4.5 Регулярні вирази у VB.NET
Для роботи з регулярними виразами в VB.NET використовується клас Regex, що знаходиться в просторі імен System.Text.RegularExpressions. За допомогою цього класу ви можете проводити наступні дії:
пошук підрядків за шаблоном;
заміна підрядків за шаблоном;
порівняння рядка з шаблоном;
розділення рядка на підрядки з використанням шаблонів.
Для твору дій з регулярними виразами необхідно створити екземпляр класу Regex. Для цього використовується стандартний конструктор New. Він переобтяжений і має дві комбінації параметрів. Ви можете задати тільки шаблон (змінна типу String), який використовуватиметься надалі, або шаблон і параметри об'єкту. Параметри задаються константами з перерахування Regexoptions.
Пошук підрядків, відповідних шаблону проводиться за допомогою переобтяженого методу Matches. Він може приймати 4 комбінації параметрів. Перший параметр - рядок, в якому проводитиметься пошук. Як другий параметр можна встановити позицію, з якою буде початий пошук. Також другим параметром можна вказати шаблон (якщо він не збігається з шаблоном, вказаним в конструкторі при створенні об'єкту). І остання комбінація параметрів - рядок для пошуку, шаблон і параметри пошуку, задані комбінацією констант перерахування Regexoptions.
Метод повертає об'єкт Matchcollection. Це колекція, яка містить об'єкти Match. Отримати об'єкт Match можна за допомогою індексованої властивості Item колекції. Нумерація елементів починається з нуля. Щоб отримати знайдений підрядок, слід використовувати властивість Value об'єкту Macth.
Нижче приведений невеликий приклад пошуку тегів в HTML коді.
Dim regexp As New Regex("<(.*?) >")
Dim html As String
Dim i As Integer
Dim m As Matchcollection
html = "<p>ето <а href='http://vbnet.ru'>пример</a> <b>поїська</b></p>"
m = regexp.Matches(html)
For i = 0 To m.Count – 1
Msgbox(m.Item(i).Value)
Next
Інша часто використовувана дія, вироблювана за допомогою класу Regex, - заміна підрядків з використанням шаблонів. Для заміни використовується метод Replace. Він, як і метод Matches, переобтяжений. Replace може приймати 10 комбінацій параметрів. Метод може приймати комбінації з наступних параметрів:
input - початковий рядок;
replacement - рядок, на який будуть замінені знайдені підрядки;
count - максимальна кількість замін;
startat - позиція в рядку input, з якою проводитиметься заміна;
pattern - замінюваний шаблон;
options - опції. Може приймати константи з перерахування Regexoptions;
evaluator - об'єкт Matchevaluator.
Метод повертає змінну типу String - рядок, в якому були вироблені заміни.
Dim regexp As New System.Text.RegularExpressions.Regex("<(.*?) >")
Dim Inputstring As String
Inputstring = "p>ето <а href='http://vbnet.ru'>пример</a> <b>pfvtys</b></p>"
txttext.Text = regexp.Replace(txttext.Text, "[вирізаний]", Regexoptions.Multiline)
Порівняння рядка з шаблоном - найпростіша операція, яку можна провести за допомогою класу Regex. Порівняння здійснюється методом Ismatch. Він переобтяжений і може приймати такі ж параметри, як і метод Matches. Значення, що повертається, має тип Boolean. Метод повертає True, якщо тестований рядок збігається з шаблоном і False інакше.Нижче приведений приклад порівняння рядка з шаблоном.
Dim regexp As New System.Text.RegularExpressions.RegEx ("[0-9]+")
Dim str As String
str = "1234567890"
Msgbox (regexp.IsMatch(str).ToString)
str = "abc"
Msgbox (regexp.IsMatch(str).ToString)
Розділення рядка використовується рідше за решту операцій. Розділення рядка з використанням регулярних виразів дуже схоже із звичайним розділенням рядка функцією Split. Але якщо в Split як роздільник використовувався рядок, то тут роздільником є регулярний вираз.
Для розділення рядка використовується переобтяжений метод Split класу Regex. Він може приймати такі ж комбінації параметрів, як і методи Matches і Ismatch. Split повертає масив типу String, який містить рядки, отримані з початкового рядка. Масив індексується з нуля.
Допустимо, потрібно розбити рядок по декількох роздільниках (скажімо, "-", "." і ","). Можна використовувати для цього функцію Split, але при цьому буде багато метушні з масивами, код буде сильно захаращений і знизиться швидкодія. А зараз подивимося, як легко ця операція буде проведена з використанням регулярних виразів. Роздільником буде наступний вираз: "[-\.,]". Наступний код розбиває рядок на підрядки з використанням цього шаблону.
Dim regexp As New Regex("[-\.,]")
Dim i As Integer
Dim s() As String
Dim str As String
str = "раз-два,трі.четире,пять"
s = regexp.Split(str)
For i = 0 To s.GetUpperBound(0)
Console.WriteLine(s(i))
Next
За умовчанням Regex компілює регулярні вирази в послідовність внутрішніх байт-кодов регулярних виразів (це високорівневий код). При виконанні регулярних виразів відбувається інтерпретація байт-кода.
Якщо при створенні об'єкту Regex в конструкторі New була встановлена константа Compiled, то Regex буде скомпільований в MSIL (Microsoft intermediate language). Це дозволить JIT-компилятору перетворити вираз в машинний код, що значно підвищує продуктивність.
Проте у виразах, що компілюють, є і погана сторона - їх не можна вивантажити з пам'яті. Регулярні вирази, що компілюють, вивантажуються тільки при завершенні роботи всього застосування. Regex залишається в пам'яті, навіть коли сам об'єкт звільнений і знищений складальником сміття.
Тому, слід задуматися над тим, чи варто встановлювати прапор Compiled. Якщо ви постійно використовуєте декілька регулярних виразів, то краще буде їх скомпілювати.
Регулярні вирази - могутня технологія для роботи з текстом. Розробники Microsoft все-таки вбудували підтримку цієї технології в .NET Framework. Можливо, вони зробили це тому що .NET Framework використовується в Web-застосуваннях (ASP .NET), де регулярні вирази більше всього необхідні.
1.5 Опис програмного забезпечення
1.5.1 Структура програмного забезпечення АРМ
Програмна частина нашого проекту достатньо проста. Проте, вона складається з двох частин:
настільне застосування для редагування бази даних електронної бібліотеки;
WEB - сайт - для здійснення пошуку книг.
Ці дві частини складають собою одне рішення (solution). Склад рішення приведений на рис. 1.11.
Додаток для редагування БД складається з наступних модулів:
frmMain.vb - головна форма MDI - застосування;
frmBook- форма зберігає інформацію про книги;
frmBookSub - форма з кодами всіх тим;
frmClient - форма з інформацією про клієнта;
frmClientStudy - форма з кодами всіх факультетів;
frmClientType - форма з кодами типів клієнтів;
frmAbout.vb - форма Про програму.
Рисунок 1.11 – Структура VB-проекта
WEB - сайт пошуку телефонних номерів складається з наступних модулів:
Default.aspx - стартова сторінка сайту;
BookHome.aspx - сторінка пошуку книг;
BookBibl.aspx - сторінка пошуку книги по бібліотеках.
1.5.2 Опис модулів і класів системи редагування
Mainform.vb - MDI - форма додатку, стартова форма. При її запуску з'являється форма входу в систему. Якщо користувач не ввів правильне ім'я і пароль, головна форма не завантажується.
Форма містить меню і панель інструментів. По командах меню завантажуються дочірні форми, в яких ведеться редагування окремих таблиць бази даних. По натисненню кнопок на панелі інструментів здійснюються команди редагування даних. Методи головної форми приведені на рис. 1.12.
Рисунок 1.12 – Методы головної форми
Методи Mainform включають: