Арифметическое кодирование Java — поиск диапазонов символов

Я пытаюсь воссоздать реализацию арифметического кодирования на Java, как описано в этой ссылке, в разделе «Арифметическое кодирование: как это работает»: ссылка

Я нахожусь в точке, где отдельным символам нужно присвоить диапазон вдоль линии вероятности. Однако у меня возникают некоторые проблемы с созданием правильных диапазонов. В моем коде, показанном ниже, это выполняется с помощью setRanges(). Ожидаемый результат должен быть таким:

Character Ranges -

            0.0 - 0.09999999999999999
A           0.1 - 0.19999999999999999
B           0.2 - 0.29999999999999999
E           0.3 - 0.39999999999999999
G           0.4 - 0.49999999999999999
I           0.5 - 0.59999999999999999
L           0.6 - 0.79999999999999999
S           0.8 - 0.89999999999999999
T           0.9 - 0.99999999999999999

Мой текущий вывод таков:

Диапазоны символов -

            0.0 - 0.09999999999999999
A           0.1 - 0.2
B           0.2 - 0.30000000000000004
E           0.30000000000000004 - 0.4
G           0.4 - 0.5
I           0.5 - 0.6
L           0.6 - 0.8
S           0.8 - 0.9
T           0.9 - 1.0

Я не уверен, есть ли лучший способ закодировать мой метод setRanges(), или это просто результат ошибок округления.

Вот класс Range, который просто содержит низкое и высокое значения с плавающей запятой:

public class Range {

    private double low, high;

    public Range(double low, double high) {
        this.low = low;
        this.high = high;
    }

    public String toString() {
        return low + " - " + high;
    }

}

Метод:

import java.util.TreeMap;

    public static TreeMap<Character, Range> setRanges(TreeMap<Character, Double> treeMap) {
        TreeMap<Character, Range> rangeMap = new TreeMap<>();
        double currentValue;
        double previousValue = 0;
        double runningTotal = 0;

        for(Character key : treeMap.keySet()) {
            currentValue = treeMap.get(key) + runningTotal;
            rangeMap.put(key, new Range(previousValue, currentValue - 0.00000000000000001));
            previousValue = currentValue;
            runningTotal += treeMap.get(key);
        }
        return rangeMap;
    }

}

java compression precision rounding-error
person Community    schedule 04.12.2015    source источник
comment
абсолютно необходимо изменить код из-за 0.000000000001?   -  person nafas    schedule 04.12.2015
comment
Меня попросили реализовать это для школьных занятий, на сайте говорится: «Обратите внимание, что персонаж «владеет» всем, вплоть до большего числа, но не включая его. Так что буква «Т» на самом деле имеет диапазон 0,90 – 0,9999….».   -  person    schedule 04.12.2015
comment
Как вы также можете прочитать в этом руководстве, никто никогда не реализует арифметическое кодирование с десятичными знаками. В нем есть все эти сумасшедшие точные ловушки, о которых трудно позаботиться, и он становится очень медленным по мере роста производительности.   -  person harold    schedule 04.12.2015

Ответы (1)


arrow_upward
1
arrow_downward

Я думаю, вам нужно использовать BigDecimal для этой точности. С опцией округления 128 или без. Смотри ниже:

double first = 1d;
double second = 0.00000000000000001d;

System.out.println("Db --> " + (first - second));

BigDecimal firstBd = new BigDecimal(first);
BigDecimal secondBd = new BigDecimal(second);
BigDecimal resultBd = firstBd.subtract(secondBd);

System.out.println("32 --> " + resultBd.round(MathContext.DECIMAL32));
System.out.println("64 --> " + resultBd.round(MathContext.DECIMAL64));
System.out.println("128--> " + resultBd.round(MathContext.DECIMAL128));
System.out.println("Unl--> " + resultBd);

Выход:

Db --> 1.0
32 --> 1.000000
64 --> 1.000000000000000
128--> 0.9999999999999999899999999999999993
Unl--> 0.9999999999999999899999999999999992845757594537807549147194381507675227382936355979836662299931049346923828125

person hsnkhrmn    schedule 04.12.2015
comment
Уровень точности произвольный, в работе говорится: «Тип данных с плавающей запятой двойной точности может использоваться для хранения закодированного значения, но имейте в виду, что в соответствии со стандартом IEEE 745 52-битная мантисса обеспечивает точность только до 16 цифр. Поэтому длина кодируемой строки должна быть соответствующим образом ограничена». Я просто использовал отрицательное значение 0,000000000001, чтобы получить наименьшую цифру, которую двойное число может позволить ниже целого числа. - person ; 04.12.2015
comment
Я проверил и вижу, что с двойным 0,0000000000000001d это предел, который вы можете вычесть из 1. Результат будет: Db --> 0,99999999999999999 Однако, когда вы добавите еще один «0» после точки, результат станет: Db --> 1,0 Итак, если сначала достаточно для вас, вы можете игнорировать решение BigDecimal и продолжать использовать double. Это может варьироваться в зависимости от установки 32-64-разрядной версии Java. - person hsnkhrmn; 04.12.2015
comment
Да, это выглядит так, однако, когда я использую это, например, в первом диапазоне, я все равно получаю 0,0 - 0,09999999999999991, что, как я полагаю, является просто неизбежной ошибкой округления. Спасибо за вашу помощь - person ; 04.12.2015