Форум программистов, компьютерный форум CyberForum.ru

Алгоритм LZ78 или трудности реализации - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 5.00
gimeo
 Аватар для gimeo
0 / 0 / 0
Регистрация: 19.02.2012
Сообщений: 4
19.02.2012, 13:17     Алгоритм LZ78 или трудности реализации #1
Предыстория: одним солнечным утром, когда был уже совсем вечер, решил я написать архиватор. Просканировав достаточно большое количество ресурсов, понял, что LZ78 - моя мечта, любовь с первого взгляда, начал реализовывать программно и столкнулся с невообразимых масштабов проблемой.

История: В соответствии с алгоритмом исходная строка (допустим ABBCBCABABCAABCAAB) сжимается в последовательность пар ((0, A) (0, B) (2, C) (3, A) (2, A) (4, A) (6, B)), далее эти пары записываются в выходной файл, причём числа записываются побитово (0A0B10C11A010A100A110B).

Вопрос: Собственно как теперь считать записанную информацию из файла и преобразовать в пары?


pss Не знал, куда написать, думаю, администрация перенесёт тему в нужный раздел.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
19.02.2012, 18:15     Алгоритм LZ78 или трудности реализации #2
для начала было бы неплохо уточнить по какой логике формируются пары, далеко не все тут знакомы с алгоритмами архивации
gimeo
 Аватар для gimeo
0 / 0 / 0
Регистрация: 19.02.2012
Сообщений: 4
19.02.2012, 20:28  [ТС]     Алгоритм LZ78 или трудности реализации #3
как "получаются" пары:
http://i41.tinypic.com/ape8th.png

как кодируются:
http://i41.tinypic.com/2ed2gkg.png
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
19.02.2012, 20:54     Алгоритм LZ78 или трудности реализации #4
ну начни с описания структуры которая будет хранить данные, допустим как-то так:
C++
1
2
3
4
5
6
7
struct cell {
 
    std::pair<int,char> data;
    int index;
    std::string string;
 
};
затем словарь:
C++
1
    std::vector<cell> dictionary;
ну а уж сам алгоритм напишешь, берёшь по 1 букве и прибавляешь к временной строке (temp).
ищешь по всему словарю, есть ли в словаре такая ячейка с полем string == temp, если есть то +1 буква к temp, если нет то добавляешь в словарь соотв. новую ячейку.
gimeo
 Аватар для gimeo
0 / 0 / 0
Регистрация: 19.02.2012
Сообщений: 4
19.02.2012, 22:38  [ТС]     Алгоритм LZ78 или трудности реализации #5
я спрашивал не как мне эти пары составить и, тем более, не как их закодировать, а как раскодировать последнюю последовательность (0A0B10C11A010A100A110B)

ps: если реализовывать хранение пар средствами stl, то о быстродействии можно забыть
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
19.02.2012, 23:06     Алгоритм LZ78 или трудности реализации #6
Цитата Сообщение от gimeo Посмотреть сообщение
я спрашивал не как мне эти пары составить и, тем более, не как их закодировать, а как раскодировать последнюю последовательность (0A0B10C11A010A100A110B)
читай 0 и 1 в строку затем через atoi перегоняй в число
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.02.2012, 23:32     Алгоритм LZ78 или трудности реализации #7
Цитата Сообщение от OstapBender Посмотреть сообщение
ну а уж сам алгоритм напишешь, берёшь по 1 букве и прибавляешь к временной строке (temp).
ищешь по всему словарю, есть ли в словаре такая ячейка с полем string == temp, если есть то +1 буква к temp, если нет то добавляешь в словарь соотв. новую ячейку.
тут словарь не обязательно использовать. Достаточно массива в каждом элементе которого будет хранится 2 числа: индекс начала подстроки в формируемой строке и ее длина.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
19.02.2012, 23:37     Алгоритм LZ78 или трудности реализации #8
И сложность алгоритма O(n) будет, где n - длина начальной строки.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
20.02.2012, 00:04     Алгоритм LZ78 или трудности реализации #9
Цитата Сообщение от gimeo Посмотреть сообщение
если реализовывать хранение пар средствами stl, то о быстродействии можно забыть
?????
gimeo
 Аватар для gimeo
0 / 0 / 0
Регистрация: 19.02.2012
Сообщений: 4
20.02.2012, 18:05  [ТС]     Алгоритм LZ78 или трудности реализации #10
Цитата Сообщение от OstapBender Посмотреть сообщение
читай 0 и 1 в строку затем через atoi перегоняй в число
Вот представь: есть файл, в котором записана последовательность 0010000010010000101001000011, иначе говоря три пары (0, A) (0, B) (2, C) вот и каким образом нужно считывать информацию из выходного файла, если длину представления записываемого числа я не знаю, известна только лишь длина символа; или может есть какой-то другой способ записи этих данных.

да, про atoi: преобразовывает строку в число и записывает его в тип integer (4 байта!), хотя можно число 2 представить всего двумя битами

Добавлено через 7 минут
Цитата Сообщение от Mayonez Посмотреть сообщение
?????
использование чёрно-красных деревьев намного увеличат скорость выполнения алгоритма
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.02.2012, 18:07     Алгоритм LZ78 или трудности реализации
Еще ссылки по теме:

Алгоритм или-не C++
Разработать форму и алгоритм для реализации задачи: Игра: Случайное число C++
Нужны задачи для новичка или способ реализации кода C++

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

Или воспользуйтесь поиском по форуму:
murderer
3175 / 1398 / 69
Регистрация: 06.10.2010
Сообщений: 3,017
20.02.2012, 18:07     Алгоритм LZ78 или трудности реализации #11
Длина индекса словаря равна логарифму по основанию 2 от длины словаря. Длина символа всегда равна 8 битам.
Yandex
Объявления
20.02.2012, 18:07     Алгоритм LZ78 или трудности реализации
Ответ Создать тему
Опции темы

Текущее время: 23:21. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru