Двійкове кодування символьної (текстової) інформації - студопедія

Основна операція, вироблена над окремими символами тексту - порівняння символів.

При порівнянні символів найбільш важливими аспектами є унікальність коду для кожного символу і довжина цього коду, а сам вибір принципу кодування практично не має значення.

Для кодування текстів використовуються різні таблиці перекодування. Важливо, щоб при кодуванні і декодуванні одного і того ж тексту використовувалася одна і та ж таблиця.

Таблиця перекодування - таблиця, яка містить упорядкований певним чином перелік кодованих символів, відповідно до якої відбувається перетворення символу в його двійковий код і назад.

Найбільш популярні таблиці перекодування: ДКОИ-8, ASCII, CP1251, Unicode.

Історично склалося, що в якості довжини коду для кодування символів було обрано 8 біт або 1 байт. Тому найчастіше одному символу тексту, що зберігається в комп'ютері, відповідає один байт пам'яті.

Різних комбінацій з 0 і 1 при довжині коду 8 біт може бути 28 = 256, тому за допомогою однієї таблиці перекодування можна закодувати не більше 256 символів. При довжині коду в 2 байти (16 біт) можна закодувати 65536 символів.

В даний час велика частина користувачів за допомогою комп'ютера обробляє текстову інформацію, яка складається з символів: букв, цифр, знаків пунктуації та ін.

Традиційно для того щоб закодувати один символ використовують кількість інформації дорівнює 1 байту, т. Е. I = 1 байт = 8 біт. За допомогою формули, яка пов'язує між собою кількість можливих подій До і кількість інформації I, можна обчислити скільки різних символів можна закодувати (вважаючи, що символи - це можливі події):

т. е. для представлення текстової інформації можна використовувати алфавіт потужністю 256 символів.

Суть кодування полягає в тому, що кожному символу ставлять у відповідність двійковий код від 00000000 до 11111111 або відповідний йому десятковий код від 0 до 255.

Необхідно пам'ятати, що в даний час для кодування українських букв використовують п'ять різних кодових таблиць (ЯКІ - 8, СР1251, ср866, Мас, ISO), причому тексти, закодовані за допомогою однієї таблиці не будуть правильно відображатися в іншому кодуванні. Наочно це можна представити у вигляді фрагмента об'єднаної таблиці кодування символів.

Одному і тому ж двійкового коду ставиться у відповідність різні символи.

Двійковий код Десятковий код КОІ8 СР1251 ср866 Мас ISO

11000010 194 б В - - Т

Втім, в більшості випадків про перекодуванні текстових документів піклується на користувач, а спеціальні програми - конвертори, які вбудовані в додатки.

Для визначення числового коду символу в кодуванні Windows (СР1251) потрібно за допомогою миші або клавіш управління курсором вибрати потрібний символ, потім клацнути по кнопці Кнопка. Після цього на екрані з'являється діалогова панель Налаштування, в якій в нижньому лівому кутку міститься десятковий числовий код вибраного символу.

Три підходи до визначення поняття "Кількість інформації"

1 комбінаторний підхід

Нехай змінна x здатне приймати значення, що належать кінцевому безлічі X, яке складається з N елементів. Кажуть, що ентропія змінного дорівнює

Вказуючи певне значення x = a змінного x, ми «знімаємо» цю ентропію, повідомляючи інфомацию

Якщо змінні x1, x2. xk здатні незалежно пробігати безлічі, які складаються відповідно з N1, N2. Nk елементів, то

Для передачі кількості інформації I доводиться вживати

довічних знаків. Наприклад, число різних «слів», що складаються з k нулів і одиниць і однієї двійки, так само 2k (k + 1),

Тому кількість інформації в такого роду собщений одно

тобто для «кодування» такого роду слів в чистій двійковій системі потрібно (усюди далі f≈g позначає, що різниця f-g обмежена, а f

g, що ставлення f: g прагне до одиниці)

нулів і одиниць. При викладі теорії інформації зазвичай не затримуються надовго на такому комбинаторном підході до справи. Але мені здається істотним підкреслити його логічну незалежність від яких би то не було імовірнісних припущень. Нехай, наприклад, нас займає завдання кодування повідомлень, записаних в алфавіті, що складається з s букв, причому відомо, що частоти

появи окремих букв в повідомленні довжини n задовольняють нерівності

Легко підрахувати, що при великих n двійковий логарифм числа повідомлень, підпорядкованих вимогу (3), має асимптотичну оцінку:

Тому при передачі такого роду повідомлень досить вжити приблизно nh довічних знаків.

Універсальний метод кодування, який дозволить передавати будь досить довге повідомлення в алфавіті з s букв, вживаючи не набагато більше ніж nh довічних знаків, не зобов'язаний бути надмірно складним, зокрема, не зобов'язаний починатися з визначення частот pr для всього повідомлення. Щоб зрозуміти це, достатньо зауважити: розбиваючи повідомлення S на m відрізків S1, S2. Sm, отримаємо нерівність

Втім, я не хочу входити тут в деталі цієї спеціальної завдання. Мені важливо лише показати, що математична проблематика, що виникає на грунті чисто комбинаторного підходи до вимірювання кількості інформації, не обмежується тривіально.

Цілком природним є чисто комбінаторний підхід до поняття «ентропії мови», якщо мати на увазі оцінку «гнучкості» мови - показника розгалуженості можливостей продовження мови при даному словнику і даних правилах побудови фраз. Для двійкового логарифма числа N українських друкованих текстів, складених зі слів, включених в «Словник української мови С. І. Ожегова і підлеглих лише вимогу« граматичної правильності »довжини n, вираженої в« числі знаків »(включно з пробілами), М. Ратнер і Н. Свєтлова отримали оцінку

Це значно більше, ніж оцінки зверху для «ентропії літературних текстів», одержувані за допомогою різних методів «вгадування продовжень». Така розбіжність цілком природно, так як літературні тексти підпорядковані не тільки вимогу «граматичної правильності.

Важче оцінити комбінаторних ентропію текстів, підпорядкованих певним змістовним обмеженням. Являло б, напри-мер, інтерес оцінити ентропію українських текстів, що можуть розглядатися як досить точні за змістом переклади заданого іншомовного тексту. Тільки наявність такої «залишкової ентропії» уможливлює віршовані переклади, де «витрати ентропії» на проходження обраному метру і характеру римування можуть бути до- вільно точно підраховані. Можна показати, що класичний чотиристопний римований ямб з деякими природними обмеженнями на частоту «переносів» і т. П. Вимагає допущення свободи звернення зі словесним матеріалом, що характеризується «залишкової ентропією» порядку 0,4 (при вказаному вище умовному способі вимірювання довжини тексту по « числу знаків, включаючи про- білі »). Якщо врахувати, з іншого боку, що стилістичні обмеження жанру, ймовірно, сніжа- ють наведену вище оцінку «повної» ентропії з 1,9 до не більше ніж 1,1-1,2, то ситуація стає примітною як в разі переведення, так і в разі оригінального поетичного творчості.

Хай вибачать мені утилітарно налаштовані Новомосковсктелі цей приклад. На виправдання зауважу, що більш широка проблема оцінки кількості інформації, з якими має справу творча людська діяльність, має дуже велике значення.

Подивимося тепер, якою мірою чисто комбінаторний підхід дозволяє оцінити «кількість інформації», що міститься в змінному x щодо пов'язаного з ним змінного y. Зв'язок між змінними x і y, пробігають соответсвенно безлічі X і Y. полягає в тому, що не всі пари x, y, що належать прямому добутку X.Y. є «можливими». За безлічі можливих пар U визначаються при будь-якому aX безлічі Ya тих y, для яких

3 - + - -

Природно визначити умовну ентропію рівністю

(Де N (Yx) - число елементів у множині Yx), а інформацію в x щодо y-формулою

Наприклад, в разі, зображеному в таблиці маємо

Зрозуміло, що H (y | x) і I (x: y) є функціями від x (в той час як y входить в їх позначення у вигляді «пов'язаного змінного»).

Без праці вводиться в чисто комбінаторної концепції уявлення про «кількість інформації, необхідній для вказівки об'єкта x при заданих вимогах до точності вказівки». (Див. З цього приводу велику літературу про «# 949; -ентропіі» множин в метричних просторах.)

2 Імовірнісний підхід

Можливості подальшого розвитку теорії інформації на основі визначень (5) і (6) залишилися в тіні з огляду на те, що надання Мінлива x і y характеру «випадкових змінних», що володіють певним спільним розподілом ймовірностей, дозволяє отримати значно багатшу систему понять і співвідношень. В паралель до введених в §1 величинам маємо тут

Як і раніше HW (y | x) і IW (x: y) є функціями від x. Мають місце нерівності

переходять у рівності при рівномірності відповідних розподілів (на X і Yx). Величини IW (x: y) і I (x: y) не пов'язані нерівністю певного знака. Як і в §1,

Але відмінність полягає в тому, що можна утворити математичні очікування MHW (y | x), MIW (x: y), а величина

характеризує «тісноту зв'язку» між x і y симетричним чином.

Варто, однак, відзначити і виникнення в ймовірнісної концепції одного парадоксу: величина I (x: y) при комбинаторном підході завжди неотрицательна, як це і природно при наївному уявленні про «кількості інформації», величина ж IW (x: y) може бути і негативною. Справжньою мірою «кількості інформації» тепер стає лише осредненная величина IW (x, y).

Імовірнісний підхід природний в теорії передачі по каналах зв'язку «масової» інформації, що складається з великого числа не зв'язаних або слабо пов'язаних між собою повідомлень, підпорядкованих певним імовірнісним закономірний- ності. У такого роду питаннях практично нешкідливий і вкорінене в прикладних роботах змішання ймовірностей і частот в межах одного досить довгого временн.ого ряду (яка отримує суворе виправдання при гіпотезі досить швидкого «перемішування»). Практично можна вважати, наприклад, питання про «ентропії» потоку вітальних телеграм і «пропускної спроможності» каналу зв'язку, що вимагається для своєчасної і неспотвореної передачі, коректно поставленим в його ймовірнісної трактуванні і при звичайній заміні ймовірностей емпіричними частотами. Якщо тут і залишається деяка незадоволеність, то вона пов'язана з відомою розпливчастістю наших концепцій, що відносяться до зв'язків між математичною теорією ймовірностей і реальними «випадковими явищами взагалі.

Але який реальний сенс має, наприклад, говорити про «кількість інформації», що міститься в тексті «Війни і миру»? Чи можна включити розумним чином цей роман в сукупність «можливих романів» та ще постулювати наявність в цій сукупності деякого розподілу ймовірностей? Або слід вважати окремі сцени «Війни і миру» утворюють випадкову послідовність з досить швидко затухаючими на відстані декількох сторінок «стохастическими зв'язками?

По суті, не менше темним є і модне вираз «кількість спадкової інформації, необхідної, скажімо, для відтворення особини виду зозуля. Знову в межах прийнятої ймовірнісної концепції можливі два варіанти. У першому варіанті розглядається сукупність «можливих видів» з невідомо звідки беруться розподілом ймовірностей на цій совокупності2 (2Обращеніе до безлічі видів, що існують або існували на Землі, навіть при чисто комбинаторном підрахунку дало б абсолютно неприйнятно малі оцінки зверху (що-небудь на зразок <100 бит!).).

У другому варіанті характеристичні властивості виду вважаються набором слабо пов'язаних між собою випадкових змінних. На користь другого варіанту можна навести міркування, засновані на реальному механізмі мутаційної мінливості. Але міркування ці ілюзорні, якщо вважати, що в результаті природного відбору виникає система узгоджених між собою характеристичних ознак виду.

3 Алгоритмічний підхід

По суті, найбільш змістовним є уявлення про кількість інформації «в чому-небудь (x) і« про що-небудь »(y). Не випадково саме воно в ймовірнісної концепції отримало узагальнення на випадок безперервних змінних, для яких ентропія нескінченна, але в широкому колі випадків звичайно.

Реальні об'єкти, що підлягають нашій вивчення, дуже (необмежено?) Складні, але зв'язку між двома реально існуючими об'єктами вичерпуються при більш простому схематизованому їх описі. Якщо географічна карта дає нам значну інформацію про ділянку земної поверхні, то все ж мікроструктура паперу і фарби, нанесеної на папір, ніякого відношення не має до микроструктуре зображеного ділянки земної поверхні.

то нова таблиця буде містити приблизно

інформації про первісну (n - число цифр в шпальтах).

У відповідності з тільки що сказаним пропоноване далі визначення величини IA (x: y) буде зберігати деяку невизначеність. Різні рівноцінні варіанти цього визначення будуть приводити до значень, еквівалентним лише в сенсі IA1≈IA2, тобто

де константа CA1A2 залежить від покладених в основу двох варіантів визначення універсальних методів програмування A1 і A2.

Будемо розглядати «цифрою область об'єктів», тобто рахункове безліч X =, кожному елементу якого поставлена ​​у відповідність як «номери» n (x) кінцева послідовність нулів і одиниць, що починається з одиниці. Позначимо через l (x) довжину послідовності n (x). Будемо припускати, що

1) відповідність між X і безліччю D довічних послідовностей описаного виду взаємно однозначно;

2) DX, функція n (x) на D общерекурсівна [1], причому для xD

де C - деяка константа;

3) разом з x і y в X входить впорядкована пара (x, y), номер цієї пари є общерекурсівная функція номерів x і y і

де Cx залежить тільки від x.

Не всі ці вимоги істотні, але вони полегшують виклад. Кінцевий результат побудови інваріантний по відношенню до переходу до нової нумерації n '(x), що володіє тими ж властивостями і виражається общерекурсівно через стару, і по відношенню до включення системи X в більш широку систему X' (в припущенні, що номери n 'в розширеній системі для елементів первісної системи общерекурсівно виражаються через початкові номери n). При всіх цих перетвореннях нові «складності» і кількості інформації залишаються еквівалентними початковим в сенсі ≈

«Відносною складністю» об'єкта y при заданому x будемо вважати мінімальну довжину l (p) програми p отримання y з x. Сформульоване так визначення залежить від «методу програмування. Метод програмування є не що інше, як функція # 966; (p, x) = y, що ставить в відповідність програмі p і об'єкту x об'єкт y.

У відповідності з універсально визнаними в сучасній математичній логіці поглядами слід вважати функцію # 966; частково рекурсивної. Для будь-якої такої функції вважаємо

При цьому функція # 965; = # 966; (u) від uX зі значеннями # 965; X називається частково рекурсивної, якщо вона породжується частково рекурсивної функцією перетворення номерів

Для розуміння визначення важливо помітити що частково рекурсивні функції, взагалі кажучи, не є всюди визначеними. Не існує регулярного процесу для з'ясування того, призведе застосування програми p до об'єкта x до якого-небудь результату чи ні. Тому функція K # 966; (y | x) не зобов'язана бути ефективно ви чіслімой (общерекурсівной) навіть у разі, коли вона свідомо конечна при будь-яких x і y.