Алгоритмы / Самораспаковывающийся HTML

Самораспаковывающимися бывают rar архивы. Это программы — exe файлы — которые состоят из двух основных частей: секция с кодом распаковщика и секция с сжатыми данными. Код распаковщика извлекает сжатые данные, распаковывает их и записывает в какое нибудь место. Я подумал, почему бы не сделать тоже самое с html файлом: там ведь тоже можно вставить секцию с кодом распаковщика на JavaScript и секцию с сжатыми данными в виде серии Unicode символов. Пользователь просто нажимает на такой html файл — также как и на обычную страницу — браузер загружает его и выполняет JavaScript-код который читает секцию с сжатыми данными, распаковывает их и вставляет на место html-разметки страницы. Это позволит прозрачно для пользователя сократить объём загружаемых html страниц. Есть, конечно, GZip, но я пока обойду его вниманием.

В этой статье я расскажу, что получилось из этой затеи.

Алгоритм LZW

Есть один очень простой алгоритм сжатия текстовых файлов. Он использует для сжатия тот факт, что в осмысленном тексте буквы появляются не случайным образом, а образуют цепочки которые часто встречаются в тексте. Каждая такая цепочка получает номер и весь текстовый файл записывается в виде последовательности таких номеров. Распаковщик по очереди читает эти номера и каждый номер заменяет на соответствующую цепочку символов. У этого алгоритма есть разные вариации — LZW, LZ77 — которые применяются не только для сжатия текста, но и для сжатия некоторых изображений.

Алгоритм LZW настолько простой, что его описание занимает в несколько раз больше места чем код упаковщика и распаковщика.

Сжатие текста

Для начала в ручном режиме сожмём строку «ABCABCABCADBCAD» = «ABC ABC ABC ADB CAD» (здесь пробелы только для наглядности, пробелов в строке нет). Будем считать, что у нас есть 4 цепочки длины 1 — каждая цепочка состоит из одного символа в строке:

0 A
1 B
2 C
3 D


Здесь цепочка «A» имеет номер 0, цепочка «B» имеет номер 1 и т.д. Таким образом у нас есть словарь из четырёх цепочек. Здесь важно, то что этот словарь есть как у упаковщика так и у распаковщика ещё до того как они получили текст.

Упаковщик будет читать текст по одному символу и пытаться составить как можно более длинную цепочку. В самом начале упаковщик читает символ «A» и его цепочка которую он составляет chain = «A». Упаковщик смотрит в словарь и видит, что такая цепочка уже есть под номером 0. Он делает вывод, что можно попробовать присоединить к цепочке chain следующий символ X в надежде на то, что цепочка chain + X вновь окажется в словаре. Он читает следующий символ «B» и видит, что chain + «B» = «AB» нету в словаре. Тогда он решает: «в этот раз я запишу в файл номер цепочки A, добавлю в словарь цепочку AB и в следующий раз когда она мне попадётся у меня будет номер для цепочки AB». После этого он записывает в файл номер цепочки которая у него уже есть (out = «0») и начинает собирать цепочку chain с символа «B» (chain = «B»). Затем он читает следующий символ «C» и повторяет рассуждения. Алгоритм упаковщика выглядит так:

lzw.compress = function(str)
{
        var dic = {}

        dic['A'] = 0
        dic['B'] = 1
        dic['C'] = 2
        dic['D'] = 3    

        var res = []
        var code = 4
        var chain = ''

        for (i = 0; i  str.length; i++)
        {
                var char = str[i]
                var newchain = chain + char

                if (dic[newchain] !== undefined)
                        chain = newchain
                else
                {
                        res.push(dic[chain])
                        dic[newchain] = code
                        code++
                        chain = char
                }
        }       

        res.push(dic[chain])

        return res
}

После того как упаковщик прочтёт всю строку, он получит следующий результат: lzw.compress(‘ABCABCABCADBCAD’) = [0,1,2,4,6,5,0,3,9,3]. Кроме того, упаковщик составит вот такой словарь:

