Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
1 / 1 / 0
Регистрация: 05.12.2015
Сообщений: 33

Арифметическое кодирование двоичной последовательности

13.12.2015, 23:23. Показов 3007. Ответов 0

Студворк — интернет-сервис помощи студентам
Доброго времени суток. Суть проблемы такова: надо кодировать двоичную последовательность арифметическим кодированием. Перелистала много статей, книг, но нигде не нашла готовой простой реализации. Или программирование слишком сложное, или ничего просто не работает, или работает, но не так, как надо. В итоге решила написать сама.
Последовательность в районе 217 (может быть меньше на 1-50) символов. Реализую по статьям напрямую, без кумулятивных вероятностей и прочего.
Сложности:
1. 217 символов - довольно много. В double даже близко не хватает точности для кодирования. Есть идея разбиваться на блоки и кодировать их отдельно, но, может, есть ещё способы.
(Такая магия с частотами нужна потому, что на декодер мы не можем передавать ни частоту, ни длину исходной последовательности)
2. Собственно, да. Для декодирования нам нужна длина исходной последовательности, но мы не должны её передавать. И на входе она может быть разной. Как же тогда нам сообщать декодеру, когда надо остановиться.
3. Энтропия. Она вроде как и должна отрезать лишнее в нашем закодированном числе (т.е. вместо 0,672387821 мы должны получать, например, 6723 в двоичном виде). Однако у меня по расчетам она выходит маленькая, а если вместо нее брать длину, на которой верхняя и нижняя граница начинают отличаться, то длина закодированного слова становится больше длины исходного

Кодирование
Java
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
public class ArithmCoding {
  public static void arithmeticCoding(String input) {
        int i;
        char[] inputArray = input.toCharArray();
        int lengthOfInput = input.length();
 // считаем, что изначально частота неизвестна, поэтому будем корректировать её в процессе кодирование/декодирования
        int costOne = 1;
        int costZero = 1;
        double pOne = 0.5;
        double pZero = 0.5;
 
        double L = 0; // нижняя граница отрезка
        double H = 1; // верхняя граница отрезка
// будем считать изначально, что при [ L .. pOne ) у нас выбирается 1, и при [ pOne .. H ) - 0
for (i = 0; i < lengthOfInput; i++) {
            if (inputArray[i] == '1') {
                H = L + (H - L) * pOne;
costOne++;
pOne = costOne * 1./(costOne+costZero);
System.out.println(" pOne = " + pOne);
} else if (inputArray[i] == '0') {
                L = (H - L) * (1-pOne) + L;
costZero++;
pZero = costZero* 1./(costOne+costZero);
System.out.println(" pZero = " + pZero);
} else System.out.println("Incorrect symbol");
}
        double entropia =  (-  (Math.log(pOne)/Math.log(2)) - (Math.log(1-pOne)/Math.log(2))) + 1;
        double codeWord = (H+L)/2;
System.out.println("кодовое слово = " + codeWord);
String codeWordString = Double.toString(codeWord);
codeWordString = codeWordString.substring(2, 2  + (int)entropia);
System.out.println("кодовое слово строкой = " + codeWordString + "  бинарное   " + Long.toBinaryString(Long.valueOf(codeWordString)) + "  длина бинарного слова " +Long.toBinaryString(Long.valueOf(codeWordString)).length());
}
Декодирование
Java
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
public static void arithmeticDecoding(String output, int n) {
        int i;
        char[] outputArray = output.toCharArray();
        int lengthOfOutput = output.length();
 
        double L = 0; 
        double H = 1; 
 
        int costOne = 1;
        int costZero = 1;
        double pOne = 0.5;
        double pZero = 0.5;
 
        String decoding = "";
        Double word = Double.valueOf(output);
        for (i = 0; i < n; i++) {
 
            if (word > L && word < (L + (H - L) * pOne)) {
                H = L + (H - L) * pOne;
                decoding = decoding + "1";
                costOne++;
                pOne = costOne * 1. / (costOne + costZero);
                System.out.print(" pOne = " + pOne);
 
            } else if (word < H && word > (L + (H - L) * pOne)) {
                decoding = decoding + "0";
                L = (H - L) * (1 - pOne) + L;
                costZero++;
                pZero = costZero * 1. / (costOne + costZero);
                System.out.print(" pZero = " + pZero);
 
            } else {
                System.out.println("Incorrect symbol");
            }
        }
 
        System.out.println("Наша последовательность     " + decoding);
    }
}
Помогите, пожалуйста, разобраться что к чему. Заранее благодарю за помощь, идеи, указания на ошибка. Статьи по АК с 1-2 страницы гугла кидать не надо, я видела((
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
13.12.2015, 23:23
Ответы с готовыми решениями:

Арифметическое кодирование
Сразу скажу что тема для меня не новая, 25 лет назад читал про это и даже что-то с преподом обсуждали, но не понял тогда не понимаю и...

Арифметическое кодирование в vp8
Всем привет, возник такой вопрос. В формате vp8 используется арифметическое кодирование. Имеется функция token_prob_update() ...

Арифметическое кодирование/сжатие
Здравствуйте! С помощью арифметического сжатия/кодирования требуется закодировать сообщение &quot;информационный&quot;, а затем...

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
13.12.2015, 23:23
Помогаю со студенческими работами здесь

Арифметическое кодирование.
Восстановите исходный текст из закодированной цепочки в 2 бита, равных «11» (число 0,11(двоичная СС)=0,75(десятичная СС)), используя...

Арифметическое кодирование.
Арифметическое кодирование динамическое. Слово-вычисление

Арифметическое кодирование
Добрый день. задали мне лабу: реализовать арифметическое кодирование. но мне не всё понятно в реализации... Надо ли разбивать на блоки...

Арифметическое кодирование
Мне задали задание по арифм. кодировании. Я что-то не очень знаю что это такое и зчем его едят.... Прошу вас о помощи... Конкретнее было...

Арифметическое кодирование на С++
Здравствуйте. Такая проблема: нужно реализовать алгоритм арифметического кодирования и декодирования. Кодирование у меня получилось. Но...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru