🗊Презентация Лекція 1/13. Організація таблиць та індексів впорядкування у вигляді масивів та структур з посиланнями

Нажмите для полного просмотра!
Лекція 1/13. Організація таблиць та індексів впорядкування у вигляді масивів та структур з посиланнями, слайд №1Лекція 1/13. Організація таблиць та індексів впорядкування у вигляді масивів та структур з посиланнями, слайд №2Лекція 1/13. Організація таблиць та індексів впорядкування у вигляді масивів та структур з посиланнями, слайд №3Лекція 1/13. Організація таблиць та індексів впорядкування у вигляді масивів та структур з посиланнями, слайд №4Лекція 1/13. Організація таблиць та індексів впорядкування у вигляді масивів та структур з посиланнями, слайд №5Лекція 1/13. Організація таблиць та індексів впорядкування у вигляді масивів та структур з посиланнями, слайд №6Лекція 1/13. Організація таблиць та індексів впорядкування у вигляді масивів та структур з посиланнями, слайд №7

Вы можете ознакомиться и скачать презентацию на тему Лекція 1/13. Організація таблиць та індексів впорядкування у вигляді масивів та структур з посиланнями. Доклад-сообщение содержит 7 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации


Слайд 1


Лекція 1/13. Організація таблиць та індексів впорядкування у вигляді масивів та структур з посиланнями, слайд №1
Описание слайда:

Слайд 2





Опис прикладу бінарного дерева 
Найпростіша реалізація цього методу базується на впорядкуванні елементів через бінарне дерево, в якому до кожного вузла може бути "підвішено" не більше двох піддерев. Кожний вузол дерева являє собою сформований елемент таблиці, причому кореневий вузол є першим елементом. Перші за порядком вказівники посилаються на елементи з меншим аргументом, а другі – на елементи з більшим аргументом. Припустимо тепер, що до таблиці необхідно записати ім’я “D”. Для нього обирається ліве піддерево, тому що “D” < “G” знаходиться в корені. 
Тепер запишемо ім’я “М”. Тому що “G” < “N”, для збереження “М” обирається праве піддерево вузла, що зберігає ім’я “G”. I, насамкінець, запишемо ім’я “Е”. Тому що “E” < “G”,  йдемо за лівою дугою i потрапляємо на ім’я “D”. Оскільки “D” < ”E”, то обираємо дугу, що веде вправо від “D”.
Принцип побудови бінарного дерева такий, що для дерев з однаковим вмістом можна побудувати багато різних варіантів, які відрізняються коренями та проміжними вершинами. Кращі характеристики мають збалансовані дерева, тобто такі, в яких кількість рівнів зв’язків в ієрархії елементів не відрізняється за будь-якою парою шляхів більш ніж на 1. 
Формальну специфікацію обмежень пошуку в бінарних деревах можна визначити через відношення порядку елементів сусідніх рівнів:
Ai+1,2j-1 < Aij < Ai+1,2j,
де i – номер рівня елементів, j – номер елемента на відповідному рівні.
Описание слайда:
Опис прикладу бінарного дерева Найпростіша реалізація цього методу базується на впорядкуванні елементів через бінарне дерево, в якому до кожного вузла може бути "підвішено" не більше двох піддерев. Кожний вузол дерева являє собою сформований елемент таблиці, причому кореневий вузол є першим елементом. Перші за порядком вказівники посилаються на елементи з меншим аргументом, а другі – на елементи з більшим аргументом. Припустимо тепер, що до таблиці необхідно записати ім’я “D”. Для нього обирається ліве піддерево, тому що “D” < “G” знаходиться в корені. Тепер запишемо ім’я “М”. Тому що “G” < “N”, для збереження “М” обирається праве піддерево вузла, що зберігає ім’я “G”. I, насамкінець, запишемо ім’я “Е”. Тому що “E” < “G”, йдемо за лівою дугою i потрапляємо на ім’я “D”. Оскільки “D” < ”E”, то обираємо дугу, що веде вправо від “D”. Принцип побудови бінарного дерева такий, що для дерев з однаковим вмістом можна побудувати багато різних варіантів, які відрізняються коренями та проміжними вершинами. Кращі характеристики мають збалансовані дерева, тобто такі, в яких кількість рівнів зв’язків в ієрархії елементів не відрізняється за будь-якою парою шляхів більш ніж на 1. Формальну специфікацію обмежень пошуку в бінарних деревах можна визначити через відношення порядку елементів сусідніх рівнів: Ai+1,2j-1 < Aij < Ai+1,2j, де i – номер рівня елементів, j – номер елемента на відповідному рівні.

Слайд 3





Приклад бінарного дерева 
 ┌─────┬─────┬─────┐
 │ “G” │ptr D│ptr M│
 └─────┴──┬──┴──┬──┘
   ┌──<───┘     └──>──────┐
