Розробка автоматизованого робочого місця науково-технічної бібліотеки університету
Говоритимемо, що зразок P входить із зрушенням s, або, еквівалентно, входить з позиції s + 1 в текст T, якщо 0 <= s <= n - m і T[s + 1..s + m]= P[1..m] (іншими словами, якщо T[s + j]= P[j] при 1 <= j <= m). Якщо P входить із зрушенням s в текст T, то говорять, що s - допустиме зрушення, інакше s - неприпустиме зрушення. Завдання пошуку підрядків полягає в знаходженні всіх допустимих зрушень для даних тексту T і зразка P.
1.4.2 Обозначення та терміни
Через Ќ* позначається множина всіх кінцевих рядків над алфавітом Ќ, включаючи порожню рядок, що має нульову довжину і е, що позначається. Довжина рядка x позначається |x| . З'єднання, або конкатенація рядків x і у виходить, якщо виписати рядок x, а за нею - рядок у. Конкатенація рядків x і у позначається xy; очевидно |xy| = |x|+|y|.
Говоритимемо, що рядок w - префікс, або початок рядка x, якщо x = wy для деякого у ? Ќ*. Говоритимемо, що рядок w - суфікс, або кінець рядка x, якщо x = yw для деякого у ? Ќ*. Писатимемо w [ x, якщо w - префікс x, і w ] x, якщо w - суфікс x. Наприклад, ab [ abcca і cca ] abcca.
Порожній рядок є префіксом і суфіксом будь-якого рядка; якщо w - префікс або суфікс x, то |w| <= |x|. Для будь-яких рядків x і у і для будь-якого символу а співвідношення x ] у і ха ] уа рівносильні; стосунки ] і [ транзитивні.
Хай x, у і z - рядки, для яких x ] z і x [ z. Тоді x ] у, якщо |x| <= |y|; у ] x, якщо |x| >= |y|, і x = у, якщо |x| = |y|.
Якщо 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 = "<p>ето <а href='vbnet'>пример</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='vbnet'>пример</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 включають:
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 - редагування;
-stateAdd - додавання запису.
При завантаженні форми в список завантажуються назви всіх книг. Змінна стану форми встановлюється в значення Перегляд. При переміщенні курсора за списком в полях форми відображаються всі поля запису. Користувач, натиснувши на кнопку на панелі інструментів головної форми, може виконати одну з відповідних дій:
-видалення запису;
-перехід в режим редагування;
-перехід в режим додавання.
При видаленні запису програма вимагає підтвердження особи: логін і пароль. Якщо логін і пароль введений вірно програма вимагає підтвердження видалення. Якщо користувач підтверджує видалення, виконується SQL - запит видалення вказаного запису в БД, запис також віддаляється із списку і курсор переходить на наступний запис.
При переході в режим редагування змінна стану форми встановлюється в значення Редагування. При переході в режим додавання змінна стану встановлюється в значення Додавання.
Після введення або зміни даних користувач може натиснути на одну з кнопок на панелі інструментів (OK або Відміна) і тим самим занести нові дані в базу даних або відмінити всі зміни на формі. У разі додавання або зміни виконується відповідний SQL - запит (INSERT або UPDATE) і зміни відображаються в списку. У будь-якому випадку курсор повертається на список і стан форми встановлюється в значення Перегляд.
Далі форма чекає подальших дій користувача - натиснення відповідної кнопки на панелі інструментів.
Оброблювані події форми Strform:
-StrForm_Load - завантаження форми. Завантажується список всіх книг, ініціалізувалися змінні;
-Lvw_ItemSelectionChanged - переміщення курсора в списку. У полях форми виводяться значення полів нового поточного запису;
-Lvw_MouseDoubleClick - подвійне клацання на назві книги. Завантажується форма книги із списком.
-Методи форми Strform:
-InitData - заповнення списку книги, ініціалізація змінних форми. Викликається при завантаженні форми;
-FillItem - заповнення полів форми даними з БД. Викликається при завантаженні форми і при переміщенні курсора в списку;
-ClearItem - очищення полів форми для додавання новому запису. Викликається при переході в режим додавання запису;
-BeginAddEdit - переклад форми в режим додавання або редагування. Метод викликається головною MDI - формою при натисненні на кнопки Додати або Редагувати на панелі інструментів, коли дочірня форма книги активна;
-DeleteItem - видалення запису. Метод викликається головною MDI - формою при натисненні на кнопку Видалити на панелі інструментів, коли дочірня форма Вулиці активна;
-CompleteEdit - завершення редагування. Залежно від стану форми виконується метод Updateitem або Additem. Метод викликається головною MDI - формою при натисненні на кнопку OK на панелі інструментів, коли дочірня форма книги активна;
-CancelEdit - відміна редагування. Курсор повертається на список, значення полів форми відновлюються на підставі запиту поточного запису БД. Метод викликається головною MDI - формою при натисненні на кнопку Відміна на панелі інструментів, коли дочірня форма Вулиці активна;
-AddItem - додавання новому запису. Виконується SQL - запит вставки запису (INSERT) із значеннями полів, введеними в полях форми. Додається рядок в списку вулиць, цей рядок стає поточним, форма переходить в режим перегляду;
-UpdateItem - зміна запису. Виконується SQL - запит оновлення запису (UPDATE) із значеннями полів, введеними в полях форми. Змінюється рядок в списку книги, цей рядок стає поточним, форма переходить в режим перегляду;
-EnableItem - переклад форми в режим додавання або редагування;
-ViewList - переклад форми в режим перегляду.
Структура модулів інших дочірніх форм аналогічна структурі описаної вище форми Strform. З форми Історія видачі і повернення книг викликається форма журнал реєстрації даної людини який останній брав книгу.
Робота зі всіма формами здійснюється однаково - командами кнопок головної панелі інструментів і розкриттям позиції списку в новий список. Такий уніфікований підхід дозволяє користувачеві швидко звикнути до програми, а програмістові - мінімізувати кількість помилок і тому швидко розробити програму.
1.5.3 Модулі програми пошуку
Стартова сторінка є ASP - сторінкою, на якій просто розташовано посилання на сторінку пошуку книг по назві.
На сторінці пошуку книги по назві розташовано поле для введення назви книги і кнопку Знайти. Після введення даних і натиснення на кнопку програма аналізує введені дані після чого знайдені дані виводяться на сторінці в списку книги.
Змінні сторінки:
-SqlFullName - текст запиту по повній назві книги.
Оброблювані події сторінки:
-завантаження форми;
-натиснення на кнопку Знайти;
-перезавантаження даних на сторінці.
Методи сторінки:
-Page_Load - обробка завантаження сторінки. Ініціалізація змінних і елементів управління;
-btnRun_Click - обробка натиснення на кнопку Знайти. Аналіз введених даних, формування і виконання запиту;
grvphonehome_databound - перевірка даних, вибраних за запитом. Формування повідомлення «Не знайдене!» у разі порожньої вибірки.
2 ТЕХНОЛОГІЧНИЙ РОЗДІЛ
2.1 Керівництво користувача
2.1.1 Головна форма програми введення та редагування
Головна форма програми електронної бібліотеки Bookapp.exe приведена на рис. 2.1

Рисунок 2.1 - Головна форма програми електронної бібліотеки
Головна форма є MDI - форму з меню.
Перед завантаженням головної форми з'являється форма входу в програму (див. рис. 2.2).
У цій формі користувач повинен ввести своє ім'я і пароль входу в програму. Якщо користувач три рази вводить невірне ім'я або пароль, головна форма програми не завантажується.

Рисунок 2.2 – Форма входу в програму редагування
По командах меню головної форми виконуються наступні дії:
-Видача - завантажується дочірня форма Клієнти, з якої можна вибрати клієнта і всі його дані ;
-Книги - завантажується дочірня форма Книги в якій описана назва книги, автори, дата видання;
-Теми книг - завантажується дочірня форма Теми книг в якій оброблюється тема книг і код цієї теми;
-Клієнти - завантажується дочірня форма Клієнти в яку заносяться всі дані клієнта, Ф.І.О., Адреса, Телефон, Тип, Дата народження, Дата реєстрації, Місце роботи і посада або якщо Студент те Групу Факультет, Курс;
-Факультети - завантажується дочірня форма Факультетів в якій Найменування факультету і його код;
-Тип клієнтів - завантажується дочірня форма Типу клієнтів в якій Найменування клієнтів і код
-Вихід - програма завершує свою роботу;
-Про програму - завантажується стандартний діалог Про програму.
2.1.2 Форма Клієнти
Дочірня форма для перегляду і редагування списку клієнтів приведена на рис. 2.3.

Рисунок 2.3 – Форма для редагування даних про клієнтів
Форма дозволяє додавати нових клієнтів, видаляти із списку,та редагувати.
Для додавання нового клієнта потрібно зробити форму активною (клацнувши на формі Клієнт) і потім натиснути кнопку Додати на панелі інструментів головної форми. При цьому поля форми очищаються і курсор переміщається на полі П.І.Б.
Для редагування даних клієнта потрібно зробити форму активною (клацнувши на формі Клієнт) і потім перейти на те місце яке нам треба змінити і набираємо зміни на панелі інструментів головної форми і підтверджуємо кнопкою змінити. Після цього всі дані зміни збережені.
Для видалення клієнта із списку потрібно зробити форму активною і потім натиснути кнопку Видалити на панелі інструментів головної форми. При цьому програма просить підтвердити видалення.
2.1.3 Форма Книги
Дочірня форма для перегляду і редагування списку книг приведена на рис. 2.4.
Форма дозволяє додавати нові книги, видаляти ті, що існують, із списку, редагувати дані про книги. Виконання цих операцій аналогічно описаному в 2.1.2.

Рисунок 2.4 – Форма для редагування даних про книги
2.1.4 Інші форма програми редагування
Дочірня форма для проглядання тем і їх створення приведена на рис. 2.5.

Рисунок 2.5 – Форма для редагування даних про теми книг
Видаляти існуючі номери не можна, оскільки цей код використовуватиметься постійно з книгами відповідними під цю тему.
Дочірня форма для перегляду і редагуванню клієнта приведена на рис. 2.6.

Рисунок 2.6 – Форма для редагування даних про клієнтів
Форма дозволяє додавати нових клієнтів, видаляти ті, що існують, із списку не можна, вони віддаляються тільки із списку, коли видаляється один з клієнтів.
Дочірня форма для перегляду і створення списку Факультетів приведена на рис. 2.7.

Рисунок 2.7 – Форма для редагування даних про факультети
Форма дозволяє додавати нові підрозділи, видаляти ті, що існують, із списку не можна.
2.1.5 Програма пошука
Стартова сторінка сайта пошуку інформаціїї в бібліотеці приведена на рис. 2.8
На стартовій сторінці розташовані посилання на сторінки пошуку книг різними способами.
.

Рисунок 2.8 – Стартова сторінка сайта пошуку
Сторінка пошуку книг приведена на рис. 2.9.

Рисунок 2.9 – Сторінка пошуку книг за назвою
У поля введення потрібно ввести назву книги (можна тільки початок). Після натиснення на кнопку Знайти виводиться список знайдених книг з авторами і роком видання або виводиться повідомлення «Не знайдено!»
Сторінка пошуку книг по бібліотеках приведена на рис. 2.10.
У поля введення потрібно ввести назву книги (можна тільки початок. Після натиснення на кнопку Знайти виводиться список знайдених книг в бібліотеках або виводиться повідомлення «Не знайдено!»