0 A
1 B
2 C
3 D
4 AB
5 BC
6 CA
7 ABC
8 CAB
9 BCA
10 AD
11 DB
12 BCAD


Распаковка архива

Теперь посмотрим на архив [0,1,2,4,6,5,0,3,9,3] со стороны распаковщика. Как я уже написал, распаковщик заранее знает алфавит текста — A, B, C, D — и он знает, что упаковщик нумерует цепочки по порядку. Распаковщик будет читать номера цепочек из архива и повторять действия за упаковщиком — он будет также заполнять словарь и составлять свою цепочку символов. Итак, у распаковщика есть архив [0,1,2,4,6,5,0,3,9,3] и словарь:

0 A
1 B
2 C
3 D


Этого достаточно, чтобы восстановить исходный текст. Сначала распаковщик берёт первый номер из архива и ищет его в словаре. Он видит, что номер 0 это цепочка «A». Каждый номер в архиве это цепочка символов из текста, поэтому распаковщик записывает в файл цепочку соответствующую очередному номеру из архива: out = «A». Попутно он составляет цепочку символов: chain = «A». Далее он читает следуюший номер из архива и видит в словаре, что 1 это «B». Он записывает в файл эту цепочку (out = «AB») и представляет, что делал упаковщик в этот момент. Рассмотрим ситуацию, когда распаковщик имеет цепочку chain и видит следующий номер X в архиве. Возможно два варианта:

• Номер X есть в словаре. Тогда распаковщик пишет в файл ту цепочку из словаря, что соответствует номеру X — назовём эту цепочку S = Dic[X]. Затем он добавляет к chain первый символ из Dic[X] (упаковщик ведь читал символы по одному) и получает цепочку newchain = chain + S[1]. Поскольку упаковщик не присоединил S[1] к chain, цепочки newchain не было в словаре и значит он поместил newchain в словарь под первым свободным номером и начал собирать цепочку заново с символа S[1]. Тоже самое делает распаковщик: он помещает newchain в словарь на первое свободное место и начинает строить цепочку chain с первого символа S. Все последующие символы из S упаковщик присоединил к цепочке chain потому что все эти цепочки — S[1], S[1..2], S[1..3] и т.д. — уже были в словаре. Распаковщик делает также: он присодиняет все символы из S к цепочке ничего не добавляя в словарь и получает chain = S.
• Номера X нет в словаре. Это единственный тонкий момент в LZW. Зачем упаковщик записал в архив номер X если такого номера в словаре не было? Рассмотрим такой текст (пробелы только для наглядности, их в тексте нет):

  QA QAB QABQ ABQT


  Когда упаковщик встречает четвёртый символ Q, он пишет в архив номер QAB из словаря (пусть это будет X) и добавляет в словарь цепочку QABQ под номером Y X. Когда упаковщик добирается до последнего Q он пишет в архив номер QABQ (эта цепочка ведь уже в словаре) и продолжает упаковку с T. Теперь посмотрим на распаковщика. Когда он встречает тот номер X, он берёт из словаря QAB. После X сразу идёт Y, но распаковщик не может знать, что это QABQ потому что на момент чтения того X в словаре длинее QAB ничего не было (иначе вместо X — номера QAB — был бы некий номер Z — код QABQ). Так получилось потому что цепочки с номерами X и Y пересекаются — конец цепочки X совпадает с началом цепочки Y. Распаковщик учитывает это и знает, что после цепочки X идёт символ совпадающий с началом цепочки X: он просто добавляет к своей цепочке chain первый символ этой цепочки и добавляет результат в словарь.

Код распаковщика выглядит так:

lzw.decompress = function(archive)
{
        var dict = {}

        dict[0] = 'A'
        dict[1] = 'B'
        dict[2] = 'C'
        dict[3] = 'D'

        var lastcode = 4
        var code = archive[0]
        var chain = dict[code]
        var result = dict[code] 

        for (i = 1; i  archive.length; i++)
        {
                var code = archive[i]
                var s = dict[code]

                if (s !== undefined)
                {
                        dict[lastcode] = chain + s[0]
                        chain = s
                }
                else
                {
                        chain += chain[0]
                        dict[lastcode] = chain
                }       

                result += chain
                lastcode++
        }       

        return result
}

Применим эту функцию к архиву и получим исходный текст: lzw.decompress([0,1,2,4,6,5,0,3,9,3]) = 'ABCABCABCADBCAD'. Проверим как сожмёт этот метод более длинную строку из тех же символов:

str = 'ABCABCABCABBACACDACCABAABBACADADCACCABABBACACDADDACCC' +
        'CCCABBBBBABACACDADCACDADCABBCACADDDDDCCCABABBACCADAADBCAD'

arc = lzw.compress(str)
cmp = (str == lzw.decompress(arc))

alert([str.length, arc.length, cmp])

Получается, что в тексте str 110 символов, а в архиве arc 52 числа. Если для записи номера в файл требуется столько же места сколько для записи одного символа, то сжатие получается в 110/52 = 2.12 раза. Для реальных текстов где каждый символ это 2 байта места (юникод), а каждый номер это 2-байтное целое число сжатие получается в 4 раза. Если текст записан в UTF8 (1 байт для английских букв) или в кодировке Win1251 (1 байт для русских букв), а номер цепочки записывается двумя байтами, то сжатие получается в два раза.

Требования к тексту

Мы выяснили, что для упаковки и распаковки нужно знать алфавит, т.е. все возможные символы которые могут встретиться в тексте. Если в алфавите есть лишние символы которых в тексте нет, то алгоритму это не помешает, но если в алфавите нет каких то символов и в тексте встретится один из них, то упаковщику будет плохо. Алфавит можно добавлять к архиву: для больших текстов это незначительная добавка. Построить алфавит текста можно так:

lzw.charset = function(str)
{
        var chars = {}

        for (var i = 0; i  str.length; i++)
                chars[str[i]] = true

        var res = []

        for (var c in chars)
                res.push(c )

        return res
}

Второй важный момент это максимальное число различных цепочек. Номер цепочки будет кодироваться целым числом которое имеет ограниченный диапазон значений. Текст из 200,000 букв создаёт примерно 50,000 цепочек в словаре, поэтому размер номера должен быть хотя бы 16 бит = 2 байта. Для ещё больших текстов соответственно нужен ещё больший размер номера.

Пример

По этой ссылке можно скачать архив. В нём html страница с js файлом распаковщика. html + js весят примерно 40 кб. Загрузив страницу в браузер и посмотрев html код внутри тега body (это можно сделать в Chrome, например) можно посчитать, что там примерно 80,000 символов (html разметка и текст). Таким образом получилось сжатие в 2 раза.

Зачем это нужно?

Метод не претендует на полезность: я написал это для интереса, а не в практических целях. Вариант с сжатием страниц при передачи их от сервера к клиенту отпадает, потому что есть более удобный GZip. Однако есть случай когда это может пригодится. Вы наверно знаете, что на сайте провайдера мобильной связи (как это сказать нормально?) можно заказать отчёт деятельности своей симки за несколько месяцев. Отчёт обычно приходит в виде html страницы. Так вот, эту html страницу можно сжимать таким методом. Такие сайты предлагают присылать отчёт в виде zip архива, но ведь, чтобы открыть html файл из архива нужно сперва распаковать архив, а это лишнее действие.

pensionary.ru

Читатели рекомендуют также прочесть по этой тематике:

1. Node.JS / Асинхронное программирование, коллбеки и использование process.nextTick()
2. Блог компании Онлайн-Про / Как засоряют ТОП
3. Информационная безопасность / Upgrade
4. Читальный зал / Саммари на четыре книжки
5. Erlang/OTP / Использование Rebar и GProc