Лекция 19. Цифровой поиск (1107994)
Текст из файла
Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годЛекция 19 Цифровой поиск19.1. Что такое цифровой поиск (поиск подстроки по образцу)?19.1.1. Цифровой поиск – частный случай поиска заданной подстроки (образца) в длиннойстроке (тексте). Поиск подстроки по образцу используется в текстовых редакторах, вИнтернетных поисковиках и т.п. Например, биологи любят искать образцы (заданныецепочки нуклеотидов) в молекулах ДНК.19.1.2.
Примеры цифрового поиска: поиск в словаре, в библиотечном каталоге и т.п., когдаделается поиск по образцу в нескольких текстах (названиях книг, фамилиях авторов,текстах на вызванных сайтах и т.п.). Хороший пример – словарь с высечками, т.е.словарь, в котором обеспечен быстрый доступ к некоторым страницам (например,начальным страницам списков слов, начинающихся на очередную букву алфавита).Иногда используются многоуровневые высечки.Из толкового словаря: «Высечка – отделочный процесс полиграфическогопроизводства для образования с помощью вырубки, высечки на высекательном прессеплощадок на внешнем поле страниц справочных изданий, чтобы можно было быстронаходить начало разделов».Еще один пример – словарь с побуквенными метками для первого и последнего слована каждой страницы (обычно помещаются в верхнем колонтитуле).19.1.3. При цифровом поиске ключи рассматриваются как последовательности символоврассматриваемого алфавита (в частности, цифр или букв).
Развивая идею побуквенныхметок до ее логического завершения, получаем схему поиска. Цифровой поиск –реализация этой идеи. Ожидаемое число сравнений порядка О(logm N), где m - числоразличных букв, используемых в словаре, N – мощность словаря. В худшем случаедерево содержит k, уровней, где k – длина максимального слова.19.2. Пример.Пусть множество используемых букв (алфавит) {A, B, C, D}. Мы добавим к алфавиту ещеодну букву (пробел).
По определении. слова АА, АА , АА, совпадают. Пусть {A, AA,ABB, AC, ADBD, BCA, BCD, CBA} – словарь (множество ключей). Построим m-ичное дерево,где m = 5 = | , A, B, C, D |. Следующая небольшая хитрость позволит иногда сократить поиск:если в словаре есть слово а1а2а3...аk и первые i его букв (i < k) задают уникальное значение:комбинация а1...аi встречается в словаре только один раз, то не нужно строить дерево для j >i, так как слово можно идентифицировать по первым i буквам.На рисунке (внизу) изображено дерево поиска (5-ичное). Прямоугольниками изображенывершины дерева, в овалах – значения слов (ключей) и связанная с ним информация(комментарий к слову или любая другая информация, которую мы будем обрабатывать).
Темсамым любая вершина дерева – массив из m элементов (в данном примере m = 5).Каждый элемент вершины содержит либо ссылку на другую вершину m-ичного дерева, либона содержащий информацию овал (ключ).Рассмотрим корень дерева: как видно из словаря все слова начинаются с А, В или С, причемс C начинается только одно слово – СВА. Поэтому ссылки на узел для слов, начинающихся сА, на узел для слов, начинающихся с В, и на слово CBA (оно единственно).Рассмотрим узел для слов, начинающихся с А: у него пять ссылок на слова A , AA, ABB,AC, ADBD.
Все перечисленные слова уникальны, так что дополнительных узлов не требуется.1(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годРассмотрим узел для слов, начинающихся с B: оба слова начинаются с комбинации ВС. Этоприводит к необходимости завести еще один узел для слов, начинающихся с ВС. Этообстоятельство ухудшает эффективность, так как рассматриваемое дерево содержит многонулевых указателей (7), что вызывает большой перерасход памяти. Можно, конечно,исправить положение, модифицировав поиск.Очень важное обобщение цифрового поиска: таким же образом можно обрабатывать любыеключи, не привязываясь к байту (8 битам), который обычно используется для кодированияAКорень дерева•nullBC•D•nullCBAA•AB••AAABBC•ACD•nullABCnullnullABCnullnull•DnullADBDnull•BCAD•BCDсимволов алфавита.
Мы можем отсекать от ключа первые m бит, использовать 2m-ичноеразветвление, т.е. строить 2m-ичное дерево поиска (когда цифровой поиск проводится надвоичных деревьях, для разветвления берется один бит: m = 1). В реальной жизнирассмотренные методы используются, например, при поиске внутренних имен, которыестроит компилятор. Чтобы сделать оценку по памяти и по эффективности, необходимымашинные эксперименты, чтобы проанализировать, как будет работать метод дляконкретного словаря..Занесение и исключение рассмотреть самостоятельно.19.3. Программа поиска.19.3.1.
Тип union (объединение). Синтаксически это структура, все поля которой наложеныодно на другое. В Паскале этому соответствует вариантная запись. Семантически – этообласть памяти, в которой хранятся данные разных типов: один и тот же набор битовинтерпретируется несколькими (двумя и более) разными способами.19.3.2. Объявление объединения.union тег {тип имя-члена;тип имя-члена;……………………тип имя-члена;2(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год} переменные этого объединения;Пример:union tree_node {struct record *r;struct tree * a[M+1];} u;19.3.3.
Текст программы.#include <stdlib.h>#define M 20 //максимальное число символов в ключе#define N 30 //мощность словаряtypedef char key[M]; //ключ – массив из M символовtypedef enum {ident, node} tag; //struct record { //key k;int value;};struct tree { //tag t;union {struct record *r;struct tree * a[M+1];} u;};int ord (char c){if (c == ' ')return 0;return c - 'A' + 1;}struct record *find (struct tree *p, key k){int i = 0;while (p != NULL) {switch (p->t){case ident:for (i = 0; i < M; i++)if (p->u.r->k[i] != k[i])return NULL;return p->u.r;case node:p = p->u.a[ord(k[i++])];}}3(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годreturn NULL;}19.4. Иногда используют комбинации нескольких методов: цифровой поиск вначале, а затемпереключение на поиск в последовательных таблицах.
Именно так мы и работаем сословарем с высечками: вначале на высечку, а затем либо последовательный поиск, либодихотомический (используя факт упорядоченности слов в словаре, факт отсортированности).Именно так или похожим образом мы и работаем со словарями. Обычно предлагаетсяпользоваться цифровым поиском пока количество различных слов не меньше некоторого k, азатем переключение к последовательным таблицам.19.5. Обобщения: поиск по неполным ключам, поиск по образцу.19.5.1. Формальная постановка задачи поиска по образцу. Даны текст – массив T [N]длины N и образец – массив P[m] длины m ≤ N, где значениями элементов массивов Tи P являются символы некоторого алфавита A.
Говорят, что образец P входит в текстT со сдвигом s (или, что то же самое, с позиции s + 1), если 0 ≤ s ≤ N – m и для всех i =0, 1, …, m – 1 T[s + i] = P [i]. Сдвиг s(T, P) называется допустимым, если P входит в Tсо сдвигом s = s(T, P) и недопустимым в противном случае.Задача поиска подстрок состоит в нахождении множества допустимых сдвиговs(T, P) для заданного текста T и образца P.4(с) Кафедра системного программирования ф-та ВМК МГУ, 2010.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
