Лежит у меня старенький модуль, реализующий арифметическое кодирование. Что-то захотел довести его до ума и максимально оптимизировать. Непонятно зачем, но хочется.
Одно из узких мест такого сжатия – поддержка частоты встречи символов в случае использования адаптивной модели. Собственно, поддержка именно таблицы частот банальна, но алгоритму нужны частоты нарастающим итогом.
То бишь, если у нас алфавит из трех символов A, B, C, каждый из которых встречается 3, 5, 2 раза (это собственно и есть таблица частот), то для алгоритма нужно вот так: 3, 8, 10.
В исходном алгоритме, который я взял в качестве основы, использовались 16-битные беззнаковые целые. Достаточно быстрая реализация, но на больших объемах данных возникало переполнения таблицы частот, поэтому когда частота достигала максимально возможного значения, вся таблица просто делилась на два, что в общем, не очень эффективно. Это гарантированно происходило каждые 65536 символов.
Для решения этой проблемы я заменил 16-битное целое на 32-битное, что позволило просто забыть про деление на два, если не сжимать данные размером больше 4 ГиБ.
С другой стороны, при добавлении каждого очередного символа приходилось пересчитывать достаточно большую таблицу частот, хоть зачастую и не полностью.
В результате сейчас у меня две идеи: хранить в памяти только классическую таблицу частот, а нарастающий итог рассчитывать каждый раз при добавлении очередного символа. Плюсы: снижается количество операций с памятью, так как таблицу частот (без нарастающего итога) можно сделать 16-битной, иногда нормируя ее делением на 2 (но не каждые 65536 символов, реже) и избежать обильной записи в память.
Минус: для расчета нарастающего итога придется суммировать всю таблицу до нужно символа.
Вторая идея состоит в том, что бы хранить все же обе таблицы, одновременно запоминая то место, где нарастающий итог уже посчитан верно. Поэтому при расчете нарастающего итога для нового символа можно будет пересчитывать не всю таблицу, а только небольшую часть, надеюсь, гораздо меньшую, чем в первоначальном варианте.Минус здесь следующий: придется все же выполнять на каждой итерации достаточно много записей в память, хоть и не так много, как в моем первоначальном варианте.
На текущий момент у меня есть подозрение, что первая идея хороша для коротких алфавитов. Наверное, для 8-битного и меньше она будет оптимальна. А вот для длинных алфавитов, видимо, интереснее второй вариант.
Но пока до конца не уверен. Надо будет потестить что ли разные варианты.
Спасибо за очередную задачку :)))
ОтветитьУдалитьМожно попробовать использовать дерево для подсчета нарастающего итога:
- размер алфавита - степень двойки
- листья - классические частоты символов
- в каждом узле храним сумму частот его листьев (32-бит): в корне для всего алфавита, на следующем уровне для 1-й и 2-й половины, далее для всех четвертей и т.д. до листьев.
Для Вашего примера (с добавлением D=0): в корне храним сумму A+B+C+D=10, следующий уровень: A+B=8, C+D=2, и далее A=3, B=5, C=2, D=0.
Если нужно найти итоговое значение скажем для C:
1. Правая половина, значит вкючаем в сумму значение из левого A+B узла (8)
2. На C+D узле идем влево, значит ничего не добавляем
3. Доходим до листа C=2
4. И того 8 + 2 = 10
За log(N) можно как добавить новый символ так и подсчитать итоговое значение.
По памяти: 2 * N - 1, но дерево можно уменьшить в 2 раза! Хранить одновременно сумму для левого, правого и поддерева целиком избыточно, так как левый+правый всегда равен поддереву целиком. Вместо этого в узле достаточно хранить сумму листьев для его левого поддерева (очень коряво написал, надеюсь понятно), и плюс сумму всех частот в отдельной переменной для всего дерева, этого будет достаточно чтобы восстановить сумму для правый поддеревьев. В памяти это будет занимать 1 (полная сумма) + (N-1 дерево) элементов = N
Хранить дерево на массиве: 0-й элемент - корень, далее следующий уровень и т.д.
Думаю будет более-менее оптимально с точки зрения кэша: верх дерева будет горячий и не будет покидать кэш, плюс читать/обновлять нужно только log(N) элементов.
Да, я уже основательно подзабыл суть алгоритма, вчера вот посидел, поразбирался. На каждой итерации сжатия (или восстановления) нужна следующая информация: частота с накоплением текущего и предыдущего символа, а также общее количество закодированных символов - фактически частота с накопление последнего символа.
УдалитьАдаптивная модель строится немного не так, как ты описал. Так как у нас есть какие-то представления о характере данных, то мы перед сжатием заполняем частоты символов сообразно этому представления, стараясь брать как можно более маленькие значения (что бы максимум отсрочить переполнения).
В простейшем случае мы не знаем о частотном распределение символов в тексте, поэтому можем предположить их равновероятное появление. Тогда первоначальная модель будет иметь следующий вид для алфавита из четырех символов: A=B=C=D=1. То есть ноля тут быть не может, ибо тогда мы утверждаем, что соответствующий символ просто не может появиться в тексте. Точно так же обычно в адаптивной модели обычно представлен весь возможный алфавит (по той же причине: мы не уверены абсолютно, что какой-либо символ не встретится в тексте).
С переходом к частотам с накоплением получаем A=1, B=2, C=3, D=4.
Далее начинаем кодировать и нам встречается первым символ D. Для сжатия на потребуются частоты символов D (два раза) и C, то есть значения 3 и 4.
После сжатия символа меняем модель: A=B=C=1, D=2; соответственно с накоплением A=1, B=2, C=3, D=5.
Следующий символ A. Нам нужно значение А=1, предыдущего символа, которого нет, значит 0 и последнего символа D=5; После чего меняем модель A=2, B=C=1, D=2; A=2, B=3, C=4, D=6.
Следующий символ С. Нам нужны С=4, B=3, и D=6. И так далее.
То есть твоя идея очень интересна, но я пока не очень понял, насколько будет выигрыш, особенно в случае добавления символа C в примере. При использовании просто массива вида array['A'..'D'] of UInt32 для получения данных нужно просто по индексу символа обратиться, но при пересчете статистики нужно изменять достаточно большое количество элементов.
> строится немного не так, как ты описал
УдалитьВ примере я добавил D=0, только чтобы размер словаря стал равен степени двойки, нужно было назвать ее PAD (padding) вместо D, а значение все равно 0, так как это не существующий символ.
> но при пересчете статистики нужно изменять достаточно большое количество элементов.
Но ведь пересчитывать статистку нужно после сжатия каждого символа? В таком случае сложность изменяется с O(N) до O(logN), но конечно с несколько большей константой, но при каком-то размере алфавита оно должно стать быстрее :)))
Попробую описать более подробнее, на Вашем примере:
Чтобы проще было понять алгоритм, я начну с дерева с избыточной информацией. Узел дерева описываю как XY=Z, Z - сумма частот символов от X до Y.
Начальное дерево: корень AD=4, промежуточный уровень: AB=2, CD=2, листья A=B=C=D=1
Кодируем первый символ D:
- общее число символов всегда в корне дерева: total=AD=4
- считаем totalPrev: проходим по дереву до D: AD -> (right) CD -> (right) D, если идем в правый узел, то левый добавляем в totalPrev получаем : totalPrev = AB + C = 2 + 1 = 3
- totalD = totalPrev + D = 3 + 1 = 4
- увеличиваем все узлы при проходе на единицу, получаем AD=5, AB=2, CD=3, A=B=C=1, D=2
Далее кодируем A:
- общее число элементов total=AD=5
- путь: AD -> (left) AB -> (left A), правых поворотов нет, значит totalPrev=0
- totalA = totalPrev + A = 0 + 1 = 1
- обновленное дерево: AD=6, AB=3, CD=3, A=2, B=C=1, D=2
Далее C:
- total=AD=6
- путь: AD -> (right) CD -> (left) C, totalPrev = AB = 3
- totalC = totalPrev + C = 3 + 1 = 4
Вроде все получается, все числа сходятся, за один проход по дереву находятся все 3 значения и обновляется дерево :)
Размер такого дерева 2 * N - 1, но половина информации в нем избыточна, на алфавите из 4-х символов пример не особо читабелен, пример для 8 символов с вероятностей 1.
Дерево описанное выше:
AH=8, AD=EH=4, AB=CD=EF=GH=2, A=B=C=D=E=F=G=H=1 всего 15 узлов
Но так как значение в узле всегда равно сумме значений его левого и правого узлов, можно выбросить правые значения и подсчитывать их в процессе, получаем следующее дерево:
- корень: AD=4, следующий уровень: AB=EF=2, листья: A=C=E=G=1 (сохраняем частоты нечетных символов, далее нечетных пар и т.д., а под конец 1-й (нечетной) половины)
- и отдельно сохраняем полное число символов total=8
По "маленькому" дереву легко восстановить полноценное, например:
- EH=total-AD=8-4=4
- GH=EH-EF=4-2=2
- H=GH-G=2-1
И при этом это "маленькое" дерево даже упрощает обход описанный выше и занимает в 2 раза меньше места в кэше, что возможно даст некоторое ускорение.
Да, похоже, это в самом деле очень интересный вариант, который точно стоит потестить. Попробую его как-нибудь реализовать. Видимо, дерево в сокращенном виде точно поместиться в исходную таблицу частот. Главное придумать, как быстро и эффективно ходить по такому дереву.
УдалитьЕще думаю что и обратный процесс по поиску символа по его частоте с накоплением, получится реализовать также быстро.
> Попробую его как-нибудь реализовать.
УдалитьБуду ждать результаты сравнения с другими реализациями :)))
> как быстро и эффективно ходить по такому дереву.
Я бы сохранял по слоям, сначала корень, дальше целиком 2-й уровень и т.д. в конце подряд листья, если массив индексируется с 0, то у i-ого узла left=i*2+1, right=i*2+2
> и обратный процесс по поиску символа по его частоте с накоплением, получится реализовать также быстро.
Вроде да, вся информация есть для этого, за log(N) находится символ и узлы дерева уменьшаются на единицу
> Я бы сохранял по слоям, сначала корень, дальше целиком 2-й уровень и т.д. в конце подряд листья,
Удалить> если массив индексируется с 0, то у i-ого узла left=i*2+1, right=i*2+2
Я так понимаю, это вариант для полного дерева. Для усеченного наполовину будет немного не так. Пока не придумал как.
Может быть мы про разное говорим?
УдалитьЯ предлагаю хранить усеченное дерево в памяти на массиве плюс как описал выше (оно ведь само по себе тоже дерево) и полное число элементов в отдельной переменной. Все операции производить над виртуальным полноценным деревом, рассчитывая его при проходе по усеченному дереву.
Для примера проход AH -> EH -> EF -> F по виртуальному полному дереву для 8 символов с расчетом значений для текущего узле (curValue), левого (leftValue) и правого (rightValue), используя информацию о родительском узле:
AH (root):
- leftIdx = 0 (индекс AD, корень усеченного), curValue = total = 8
- leftValue = tree[leftIdx] = AD = 4, rightValue = curValue - leftValue = 8 - 4 = 4
EH (right):
- leftIdx = right(leftIdx) (индекс EF усеченного), curValue = rightValue = 4
- leftValue = tree[leftIdx] = EF = 2, rightValue = curValue - leftValue = 4 - 2 = 2
EF (left):
- leftIdx = left(leftIdx) (индекс E усеченного), curValue = leftValue = 2
- leftValue = tree[leftIdx] = E = 1, rightValue = curValue - leftValue = 2 - 1 = 1
F (right)
- curValue = rightValue = 1, остальное не нужно расчитывать так как F - лист.
Поверх этого нужно еще реализовать расчет частоты ну и конечно обновлять усеченное дерево, когда в виртуальном нужно увеличить/уменьшить левые узлы.