Решение задач на использование алгоритмов обработки данных

Решение задач  на использование алгоритмов обработки  данных.

Приведем общую  схему решения задач по программированию состоит из 6 шагов:

1. Чтение условия задачи. Необходимо внимательно прочитать условие задачи не пропуская ни единой фразы. Как правило именно в условие любой задачи скрыто до 98% решения.
2. Построение математической модели. Необходимо понять в чем заключается задача. Построить ее математическую модель в любой форме.
3. Построение общей схемы решения задачи, т.е. перейти от понимаю того, что необходимо сделать к пониманию того, как это сделать. Т.е. наметить эффективный алгоритм решения задачи и пути его реализации.
4. Стыковка, т.е. уточнение решений принятых на этапе 3, необходимо достаточно медленно и тщательно продумать из каких частей будет состоять программа, какие массивы, структуры и другие типы данных будут выделены.
5. Реализация кодирования нашего алгоритма. Пишется сама программа, одним из трех рассмотренных способов.
6. Отладка и тестирование. Отмечаем, что проблемы могут быть как правило  в мелких ошибках, недочетах., а именно перепутанные имена, переменные, неверные знаки в формулах и т.д. Решение  может быть принципиально неправильным или неэффективным. Размер массива может быть недостаточным или чрезмерным.

Алгоритмы сжатия данных.

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

Энтропийное кодирование- метод кодирования данных, который обеспечивает компактность данных за счет удаления лишней информации. Сжатые сообщения имеют соответственно очень маленькую энтропию. А текст, закодированный с помощью ASC22, потому что при кодирование всех символов используется одно и тоже количество битов-8 и известно, что буквы. Идея заключалась в том, чтобы закодировать только эти буквы четырьмя битами. И при этом текст будет содержать полную информацию и иметь меньшую энтропию. Однако встает задача, как различить при декодировании сколькими битами был закодирован наш очередной символ-4 или 8 битами. Проблема решается с помощью префиксного кодирования. В такой схеме кодирования любое количество видов может быть использовано для конкретного символа. Однако, для того, чтобы иметь возможность восстановить информацию, запрещено, чтобы последовательность битов, кодирующая некоторый символ, была префиксом битовой последовательности, используемой для кодирования другого символа, что позволяет читать бит за битом. И как только встречается обозначение символа, мы его декодируем. Когда мы будем читать слева направо, ты мы убедимся, что префиксное кодирование обеспечить простое кодирование.

Составить фразу  на латинском коде. Исходную до кодирования. Длину сообщения после сжатия и коэффициент сжатия.

Процесс сжатия данных можно разделить на два основных типа: Сжатие без потерь , т.е. в этом случаи раннее закодированная порция данных после их распаковки восстанавливается полностью без внесения изменений. Для каждого типа данных существуют свои оптимальные алгоритмы сжатия. В этом случаи часть данных, содержащихся в массиве отбрасывается. Значит для текстовых, числовых и табличных данных использование подобных методов недопустимо и в основном такие алгоритмы применяются для сжатия аудио, видео данных. Алфавитом кода будем называть множество всех символов входного потока. Наименьшая единица. Кодовым словом будем называть последовательность кодовых символов. Если все слова имеют одинаковую длину, то такой код мы будем называть равномерным или фиксированной длины. Код будет представлять полное множество слов. Токен – это единица данных, записываемая в сжатый поток с помощью некоторого алгоритма сжатия. Токен состоит из нескольких полей фиксированной или переменной длины. Фраза- фрагмент данных, помещенный в словарь для дальнейшего использования при сжатии. Кодирование-процесс сжатия данных. Декодирование-распаковка данных. Отношение сжатия определяется... Коэффициент сжатия является обратной величиной отношению. Существует два основных способа проведения сжатия: статистические методы, присваивающие коды переменной длины. Причем более короткие коды присваиваются символам или группам во входном потоке. Лучшие статические методы применяют кодирование Хапмана; словарное сжатие, т.е. это методы, хранящие фрагменты данных в словаре, т.е. некоторая структура данных и в этом случаи, если строка новых данных, то в выходной поток помещается указатель на этот фрагмент. Идея алгоритма заключается в след: Зная вероятности вхождения символов в исходный текст, можно описать процедуру построения кода переменной длины, состоящих из целого количества битов. Символам с большей вероятностью присваиваются оптимальный префиксный код-код, в котором никакое другое слово не является префиксом другого. Коды имеют переменную длину. Оптимальным кодом будем называть код, имеющий минимальную среднюю длину. Алгоритм Хафмана делится на два этапа: определение вероятности появления символов в тексте, т.е. считываем полностью исходный текст, вычисляем вероятности появление символов в нем и если в нашем тексте задействованы все 256 символов нашей кодовой таблицы, т.е. к=3. Второй этап: нахождение оптимального кода. Т.е. выбираются два символа с мин вероятностью появления и заменяются одним фективным. Коды Хафмана имеют префикс. Алгоритм Хафмана является универсальным и его можно применять для любых типов данных. Единственный недостаток алгоритма- малая эффективность для малых файлов. За счет необходимости сохранения словаря. Этот алгоритм является единственным, который не увеличивает размеры данных в худшем случаи. Кодовое дерево- дерево кодирования Хафмана- это бинарное дерево, у которого листья помечены символами, для которых разрабатывается кодировка. Ребра помечены суммой вероятностей появления всех символов, соответствующих листьям поддерева.

Алгоритм построения дерева:

1. Символы исходного алгоритма образуют список свободных узлов, листьев. Каждый лист имеет вес, который может быть равен либо вероятности, либо частоте вхождения символов в сжимаемый текст. Символы исходного алгоритма образуют список входных узлов. Каждый лист обозначаем весом, который.
2. Выбираем два свободных узла дерева с наименьшими весами.
3. Создается их родитель, вес которого определяется суммой весов
4. Родитель добавляется в список свободных узлов, а двое его детей- удаляются.
5. Одной дуги, исходящей от родителя задаем 1, а другой 0
6. Повторяем шаги, начиная со второго, пока в списке свободных узлов не останется только один, который будем считать корнем дерева.

Алгоритмы хэширования данных.

Хэшированием будем называть преобразование входного массива данных определенного типа и произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называют хэш функция или функция свертки, а результаты называют хэш кодом, хэш таблицей или дайджистом. Хэш таблица- это структура данных, реализующая интерфейс ассоциативного массива. И выполнять три операции: добавлять новую пару, операцию поиска и удаление пары по ключу. Хэш таблица является массивом, формируемым с помощью хэш функций в определенном порядке. Хорошая хэш функция должна удовлетворять след условиям: должна быть простой с точки зрения вычислительной, должна распределять хэш ключи равномерно, не должна отображать связь между. Должна минимизировать количество калезий, т.е. ситуаций, при которой разным ключам, соответствует одна хэш функция и в этом . Первое свойство хорошей хэш функции зависит от характеристик компьютера, второе- от значения данных. Но на практике как правило такое не случается, и приходится создавать функцию, которая бы зависила от всего ключа. Если хэш функция распределяет совокупность ключей равномерно, то хэширование разбивает эффективно множество ключей. Наихудший случай, когда все ключи хэшируются на один индекс. При возникновении кализий необходимо найти новое место для хранения ключей, претендующих на одну и ту же ячейку хэш таблицы, причем если кализии возникают, то их количество необходимо минимизировать, а лучше постараться их вообще. Например, если все ключи элементов заранее известны или очень редко меняются, то для них можно найти некоторую хэш функцию, которая распределит их по ячейкам хэш таблицы без кализии. Хэш таблицы, которые не нуждаются в механизме кализий называют хэш таблицы с прямой адресацией. Хэш таблицы должны соответствовать след свойствам: выполнение операции начинается. Количество хранимых элементов массива, деленное на число возможных значений хэш функций называется коэффициентом заполнения хэш таблицы или load фактор, который является важным фактором и от него зависит среднее время выполнения операции. Операции поиска, вставки и удаления в среднем должны выполняться за время О(1). Однако при такой оценке не учитываются возможные затраты, связанную с увеличением размеров массива и добавлением в хэш таблицу новой пары. Механизм является важной составляющей любой. Хэш таблицы часто применяют в базах данных и особенно в языковых процессорах типа  компиляторов и ассемблеров. В повседневной жизни примером хэширования может служить распределение книг по тематическим заголовкам. Упорядовачивание слов в словарях и т.д. Методы разрешения кализий. Каждая ячейка массива является указателем на связный список(цепочку)пар, ключ-значение, соответствующих одному и тому же значения ключа. Кализия приводят к тому. Операции поиска и удаления данных  требуют просмотра всех элементов цепочки, чтобы найти в ней элемент с заданным ключом. Для добавления новых данных добавляем элемент в начало или конец соответствующего списка и если коэффициент заполнения станет слишком велик, то увеличиваем размер массива и соответственно перестраиваем таблицу, при этом среднее время операции поиска будет составлять O(1+к), где к- коэффициент заполнения нашей таблицы.

Метод открытой адресации.

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

Алгоритмы хэширования

Таблица прямого  доступа

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

Метод остатков от деления

Простейшей хэш функцией является деление по модулю числового значения ключа

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

Функция середины квадрата.

В этом методе значение ключа преобразуется в число, которое затем возводится в квадрат.

Метод свертки.

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

Метод открытого хэширования.

Основная идея заключается в том, что потенциальное  множество, возможно бесконечное, разбивается  на конечное число классов, пронумерованных. Что для любого элемента X функция H(x) принимает значение от 0 до B-1, соответствующая классу, которая принадлежит наш элемент X. Часто классы называют сегментами. Массив называемый таблицей сегментов и проиндексированный номерами от 0 до B-1 содержит заголовки для B списков. Если исходное множество из N элементов, то тогда средняя длина будет составлять n/3. Если можно оценить величину. Тогда время обработки словарей будет. Закрытое хэширование. При закрытом хэширование применяется методика повторного хэширования, т.е. если осуществляется попытка размещения элемента x в сегмент с номером H(x), который уже занят другим элементом, коллизия, и тогда в соответствии с методикой повторного хэширования будем. Пусть h3(x) первый пустой элемент, то тогда невозможно нахождение нашего элемента х в сегментах 4 или 5. Если в нашей хэш таблице запускается удаление элементов, то при подании в пустой сегмент, мы не можем гарантировать, что наш элемент не находится в таблице вообще, т.к. сегмент может оказаться пустым уже после добавления элемента и поэтому для устранения такой ситуации в качестве альтернативы можно ввести дополнительное поле в таблицу, которое показывает состояние элемента. Существует несколько методов повторного хэширования: линейное пробование, квадратичное пробованиие и двоичное. Линейное сводится к последовательному перебору сегменту таблицы с некоторым фиксированным шагом, где i-коллизию, c-константа, определяющая шаг перебора. Квадратичное пробование отличается от линейного тем, что шаг перебора сегментов не линейно зависит . Благодаря нелинейности уменьшается число проб. Однако, даже относительно небольшое число проб может быстро привести к выходу за адресное пространство небольшой таблицы. Двойное хэширование основано на линейной, при которой адрес вычисляется за счет двойной. Для устранения выхода за пределы адресного пространства можно пойти на увеличение размера таблицы по сравнению с диапазоном адресов, выдаваемых хэш функцией. Однако этот метод может привести к нерациональному расходованию памяти. Хэширование будет иметь применение на практике…