22. Внешняя сортировка, прямое слияние, естественное слияние.

Принято называть "внешней" сортировкой сортировку последовательных файлов, располагающихся во внешней памяти и слишком больших, чтобы можно было целиком переместить их в основную память и применить один методов внутренней сортировки.

Сортировка состоит из последовательности шагов, в каждом из которых выполняется распределение состояния файла A в файлы B и C, а затем слияние файлов B и C в файл A

Файлы A, B и C будут O(log n) раз прочитаны и столько же раз записаны

Естественное слияние

Серией называется подпоследовательность записей ai, a(i+1), ..., aj такая, что ak <= a(k+1) для всех i <= k < j, ai < a(i-1) и aj > a(j+1).

Сортировка выполняется за несколько шагов, в каждом из которых сначала выполняется распределение файла A по файлам B и C, а потом слияние B и C в файл A. При распределении распознается первая серия записей и переписывается в файл B, вторая - в файл C и т.д. При слиянии первая серия записей файла B сливается с первой серией файла C, вторая серия B со второй серией C и т.д.

­23. Алгоритмы поиска в тексте.Прямой поиск, алгоритм Рабина-Карпа

Линейный поиск – циклическое сравнение всех символов строки с подстрокой

Алгоритм Рабина-Карпа - это алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте, используя хеширование

Каждый символ имеет свой уникальный код от 0 до 255. Суть метода заключается в том, чтобы для подстроки подсчитать некоторую хэш-функцию (например сумму кодов всех символов в строке), затем посчитать ту же самую хэшфункцию для части строки, равной по длине подстроке, и, в случае совпадения хэш-функции, полностью сравнить его

Сложность O(n*m)

­24. Алгоритмы поиска в тексте, алгоритм Боуера-Мура.

Алгоритм Байера-Мура

Поиск подстроки ускоряется благодаря созданию таблиц сдвигов. Сравнение подстроки со строкой начинается с последнего символа подстроки, а затем происходит прыжок, длина которого определяется по таблице сдвигов. Таблица сдвигов строится по подстроке так чтобы перепрыгнуть максимальное количество символов строки и не пропустить вхождение подстроки в строку.

Правила построения таблицы сдвигов:

1) Значение элемента таблицы равно удаленности соответствующего символа от конца шаблона (подстроки).

2) Если символ встречается более одного раза, то применятся значение, соответствующее символу, наиболее близкому к концу шаблона.

3) Если символ в конце шаблона встречается 1 раз, ему соответствует значение, равное длине образа; если более одного раза – значение, соответствующее символу, наиболее близкому к концу образа.

4) Для символов, отсутствующих в образе, применяется значение, равное длине шаблона.

Сложность: O(n+m)

­25. Файловые структуры данных. Классификация файлов. Индексные файлы. Инвертированные списки.

Файл – поименованная область памяти на внешнем носителе. С точки зрения пользователя, файл - линейная последовательность записей, расположенных на внешних носителях.

Прямой доступ к данным.

Для файлов с постоянной длиной записи адрес размещения записи с номером К может быть вычислен по формуле: ВА+ (К- 1) * LZ + 1, где ВА - базовый адрес, LZ - длина записи

На устройствах последовательного доступа могут быть организованы файлы только последовательного доступа. Файлы с переменной длиной записи всегда являются файлами последовательного доступа. Они могут быть организованы двумя способами:

1. Конец записи отличается специальным маркером.

2. В начале каждой записи записывается ее длина (LZ).

Индексные фaйлы можно представить как файлы, состоящие из двух частей. Это не обязательно физическое совмещение этих двух частей в одном файле, в большинстве случаев индексная область образует отдельный индексный файл, а основная область образует файл, для которого создается индекс. В зависимости от организации индексной и основной областей различают 2 типа файлов: с плотным индексом и с неплотным индексом. Файлы с плотным индексом называются также индексно-прямыми файлами, а файлы с неплотным индексом называются также индексно-последовательными файлами.

В индексно-прямых файлах основная область содержит последовательность записей одинаковой длины, расположенных в произвольном порядке, а индексная запись состоит из значения ключа и номера записи. Здесь значение ключа - это значение первичного ключа, а номер записи - это порядковый номер записи в основной области, которая имеет данное значение первичного ключа

Для индексно-последовательных файлов используется принцип внутреннего упорядочения для уменьшения количества хранимых индексов. Структура записи индекса для таких файлов состоит из значения ключа первой записи блока и номера блока с этой записью. В индексной области мы теперь ищем нужный блок по заданному значению первичного ключа. Так как все записи упорядочены, то значение первой записи блока позволяет нам быстро определить, в каком блоке находится искомая запись. Все остальные действия происходят в основной области.

Принцип организации связанных файлов

Связаны два файла, например F1 и F2, где одна запись в файле F1 может быть связана с несколькими записями в файле F2. При этом файл F1 в этом комплексе условно называется "Основным", а файл F2 - "зависимым" или "подчиненным".

Структура основного файла может быть условно представлена в виде трех областей:

• Ключ

• Запись.

• Ссылка-указатель на первую запись в "подчиненном" файле, с которой начинается цепочка записей файла F2, связанных с данной записью файла F1.

В подчиненном файле также к каждой записи добавляется специальный указатель, в нем хранится номер записи, которая является следующей в цепочке записей "подчиненного" файла, связанной с одной записью "основного" файла.

Таким образом, каждая запись "подчиненного файла" делится на две области:

• область указателя;

• область, содержащую собственно запись.

Инвертированный список в общем случае - это двухуровневая индексная структура.

Здесь на первом уровне находится файл или часть файла, в которой упорядочение расположены значения вторичных ключей. Каждая запись с вторичным ключом имеет ссылку на номер первого блока в цепочке блоков, содержащих номера записей с данным значением вторичного ключа.

На втором уровне находится цепочка блоков, содержащих номера записей, содержащих одно и то же значение вторичного ключа. При этом блоки второго уровня упорядочены по значениям вторичного ключа.

И, наконец, на третьем уровне находится собственно основной файл.