Удалось добиться такого эффекта за счёт использования деревьев секущих функций, которые позволяют получать среднюю длину кода почти как у теоретического Хаффмана.
В алгоритме и правда нет компенсации движения, тем не менее он весьма неплохо показывает себя на обычных записях. В качестве эксперимента алгоритмом был сжат полный сезон сериала Star Trek. Итоговый коэффициент сжатия оказался даже чуть больше, чем расчётный.
Я даже могу предположить, что это за причина: энтропийные префиксные кодировщики только в теории выглядят красиво, на практике реализовать их весьма тяжело (из-за ошибок с округлением или переполнением), кроме того процесс кодирования условно сводится к поиску соответствующего элемента среди всех листьев дерева и восстановлению траектории по дереву. Если листьев несколько сот миллионов это довольно тяжело.
Основная «фишка» данного метода — использование деревьев секущих, что позволяет строить префиксе деревья и кодировать на их основе почти в реальном времени.
Конечно можно и так поступать. Возможно многие так и делают, но разве это повод не изобретать что-то новое и более эффективное? Кроме того Yuls(Max) использует преобразование цветовых пространств, что привносит ошибки. Если разрешить преобразование цветовых пространств для МФС коэффициент сжатия станет >5, а это уже выигрыш не на 2%, а как минимум на 40%.
Я не спорю, что у метода достаточно узкая область применения, но в той сфере, где он используется (медицинские записи) он показывает большую эффективность. И выигрыш в степени сжатия в несколько процентов на практике превращается в сотни мегабайт, что на установках с ограниченными ресурсами очень важно.
Код выложу на github, когда приведу его в порядок. Сейчас там очень много лишнего. Скорость сжатия пока оставляет желать лучшего секунда видео жмётся где-то за 1.2-1.5 секунды реального времени, но есть обоснованное подозрение, что после приведения кода в порядок скорость вырастет.
Если у нас алфавит из десятков миллионов, то и размер описания дерева тоже будет — десятки миллионов байтов.
И экономия хотя бы одного бита на символ выльется в сотни мегабайт экономии.
Кодирование Хаффмана в принципе не очень подходит для решения задач в таких масштабах. В моей работе используется разработанный специально для подобных задач вид бинарных деревьев.
Особенностью нашего метода является то, что сжимаются массивы из миллиардов элементов, при этом алфавиты составляют десятки миллионов элементов. При таких масштабах даже концептуально простые алгоритмы реализовать становится если не невозможно, то очень и очень сложно. А учитывая, что работа имеет не только академическую, но и практическую ценность, вычислительную сложность тоже надо учитывать.
Напишу обязательно. Я использую не Хаффмана, а кодирование с помощью специального бинарного дерева, которые разработали на кафедре. А арифметическое кодирование тут применять вообще равносильно самоубийству. Вы хоть представляете какая точность арифметики понадобится?
Касаемо сути. Эвристики используются для того, чтобы потенциально наиболее сильные ходы рассматривались раньше. Логичным способом сравнения эффективности традиционных и «машинных» эвристик является сравнение индексов действительно сильных ходов (подтверждённых просчётом дерева) в массивах упорядоченных по различным оценкам. Сравнение эффективности на основе количества вызовов процедуры отсечения кажется мне богомерзким извращением.
1. Ты умудрился так написать про AB-отсечение, что я его наконец-то понял.
2. Идея использовать машинное обучение для предварительной сортировки ходов порочна по сути своей.
3. В сёги я играю лучше.
Основная «фишка» данного метода — использование деревьев секущих, что позволяет строить префиксе деревья и кодировать на их основе почти в реальном времени.
И экономия хотя бы одного бита на символ выльется в сотни мегабайт экономии.
Кодирование Хаффмана в принципе не очень подходит для решения задач в таких масштабах. В моей работе используется разработанный специально для подобных задач вид бинарных деревьев.
2. Идея использовать машинное обучение для предварительной сортировки ходов порочна по сути своей.
3. В сёги я играю лучше.