C, PHP, VB, .NET

Дневникът на Филип Петров


* Съхранение на символи

Публикувано на 05 октомври 2015 в раздел Информатика.

Вече изяснихме, че при съхранение на използваните в нашата практика числа в десетична бройна система, компютрите извършват преобразуване в двоична. Хората обаче не работят само с числа, а в комуникацията използват всякакви сетива – писмено записват символи и изображения, устно звуци, използват допир, усещат мирис и т.н. Компютърната техника се използва за съхранение и обработка на голяма част от тази информация. Сега ще се фокусираме върхи символите – основните единици за изписване на текст и комуникиране в писмена форма.

Първото нещо, което трябва да знаем, е че всичко в компютъра се записва във вид на двоични числа. Това, което на екрана виждате като текст, всъщност се съхранява като бинарни числа. Компютърът превръща цифровите стойности в знаци и ги изобразява в букви, символи и знаци. Той прави това, използвайки кодиращ стандарт според формата на файла (начинът, по който сме записали файла). Тоест ако ние желаем да запишем букви, трябва да извършим преобразуване на тези букви в двоичен код. Процесът на преобразуване ще наричаме кодиране на информацията. Така например при съхранението на десетични числа, компютърът извършва кодиране и ги съхранява в двоичен вид. Обратното преобразуване се нарича декодиране. То се използва, за да прочетем вече записаната информация и да я изведем в подходящ за нас вид. Когато говорим за съхранение на информация на текст, едно важно свойство е тя да бъде съхранявана без загуби. Загуба на информация се получава тогава, когато при извършване на процеса „оригинални данни -> кодиране -> съхранение -> прочитане -> декодиране -> възстановени данни“ се получава разлика между оригиналните и възстановените данни. При определени видове данни понякога това е допустимо – например при запис на изображения, звук и видео. Когато говорим за запис на текст, обикновено това се счита за недопустимо. Затова ние търсим алгоритми за кодиране и декодиране, при които няма загуба на информация. Различните алгоритми генерират различни изходни бинарни поредици за един и същи текст, които ще наричаме кодировки. Ще разгледаме някои от най-разпространените такива.

US-ASCII 7 битова кодова таблица

American Standard Code for Information Interchange (ASCII) до средата на 90-те беше най-често използвания стандарт за кодиране на текст. Историята му започва през 60-те години на 20 век и търпи леки редакции до 1986 г., от когато е и последната му версия. Базира се изцяло върху английската азбука. Идеята е на всеки символ да се съпостави точно определено число. Кодировката оригинално е 7 битова, т.е. може да побере общо 128 различни кода. 33 от тях са т.нар. „контролни кодове“ – не са символи, които могат да се изобразят, а са резервирани за специални клавишни комбинации (например бутоните на клавиатурата Delete, Backspace, Home, End и т.н.). Представяме ги в следната таблица:

Бинарно Десетично Код Наименование
0000000 0 \0 Null character
0000001 1 Start of Header
0000010 2 Start of Text
0000011 3 End of Text
0000100 4 End of Transmission
0000101 5 Enquiry
0000110 6 Acknowledgment
0000111 7 \a Bell
0001000 8 \b Backspace
0001001 9 \t Horizontal Tab
0001010 10 \n Line feed
0001011 11 \v Vertical Tab
0001100 12 \f Form feed
0001101 13 \r Carriage return
0001110 14 Shift Out
0001111 15 Shift In
0010000 16 Data Link Escape
0010001 17 Device Control 1
0010010 18 Device Control 2
0010011 19 Device Control 3
0010100 20 Device Control 4
0010101 21 Negative Acknowledgment
0010110 22 Synchronous idle
0010111 23 End of Transmission Block
0011000 24 Cancel
0011001 25 End of Medium
0011010 26 Substitute
0011011 27 \e Escape
0011100 28 File Separator
0011101 29 Group Separator
0011110 30 Record Separator
0011111 31 Unit Separator
1111111 127 Delete

Останалите 95 кода са т.нар. „printable characters“ (символи, които могат да се отпечатват). Представяме ви всички символи в следната таблица:

