1. Дивитися лекцію на: ІНТУЇТ | youtube.com

Анотація: Подання текстів в двійковому вигляді.

Дивитися лекцію на: ІНТУЇТ | youtube.com

Якщо проблеми з відео, натисніть вище посилання youtube

Ми розглядаємо уявлення тексту, записаного в алфавіті P текстом в алфавіті Q. Коли алфавіти P і Q мають однакову кількість символів, то завдання вирішується досить просто, - між алфавітами можна встановити взаємно однозначну відповідність. Кожному символу з алфавіту P ставиться у відповідність символ алфавіту Q. Звичайно, навіть в цьому випадку можуть виникати проблеми, оскільки різних способів встановлення відповідності багато. Неважко зрозуміти, що якщо в алфавіти містять n символів, то існує n! різних способів встановлення відповідності - першому з символів алфавіту P можна поставити у відповідність кожній із n символів алфавіту, для другого таких способів буде n-1, а всього - n !. Прийнятий спосіб кодування можна записати у вигляді таблиці кодування, що складається з двох рядків однакової довжини. У першій з них символи алфавіту P, у другій - відповідні символи алфавіту Q.

Завдання: дано два алфавіту P = {а, і, м, н, п} і {α, γ, ε, π, ω}. Дана таблиця кодування T1 = <s1, s2>, де s1 = "аімнп", s2 = "?????". Тоді текст "мама і тато" буде закодований наступним чином "απαπ ε γπγπ", вважаючи, що символ пробілу не кодують, зберігаючи своє значення в обох алфавітах.

Закодований текст може бути однозначно береться стверджувати, якщо відома таблиця кодування.

Розглянемо тепер ситуацію, коли алфавіти P і Q мають різну довжину і символів в алфавіті Q менше ніж символів алфавіту P. Нас, перш за все, буде цікавити ситуація, коли Q - алфавіт комп'ютера, що містить всього два символи {0, 1}.

Як уявити текст в алфавіті P потужності k> 2 текстом в алфавіті Q = {0, 1}?

Рішення просте. Потрібно від алфавіту Q перейти до алфавітом, символами якого будуть слова довжини n алфавіту Q. Довжина слів залежить від числа символів в алфавіті P. Нехай алфавіт P містить k символів. Тоді, щоб забезпечити можливість кодування повинно виконуватися умова:

2n> = k

Ефективне кодування передбачає мінімальне значення n, що задовольняє цій умові.

Нагадаю дві важливі формули, що зв'язують потужність алфавіту - число його символів - і кількість слів довжини n в цьому алфавіті.

Нехай потужність алфавіту P дорівнює k. Нехай N - кількість слів довжини n в цьому алфавіті, M - число слів довжини менше n. Справедливі наступні співвідношення:

Завдання: Яка мінімальна довжина двійкового слова для кодування малих і великих літер кирилиці.

Рішення: Потужність алфавіту k = 66. Кодування можливо, коли n = 7. Це мінімальне значення, при якому 2n> 66. Зауважте, словами довжини 7 можна кодувати алфавіт, що містить 128 символів. При такому кодуванні вихідний алфавіт крім символів кирилиці може містити й інші символи, що використовуються під час запису тексту - пробіл, цифри, розділові знаки, знаки арифметичних операцій і інші корисні символи.

Яка ж кодування використовується сьогодні в реальній роботі з текстами на комп'ютері. Тексти, оброблювані на комп'ютерах в різних країнах, належать різним природним мовам - російському і китайському, англійської та індійському - мов досить багато, у кожного свій алфавіт. Як впоратися з завданням подання та обробки таких текстів? Довгий час для роботи з текстами використовувався 8-й біт код ASCII (American Standard Code Interchange Information). У цьому кодуванні кожен символ алфавіту кодується двійковим словом довжини 8 - одним байтом. У цьому випадку вихідний алфавіт може включати 256 символів. Для представлення тексту однієї мови такого алфавіту цілком вистачає. Для безлічі різних природних мов потужності алфавіту не вистачає. Вирішення цієї проблеми полягала в тому, що алфавіт розбивався на дві половини (дві сторінки). Перша половина з 128 символів була постійною і містила символи латиниці, цифри та інші загальні для всіх мов символи. Інша кодова сторінка була змінною, своя для кожного природної мови - російської, німецької та інших мов. Довгий час таке рішення проблеми влаштовувало користувачів комп'ютера. Код ASCII застосовується і сьогодні в деяких ситуаціях. Але з здешевленням і зростанням обсягу пам'яті комп'ютера стало ясно, що слід поступитися об'ємом пам'яті при кодуванні текстів заради зручності роботи з текстами, записаними на різних природних мовах, не використовуючи ніяких змінних таблиць.

