Б-дерева

Для великих сховищ даних, якими є, наприклад, СУБД, використання бінарних дерев пошуку не є доцільним. У таких випадках використовуються так звані Б-дерева, які відрізняються від бінарних тим, що у кожному вузлі можуть зберігати по декілька ключів.

Рисунок 7.22 - Б-дерево з 3 ключами на вузол

Варіація Б-дерева – Б+-дерево, у якому дані зберігаються лише в листі:

Рисунок 7.23 – Б+-дерево

Лекція 8. Алгоритми обробки текстових даних на основі регулярних виразів

Перелік питань:

1. Введення до теорії кінцевих автоматів.

2. Графічне представлення кінцевих автоматів.

3. Використання кінцевого автомату: синтаксичний аналіз.

4. Реалізація синтаксичного аналізу файлу з розділяючими комами.

5. Детерміновані та недетерміновані кінцеві автомати.

6. Регулярні вирази.

7. Форма Бекуса-Наура для запису регулярних виразів.

8. Синтаксичний аналіз регулярних виразів.

9. Компіляція регулярних виразів.

10. Інструменти для спрощення роботи з регулярними виразами.

11. Зіставлення рядків з регулярними виразами.

12. Використання регулярних виразів для автоматизації типових задач.

8.1. Введення до теорії кінцевих автоматів

Кінцевий автомат – математична абстракція, яка дозволяє описувати шляхи зміни стану об’єкту в залежності від його поточного стану та вхідних даних, за умови, що кількість станів є кінцевою.

Приклад задання кінцевого автомату:

M = (Q, Σ, δ, q0, F),

де Q – кінцева множина станів автомату;

q0- початковий стан автомату;

F – множина заключних чи допускаючих станів, таких, що F входить в Q;

Σ – допустимий вхідний алфавіт (кінцева множина допустимих символів), із якого формуються рядки, що зчитуються автоматом;

δ – функція переходів автомату: δ: Q × Σ  P (Q)

8.2. Графічне представлення кінцевих автоматів

Графічно автомат представляється за допомогою графа. Вузли графа представляють стани автомата (на рисунку їх 5).

Рисунок 8.1 – Графічне представлення кінцевого автомату

Допускаючий стан (другий) помічений подвійною межею кола. Стрілки (ребра графа) зображають таблицю правил переходу. Стрілка, для якої не задано стан, звідки вона спрямована, відображає початковий стан.

8.3. Використання кінцевого автомату: синтаксичний аналіз.

Приклад кінцевого автомату для синтаксичного аналізу адреси електронної пошти

Рисунок 8.2 - Кінцевий автомат для синтаксичного аналізу адреси електронної пошти

Реалізація кінцевого автомату, який перевіряє адресу:

8.4. Реалізація синтаксичного аналізу файлу з розділяючими комами

Задача синтаксичного аналізу файлу з деякими розділяючими знаками, наприклад, комами (CSV) – типова задача, яка для свого вирішення вимагає використання кінцевих автоматів.

Допустимо, ми маємо файл, рядки якого наведені у наступному вигляді:

Julian, Bucknall,,43, “Author, and Columnist”

Наведений рядок містить п’ять полів:

Julian

Bucknall

<Без значення>

Author, and Columnist

Графічне зображення кінцевого автомату для синтаксичного аналізу файлу з розділяючими комами (рис 8.3).

Рисунок 8.3 - Графічне зображення кінцевого автомату для синтаксичного аналізу файлу з розділяючими комами

8.5. Детерміновані та недетерміновані кінцеві автомати

Детермінований кінцевий автомат аналогічно ДМТ може безальтернативно переходити з одного стану лише у один наступний стан.

В той час, недетерміновайни кінцевий автомат, як і НМТ може переходити у декілька станів, створюючи стільки копій автомату, до скількох додаткових станів необхідно перейти.

Приклад недетермінованого кінцевого автомату:

8.6. Регулярні вирази

Визначення:

Регулярними виразами над алфавітом Σ є будь-які елементи алфавіту Σ, а також пустий рядок ε: a, де а – будь-який елемент алфавіту Σ.

Крім того, регулярними виразами будуть і результати операцій з регулярними виразами над Σ.

Приклад:

Σ = {a, b, c}. Будь-який елемент алфавіту буде регулярним виразом над ним. Оскільки a і b – регулярні вирази над Σ, то із них можна побудувати більш складні вирази: ab, ba, acb і т.д.

Регулярному виразу виду (а U b) відповідають усі рядки, які задаються регулярним виразом a, а також всі рядки, які задаються регулярним виразом b. (a, ab, aab, bab, bbb ….)

Регулярному виразу виду (ab) відповідає мова, яка складається із рядків вигліду xy, де x – деякий рядок із мови L(a), а y – рядок із мови L(b). Тобто в мову L((ab)) входять всі рядки, які можна отримати завдяки дописування в кінець деякого рядку із мови L(a) рядку із мови L(b) – тобто виконання операції конкатенації. У такому разі це будуть рядки: abaab, abbb, abbbb, aaabbbb і т.д.

8.7. Форма Бекуса-Наура для запису регулярних виразів

Форма Бекуса-Наура (БНФ) – формальна система для опису синтаксису.

Часто використовується для запису регулярних виразів. Приклад:

8.8. Синтаксичний аналіз регулярних виразів

Використання регулярних виразів здійснюється у три етапи: синтаксичний аналіз; компіляція; використання для перевірки відповідності рядкам вхідних даних.

Синтаксичний аналіз – процес перевірки відповідності наведеного синтаксису граматичним правилам.

Процес синтаксичного аналізу також має назву “парсинг” (parsing). Для синтаксичного аналізу регулярних виразів, як правило, будується нисхідний синтаксичний аналізатор (top down parser).

8.9. Компіляція регулярних виразів

Компіляція регулярного виразу – перетворення його на недетермінований кінцевий автомат.

Приклад компіляці для виразу “(a|b)*bc” (повторення нуль чи більше раз символу а чи b, за якими йдуть символи b та c).

Дата добавления: 2014-01-04