Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/15: Рейтинг темы: голосов - 15, средняя оценка - 4.80
gimeo
0 / 0 / 0
Регистрация: 19.02.2012
Сообщений: 4
1

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

19.02.2012, 13:17. Просмотров 2787. Ответов 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
Ответы с готовыми решениями:

Трудности в реализации класса
Не могу понять, почему не работают конструкторы класса... Прошу понятного...

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

трудности с пониманием синтаксиса на примере реализации паттерна "стратегия"
#include <iostream> #include <string> // Иерархия классов, определяющая...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки )
#include "stdafx.h" #include <iostream> #include <conio.h> using...

Алгоритм реализации двоичного дерева
Нужно написать реализацию двоичного дерева с использованием шаблонов в...

10
OstapBender
584 / 523 / 75
Регистрация: 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
584 / 523 / 75
Регистрация: 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
584 / 523 / 75
Регистрация: 22.03.2011
Сообщений: 1,585
19.02.2012, 23:06 6
Цитата Сообщение от gimeo Посмотреть сообщение
я спрашивал не как мне эти пары составить и, тем более, не как их закодировать, а как раскодировать последнюю последовательность (0A0B10C11A010A100A110B)
читай 0 и 1 в строку затем через atoi перегоняй в число
0
valeriikozlov
Эксперт С++
4686 / 2512 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
19.02.2012, 23:32 7
Цитата Сообщение от OstapBender Посмотреть сообщение
ну а уж сам алгоритм напишешь, берёшь по 1 букве и прибавляешь к временной строке (temp).
ищешь по всему словарю, есть ли в словаре такая ячейка с полем string == temp, если есть то +1 буква к temp, если нет то добавляешь в словарь соотв. новую ячейку.
тут словарь не обязательно использовать. Достаточно массива в каждом элементе которого будет хранится 2 числа: индекс начала подстроки в формируемой строке и ее длина.
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
19.02.2012, 23:37 8
И сложность алгоритма O(n) будет, где n - длина начальной строки.
0
Mayonez
382 / 274 / 53
Регистрация: 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
3319 / 1465 / 134
Регистрация: 06.10.2010
Сообщений: 3,217
20.02.2012, 18:07 11
Длина индекса словаря равна логарифму по основанию 2 от длины словаря. Длина символа всегда равна 8 битам.
0
20.02.2012, 18:07
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.02.2012, 18:07

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

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

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


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

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