Відбувся перехід до універсальної кодуванні Unicode. Це кодування передбачає використання слів довжиною 4 байта - тобто 32-х розрядних двійкових слів для зберігання одного символу тексту. Зрозуміло, що при такому способі кодування вихідний алфавіт може включати більше 4-х мільярдів символів, що свідомо більше числа символів, використовуваних сьогодні людством. Тому на практиці такий потужний зарезервований алфавіт не застосовується, а використовується в Unicode - 2-х байтная кодування. В цьому випадку алфавіт включає 65536 символів, що вистачає для алфавітів всіх використовуваних мов, включаючи ієрогліфи.

Завдання: Текст містить 120 символів. При переході від кодування ASCII до двухбайтное кодуванні Unicode наскільки збільшиться пам'ять, необхідна для зберігання тексту в пам'яті комп'ютера.

Рішення: В кодуванні ASCII текст займає 120 байтів, в новому кодуванні - в два рази більше. Відповідь: 120 байтів.

Завдання: Текст шкільного підручника в середньому містить 200 сторінок, на кожній з яких в середньому 2000 символів. Який обсяг пам'яті потрібно для зберігання тексту в кодуванні Unicode?

Рішення: Обсяг підручника становить 4 * 105 символів, що вимагає для зберігання в кодуванні Unicode 8 * 105 байтів. Оскільки 1 кілобайт становить 210 = 1024 байта, то для зберігання тексту досить 800 Кб пам'яті.

Завдання: Скільки текстів шкільних підручників можна зберегти на флешці об'ємом 8 Гб?

Рішення. Не будемо дріб'язковими при оцінці кількості підручників. Будемо нехтувати тієї невеликої позитивної різницею між 210 і 1000, що становить менше трьох відсотків. Надалі при розрахунках будемо вважати, що кілобайт приблизно дорівнює 1000 байтів, мегабайт дорівнює 1000 кілобайт, а гігабайт дорівнює 1000 мегабайтів. Оскільки для зберігання тексту одного підручника досить 0,8 Мб. (Дивись попередню задачу), то в 8-й гігабайти пам'яті можна зберегти тексти N підручників, де

N = 8000/0, 8 = 10000

Зрозуміло, що шкільний підручник містить не тільки тексти, а й графічну інформацію - кольорові малюнки, графіки. Для зберігання цієї інформації потрібно більше пам'яті, ніж для зберігання текстів. Тому зберегти на флешці 10 тисяч підручників з урахуванням всієї інформації, представленої в підручнику, не вдасться. Але якщо мова йде тільки про текстах, то однією флешки досить для зберігання всіх підручників за всі 10 років навчання, навіть за умови, що з кожного предмета може бути написано десяток різних підручників.

завдання

Завдання 1. Закодуйте текст, використовуючи наступну таблицю кодування

Завдання 2. декодуючими текст, закодований з використанням такої таблиці кодування.

Завдання 3. Текст був закодований з використанням таблиці кодування T1. При передачі закодованого тексту він був ще раз закодований з використанням таблиці T2. Який текст отримає одержувач повідомлення.

Завдання 4. декодуючими текст, двічі закодований з використанням таблиць кодування T1 і T2.

Завдання 5. Скільки слів довжини n в алфавіті потужності k

Завдання 6. Скільки слів довжини менше ніж n в алфавіті потужності k

Завдання 7. Код кириличної малої літери "а" дорівнює 1074 (в десятковій системі). Кодування символів алфавіту щільна. Це означає, що код символу алфавіту на одиницю більше коду попереднього символу (алфавіт впорядкований). В кирилиці єдиним винятком є ​​буква е, у якій особливий код. Знаючи код букви а, запишіть в двійковій системі багатобайтових код букви м.

Завдання 8. Оцініть обсяг пам'яті, достатній для зберігання документа (Вибрати один з 4-х варіантів відповіді)

Завдання 9. Скільки документів можна зберегти в пам'яті заданого обсягу

Завдання 10. Дан алфавіт (цифри, грецький) Яка довжина слова в двійковому алфавіті