8. Файловые системыFat, ntfs

Начальная файловая система – FAT. Максимальное кол-во файлов 32000. Не было backup. Медленный. FAT выполняют поиск файлов по имени файла. Основные элементы:

FAT (FAT Allocation Table) и root directory

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

В отличии от FAT, NTFS для поисков файлов в корневой директории используется B+дерево.

Другим важным достоинством NTFS является backup. Если система накроется, её можно восстановить.

Система NTFS поддерживает журнал транзакций(позволяет восстановить состояние файлов при аварии).

9. B+дерево (кластерное индексирование)

B+ дерево является развитием механизма бинарного дерева.

483585

123456

134672

523801

134672

211625

123456

211625

485600

601110

483585

485600

564673

523801

564673

601110

Самая длинная ветка = log₂N

B+ дерево называется кластерным. Вершина соответствует не одному файлу а группе(кластеру). То есть в каждом узле может находиться группа файлов.

10. Проблема фрагментации диска и её решение.

Благодаря разбиению кластеров на блоки проблема фрагментации является решенной.

Чем меньше разрешение кластера, тем больше кластеров.

Для ускорения доступа применяются буфера ввода-вывода. Буферы ввода-вывода – область оперативной памяти.

Используется режим прямого доступа к памяти. В режиме пр. доступа к памяти процессор отсоединяется от шины. Процессор также исполняет опережающую подкачку. У процессора имеется Кэш-память.

11. Сжатие файлов на диске

В основе сжатия файлов лежит принцип Лемпеля-Зива.

Алгоритм Хофмана.

Есть данные 18 бит

101010010000111000 – исходные данные.

1. Разобьём на триады:

101’010’010’000’111’000’

2. Считаем частоту встречаемости:

101 – 1 010 – 2 000 – 2 111 – 1

3. Располагаем по убыванию:

010 - 2 000 - 2 101 - 1 111 - 1

4. Объединяем последние 2 комбинации в одну:

010 - 2 000 - 2 101 + 111 - 2

000+101+111 – 4 010 -2

5. Выполняем этап маркировки

010 – «1» 000 – «01» 101 – «001» 111 – «000»

6. Получаем сжатую информацию

001 1 1 01 000 01 – 12 бит.

12. Шифрование файлов

Можно рекомендовать следующий способ использования шифра. Человек знает секретное слово(student). Это слово преобразуется в число с помощью функции Хэширования: student-055A27.

Полученное значение хэш функции сохраняется в файл на диск. Система запрашивает у пользователя пароль. Он вводит слова student – это слово преобразуется хэш функцией в число. Считывается значение файла со знанием хэй-функции.

Основной принцип шифрования: получиться шифр-просто, а расшифровать практически не возможно. Алоритм шифрования играет второстепенную роль а решающую роль играет ключ.

В настоящее время ведущим является DES алгоритм. Он использует две основные операции: подстановка и перемешивание.

10010101, Ключ 1101

Подстановка восстановление

1001 0100

1101 1101

0100 1001

DES использует 64 разрядный ключ. В данном алгоритме варьируют размеры блока: 8бит, 16 бит, 32бит.

Алгоритм RSA более сложные.

13. Сжатие графических файлов

Как работает алгоритм JPEG

Прежде всего программа делит изображение на блоки - матрицы размером 8х8 пикселов. Поскольку при использовании метода JPEG время, затрачиваемое на сжатие изображения, пропорционально квадрату числа пикселов в блоке, обработка нескольких блоков меньшего размера делается значительно быстрее, чем обработка всего изображения целиком.

К значениям пикселов применяется формула, названная дискретным косинусоидальным преобразованием (Discrete Cosine Transform - DCT). DCT переводит матрицу значений пикселов 8х8 в матрицу значений амплитуд такой же размерности, соответствующую определенным частотам синусоидальных колебаний. Левый верхний угол матрицы соответствует низким частотам, а правый нижний - высоким.

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

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

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

Декодирование JPEG-изображения начинается с шага обратного кодированию без потерь, в результате чего восстанавливается матрица квантования пикселов.

Значения из матрицы пикселов умножаются на значения из матрицы квантования, чтобы восстановить, насколько это возможно, матрицу, которая была вычислена на шаге применения DCT. На этапе квантования была потеряна некоторая часть информации, поэтому числа в матрице будут близки к первоначальным, но не будет абсолютного совпадения.

Обратная к DCT формула (IDCT) применяется к матрице для восстановления значений пикселов исходного изображения. Еще раз отметим, что полученные цвета не будут полностью соответствовать первоначальным из-за потери информации на шаге квантования. Восстановленное изображение, при сравнении с оригиналом, будет выглядеть несколько размытым и обесцвеченным.

Для сжатия используют YGrGb где Y- яркость, Cr Gb- световые (хроматические числа)

3	2	5	1
4	4	3	6
2	0	5	2
0	1	0	3

D=

M-да преобразования . Дискретный косинусоидальный преобразователь.

1	1	1	1
1	1	-1	-1
1	-1	-1	1
1	-1	1	-1

W =

Ортогональная М-да позволяет 1) сохранить свойства исходного изображения; 2) При обратном преобразовании мы гарантированно получим обратную матрицу.

1. C=1/2*W*D

2. C’=1/2*C