┌──┴──┬─────┬─────┐    ┌──┴──┬─────┬─────┐            
│ “D” │ptr A│ptr E│    │ “M” │null │null │
└─────┴───┬─┴──┬──┘    └─────┴─────┴─────┘            
   ┌───<──┘    └─────>────┐
┌──┴──┬─────┬─────┐    ┌──┴──┬─────┬─────┐
│ “A” │null │ptr B│    │ “E” │null │ptr F│
└─────┴─────┴──┬──┘    └─────┴─────┴──┬──┘
   ┌───<───────┘          ┌────<──────┘
┌──┴──┬─────┬─────┐    ┌──┴──┬─────┬─────┐
│ “B” │null │null │    │ “F” │null │null │
└─────┴─────┴─────┘    └─────┴─────┴─────┘”
Описание слайда:
Приклад бінарного дерева ┌─────┬─────┬─────┐ │ “G” │ptr D│ptr M│ └─────┴──┬──┴──┬──┘ ┌──<───┘ └──>──────┐ ┌──┴──┬─────┬─────┐ ┌──┴──┬─────┬─────┐ │ “D” │ptr A│ptr E│ │ “M” │null │null │ └─────┴───┬─┴──┬──┘ └─────┴─────┴─────┘ ┌───<──┘ └─────>────┐ ┌──┴──┬─────┬─────┐ ┌──┴──┬─────┬─────┐ │ “A” │null │ptr B│ │ “E” │null │ptr F│ └─────┴─────┴──┬──┘ └─────┴─────┴──┬──┘ ┌───<───────┘ ┌────<──────┘ ┌──┴──┬─────┬─────┐ ┌──┴──┬─────┬─────┐ │ “B” │null │null │ │ “F” │null │null │ └─────┴─────┴─────┘ └─────┴─────┴─────┘”

Слайд 4





Опис прикладу B-дерева 
Подальший розвиток методів роботи з деревоподібними структурами призвів до використання більш розгалужених деревоподібних структур, що одержали назву В-дерев. В них зберігаються відношення впорядкування зв’язків вузлів i додаються відношення впорядкування внутрішніх елементів одного вузла, які мають бути узгоджені. Для лексикографічних порівнянь це однакові відношення аргументів попередніх та наступних елементів. Вузли В-дерева зберігають інформацію про декілька впорядкованих елементів. Звичайно кількість елементів у вузлі невелика i лежить в межах 3<n<256.
Як закони впорядкування даних у вузлах В-дерев та між їхніми вузлами можуть використовуватись правила впорядкування за алфавітом та правила впорядкування за хеш-функцiями. На наступному слайді наведено приклад В-дерева, що вміщує, ту ж інформацію, що i бінарне дерево з рис. 13.1, але займає лише два рівні ієрархії. При використанні хеш-функцiй для впорядкування в вузлі дерева доцільні алгоритми заповнення вузлів з гори до низу, а при алфавітному впорядкуванні вузлів - побудова вузлів нових рівнів з низу до гори.
Описание слайда:
Опис прикладу B-дерева Подальший розвиток методів роботи з деревоподібними структурами призвів до використання більш розгалужених деревоподібних структур, що одержали назву В-дерев. В них зберігаються відношення впорядкування зв’язків вузлів i додаються відношення впорядкування внутрішніх елементів одного вузла, які мають бути узгоджені. Для лексикографічних порівнянь це однакові відношення аргументів попередніх та наступних елементів. Вузли В-дерева зберігають інформацію про декілька впорядкованих елементів. Звичайно кількість елементів у вузлі невелика i лежить в межах 3<n<256. Як закони впорядкування даних у вузлах В-дерев та між їхніми вузлами можуть використовуватись правила впорядкування за алфавітом та правила впорядкування за хеш-функцiями. На наступному слайді наведено приклад В-дерева, що вміщує, ту ж інформацію, що i бінарне дерево з рис. 13.1, але займає лише два рівні ієрархії. При використанні хеш-функцiй для впорядкування в вузлі дерева доцільні алгоритми заповнення вузлів з гори до низу, а при алфавітному впорядкуванні вузлів - побудова вузлів нових рівнів з низу до гори.

Слайд 5





Приклад B-дерева 
                  	 		┌───┬─────┬───┬─────┬───┬─────┬───┬─────┐
      │0/0│ptr<D│”D”│ptr>D│”E”│ptr>E│”X”│ptr>X│
      └───┴──┬──┴───┴──┬──┴───┴──┬──┴───┴──┬──┘
  ┌────<─────┘      null         └──>───┐ null
┌─┴─┬─────┬───┬─────┬───┬─────┬─┬────┐  │
│1/0│ptr<A│”A”│ptr>A│”B”│ptr>B│.│null│  │
└───┴──┬──┴───┴──┬──┴───┴──┬──┴─┴────┘  │   
     null      null      null           │
  ┌────────────────<────────────────────┘
┌─┴─┬─────┬───┬─────┬───┬─────┬─┬──
│1/1│ptr<F│”F”│ptr>G│”H”│ptr>H│.│
└───┴──┬──┴───┴──┬──┴───┴──┬──┴─┴─┬
  null      null      null
