ГБОУ СОШ № 000 с углубленным изучением экологии
Создание алгоритма сжатия двоичного кода
Исследовательская работа
Авторы:
Толмачева Мария, Шмелева Тамара,
учащиеся 11б класса
Руководитель: ,
учитель информатики и ИКТ
Москва – 2012
Оглавление
Введение | 3 |
Глава 1. Кодирование текста. | 5 |
1.1. Способы кодирования текста | 6 |
2. Методы исследования и их описание | 10 |
2.1. Анализ результатов исследования | 12 |
2.1.1. Сжатие двоичных кодов | 12 |
Заключение | 15 |
Список источников информации | 17 |
Приложение 1 | 18 |
Приложение 2 | 19 |
Приложение 3 | 20 |
Введение
Данная работа посвящена интересной и познавательной теме: «Создание алгоритма сжатия двоичного кода». В работе часто употребляются следующие термины:
Модель – это искусственный объект, который отражает существенные особенности изучаемого объекта, явления, процесса.
Моделирование – метод познания, заключающийся в построении моделей для исследования и изучения объектов, процессов и явлений.
Цель проекта: разработать алгоритм кодирования текстовой информации.
Для реализации поставленной цели, нами были выдвинуты следующие задачи:
Изучение литературы и различных источников на данную тему. Изучение процессов обработки и кодирования текста. Проведение анкетирования учащихся. Проведение экспериментов по определению частоты встречаемости символов алфавита русских букв. Создание алгоритма сжатия двоичных кодов текстовой информации.В исследовании были использованы следующие методы и методики:
Эмпирические методы:
- Эксперименты по определению частоты встречаемости символов алфавита русских букв. Эксперимент по сжатию двоичного кода.
Теоретические методы:
- Анализ и синтез полученных данных в процессе изучении источников информации. Сравнение данных, полученных при изучении источников информации. Обобщение полученных данных в ходе проделанной работы. Метод мысленного моделирования.
Работа над проектом была проведена в четыре этапа. На первом этапе, для получения представления о предмете исследования, необходимо было изучить материал по тематике исследования в различных источниках информации.
На втором этапе над работой была проведена систематизация информации о кодировании текстовой информации.
Третий этап был посвящен проведению экспериментов по определению частоты встречаемости символов русского алфавита и сжатию двоичного кода, а также составлению алгоритма сжатия двоичного кода.
На заключительном этапе работы была создана компьютерная презентация проекта в среде Power Point для защитной речи.
Практическим результатом работы явилось создание алгоритма сжатия двоичного сигнала.
Глава 1. Кодирование текста
Кодирование – это представление информации в виде комбинации символов. Кодирование производится по определенным правилам. Правила кодирования зависят от назначения кода, т. е. от того, как и для чего он будет использоваться. Письменность - это способ кодирования речи на естественном языке. Письменный текст (письменная речь) предназначен для передачи информации от одного человека к другим людям как в пространстве (письмо, записка), так и во времени (книги, дневники, архивы документов и пр.). Правила, по которым люди осуществляют письменное кодирование информации, называются грамматикой языка (русского, английского, немецкого и др.), а человека, умеющего читать и писать, называют грамотным человеком. Если запись речи называть кодированием, то чтение письменного текста – это его декодирование.
С изобретением технических средств связи появилась возможность быстрой передачи текстов на большие расстояния. Но этот процесс требует использования дополнительного уровня кодирования. Любой способ кодирования зависит от назначения кода.
Рис. 1. Процесс передачи телеграфного сообщения с использованием азбуки Морзе.
Способы кодирования текста
Кодирование текста всегда происходит по следующему правилу: каждый символ алфавита исходного текста заменяется на комбинацию символов алфавита кодирования. В таблице азбуки Морзе для кодирования 32 букв русского алфавита (буква Ё стала использоваться в письменном тексте только в середине XX века) применяются два символа: точка и тире. Однако при передаче слов из-за неравномерности кодов различных букв приходится применять еще пропуск между буквами: пауза во времени передачи или пробел на телеграфной ленте. Поэтому фактически алфавит телеграфного кода Морзе содержит три символа: точка, тире, пропуск.
А | А | ._ | L | Л | ._.. | С | Ц | _._. |
В | Б | _... | М | М | _ _ | Ч | _ _ _ . | |
W | В | ._ _ | N | Н | _. | Ш | _ _ _ _ | |
G | Г | _ _. | О | О | _ _ _ | Q | Щ | _ _._ |
D | Д | _.. | Р | П | ._ _. | Ъ | ._ _._. | |
Е | Е | . | R | Р | ._. | Ы | _._ _ | |
V | Ж | …_ | S | С | … | Х | Ь | _.._ |
Z | З | _ _.. | Т | Т | _ | Э | .._.. | |
I | И | .. | U | У | .._ | Ю | .._ _ | |
J | Й | ._ _ _ | F | Ф | .._. | Я | ._._ | |
К | К | _._ | Н | Х | …. |
Рис. 2. Кодовая таблица азбуки Морзе.
Телеграфный код Бодо является двоичным равномерным пятиразрядным кодом. На его основе в 1932 году был разработан международный телеграфный код ITA2, кодовая таблица которого представлена на рис. 2. Двоичные коды символов свернуты в формат двузначных шестнадцатиричных чисел, в которых первая цифра принимает значения 0 или 1. Есть три типа символов: буквы (letters), цифры и знаки (figures), управляющие символы (control chars). Переключение в режим ввода букв происходит по коду 1F16 (двоичная форма 11111).
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | |||||||
NUL | E | 3 | LF | A | - | SP | S | ` | I | 8 | U | 7 | ||
08 | 09 | 0A | 0B | 0C | 0D | 0E | 0F | |||||||
CR | D | ENQ | R | 4 | J | BEL | N | , | F | ! | C | : | K | ( |
10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | |||||||
T | 5 | Z | + | L | ) | W | 2 | H | Y | 6 | P | 0 | Q | 1 |
18 | 19 | 1A | 1B | 1C | 1D | 1E | 1F | |||||||
0 | 9 | B | ? | G | FIGS | M | . | X | / | V | ; | LTRS | ||
Letters | Figures | Control Chars |
Рис. 3. Телеграфный код ITA2.
Буква А имеет код 0316 (00011). Во второй половине XX века создаются и распространяются компьютеры. Для компьютерной обработки текстов потребовалось создать стандарт кодирования символов. В 1963 году был принят стандарт, который получил название ASCII – Американский стандартный код для информационного обмена. ASCII – семиразрядный код, он приведен в таблице 1. Код символа – это его порядковый номер в кодовой таблице. Он может быть представлен в десятичной системе, двоичной и шестнадцатеричной системах счисления. Код в памяти компьютера – семиразрядное двоичное число. Первые 32 символа (от 00 до 1F) называются управляющими. Они не отражаются какими-либо знаками на экране монитора или при печати, но определяют некоторые действия при выводе текста. Символы, имеющие графическое отображение, начинаются с кода 2016. Это пробел - пропуск позиции при выводе. Важным свойством таблицы ASCII является соблюдение алфавитной последовательности кодировки прописных и строчных букв, а также десятичных цифр. Это свойство чрезвычайно важно для программной обработки символьной информации, в частности, для алфавитной сортировки слов.
Расширение кода ASCII
Восьмиразрядная двоичная кодировка позволяет кодировать алфавит из 28=256 символов. Первая половина восьмиразрядного кода совпадает с ASCII. Вторая половина состоит из символов с кодами от 128=8016=100000002 до 255=FF16=111111112. Эта часть таблицы кодировки называется кодовой страницей. На кодовой странице размещают нелатинские алфавиты, символы псевдографики и некоторые другие знаки, не входящие в первую половину.
16-разрядный стандарт UNICODE.
В 1991 году был разработан шестнадцатеричный международный стандарт символьного кодирования Unicode, который позволяет закодировать 216=65536 символов. В такую кодовую таблицу помещаются английский (латиница), русский (кириллица), греческий алфавиты, китайские иероглифы, математические символы и многое другое. Отпадает потребность в кодовых страницах. Диапазон кодов символов в шестнадцатеричной форме: от 0000 до FFFF. В начале кодовой таблицы, в области от 000016 до 007F16, содержатся символы ASCII. Под символы кириллицы выделены области знаков с кодами от 040016 до 052F16, от 2DE016 до 2DFF16, от А64016 до А69F16.
Выводы
Таким образом, кодирование – это представление информации в виде комбинации символов. Для кодирования текста в настоящее время используют кодовые таблицы ASCII и Unicod.
Восьмиразрядная двоичная кодировка позволяет кодировать алфавит из 28=256 символов. Первая половина восьмиразрядного кода совпадает с ASCII. Вторая половина состоит из символов с кодами от 128=8016=100000002 до 255=FF16=111111112.
Unicode позволяет закодировать 216=65536 символов. В такую кодовую таблицу помещаются английский (латиница), русский (кириллица), греческий алфавиты, китайские иероглифы, математические символы и многое другое. Отпадает потребность в кодовых страницах. Диапазон кодов символов в шестнадцатеричной форме: от 0000 до FFFF. В начале кодовой таблицы, в области от 000016 до 007F16, содержатся символы ASCII. Под символы кириллицы выделены области знаков с кодами от 040016 до 052F16, от 2DE016 до 2DFF16, от А64016 до А69F16.
Методы исследования и их описание
Данное исследование посвящено созданию алгоритма сжатия двоичного кода. В исследовании были поставлены следующие задачи:
- создать кодовую таблицу; создать алгоритм сжатия двоичных кодов.
База исследования: учащиеся средних и старших классов, а также педагоги ГБОУ СОШ № 000 с углубленным изучением экологии.
Анкетирование – ответы на вопросы, поставленные в форме опросного листа – анкеты. Использование разработанной анкеты.
Компьютерный (численный) эксперимент - это эксперимент над математической моделью объекта исследования на ЭВМ, который состоит в том что, по одним параметрам модели вычисляются другие ее параметры и на этой основе делаются выводы о свойствах объекта, описываемого математической моделью.
Кодовая страница (англ. code page) — таблица, сопоставляющая каждому значению байта некоторый символ.
Последовательность действий:
анкетирование учащихся 7-11 классов и педагогов ГБОУ СОШ № 000 с углубленным изучением экологии; обработка данных, полученных в ходе анкетирования; обработка данных, полученных во время проведения экспериментов; создание кодовой таблицы; создание алгоритма сжатия двоичного кода; написание выводов.Первичная обработка, анализ и представление результатов исследования:
внесение полученных результатов исследования в соответствующие формы записей; схематичное, графическое, иллюстративное представление результатов; написание выводов.Анализ результатов исследования
Сжатие двоичного кода
Любая информация в компьютере представляется в форме двоичного кода. Чем больше объем этого кода, тем больше места в памяти он занимает, тем больше времени требуется для его передачи по каналам связи. Все это сказывается на производительности компьютера. Сокращение объема данных происходит путем сжатия двоичного кода. Возможны две ситуации при сжатии: 1) потеря информации в результате сжатия недопустима; 2) допустима частичная потеря информации при сжатии. Второй пункт касается графики, видео и звука. Мы исследовали упаковку без потери информации. Идея заключается в выявлении повторяющихся фрагментов кода. Дело в том, что частота встречаемости разных букв (знаков) в тексте разная. Исходим из того, что информационный вес символов тем больше, чем меньше его частота встречаемости. С этим обстоятельством мы и связали идею сжатия текста в компьютерной памяти: отказаться от кодирования всех символов кодами одинаковой длины. Символы с меньшим информационным весом, т. е. часто встречающиеся, кодировать более коротким кодом по сравнению с реже встречающимися символами. Мы считаем, что при таком подходе можно существенно сократить объем общего кода текста и, соответственно места, занимаемого им в памяти компьютера.
Эксперимент № 1. 25 учащимся ГБОУ СОШ № 000 с углубленным изучением экологии было предложено взять в библиотеке свою любимую книгу и любой журнал. Подсчитать, сколько букв расположено в одной полной строке (обычно 40-50). Отсчитать такое количество строк, чтобы в них содержалось примерно 1000 букв (20-25 строк).
В выделенном фрагменте как можно более точно пересчитать сначала все буквы "а", затем "б", "в" и так далее по алфавиту. Полученные результаты были занесены в таблицу. В этой таблице русские буквы расположены в порядке убывания частоты повторяемости текста. Разделим условно на 3 части. Наиболее часто используемые символы: О, Е, А, И и т. д. (на 1 тысячу символов от 90 до 40 повторений), среднее количество раз встречаются символы: В, Л, К, и т. д. (на 1 тысячу символов от 38 до 10 повторений). Самые непопулярные буквы: Х, Ж, Ш, Ц, Щ, Ф (на 1 тысячу символов от 9 до 2 повторений). Самым часто используемым в текстах буквам присвоили трехзначные коды; буквам, которые встречаются в текстах среднее количество раз, присвоили четырехзначные коды; буквам, встречающимся редко, присвоили пятизначные коды. Чем больше размер текста, закодированного таким кодом, тем меньше его информационный объем по сравнению с объемом при использовании однобайтовой кодировки.
Эксперимент № 2. Используя полученную кодовую таблицу, закодировать текст «НАУЧНОПРАКТИЧЕСКАЯКОНФЕРЕНЦИЯ»:
101 010 0111 00101 101 000 0110 111 010 0011 100 011 00101 001
110 0011 010 0011 000 101 01000 001 111 001 101 00101 011 1000.
После размещения в памяти побайтно он примет вид:
10101001 11001011 01000011 01110100 01110001 10010100 11100011
01000110 00101010 00001111 00110100 10101110 00.
Таким образом, текст занимает в кодировке ASCII 29 байт. Используя новую кодовую таблицу, этот же текст займет всего 13 байт, т. е. почти в два раза меньше.
По такому же алгоритму можно составить таблицу и для латинских букв, и для специальных символов. А можно воспользоваться уже готовой таблицей Хаффмана, она была составлена еще в 1953 году.
Выводы
В ходе выполнения проекта было проведено 2 эксперимента. Эксперимент № 1 был посвящен определению частоты встречаемости символов русского алфавита в художественной, в учебной и в научно-популярной литературе. В результате выполнения эксперимента № 1 стало ясно, чаще всего и в художественной, и в учебной, и в научно-популярной литературе встречаются буквы О, Е, А, И. Самыми «непопулярными» символами оказались Ю, Ы, З, Ъ. часто используемым в текстах буквам присвоили трехзначные коды; буквам, которые встречаются в текстах среднее количество раз, присвоили четырехзначные коды; буквам, встречающимся редко, присвоили пятизначные коды. Чем больше размер текста, закодированного таким кодом, тем меньше его информационный объем по сравнению с объемом при использовании однобайтовой кодировки.
Эксперимент № 2 был посвящен кодированию текста «НАУЧНОПРАКТИЧЕСКАЯКОНФЕРЕНЦИЯ» по предложенному алгоритму сжатия двоичного кода. После его выполнения стало ясно, что текст занимает в кодировке ASCII 29 байт. Используя новую кодовую таблицу, этот же текст займет всего 13 байт, т. е. почти в два раза меньший объем.
Таким образом, текст, закодированный с использованием предлагаемой кодовой таблицы, занимает в два раза меньший объем памяти.
Заключение
Проект посвящен созданию новой кодовой таблицы, позволяющей сжимать двоичные коды сохраняемого в памяти компьютер текста.
Для кодирования текста в настоящее время используют кодовые таблицы ASCII и Unicod.
В ходе выполнения проекта были выполнены 2 эксперимента. Эксперимент № 1 был посвящен определению частоты встречаемости символов русского алфавита в художественной, в учебной и в научно-популярной литературе.
В результате выполнения эксперимента № 1 стало ясно, чаще всего и в художественной, и в учебной, и в научно-популярной литературе встречаются буквы О, Е, А, И. Самыми «непопулярными» символами оказались Ю, Ы, З, Ъ. часто используемым в текстах буквам присвоили трехзначные коды; буквам, которые встречаются в текстах среднее количество раз, присвоили четырехзначные коды; буквам, встречающимся редко, присвоили пятизначные коды. Чем больше размер текста, закодированного таким кодом, тем меньше его информационный объем по сравнению с объемом при использовании однобайтовой кодировки.
Эксперимент № 2 был посвящен кодированию текста «НАУЧНОПРАКТИЧЕСКАЯКОНФЕРЕНЦИЯ» по предложенному алгоритму сжатия двоичного кода. После его выполнения стало ясно, что текст занимает в кодировке ASCII 29 байт. Используя новую кодовую таблицу, этот же текст займет всего 13 байт, т. е. почти в два раза меньший объем.
Таким образом, была создана кодовая таблица, позволяющая существенно сократить объем общего кода текста и, соответственно, места, занимаемого им в памяти компьютера.
Все поставленные задачи проекта решены, цели выполнены. Гипотеза подтвердилась.
Список источников информации
Бурсиан 100 задач для решения на компьютере: Учебное пособие. - СПб.: ИД "МиМ", 2009. - 256 с. омпьютерное моделирование в физике: В 2-х частях. Часть первая.- М.: Мир, 1990.- 400 с. изуальное моделирование в среде MATLAB: учебный курс - СПб.: Питер, 2008. - 432 c. , Сагдеев в нелинейную физику: От маятника до турбулентности и хаоса.- М.: Наука, 2008.- 368 с. Зельдович математика для начинающих и ее приложения к физике. - М.: Наука, 1963. - 560 с. , Мышкис прикладной математики. - М.: Наука, 2006. - 615 с. , Михайлов в синергетику: Учеб. руководство.- М.: Наука, 2007.- 272 с. Санин и хаос. - Проблемы физики.- Л.: Знание, 1985.- 32 с. , , Хеннер : Учеб. послобие для студ. пед. вузов / Под ред. .- М.: Изд. центр "Академия", 2001. - 816 с. , Самарский математической физики. - М.: Наука, 2009. - 724 с. Сайт «Компьютерное моделирование»: www. pcmodel. narod. ru. Сайт «Основы компьютерного моделирования»: www. ggpi. org. Сайт «Цифровой звук»: www. audasity. ru.Приложение 1
Расположение букв русского алфавита по частоте использования
О | 90 | 000 |
Е, Ё | 72 | 001 |
А | 62 | 010 |
И | 62 | 011 |
Т | 53 | 100 |
Н | 53 | 101 |
С | 45 | 110 |
Р | 40 | 111 |
В | 38 | 0001 |
Л | 35 | 0010 |
К | 28 | 0011 |
Д | 25 | 0100 |
М | 26 | 0101 |
П | 23 | 0110 |
У | 21 | 0111 |
Я | 18 | 1000 |
Ю | 16 | 1001 |
Ы | 16 | 1010 |
З | 16 | 1011 |
Ь, Ъ | 14 | 1100 |
Б | 14 | 1101 |
Г | 13 | 1110 |
Й | 10 | 1111 |
Х | 9 | 00001 |
Ж | 7 | 00010 |
Ш | 6 | 00011 |
Ц | 4 | 00100 |
Ч | 4 | 00101 |
Щ | 3 | 00110 |
Э | 3 | 00111 |
Ф | 2 | 01000 |
Приложение 2
Таблица Хаффмана
E | 92 |
T | 76 |
A | 74 |
O | 68 |
N | 51 |
R | 48 |
I | 48 |
S | 39 |
H | 38 |
D | 23 |
L | 22 |
F | 19 |
C | 18 |
M | 16 |
U | 15 |
G | 14 |
Y | 14 |
P | 13 |
W | 12 |
B | 10 |
V | 9 |
K | 5 |
X | 4 |
J | 4 |
Q | 3 |
Z | 2 |
Приложение 3
Анкета для учащихся и педагогов ГОУ СОШ № 000
Наша анкета предназначена для изучения мнения учащихся и педагогов ГОУ СОШ № 000 о необходимости создания компьютерных моделей физических процессов и явлений. Мы просим Вас ответить на все вопросы анкеты, следуя инструкции и вопросам. Пожалуйста, внимательно прочитайте вопрос и отметьте правильный ответ. Если ответы на вопрос не предлагаются, то необходимо на выделенных строках ответ написать самим. Ценность нашего исследования будет зависеть от того, насколько обстоятельно и полно Вы ответите на все вопросы. Заранее благодарны за участие.
Ваш пол? А) М; Б) Ж2. Ваш возраст ____________________
3. Интересуетесь ли Вы естественнонаучными дисциплинами (физикой, химией, биологией, географией)? А) Да, мне интересно их изучать; Б) Интересуюсь другими предметами; В) Затрудняюсь ответить.
4. Можно ли продемонстрировать в условиях школьных лабораторий опыты, связанные с изучением некоторых природных явлений и процессов? А) Да; Б) Нет; В) Затрудняюсь ответить.
5. Если есть трудности (см. вопрос № 4), то с чем они связаны? __________________________________________________________________________________________________________________________
6. При изучении какого учебного материала возникают эти трудности (каких учебных дисциплин)? __________________________________________________________________________________________________________________________
7. Как Вы считаете, можно ли использовать компьютерные модели для демонстрации некоторых физических явлений или процессов, которые невозможно продемонстрировать в условиях школьных лабораторий? __________________________________________________________________________________________________________________________
8. На каких предметах Вы бы хотели в большей степени использовать компьютерные модели явлений и процессов?
________________________________________________________________________________________________________________________________
