Вход | Регистрация

Информационные технологии :: Математика и алгоритмы

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

Арифметическое кодирование.
Я
   megabax
 
27.10.16 - 10:04
Подскажите пожалуйста идею, как решить проблему потери точности при арифметическом кодировании. Допустим есть у меня вот такой код на C#
            low = 0;
            high = 1;
            int i = next_simbol();
            while (i != -1)
            {                
                double range = high - low;
                double dhigh = range * dictionary.items[i].p;
                if (i > 0)
                {
                    low = low + range * dictionary.items[i - 1].p;
                }
                high=low+dhigh;
                i = next_simbol();
            }
где low и high переменные типа double. Но уже при кодировании 21 буквы high и low отличаются только одной значащей цифрой, а дальше они вообще сливаются. Как можно решить эту проблему? Написать свои классы супервысокой точности? Или каким-то волшебным образом интервал сразу кодировать в бинарном коде?
 
 
   megabax
 
1 - 27.10.16 - 10:35
up
   Волшебник
 
Модератор
2 - 27.10.16 - 10:38
перестать заниматься хернёй
   Кирпич
 
3 - 27.10.16 - 10:38
нифига не понял где тут дебет и где кредит
   megabax
 
4 - 27.10.16 - 10:41
(2) Это не херня, это лабораторная работа в институте.
   Волшебник
 
Модератор
5 - 27.10.16 - 10:42
(4) все лабораторные работы в институтах - херня
   ovrfox
 
6 - 31.10.16 - 20:02
Алгоритм, который здесь указан ничего не кодирует. (В смысле не уменьшает размер). Соответственно данное суммирование быстро приводит к переполнению переменных.

Советую проверить алгоритм.
   megabax
 
7 - 31.10.16 - 20:29
(6)Да, вы правы. Переделал вот так:
            low = 0;
            high = 1;
            StringBuilder sb = new StringBuilder();

            int i = next_simbol();
            while (i != -1)
            {
                double range = high - low;

                RangeDictionaryItem item = dictionary.items[i] as RangeDictionaryItem;

                high = low + range * item.end;
                low = low + range * item.beg;

                sb.AppendFormat("{0};[{1};{2});{3};{4};{5}\n", i, low, high, range, item.beg, item.end);

                i = next_simbol();
            }
И обратный алгоритм:
            high = 1;
            low = 0;
            for (int i = 1; i <= count; i++)
            {
                DictionaryItem item=dictionary.items.Find(
                    delegate(DictionaryItem litem)
                    {
                        return (litem as RangeDictionaryItem).beg <= (value - low) / (high - low)
                            && (value - low) / (high - low) < (litem as RangeDictionaryItem).end;
                    }
                );
                output_text += item.simbol;

                double range = high - low;
                high = low+range * (item as RangeDictionaryItem).end;
                low = low + range * (item as RangeDictionaryItem).beg;
            }

но проблема осталось. Успешно кодирует и декодирует только примерно 10 символов, а дальше уже не может отработать обратное декодирование.
Возникла идея double заменить на decimal, но он тоже не безграничный.
Вот непонятно, как тут быть? Кодировать блоками? Или вводить какие-то коэффициенты и когда разница становиться маленькой, умножать на них? Или может разработать свои суперточные числа?
   NorthWind
 
8 - 31.10.16 - 21:19
(7) >> Или может разработать свои суперточные числа?
Зачем? Если вам не хватает того, что после запятой, вы можете использовать то, что до.

Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Тема не обновлялась длительное время, и была помечена как архивная. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.
Рекламное место пустует