48862 (588615), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Якщо S[1..r] - рядок довжини r, то його префікс довжини до <= r позначатиметься Sk = S[1..k] (зокрема, S0 = е і Sr = S). У цих позначеннях завдання про знаходження зразка P довжини m в тексті T довжини n полягає в знаходженні всіх таких s з проміжку 0 <= s <= n - m, що P ] Ts+m.

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

Найпростіший алгоритм пошуку зразка P в тексті T послідовно перевіряє рівність P[1..m]= T[s + 1..s + m] для всіх n - m + 1 можливих значень s:

for s = 0 to n - m

if P[1..m]= T[s+1..s+m]

then print «рядок входить із зрушенням» s

Можна сказати, що ми рухаємо зразок уздовж тексту і перевіряємо всі його положення. Відзначимо, що перевірка рівності рядків (P[1..m]= T[s+1..s+m]) є ще одним внутрішнім циклом.

Час роботи приведеної процедури пошуку у гіршому разі є І((n - m + 1)m). Насправді, хай T = an (буква а, повторена n разів), а P = am. Тоді для кожної з n - m + 1 перевірок буде виконано m порівнянь символів, всього (n - m + 1)m, що є І(n2) (при m = n / 2).

Простий алгоритм - не кращий. Неефективність пов'язана з тим, що інформація про текст T, що отримується при перевірці даного зрушення s, ніяк не використовується при перевірці подальших зрушень. Тим часом, така інформація може дуже допомогти. Хай, наприклад, P = aaab і ми з'ясували, що зрушення s = 0 допустимий. Тоді зрушення 1, 2 і 3 свідомо недопустимі, оскільки T[4]= b.

1.4.4 Швидкий алгоритм текстового пошуку

Цей алгоритм, запропонований Кнутом, Морісом і Праттом, працює за час І(n + m). Таке прискорення досягається за рахунок того, що при подальшому пошуку заздалегідь обчислюється спеціальна «префікс-функція» на основі вже відомої інформації.

Префікс-функція, асоційована із зразком 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 = "

ето пример поїська

"

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>ето пример pfvtys

"

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 включають:

• frmMainLoad - обробка завантаження програми;

• LoadSubForm(Of frmtype) - процедура завантаження вказаної дочірньої форми;

• btnAdd_Click - виклик процедури почала додавання даних в активній дочірній формі;

• btnDelete_Click - виклик процедури видалення даних в активній дочірній формі;

• btnEdit_Click - виклик процедури редагування даних;

• btnOk_Click - виклик процедури завершення додавання або редагування даних в активній дочірній формі;

• btnCancel_Click - виклик процедури відміни додавання або редагування даних в активній дочірній формі;

• Головний модуль Mainmodule.vb містить глобальні дані програми, використовувані у всіх модулях дочірніх вікон:

• ConnString - рядок з'єднання з БД;

• frmMain - посилання на головну форму.

Всі модулі дочірніх форм мають однакове призначення - редагування даних відповідних таблиць БД. Тому вони мають однакову структуру і практично однаковий набір елементів.

На рис. 1.13 приведена структура модуля форми Книги (frmbook)

Рисунок 1.13 – Поля, методы и типи форми книг

Змінні рівня модуля: тексти запитів, стан форми.

Змінна стану форми може приймати одне з трьох значень:

-stateView - перегляд;

-stateEdit - редагування;

Характеристики

Список файлов ВКР