Бинарно Десетично Символ
0100000 32 (интервал)
0100001 33 !
0100010 34
0100011 35 #
0100100 36 $
0100101 37 %
0100110 38 &
0100111 39
0101000 40 (
0101001 41 )
0101010 42 *
0101011 43 +
0101100 44 ,
0101101 45
0101110 46 .
0101111 47 /
0110000 48 0
0110001 49 1
0110010 50 2
0110011 51 3
0110100 52 4
0110101 53 5
0110110 54 6
0110111 55 7
0111000 56 8
0111001 57 9
0111010 58 :
0111011 59 ;
0111100 60 <
0111101 61 =
0111110 62 >
0111111 63 ?
1000000 64 @
1000001 65 A
1000010 66 B
1000011 67 C
1000100 68 D
1000101 69 E
1000110 70 F
1000111 71 G
1001000 72 H
1001001 73 I
1001010 74 J
1001011 75 K
1001100 76 L
1001101 77 M
1001110 78 N
1001111 79 O
1010000 80 P
1010001 81 Q
1010010 82 R
1010011 83 S
1010100 84 T
1010101 85 U
1010110 86 V
1010111 87 W
1011000 88 X
1011001 89 Y
1011010 90 Z
1011011 91 [
1011100 92 \
1011101 93 ]
1011110 94 ^
1011111 95 _
1100000 96 `
1100001 97 a
1100010 98 b
1100011 99 c
1100100 100 d
1100101 101 e
1100110 102 f
1100111 103 g
1101000 104 h
1101001 105 i
1101010 106 j
1101011 107 k
1101100 108 l
1101101 109 m
1101110 110 n
1101111 111 o
1110000 112 p
1110001 113 q
1110010 114 r
1110011 115 s
1110100 116 t
1110101 117 u
1110110 118 v
1110111 119 w
1111000 120 x
1111001 121 y
1111010 122 z
1111011 123 {
1111100 124 |
1111101 125 }
1111110 126 ~

Трябва да се отбележи, че ASCII определя съответствие между кодовете и семантичната стойност на символите, а не техните конкретни реализации. Казано с други думи: начинът за изобразяване на екрана на компютъра зависи допълнително от шрифта, който се използва, а той не е част от кодиращата таблица.

Едно важно качество на ASCII таблицата е, че буквите се кодират с поредни цифри в същата последователност, както са в азбуката. Това позволява на програмистите да правят лесно сравнения според големината на кодовете на буквите (т.е. буквите разгледани като числа). Например:

// например четем символ от клавиатурата
char c = ...;
// проверяваме дали е главна буква
if(c >= 'A' && c <= 'Z') ...
// проверяваме дали е малка буква или цифра
if((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9')) ...
// проверяваме дали е малка или главна буква
if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) ...

Със сигурност трябва да запомните, че символите на цифрите, т.е. ‘0’, ‘1’, ‘2’, …, се кодират с числата от 48 до 57. Важно за всеки „прохождащ“ в програмирането е да осъзнае разликата между ‘0’ и 0 в самото начало.

ASCII code page 437 – 8 битова кодова таблица

В началото на 80-те паметите на компютрите вече значително са увеличили обема си, а 8 битове компютри се налагат масово. Това кара IBM, при въвеждането на своята серия от персонални компютри на пазара, да допълнят ASCII таблицата с още 1 бит информация, т.е. тя става 8 битова – такава, каквато я ползваме и до днес. По този начин символите се увеличават до 256 възможни. Първите 127 си остават същите, а допълнителните символи от т.нар. „extended ASCII table“ (разширена ASCII таблица) са главно букви от западноевропейски азбуки, гръцки букви, математически символи и графични зна;и, които позволяват изчертаването на графика в конзолен режим:

Бинарно Десетично Символ
10000000 128 Ç
10000001 129 ü
10000010 130 é
10000011 131 â
10000100 132 ä
10000101 133 à
10000110 134 å
10000111 135 ç
10001000 136 ê
10001001 137 ë
10001010 138 è
10001011 139 ï
10001100 140 î
10001101 141 ì
10001110 142 Ä
10001111 143 Å
10010000 144 É
10010001 145 æ
10010010 146 Æ
10010011 147 ô
10010100 148 ö
10010101 149 ò
10010110 150 û
10010111 151 ù
10011000 152 ÿ
10011001 153 Ö
10011010 154 Ü
10011011 155 ¢
10011100 156 £
10011101 157 ¥
10011110 158
10011111 159 ƒ
10100000 160 á
10100001 161 í
10100010 162 ó
10100011 163 ú
10100100 164 ñ
10100101 165 Ñ
10100110 166 ª
10100111 167 º
10101000 168 ¿
10101001 169
10101010 170 ¬
10101011 171 ½
10101100 172 ¼
10101101 173 ¡
10101110 174 «
10101111 175 »
10110000 176
10110001 177
10110010 178
10110011 179
10110100 180
10110101 181
10110110 182
10110111 183
10111000 184
10111001 185
10111010 186
10111011 187
10111100 188
10111101 189
10111110 190
10111111 191
11000000 192
11000001 193
11000010 194
11000011 195
11000100 196
11000101 197
11000110 198
11000111 199
11001000 200
11001001 201
11001010 202
11001011 203
11001100 204
11001101 205
11001110 206
11001111 207
11010000 208
11010001 209
11010010 210
11010011 211
11010100 212
11010101 213
11010110 214
11010111 215
11011000 216
11011001 217
11011010 218
11011011 219
11011100 220
11011101 221
11011110 222
11011111 223
11100000 224 α
11100001 225 ß
11100010 226 Γ
11100011 227 π
11100100 228 Σ
11100101 229 σ
11100110 230 µ
11100111 231 τ
11101000 232 Φ
11101001 233 Θ
11101010 234 Ω
11101011 235 δ
11101100 236
11101101 237 φ
11101110 238 ε
11101111 239
11110000 240
11110001 241 ±
11110010 242
11110011 243
11110100 244
11110101 245
11110110 246 º
11110111 247
11111000 248 °
11111001 249
11111010 250 ·
11111011 251
11111100 252
11111101 253 ²
11111110 254
11111111 255

От този момент нататък започват да се появяват множество вариации на тази кодова таблица. Общото между тях е, че първите 128 символа са винаги от стандартната таблица, а разширените символи се различават в зависимост от имплементацията. 8 битовите ASCII таблици често биват наричани от хората като „ANSI“.

Windows 1251

Едно от популярните 8 битови разширения на ASCII таблицата е Windows 1251 – тази кодировка включва букви на кирилица и се използва доста масово през 90-те години в България, Македония и Русия.

Бинарно Десетично Символ
10000000 128 Ђ
10000001 129 Ѓ
10000010 130
10000011 131 ѓ
10000100 132
10000101 133
10000110 134
10000111 135
10001000 136
10001001 137
10001010 138 Љ
10001011 139
10001100 140 Њ
10001101 141 Ќ
10001110 142 Ћ
10001111 143 Џ
10010000 144 ђ
10010001 145
10010010 146
10010011 147
10010100 148
10010101 149
10010110 150
10010111 151
10011000 152 неизползван
10011001 153
10011010 154 љ
10011011 155
10011100 156 њ
10011101 157 ќ
10011110 158 ћ
10011111 159 џ
10100000 160 nbsp
10100001 161 Ў
10100010 162 ў
10100011 163 Ј
10100100 164 ¤
10100101 165 Ґ
10100110 166 ¦
10100111 167 §
10101000 168 Ё
10101001 169 ©
10101010 170 Є
10101011 171 «
10101100 172 ¬
10101101 173 ­
10101110 174 ®
10101111 175 Ї
10110000 176 °
10110001 177 ±
10110010 178 І
10110011 179 і
10110100 180 ґ
10110101 181 µ
10110110 182
10110111 183 ·
10111000 184 ё
10111001 185
10111010 186 є
10111011 187 »
10111100 188 ј
10111101 189 Ѕ
10111110 190 ѕ
10111111 191 ї
11000000 192 А
11000001 193 Б
11000010 194 В
11000011 195 Г
11000100 196 Д
11000101 197 Е
11000110 198 Ж
11000111 199 З
11001000 200 И
11001001 201 Й
11001010 202 К
11001011 203 Л
11001100 204 М
11001101 205 Н
11001110 206 О
11001111 207 П
11010000 208 Р
11010001 209 С
11010010 210 Т
11010011 211 У
11010100 212 Ф
11010101 213 Х
11010110 214 Ц
11010111 215 Ч
11011000 216 Ш
11011001 217 Щ
11011010 218 Ъ
11011011 219 Ы
11011100 220 Ь
11011101 221 Э
11011110 222 Ю
11011111 223 Я
11100000 224 а
11100001 225 б
11100010 226 в
11100011 227 г
11100100 228 д
11100101 229 е
11100110 230 ж
11100111 231 з
11101000 232 и
11101001 233 й
11101010 234 к
11101011 235 л
11101100 236 м
11101101 237 н
11101110 238 о
11101111 239 п
11110000 240 р
11110001 241 с
11110010 242 т
11110011 243 у
11110100 244 ф
11110101 245 х
11110110 246 ц
11110111 247 ч
11111000 248 ш
11111001 249 щ
11111010 250 ъ
11111011 251 ы
11111100 252 ь
11111101 253 э
11111110 254 ю
11111111 255 я

Много стари уеб страници все още използват тази кодировка. Понякога може да видите, че уеб браузърите не изобразяват правилно символите от нея. Например вместо думата „Новини“ понякога се появяват странните за нас символи „Íîâèí萓. Подобно нещо се случва когато документа е написан в една кодировка (в нашия пример Windows 1251 – cyrilic windows), но се декодира в друга (Windows 1252 – western european windows). Подобни проблеми се появяват понякога при файлови, които са записвани със стари софтуерни продукти. Ако във файла няма т.нар. „метаданни“, които да опишат изрично кодировката на символите, то когато бъдат отворени с друг софтуерен продукт, той не може разбере с какво точно да ги декодира. В такива случаи обикновено програмите избират латинска ASCII таблица по подразбиране и текст написан на кирилица става нечетим.

Универсално множество символи (Universal Character Set – UCS)

С налагането на 16 битовите компютри в края на 80-те години започва работа по създаване на „универсална кодировка“ (UCS). Целта е била да се съберат всички символи от всички кодировки познати до този момент в една таблица. Първоначалната версия на стандарта се е казвала UCS-2 („2“ идва от „2 байта“). Оказало се обаче, че тези 65536 комбинации (наречени „базово мултиезично поле“ – BMP) не са достатъчни, за да „поемат“ всички познати до този момент символи. Затова от IEEE решили да разширят стандарта с нова 31 битова кодировка наречена UCS-4. Били дефинирани всички познати символи, всеки от който получава уникално число, наречено „code point“ (кодова точка). За дефиниция на конкретна кодова точка е прието да се използват числа в осмична форма (заради по-краткия запис спрямо десетичните) с префикс буквата „U“ (от Unicode) – например U+005A e кодовата точка на латинската буква „Z“. Преди 2000 г. най-често се използвало BMP, но след по-масовото навлизане на Китай в пазара на софтуер това се променило и в днешно време UCS-4 се използва почти навсякъде като основен стандарт.

Имайте предвид, че UCS е стандартизирано множество от символи и техните отговарящи номера (кодове), но за разлика от ASCII таблиците това все още не е достатъчно да бъде наречено „кодировка“. Различните алгоритми, които имплементират практически UCS са тези, които ще наричаме encoding (кодировка).

UTF-8 (Unicode Transformation Format 8 bit)

UTF-8 е доминиращия стандарт за кодировка в Unix/Linux средите, а в последно време и в интернет комуникацията. Интересното при него е, че е с променлива дължина. Символи кодирани с UTF-8 заемат между 1 и 4 байта. Негативите от това са, че например не можем да кажем какъв е броя букви на даден текст, без да го обходим символ по символ. Не можем и да „отидем директно на N-ти символ“ – трябва да започнем отначало и да минем всички предишни символи 1 по 1, докато го достигнем. За щастие това рядко е значим проблем при обработката на информация.

UTF-8 съхранява кодовете на символите по следния начин:

  • Ако кодовата точка е в интервала от U+0000 до U+007F, тя се разглежда като 7-битово цяло число и се съхранява в 1 байт – същото като US-ASCII стандарта;
  • Ако кодовата точка е в интервала от U+0080 до U+07FF, тя се разглежда като 11-битово цяло число и се съхранява в 2 байта. Първите 5 бита се съхраняват в първия байт, а останалите 6 бита във втория;
  • Ако кодовата точка е в интервала от U+0800 до U+FFFF, ще бъде разглеждан като 16-битово цяло число и се съхранява в 3 байта. Първите 4 бита се съхраняват в първия байт, следващите 6 бита във втория и останалите 6 бита в третия байт;
  • Ако кодовата точка е в интервала от U+10000 до U+10FFFF, ще бъде разглеждано като 21-битово цяло число и се съхранява в 4 байта. Първите 3 бита се съхраняват в първия байт, следващите 6 бита във втория, следващите 6 бита в третия и последните 6 бита в четвъртия байт.

Алгоритъмът за прочитане на UTF-8 кодиран текст е елементарен. Програмата трябва да прочете първия бит на съхраненото число. Ако той е 0, символа е кодиран в 1 байт – този байт се прочита и на намереното число се съпоставя съответния символ. Ако първият бит не е 0, тогава броя на битовете в началото на прочетения байт, които са ненулеви, дава броя байтове, които трябва да се прочетат за текущия символ. Ако например в двоичен вид числото започва с 110…, то това означава, че имаме 2 байтов символ. Ако в двоичен вид числото започва с 1110…, тогава ще имаме 3 байтов, а при 1111… – 4 байтов. Освен това при многобайтовите символи има едно удобно свойство, че всеки байт след първия започва с битове 10… Така ако в даден момент се намираме „по средата на дадена многобайтова буква“ имаме лесен начин да намерим нейното начало – просто се връщаме назад до достигане на число, което не e от вида 10….

UTF-8 е много ефективен при съхранение на западноевропейски езици – почти всички букви от тях са в първия интервал, т.е. заемат по 1 байт на символ. Това е може би и причината UTF-8 да е най-разпространената кодировка до този момент. При това има едно голямо предимство – началото на UTF-8 кодировката съвпада със 7-битовата US-ASCII таблица, т.е. може да се каже, че ASCII таблицата е подмножество на UTF-8. Това, че дължината се намира с прочитане на първите битове на символа го прави много удобен за мрежова комуникация – при предаването на данните по сокет (мрежови канал) е достатъчно да прочетем само първите няколко бита на символа, за да знаем цялата му дължина.

UTF-16 (Unicode Transformation Format 16 bit)

UTF-16 е познатият като „Unicode“ стандарт под Windows и също е кодиране с променлива дължина. Символи кодирани с UTF16 заемат между 2 и 4 байта. Използва се по подразбиране в множество съвременни програмни среди като Java и .Net и е доминантното кодиране под Windows операционна система. Идеята на UTF-16 е да събере най-често използваните кодиращи точки (BMP от UCS-2) в два байта от информация и те да са с фиксирана дължина. Само символи, които са с кодови точки с число над 216 (т.е. такива, които са от UCS-4 стандарта) се кодират с четири байта. Идеологията принципно е сходна с тази на UTF-8:

  • Ако кодовата точка е в интервала от U+0000 до 0xFFFF, тя се съхранява в 2 байта;
  • Ако кодовата точка е в интервала от U+10000 до 0x10FFFF, тя се съхранява в 4 байта.

За разлика от UTF-8 обаче, тук алгоритъма за разпознаване на 4 байтов символ не е толкова елементарен. Тук се използват т.нар. „сурогатни двойки“. Идеята е, че в Unicode интервала от 0xD800 до 0xDFFF не се използва – в него няма кодови точки. Този интервал ще наричаме сурогатно поле. Сурогатните двойки са две числа в тези интервали – първото в интервала от U+D800 до U+DBFF, а второто в интервала от U+DC00 до U+DFFF. При попадане на 2 байтов символ, който е от сурогатното поле, това е индикация в UTF-16, че сме попаднали на 4 байтов символ. За да го намерим, трябва извършим преобразувание на сурогатната двойка. Нека разгледаме алгоритъма за кодиране на такива символи (примера е взет 1:1 от Уикипедия, но лесно може да се направи друг). Ако искаме да кодираме U+10437:

  • Извадете 0x10000 от 0x10437. Резултатът е 0x00437 или 0000 0000 0100 0011 0111.
  • Разделяме това число на две двойки по 10 бита: 0000000001 (0x0001) и 0000110111 (0x0037).
  • Добавяме 0xD800 към първото: 0xD800 + 0x0001 = 0xD801.
  • Добавяме 0xDC00 къв второто: 0xDC00 + 0x0037 = 0xDC37.
  • Записваме двете числа последователно, т.е. символа се кодира като 2 байта за 0xD801 последвани от 2 байта за 0xDC37.

Виждате, че първите два байта са от сурогатното поле, като първото е от първия интервал, а второто от втория. Декодирането става като приложим горните операции наобратно – на първото число вадим 0xD800, а на второто вадим 0xDC00, след което ги съединяваме.

Единственото предимство на UTF-16 спрямо UTF-8 е при съхранение на китайски, японски и корейски текст. При тях UTF-8 използва 3 байта за символ, докато UTF-16 използва само 2 байта на символ.

UTF-32 (Unicode Transformation Format 32 bit)

UTF-32 e най-пряката имплементация на UCS-4. При него всяко складирано число съвпада със съответен code point. Всеки символ се записва с точно 32 бита, т.е. 4 байта. С тази кодировка се работи много бързо на съвремените компютри. Когато се налага индексиране и търсене в текст, тази кодировка е много по-бърза от нейните алтернативи, които ще разгледаме по-долу. За съжаление UTF-32 разхищава много памет – например 4 пъти повече при стандартни текстове на английски език спрямо UTF-8. Оказва се, че най-голямото предимство на фиксираната дължина на UTF-32 – търсене на N-ти символ вътре в текст – не е често срещана в практиката операция. Поради тази причина UTF-32 се използва доста рядко. Противно на очакването, UTF-32 не е по-ефективен от UTF-16 при намиране на дължина на текст. Причината за това е, че в него има включени т.нар. „комбиниращи маски“ (combining masks) – това са символи, които се използват за допълване на други символи (например ченгелчета, апострофи и т.н.). Така се оказва, че UTF-32 е еднакво бърз при тази операция с UTF-16. При това в най-новия стандарт в интернет – HTML5 – специално е указано да не се използва UTF-32 кодировка.

Byte Order Mask (BOM)

BOM е специален Unicode символ, който може да се постави в началото на текста. При UTF-8 той е поредицата 0xEF,0xBB,0xBF, но в тази кодировка няма особено значение. Ако този символ бъде сложен в началото на UTF-8 кодиран файл, текстовите редактори ще бъдат уведомени, че файла е кодиран с UTF-8 и нищо повече. Когато се публикуват html страници в интернет, които са UTF-8 кодирани, този символ не се слага – вместо това в head частта на HTML страницата се указва кодировката чрез т.нар. мета-таг (meta tag). Това е възможно понеже ако не се сложи BOM, UTF-8 кодиран файл може спокойно да бъде отворен и интерпретиран като ASCII (естествено нормално четими ще бъдат само латинските букви, а останалите ще бъдат неразбираеми). Понеже метатага в html документите се изписва изцяло с латински букви, той е четим за браузърите – така те изтеглят документа, първоначално го декодират като ASCII, след което виждат метатага и изобразяват на екрана на потребителя същия документ, но декодиран като UTF-8.

При UTF-16 BOM има значително по-важно значение. При UTF-16 е възможно числата да се записват с различен „endianness“ (припомняме, че това е начина за записване на цялото число – право или наобратно – вижте статията за съхранение на цели числа). Ако в началото на файла BOM символът е кодиран като 0xFE последвано от 0xFF, то файла се приема за Big Endian, а кодировката се счита за UTF-16BE. Ако е наобратно, т.е. е кодиран като 0xFF последвано от 0xFE, това се приема за Little Endian формат, а кодировката се счита за UTF-16LE. Голям проблем се получава тогава, когато UTF-8 редактор отвори UTF-16 кодиран текст, който има BOM. За такъв редактор текста би бил напълно нечетим. Поради тази причина употребата на BOM и тук е непрепоръчителна. Обикновено се приема, че UTF-16 кодиран текст без BOM е UTF-16BE.

Положението с BOM при UTF-32 е аналогично на това с UTF-16. Там UTF-32BE се указва с 0000FEFF, а UTF-32LE с FFFE0000. При липса на BOM в UTF-32 се приема, че текста е UTF-32BE.

 

 

 



Добави коментар

Адресът на електронната поща няма да се публикува


*