Пред.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
2.4.2. Структура словаря LZWДо этого момента считалось, что словарем LZW служит массив из строк переменной длины. Чтобы понять, почему специальное дерево будет являться лучшей структурой для словаря, следует напомнить работу кодера. Он считывает символы и добавляет их в строку I до тех пор, пока I находится в словаре. В некоторый момент строка Iх в словаре не обнаруживается, и тогда строка Iх помещается в словарь. Значит, при добавлении новых строк в словарь поступает всего один новый символ х. Это предложение можно перефразировать еще так: для каждой словарной строки в словаре найдется «родительская» строка, которая короче ровно на один символ.
Поэтому
для наших целей хорошим выбором будет структура дерева, которая уже
использовалось в LZ78, при построении которого
добавление новых строк Iх делается добавлением всего
одного нового символа х. Основная проблема состоит в том, что каждый узел
дерева LZW может иметь много потомков
(дерево не двоичное, а Один путь конструирования такой структуры данных это построение дерева в виде массива узлов, в котором каждый узел является структурой из двух полей: символа и указателя на узел родителя. В самом узле нет указателей на его потомков. Перемещение вниз по дереву от родителя к потомку делается с помощью процесса хеширования (перемешивания или рандомизации), в котором указатели на узлы и символы потомков перемешиваются некоторой функцией для создания новых указателей. Предположим, что строка abc уже была на входе, символ за символом, и ее сохранили в трех узлах с адресами 97, 266, 284. Пусть далее за ними следует символ d. Теперь кодер ищет строку abed, а точнее, узел, содержащий символ d, чей родитель находится по адресу 284. Кодер хеширует адреса 284 (указатель на строку abc) и 100 (ASCII код d) и создает указатель на некоторый узел, скажем, 299. Потом кодер проверяет узел 299. Возможны три случая: 1. Этот узел не используется. Это означает строки abed еще нет в словаре и его следует туда добавить. Кодер делает это путем сохранения родительского указателя и ASCII кода 100 в этом узле. Получаем следующий результат:
2. Узел содержит родительский указатель 284 и ASCII код символа d. Это означает, что строка abcd уже есть на дереве. Тогда кодер вводит следующий символ, скажем, е и ищет на дереве строку abcde. 3. В узле хранится что-то другое. Это означает, что хеширование другой пары указателя и кода ASCII дало адрес 299, и узел 299 уже содержит в себе информацию про другие строки. Такая ситуация называется коллизией, и ее можно разрешить несколькими путями. Простейший путь разрешения коллизии это увеличивать адрес до 300, 301,... до тех пор, пока не будет найден пустой узел или узел с содержимым (284: «d»). На практике узлы строятся состоящими из трех полей: указателя на родительский узел, указателя (или индекса), созданного в процессе хеширования, и кода (обычно, ASCII) символа, лежащего в этом узле. Второе поле необходимо для разрешения коллизий. Таким образом, узел имеет вид триплета
Пример: Проиллюстрируем эту структуру данных с помощью строки «ababab…» из примера на стр. 103). Словарем будет служить массив diсt, элементами которого являются структуры с тремя полями parent, index, symbol. Мы будем обращаться к этим полям с помощью выражения вида dict[pointer].parent, где pointer - индекс в массиве. Словарь инициализируется двумя символами а и b. (Для простоты мы не будем использовать коды ASCII, но будем считать, что а и b имеют коды 1 и 2.) Первые несколько шагов кодера будут следующими: Шаг 0: Отметить все позиции, начиная с третьей, как неиспользуемые.
Шаг 1: Первый входной символ а помещается в переменную I. Точнее, переменной I присваивается значение кода l. Поскольку это первый символ входного файла, кодер его не ищет в словаре. Шаг 2: Второй символ b помещается в переменную J, то есть, J=2. Кодер должен искать в словаре строку ab. Он выполняет операцию pointer:=hash(I,J). Здесь hash(x,у) обозначает некоторую функцию двух аргументов х и у. Предположим, что результатом этой операции будет 5. Поле dict[pointer].index содержит «пусто», так как строки аb нет в словаре. Она туда заносится с помощью следующих действий dict[pointer].parent:=I; dict[pointer].index:=pointer; dict[pointer].symbol:=J; причем pointer=5. После чего J помещается в I, то есть I=2.
Шаг 3: Третий символ а поступает в J, то есть, J=1. Кодер должен искать в словаре строку bа. Выполняется pointer:=hash(I,J). Пусть результат равен 8. Поле dict[pointer].index содержит «пусто», то есть, строки bа нет в словаре. Добавляем ее в словарь с помощью операций dict[pointer].parent:=I; dict[pointer].index:=pointer; dict[pointer].symbol:=J; причем pointer=8. После чего J помещается в I, то есть I=1.
Шаг 4: Четвертый символ b переносится в J, теперь J=2. Кодер должен искать в словаре строку ab. Выполняется pointer:=hash(I,J). Мы знаем из шага 2, что результат - 5. Поле dict[pointer].index содержит 5, то есть строка ab имеется в словаре. Значение переменной pointer заносится в I, I=5. Шаг 5: Пятый символ а попадает в J, теперь J=l. Кодер должен искать в словаре строку aba. Как обычно, выполняется оператор pointer:=hash(I,J). Предположим, что результатом будет 8 (коллизия). Поле dict[pointer].index содержит 8, что хорошо, но поле dict[pointer].parent содержит 2 вместо ожидавшего указателя 5. Произошла коллизия, это означает, что строки aba нет в словаре по адресу 8. Тогда pointer последовательно увеличивается на 1 до тех пор, пока не найдет узел, для которого index=8 и parent=5 или, который пуст. В первом случае aba имеется в словаре, и pointer записывается в I. Во втором случае aba нет в словаре, кодер сохраняет его в узле pointer и записывает в I содержимое J.
Пример: Сделаем процедуру хеширование для кодирования строки символов «alf_eats_alfalfa». Сам процесс кодирования детально разобран в предыдущем примере. Результаты хеширования выбраны произвольно. Они не порождены какой-либо реальной функцией хеширования. Все 12 построенных узлов этого дерева показаны на рис. 2.10. 1. Hash(1,97)=278. По адресу 278 заносится (97,278,1). 2. Hash(f,.108)=266. По адресу 266 заносится (108,266,f). 3. Hash(_,102)=269. По адресу 269 заносится (102,269,_). 4. Hash(e,32)=267. По адресу 267 заносится (32,267,е). 5. Hash(a,101)=265. По адресу 265 заносится (101,265,а). 6. Hash(t,97)=272. По адресу 272 заносится (97,272,t). 7. Hash(s,116)=265. Коллизия! Спускаемся в следующую свободную позицию 268 и заносим (116,265,s). 8. Hash(_,115)=270. По адресу 270 заносится (115,270,_). 9. Hash(a,32)=268. Коллизия! Спускаемся в следующую свободную позицию 271 и заносим (32,268,а). 10. Hash(l,97)=278. По адресу 278 в поле index записано 278, а поле symbol содержит 1. Значит, ничего не надо записывать или сохранять на дереве. 11. Hash(f ,278)=276. По адресу 276 заносится (278,276,f). 12. Hash(a,102)=274. По адресу 274 заносится (102,274,а). 13. Hash(l,97)=278. По адресу 278 в поле index записано 278, а поле symbol содержит 1. Значит, ничего не надо делать. 14. Hash(f,278)=276. По адресу 276 в поле index записано 276, а поле symbol содержит f. Значит, ничего не надо делать. 15. Hash(a,276)=274. Коллизия! Спускаемся в следующую свободную позицию 275, и заносим (276,274,а). Читатель, который тщательно следил за нашими построениями до этого момента будет счастлив узнать, что декодер LZW использует словарь очень простым способом, не применяя хеширование.
Рис. 2.10. Рост дерева LZW для «alf_eats_alfalfa». Сначала декодер, как и кодер заполняет первые 256 позиций словаря кодами ASCII. Затем он читает указатели из входного файла и использует их для нахождения символов в словаре. На первом шаге декодирования, декодер вводит первый указатель и использует его для обнаружения в словаре первой строки I. Этот символ записывается в выходной (разжатый) файл. Теперь необходимо записать в словарь строку Iх, но символ х еще не известен; им будет первый символ следующей строки извлекаемой из словаря. На каждом шаге декодирования после первого декодер читает следующий указатель из файла, использует его для извлечения следующей строки J из словаря и записывает эту строку в выходной файл. Если указатель был равен, скажем, 8, то декодер изучает поле dict[8].index. Если это поле равно 8, то это правильный узел. В противном случае декодер изучает последующие элементы массива до тех пор, пока не найдет правильный узел. После того, как правильный узел найден, его поле parent используется при проходе назад по дереву для извлечения всех символов строки в обратном порядке. Затем символы помещаются в J в правильном порядке (см. пункт 2 после следующего примера), декодер извлекает последний символ х из J и записывает в словарь строку Iх в следующую свободную позицию. (Строка I была найдена на предыдущем шаге, поэтому на дерево необходимо добавить только один узел с символом х.) После чего декодер перемещает J в I. Теперь он готов для следующего шага. Для извлечения полной строки из дерева LZW декодер следует по указателям полей parent. Это эквивалентно продвижению вверх по дереву. Вот почему хеширование здесь не нужно. Пример: В предыдущем примере описана процедура хеширования строки «alf_eats_alfalfa». На последнем шаге в позицию 275 массива был записан узел (276,274,а), а в выходной сжатый файл был записан указатель 275. Когда этот файл читается декодером, указатель 275 является последним обработанным им элементом входного файла. Декодер находит символ а в поле symbol узла с адресом 275, а в поле pernt читает указатель 276. Тогда декодер проверяет адрес 276 и находит в нем символ f и указатель на родительский узел 278. В позиции 278 находится символ 1 и указатель 97. Наконец, в позиции 97 декодер находит символ а и нулевой указатель. Значит, восстановленной строкой будет alfa. У декодера не возникает необходимости делать хеширование и применять поле index. Нам осталось обсудить обращение строки. Возможны два варианта решения. 1. Использовать стек. Это часто применяемая структура в современных компьютерах. Стеком называется массив в памяти, к которому открыт доступ только с одного конца. В любой момент времени, элемент, который позже попал в стек, будет раньше других извлечен оттуда. Символы, которые извлекаются из словаря, помещаются в стек. Когда последний символ будет туда помещен, стек освобождается символ за символом, которые помещаются в переменную J. Строка оказывается перевернутой. 2. Извлекать символы из словаря и присоединять их к J справа налево. В итоге переменная J будет иметь правильный порядок следования символов. Переменная J должна иметь длину, достаточную для хранения самых длинных строк.
2.4.3. LZW в практических приложенияхОпубликование в 1984 году алгоритма LZW произвело большое впечатление на всех специалистов по сжатию информации. За этим последовало большое количество программ и приложений с различными вариантами этого метода. Наиболее важные из них приведены в [Salomon 2000].
|
1 |
Оглавление
|