Описание слайда:
Приклад B-дерева ┌───┬─────┬───┬─────┬───┬─────┬───┬─────┐ │0/0│ptr<D│”D”│ptr>D│”E”│ptr>E│”X”│ptr>X│ └───┴──┬──┴───┴──┬──┴───┴──┬──┴───┴──┬──┘ ┌────<─────┘ null └──>───┐ null ┌─┴─┬─────┬───┬─────┬───┬─────┬─┬────┐ │ │1/0│ptr<A│”A”│ptr>A│”B”│ptr>B│.│null│ │ └───┴──┬──┴───┴──┬──┴───┴──┬──┴─┴────┘ │ null null null │ ┌────────────────<────────────────────┘ ┌─┴─┬─────┬───┬─────┬───┬─────┬─┬── │1/1│ptr<F│”F”│ptr>G│”H”│ptr>H│.│ └───┴──┬──┴───┴──┬──┴───┴──┬──┴─┴─┬ null null null

Слайд 6





ПОБУДОВА ПРОЦЕДУР ВИЗНАЧЕННЯ МІР БЛИЗЬКОСТІ ДЛЯ КЛЮЧОВИХ ПОЛІВ
При пошуку помилково підготовлених слів в текстових редакторах та процесорах часто виникає потреба в визначенні схожості ключів пошуку. Такі дії часто виконуються в текстовому процесорі MS Word. Вони можуть будуватися на підрахунку кількості однакових ne, схожих літер nsi за i-м типом схожості, а також літер, які не мають відповідника в іншому ключі і можуть спиратися на абсолютні і відносні формульні критерії схожості. Схожість літер може визнача-тися залежно від випадку аналізу за схожістю написання літер в різних алфавітах ns1, за близькістю комп’ютерних кодів ns2 та за близькістю розташування на клавіатурі ns3, а також з урахуванням кількості літер ns4, які не мають відповідників в обох ключах.
При створенні програм порівняння за мірою близькості треба побудувати загальний критерій близькості як монотонну функцію f(ns1, ns2, ns3, ns4) в одному напрямку від ns1, ns2 і ns3 та в іншому напрямку від ns4. Крім того, попередньо необхідно організувати підрахунок ns1, ns2, ns3 і ns4, при порівняльному перегляді ключів, які порівнюються. Результат пошуку за таким критерієм може бути неоднозначним, навіть за умови вимоги однозначності ключів. На алгоритм лінійного пошуку це практичного не впливає, а у випадку базового двійкового пошуку доцільно починати пошук навколо найближчого ключа, знайденого за відношенням порядку.
Описание слайда:
ПОБУДОВА ПРОЦЕДУР ВИЗНАЧЕННЯ МІР БЛИЗЬКОСТІ ДЛЯ КЛЮЧОВИХ ПОЛІВ При пошуку помилково підготовлених слів в текстових редакторах та процесорах часто виникає потреба в визначенні схожості ключів пошуку. Такі дії часто виконуються в текстовому процесорі MS Word. Вони можуть будуватися на підрахунку кількості однакових ne, схожих літер nsi за i-м типом схожості, а також літер, які не мають відповідника в іншому ключі і можуть спиратися на абсолютні і відносні формульні критерії схожості. Схожість літер може визнача-тися залежно від випадку аналізу за схожістю написання літер в різних алфавітах ns1, за близькістю комп’ютерних кодів ns2 та за близькістю розташування на клавіатурі ns3, а також з урахуванням кількості літер ns4, які не мають відповідників в обох ключах. При створенні програм порівняння за мірою близькості треба побудувати загальний критерій близькості як монотонну функцію f(ns1, ns2, ns3, ns4) в одному напрямку від ns1, ns2 і ns3 та в іншому напрямку від ns4. Крім того, попередньо необхідно організувати підрахунок ns1, ns2, ns3 і ns4, при порівняльному перегляді ключів, які порівнюються. Результат пошуку за таким критерієм може бути неоднозначним, навіть за умови вимоги однозначності ключів. На алгоритм лінійного пошуку це практичного не впливає, а у випадку базового двійкового пошуку доцільно починати пошук навколо найближчого ключа, знайденого за відношенням порядку.

Слайд 7





Підсумки
Найбільш зручними методами організації роботи з впорядкованими таблицями є побудова таблиць та індексів з деревоподібними структурами. 
Двійкові дерева часто використовуються для побудови індексів в базах даних і системних програмах
Розгалужені B-дерева використовуються для побудови комбінованих індексів в базах даних і системних програмах
Описание слайда:
Підсумки Найбільш зручними методами організації роботи з впорядкованими таблицями є побудова таблиць та індексів з деревоподібними структурами. Двійкові дерева часто використовуються для побудови індексів в базах даних і системних програмах Розгалужені B-дерева використовуються для побудови комбінованих індексів в базах даних і системних програмах



Похожие презентации
Mypresentation.ru
Загрузить презентацию