- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Способы представления словарей презентация
Содержание
- 1. Способы представления словарей
- 2. Способы представления Линейный упорядоченный список Деревья Хэш-таблицы
- 3. Словарь, базирующийся на линейном списке Потребуются функции
- 4. Представление словарей в виде деревьев Двоичного поиска
- 5. Представление словарей в виде Бора В боре
- 6. Представление словарей в виде Бора Допустим в
- 7. Организация словаря в виде бора кон конь корт кот кран крем крен крест крона крот
- 8. Реализация словаря в виде бора В
- 9. Реализация словаря с помощью хэш-таблицы Словарь представляет
- 10. Реализация словаря с помощью хэш-таблицы Функция расстановки
- 11. Реализация словаря с помощью хэш-таблицы Способы задания
- 12. Реализация словаря с помощью хэш-таблицы Например: Можно
- 13. Реализация словаря с помощью хэш-таблицы Часто используется
- 14. Реализация словаря с помощью хэш-таблицы При использовании
- 15. Разрешение конфликтов хэш-индексов Существует 2 подхода к
- 16. Открытая адресация Если при попытке записи элемента
- 17. Методы зондирования Линейное зондирование: Допустим в таблицу
- 18. Допустим после удаления элемента 0628, необходимо найти - 3658 Получаем таблицу После удаления
- 19. Методы зондирования Квадратичное зондирование : проводится зондирование
- 20. Пример Получаем таблицу
- 21. Методы зондирования Двойное хэширование : последовательность проверяемых
- 22. Двойное хэширование Пример Допустим таблица хэширования содержит
- 23. Перестройка таблицы хэширования Способ 1: каждая ячейка
- 24. Чем отличается хорошая функция хэширования Функция хэширования
- 25. Достоинство хэширования При хэшировании такие операции
- 26. Недостатки хэширования Если в разрабатываемом приложении
- 27. Одновременное применение нескольких структур данных В приложениях
- 28. Одновременное применение нескольких структур данных Например, в
- 29. Одновременное применение нескольких структур данных Проблема: Если
- 30. Одновременное применение нескольких структур данных Удобно предусмотреть
- 31. Одновременное применение нескольких структур данных Операции вставки
- 32. Одновременное применение нескольких структур данных Удаление Удаляем
- 33. Одновременное применение нескольких структур данных Улучшение: В
- 34. Одновременное применение нескольких структур данных В этом
- 35. Одновременное применение нескольких структур данных Еще более
Способы представления Линейный упорядоченный список Деревья Хэш-таблицы
Слайд 3Словарь, базирующийся на линейном списке
Потребуются функции
Вставки элемента
Поиска элемента
Просмотр всех элементов
списка
Недостатки данной реализации:
В случае большого числа слов данное представление приводит к длительному поиску
Слайд 4Представление словарей в виде деревьев
Двоичного поиска
В этом случае потребуются функции вставки
элемента, поиска элемента, обхода дерева
Реализация словарей в виде бинарного дерева даже для текста, содержащего 40-50 слов оказывается более выгодной, чем реализация в виде линейного списка
Реализация словарей в виде бинарного дерева даже для текста, содержащего 40-50 слов оказывается более выгодной, чем реализация в виде линейного списка
Слайд 5Представление словарей в виде Бора
В боре слова хранятся не целиком, а
побуквенно
Данная реализация особенно удобна, если многие слова имеют одинаковые префиксы и отличаются только своими окончаниями
Данная реализация особенно удобна, если многие слова имеют одинаковые префиксы и отличаются только своими окончаниями
Слайд 6Представление словарей в виде Бора
Допустим в словаре необходимо хранить следующие слова:
кон,
конь, корт, кот, кран, крем, крест, крона, крот.
Слайд 8Реализация словаря в виде бора
В реализации бор может быть представлен
в виде списка деревьев, узлы которого состоят из букв
Каждый узел дерева будет содержать:
Info – поле, содержащее очередную букву либо указатель на связанный со словом объект
Son – указатель на список поддеревьев следующего уровня
Brother – указатель на следующий узел в списке узлов одного уровня
Каждый узел дерева будет содержать:
Info – поле, содержащее очередную букву либо указатель на связанный со словом объект
Son – указатель на список поддеревьев следующего уровня
Brother – указатель на следующий узел в списке узлов одного уровня
Слайд 9Реализация словаря с помощью хэш-таблицы
Словарь представляет собой массив слов
Для эффективной организации
вставки и удаления элементов в массив используются функции расстановки или хэширования
Слайд 10Реализация словаря с помощью хэш-таблицы
Функция расстановки получая в качестве параметра слова,
выдает в качестве результата некоторое целое число – индекс в словаре, под которым следует хранить это слово.
В этом случае вместо поиска вычисляется значение функции расстановки
В этом случае вместо поиска вычисляется значение функции расстановки
Слайд 11Реализация словаря с помощью хэш-таблицы
Способы задания функций расстановки:
Необходимо, чтобы данная функция
легко вычислялась и зависела от всех символов слова.
Слайд 12Реализация словаря с помощью хэш-таблицы
Например:
Можно взять сумму кодов всех букв.
Чтобы функция
расстановки зависела от позиции символа в слове к коду каждой буквы можно добавить номер ее позиции
При создании функции расстановки необходимо учитывать, чтобы ее значения были равномерно распределены между на множестве обрабатываемых слов
При создании функции расстановки необходимо учитывать, чтобы ее значения были равномерно распределены между на множестве обрабатываемых слов
Слайд 13Реализация словаря с помощью хэш-таблицы
Часто используется следующая формула:
(P*X+Q)%N
где P и Q
– некоторые простые числа, по порядку близкие к N
X – вычисленная сумма кодов
N – размер массива
Например, при N=1000 F=(557*x+811)%1000
Например, при N=1000 F=(557*x+811)%1000
Слайд 14Реализация словаря с помощью хэш-таблицы
При использовании функций расстановки может оказаться, что
два слова имеют один и тот же индекс.
В этом случае говорят, что происходит конфликт хэш-индексов
Слайд 15Разрешение конфликтов хэш-индексов
Существует 2 подхода к разрешению конфликтов:
Открытая адресация: поиск внутри
таблицы другой свободной ячейки
Перестройка структуры таблицы
Перестройка структуры таблицы
Слайд 16Открытая адресация
Если при попытке записи элемента в ячейку выяснилось, что она
занята, зондируется другая пустая, или открытая ячейка, в которую можно записать новый элемент
Последовательность проверяемых ячеек называется зондируемой последовательностью.
Последовательность проверяемых ячеек называется зондируемой последовательностью.
Слайд 17Методы зондирования
Линейное зондирование:
Допустим в таблицу хэширования необходимо занести значения: 7597, 4567,
0628, 3658
Возьмем функцию H(x)=x mod 101 Для каждого из значений получаем H(x)=22
Возьмем функцию H(x)=x mod 101 Для каждого из значений получаем H(x)=22
Слайд 18Допустим после удаления элемента 0628, необходимо найти - 3658
Получаем таблицу
После удаления
Слайд 19Методы зондирования
Квадратичное зондирование :
проводится зондирование свободных ячеек h(x), h(x)+12, h(x)+22, …
Проблемы:
происходит
вторичная кластеризация:
если два элемента хэшируются в одну и ту же ячейку, проверяется одна и та же последовательность
если два элемента хэшируются в одну и ту же ячейку, проверяется одна и та же последовательность
Слайд 21Методы зондирования
Двойное хэширование :
последовательность проверяемых ячеек зависит от значения
Хэширование начинается с
ячейки h1(x).
Размер шага задается функцией h2(x).
При этом h2(x)≠0, h1(x) ≠ h2(x).
Слайд 22Двойное хэширование Пример
Допустим таблица хэширования содержит 11 элементов.
Определим функции хэширования:
h1(x)=x mod
11
h2(x)=7 – (x mod 7)
Допустим x=58. h1=3, h2=5
Последовательность зондируемых ячеек: 3, 8, 2, 7, 1, 6, 0, 5, 10, 4, 9
Для х=14, последовательность выглядит иначе: 3, 10, 6, 2, 9, 5, 1, 8, 4 (h1=3, h2=7)
Допустим x=58. h1=3, h2=5
Последовательность зондируемых ячеек: 3, 8, 2, 7, 1, 6, 0, 5, 10, 4, 9
Для х=14, последовательность выглядит иначе: 3, 10, 6, 2, 9, 5, 1, 8, 4 (h1=3, h2=7)
Слайд 23Перестройка таблицы хэширования
Способ 1:
каждая ячейка таблицы сама является массивом, содержащий элементы,
которые хэшируются в эту ячейку
Способ 2: Таблица хэширования представляется в виде массива связных списков
Способ 2: Таблица хэширования представляется в виде массива связных списков
Слайд 24Чем отличается хорошая функция хэширования
Функция хэширования должна легко и быстро вычисляться
Функция
хэширования должна равномерно распределять данные по таблице
Слайд 25Достоинство хэширования
При хэшировании такие операции как вставка, удаление, поиск элемента
выполняются наиболее эффективно (даже по сравнению со сбалансированными деревьями)
Слайд 26Недостатки хэширования
Если в разрабатываемом приложении нужно выполнять упорядоченные операции, хэширование
не дает эффективного решения.
Слайд 27Одновременное применение нескольких структур данных
В приложениях бывают необходимы структуры данных, предназначенные
для решения разных задач.
Слайд 28Одновременное применение нескольких структур данных
Например, в приложении рассматривается очередь записей о
клиентах банка.
При этом следует предусмотреть возможность вывода фамилий клиентов в алфавитном порядке
При этом следует предусмотреть возможность вывода фамилий клиентов в алфавитном порядке
Слайд 29Одновременное применение нескольких структур данных
Проблема:
Если реализовать структуру в виде очереди, записи
не будут идти в алфавитном порядке
Если записи хранятся в виде упорядоченного списка, нарушается принцип FIFO
Если записи хранятся в виде упорядоченного списка, нарушается принцип FIFO
Слайд 30Одновременное применение нескольких структур данных
Удобно предусмотреть две независимые структуры данных: очередь
и упорядоченный список
Легко реализуются операции, при которых данные извлекаются: GetFront и Traverse(обход списка)
Легко реализуются операции, при которых данные извлекаются: GetFront и Traverse(обход списка)
Слайд 31Одновременное применение нескольких структур данных
Операции вставки и удаления элемента выполнить труднее:
Вставка
Вставляем
новое значение в конец очереди
Вставляем копию значения в упорядоченный список
Вставляем копию значения в упорядоченный список
Слайд 32Одновременное применение нескольких структур данных
Удаление
Удаляем значение из начала очереди очереди
Удаляем значение
из упорядоченного списка
Слайд 33Одновременное применение нескольких структур данных
Улучшение:
В структуре данных линейный список продолжает хранить
записи о клиентах
Очередь содержит только указатели на соответствующие значения в списке
Очередь содержит только указатели на соответствующие значения в списке
Слайд 34Одновременное применение нескольких структур данных
В этом случае операция удаления элемента будет
реализована очень эффективно, поскольку в удаляемом элементе очереди содержится указатель, который необходимо удалить из списка
Список в этом случае должен быть двусвязным
Список в этом случае должен быть двусвязным
Слайд 35Одновременное применение нескольких структур данных
Еще более эффективной получится схема, которая объединяет
очередь с бинарным деревом: в этом случае операция вставки элемента будет происходить много быстрее
При этом очередь должна по-прежнему содержать указатели на соответствующие узлы дерева.
При этом очередь должна по-прежнему содержать указатели на соответствующие узлы дерева.
