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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 5.00
gimeo
0 / 0 / 0
Регистрация: 19.02.2012
Сообщений: 4
#1

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

19.02.2012, 13:17. Просмотров 2584. Ответов 10
Метки нет (Все метки)

Предыстория: одним солнечным утром, когда был уже совсем вечер, решил я написать архиватор. Просканировав достаточно большое количество ресурсов, понял, что LZ78 - моя мечта, любовь с первого взгляда, начал реализовывать программно и столкнулся с невообразимых масштабов проблемой.

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

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


pss Не знал, куда написать, думаю, администрация перенесёт тему в нужный раздел.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.02.2012, 13:17
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм LZ78 или трудности реализации (C++):

Трудности в реализации класса - C++
Не могу понять, почему не работают конструкторы класса... Прошу понятного объяснения=) вот код 1 файл #ifndef ___MAS #define ___MAS...

Алгоритм для реализации оператора "побитовое исключающее ИЛИ" - C++
Помогите пожалуйста не могу делать. Для заданных двух целых чисел предложите описание алгоритма для реализации оператора «побитовое...

трудности с пониманием синтаксиса на примере реализации паттерна "стратегия" - C++
#include <iostream> #include <string> // Иерархия классов, определяющая алгоритмы сжатия файлов class Compression { ...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; void lab () { int s1 = 0; int s2 =...

Алгоритм реализации двоичного дерева - C++
Нужно написать реализацию двоичного дерева с использованием шаблонов в упрощенном виде следуя конвенциям STL контейнеров. Основные...

Разработать форму и алгоритм для реализации задачи: Игра: Случайное число - C++
Привет, народ! Сессия на носу, задали лабораторку на С#, надо сдать до 14(, а я в нем ноль, последнее время сам по книжке практикую С++....

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

как кодируются:
http://i41.tinypic.com/2ed2gkg.png
0
OstapBender
583 / 522 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
19.02.2012, 20:54 #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, если нет то добавляешь в словарь соотв. новую ячейку.
0
gimeo
0 / 0 / 0
Регистрация: 19.02.2012
Сообщений: 4
19.02.2012, 22:38  [ТС] #5
я спрашивал не как мне эти пары составить и, тем более, не как их закодировать, а как раскодировать последнюю последовательность (0A0B10C11A010A100A110B)

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

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

Добавлено через 7 минут
Цитата Сообщение от Mayonez Посмотреть сообщение
?????
использование чёрно-красных деревьев намного увеличат скорость выполнения алгоритма
0
murderer
3201 / 1425 / 75
Регистрация: 06.10.2010
Сообщений: 3,097
20.02.2012, 18:07 #11
Длина индекса словаря равна логарифму по основанию 2 от длины словаря. Длина символа всегда равна 8 битам.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.02.2012, 18:07
Привет! Вот еще темы с ответами:

Запись в файл результата работы алгоритма lz78 - C++
Пробую реализовать алгоритм сжатия lz78. Сжать у меня получается сжать строку, получаю примерно вот это Подскажите, что мне делать с...

Нужны задачи для новичка или способ реализации кода - C++
Дайте мне какую-нить задачу, которая будет больше на логическое мышление и решения логические должны быть, нежели на большое знание языка...

DES / AES (Готовый пример или описание реализации различных этапов) - C++
Где можно доходчиво почитать именно о реализации этих алгоритмов, может кто знает и может подсказать. Или же дайте ссылку если где-то есть...

Подскажите где ошибка, или может есть другой вариант реализации кода - C++
// Упорядочить статический массив(заполненый случайными числами), чтобы в нём чередовались чётные и нечётные элементы, разницу записываем в...


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

Или воспользуйтесь поиском по форуму:
11
Yandex
Объявления
20.02.2012, 18:07
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru