Форум программистов, компьютерный форум, киберфорум
Pascal ABC
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.71/21: Рейтинг темы: голосов - 21, средняя оценка - 4.71
78 / 3 / 2
Регистрация: 03.10.2015
Сообщений: 26

Алгоритм Хаффмана, кодировка битов

11.12.2016, 12:12. Показов 4857. Ответов 34
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте! Есть ДЗ по информатике - создать программу на Pascal ABCnet, которая сжимает файл по алгоритму Хаффмана.

Я сначала написал программу хотя бы создания дерева и словаря, чтобы была основа, и думал, что с битами разберусь позже. Дело в том, что нам вообще ничего не рассказывали про саму кодировку, и если на Си я нашел очень много информации по тому, как можно менять биты внутри байтового символа, например, то на Паскале я так и не нашел решения..

В общем, ниже представлена программа, которая кодирует ТЕКСТОВЫЙ файл по алгоритму Хаффмана (текстовый или нет - не важно, это я, скорее всего, поменяю), и она заменяет один байт символа на пять-шесть байт последовательностей цифр D А нужно, чтобы эти цифры вгонялись в биты.

Плюс преподаватель рассказывал, что обратная программа (разархиватор) идет по коду, находит префиксный код и прекращает чтение, переключается на следующий "байт" как бы, а найденный заменяет числом. Но я не представляю, как можно сделать так, чтобы читались БИТЫ, и если находится последовательность БИТ из 4 штук, то все это прекращалось. Пожалуйста, просветите невежду!

Буду очень благодарен, если хотя бы расскажете, как мне это сделать (я не прошу именно менять что-то в программе). Просто на основе моих замен объяснить, как то же самое запихнуть внутрь байта. Я знаю лишь shr и shl, но не смог придумать применения этому(

Еще самое обидное, что дедлайн передвинули на 10 дней ближе, и теперь вообще все плохо..

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
Program Huffman;
 
Const
  n = 255;
  textIn = 'Huffman1.txt'; //Ввод текста
  textOut = 'Huffman2.txt'; //Вывод текста
 
Type
  symbolsArray = array[1..20000] of string;
  numbersArray = array[1..n] of integer;
 
Procedure sorting(var tempSymbols: symbolsArray; var numbers: numbersArray; var k: integer);
  Var
    i, j: integer; //Счетчики
    temp1: string; //Переменная для обмена значений
    temp2: integer; //Переменная для обмена значений
  Begin
    for i := 1 to k do
      for j := 1 to (k - 1) do
        if (numbers[j] > numbers[j + 1]) then begin
          temp1 := tempSymbols[j]; tempSymbols[j] := tempSymbols[j + 1]; tempSymbols[j + 1] := temp1;
          temp2 := numbers[j]; numbers[j] := numbers[j + 1]; numbers[j + 1] := temp2;
          end;
  End;
 
Procedure code(m, k: integer; symbols, tempSymbols: symbolsArray; var codes: symbolsArray);
Var
  i, j: integer; //Счетчики
  flag: boolean; //Флаг
  a, b: byte; //Коды
  line: string;
  Begin
    a := 0; b := 1;
    line := tempSymbols[m + 1];
    for i := 1 to length(line) do begin
      flag := false; j := 1; //Сбрасывание флага и счетчика
      while (flag = false) and (j <= k) do begin
        if (line[i] = symbols[j]) then begin
          if (m = 0) then codes[j] := a + codes[j] else codes[j] := b + codes[j];
          flag := true;
          end;
        j := j + 1;
        end;
      end;
  End;
 
Var
  tfIn, tfOut: textfile; //Файлы
  text1, text2: symbolsArray; //Текст из файла и текст в файл
  text: string; //Строка текста
  symbols, tempSymbols: symbolsArray; //Символы
  codes: symbolsArray; //Коды символов
  numbers: numbersArray; //Кол-во повторений
  i, j, l, m: integer; //Счетчики
  k, tempK: integer; //Длины массивов
  flag: boolean; //Флаг для прерывание цикла
 
Begin
  assignfile(tfIn, textIn);
  reset(tfIn);
  m := 0; //Кол-во строк
  //Ввод текста до последней строки
  while not eof(tfIn) do begin
    m := m + 1; //Кол-во строк
    readln(tfIn, text1[m]);
    end;
  closefile(tfIn);
  //Ввод символов
  k := 0; //Кол-во символов
  for l := 1 to m do begin
    text := text1[l];
    for i := 1 to length(text) do begin
      flag := false; j := 1; //Сбрасывание флага и счетчика
      while (flag = false) and (j <= n) do begin  //Нет совпадений - flag = false
        if (text[i] = symbols[j]) then begin
          flag := true;
          numbers[j] := numbers[j] + 1; //+1 к кол-ву повторений
          end;
        j := j + 1;
        end;
      if (flag = false) then begin
        k := k + 1;
        symbols[k] := text[i];
        tempSymbols[k] := text[i];
        numbers[k] := 1;
        end;
      end;
    end;
  tempK := k;
  if (tempK = 1) then codes[1] := '0';
  while (tempK > 1) do begin
    //Сортировка по возрастанию кол-ва повторений
    sorting(tempSymbols, numbers, tempK);
    //Добавление 0 к самому редкому символу
    code(0, k, symbols, tempSymbols, codes);
    //Добавление 1 ко 2-ому самому редкому символу
    code(1, k, symbols, tempSymbols, codes);
    //Соединение двух самых редких строк
    numbers[1] := numbers[1] + numbers[2];
    tempSymbols[1] := tempSymbols[1] + tempSymbols[2];
    if (tempK > 2) then
      for i := 2 to (tempK - 1) do begin
        numbers[i] := numbers[i + 1];
        tempSymbols[i] := tempSymbols[i + 1];
        end;
    tempK := tempK - 1;
    end;
  //Создание нового текста
  for l := 1 to m do begin
    text := text1[l];
    for i := 1 to length(text) do begin
      flag := false; j := 1;
      while (flag = false) and (j <= k) do begin
        if (text[i] = symbols[j]) then text2[l] := text2[l] + codes[j];
        j := j + 1;
        end;
      end;
    end;
  //Вывод архивированного текста
  if (k > 0) then begin
    assignfile(tfOut, textOut);
    rewrite(tfOut);
    for i := 1 to k do writeln(tfOut, symbols[i],' - ', codes[i]);
    writeln(tfOut);
    for i := 1 to m do writeln(tfOut, text2[i]);
    closefile(tfOut);
    end;
end.
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
11.12.2016, 12:12
Ответы с готовыми решениями:

Записать дерево Хаффмана в виде последовательности битов
Пытаюсь написать архиватор, но никак не выходит записать дерево в виде последовательности битов. Алгоритм следующий: при входе дерево, если...

кодировка Хаффмана
Дорогие программисты. Вот был написан код &quot;кодировка Хаффмана&quot;, и тут мы вводим количество данных и их частоту. Но я не могу то ли...

Кодировка Хаффмана
Добрый день Форумчане. Есть Код На Java набирал я его в Eclipse. Кто может подсказать что с ним не так и меня поправить. В Java новичок...

34
78 / 3 / 2
Регистрация: 03.10.2015
Сообщений: 26
12.12.2016, 18:01  [ТС]
Студворк — интернет-сервис помощи студентам
Хорошо, большое спасибо! Вечером попробую воплотить мечту в реальность.

Добавлено через 7 часов 59 минут
Извините, а существует более адекватный способ закодировать байты, нежели представленный мной в коде первой программы? Несколько людей высказали свое недовольство таким методом, а что-то поправить не могу сообразить (+ переделать на байтовый лад).

Я решил сделать
Pascal
1
2
cif = array[1..8] of (0,1);
   code = array[1..256] of cif;
В первом будут храниться биты, во втором - байты из этих бит. И вот тогда работать с созданием дерева Хаффмана у меня не получается.. Не знаю, насколько это рационально, и как все представить грамотно.
0
Модератор
Эксперт по электронике
 Аватар для ФедосеевПавел
8679 / 4516 / 1670
Регистрация: 01.02.2015
Сообщений: 13,963
Записей в блоге: 14
12.12.2016, 20:01
Pascal
   code = array[0..255] of cif;
Если "недовольство" выказал преподаватель, то он и пояснил оптимальный вариант. Если не преподаватель - делайте, как сможете. Иначе совсем запутаетесь.
Можно, конечно так Декодирование префиксным кодом

В любом случае, код каждого символа имеет собственную длину. Значит под хранение кода каждого символа нужно выделить 1 байт под хранение длины, несколько байт (2-3) под хранение самого кода.

Сделайте, как сможете. Потом будете оптимизировать внутренние структуры.
0
78 / 3 / 2
Регистрация: 03.10.2015
Сообщений: 26
12.12.2016, 21:36  [ТС]
Не могли бы Вы помочь последний раз? Я куда больше путаюсь, когда пытаюсь найти немногочисленную информацию сам, чем от Ваших рук. Прошу прощения...
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
type
   cif = array[1..8] of integer;
   codes = array[0..255] of cif;
procedure code(m, k: integer; symbols: CharList; var code: codes);
Var
  CurrBy, a, b: byte;  
  begin
    a:=0;
    b:=1;
    CurrBy:=symbols[m+1];
    if (m=0) then code[]:=a + code[]
          else code[]:=b + code[];
Это незавершенная процедура. В основной программе я вызываю эту процедуру два раза с различными m (0 и 1), таким образом прибавляя нуль или единицу к коду символа, а дальше объединяю их и их частоты до тех пор, пока не останется 1 общий "символ". Все по алгоритму Хаффмана.
Вот только со старой программой по строкам я четко мог ориентироваться и складывать нужные кол-ва повторений и символы, то тут я опять наступаю на неверные кнопки и все ломаю.

Могу ли я попросить Вас помочь с кодом составления кодов символов? Если потребуется, попробовал бы как-то отблагодарить... Неделя перед сессией ужасно выносит мозг (я не давлю на жалость, ни в коем случае).
0
Модератор
Эксперт по электронике
 Аватар для ФедосеевПавел
8679 / 4516 / 1670
Регистрация: 01.02.2015
Сообщений: 13,963
Записей в блоге: 14
12.12.2016, 22:05
Оставьте со строками - не ломайте себя.

Добавлено через 1 минуту
Мне трудно ориентироваться в чужеродном синтаксисе PABC.NET. А вы его вовсю применяете.

Добавлено через 1 минуту
Что вы хотите от этих строк? Я не пойму синтаксис...
Pascal
1
2
    if (m=0) then code[]:=a + code[]
          else code[]:=b + code[];
0
78 / 3 / 2
Регистрация: 03.10.2015
Сообщений: 26
12.12.2016, 22:06  [ТС]
Через строки я читал именно строки и работал с ними, но тут же мы уже читали байты и заносили в массивы различные байты. Плюс ваш предложенный вариант занесения битов в самом начале действует с чарами или байтами (опять же).. Все работает, осталось лишь связать части кодированием..
0
Модератор
Эксперт по электронике
 Аватар для ФедосеевПавел
8679 / 4516 / 1670
Регистрация: 01.02.2015
Сообщений: 13,963
Записей в блоге: 14
12.12.2016, 22:07
code - это таблица кодов Хаффмана?
А в этих строках вы хотите удлинить код для конкретного символа?

Поступайте, как со строками:
1. Один байт - длина кода
2. Последовательность бит или байт или символов в строке - это сам код.
0
78 / 3 / 2
Регистрация: 03.10.2015
Сообщений: 26
12.12.2016, 22:15  [ТС]
А если Вам написать так, как видите Вы и как удобно Вам, не ломая голову моим кривым кодом? Я серьезно чувствую себя отсталым.

Добавлено через 6 минут
Все равно не могу провести параллели(
0
Модератор
Эксперт по электронике
 Аватар для ФедосеевПавел
8679 / 4516 / 1670
Регистрация: 01.02.2015
Сообщений: 13,963
Записей в блоге: 14
12.12.2016, 22:25
Сдавать - не мне, а вам.
Сделайте код на строках, чтобы он совпадал с каким нибудь эталонным (файл из 1 строки).
А я под ваш тип code подстроюсь.
0
78 / 3 / 2
Регистрация: 03.10.2015
Сообщений: 26
12.12.2016, 23:29  [ТС]
Код на строках есть изначально. Я понимаю, что сдавать мне, но я могу и написать какую-то дичь, к которой не подстроишься, а забот больше вам (вроде как).
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Type
  symbolsArray = array[1..20000] of string;
  numbersArray = array[1..255] of integer;
Procedure code(m, k: integer; symbols, tempSymbols: symbolsArray; var codes: symbolsArray);
Var
  i, j: integer; //Счетчики
  flag: boolean; //Флаг
  a, b: byte; //Коды
  line: string;
  Begin
    a := 0; b := 1;
    line := tempSymbols[m + 1];
    for i := 1 to length(line) do begin
      flag := false; j := 1; //Сбрасывание флага и счетчика
      while (flag = false) and (j <= k) do begin
        if (line[i] = symbols[j]) then begin
          if (m = 0) then codes[j] := a + codes[j] else codes[j] := b + codes[j];
          flag := true;
          end;
        j := j + 1;
        end;
      end;
  End;
И основная программа уже после сортировки по вашим рекомендациям (есть массивы с байтами, массивы с их кол-вом повторений, мы это отсортировали по возрастанию)
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
tempK := k; // присваиваем переменной tempk количество (в нашем случае байт)
  if (tempK = 1) then codes[1] := '0';  // Если байт всего один - то его код 0, и все замечательно
  while (tempK > 1) do begin  // Начинаем сокращать кол-во символов, объединяя их и их частоты (по Хаффману)
    //Сортировка по возрастанию кол-ва повторений
    sorting(tempSymbols, numbers, tempK);
    //Добавление 0 к самому редкому символу
    code(0, k, symbols, tempSymbols, codes);
    //Добавление 1 ко 2-ому самому редкому символу
    code(1, k, symbols, tempSymbols, codes);
    //Соединение двух самых редких строк
    numbers[1] := numbers[1] + numbers[2];
    tempSymbols[1] := tempSymbols[1] + tempSymbols[2];
    if (tempK > 2) then
      for i := 2 to (tempK - 1) do begin
        numbers[i] := numbers[i + 1];   //Это кол-во повторений, здесь их индексы совпадают с индексами байтов
        tempSymbols[i] := tempSymbols[i + 1];  //Это сами байты
        end;
    tempK := tempK - 1;   // Из двух сделали один
    end;
Добавлено через 56 минут
Лучше уж научиться чему-то правильному, нежели копаться в своем мусоре. Если будет сегодня-завтра возможность - я был бы очень признателен (я не отказываюсь от своих слов). Я уже понял свою ошибку в плане амбиций, но нужно выжить здесь и вынести урок. Поэтому сердечно прошу помощи..
0
Модератор
Эксперт по электронике
 Аватар для ФедосеевПавел
8679 / 4516 / 1670
Регистрация: 01.02.2015
Сообщений: 13,963
Записей в блоге: 14
12.12.2016, 23:58
Завтра подумаю.

Посмотрите ссылки. Мне кажется, что у вас не совсем корректно.
Даже с примером на Pascal.
http://algolist.manual.ru/comp... uffman.php
https://habrahabr.ru/post/144200/
0
78 / 3 / 2
Регистрация: 03.10.2015
Сообщений: 26
13.12.2016, 13:28  [ТС]
Я читал обе этим темы. Код с habrahabr'а я не вижу, а из первой ссылки он ооочень уж тяжел и нагружен. Плюс мне необходимо создать программу без подключенных модулей, и в итоге для меня тот ад становится вообще невероятным. Поэтому пришлось импровизировать, хоть и, извиняюсь, не очень вышло.

По алгоритму Хаффмана после сортировки (не важно, по возрастанию или по убыванию, но логичнее по возрастанию, чтобы удобнее было брать редкие) мы объединяем элементы массива байтов в одно целое, и то же самое должны сделать с вхождениями этих байтов, после чего вновь произвести сортировку и продолжить это действо. Вот я и заикался о том, чтобы сделать одинаковые индексы для кол-ва вхождений и самих байтов.

И особенно тяжелой сейчас для меня является создание самого кода. На деле-то понятно, когда мы идем по нарисованному дереву, но вот как это объяснить дереву (к тому же если дерево будет постоянно различаться).. В итоге я пришел к выводу, что погряз в этом достаточно серьезно, а дедлайн жесток.

Добавлено через 5 часов 36 минут
Все оказалось куда хуже. Мы сегодня прошли указатели (как бы прошли, но только теория). Задание сдавать в пятницу, и препод мне сказал, что кодирование по дереву Хаффмана делается только по указателям) Сказать, что я выпал в осадок.. В общем, весело. Если вам информация про указатели поможет, буду рад... Ибо в них уж точно беда, когда я узнал о них лишь сегодня.
0
Модератор
Эксперт по электронике
 Аватар для ФедосеевПавел
8679 / 4516 / 1670
Регистрация: 01.02.2015
Сообщений: 13,963
Записей в блоге: 14
13.12.2016, 15:30
Правильно говорят - не торопись делать, много исправлять придётся.
Как вариант: "Чем круче джип, тем дальше за трактором идти"
0
78 / 3 / 2
Регистрация: 03.10.2015
Сообщений: 26
13.12.2016, 23:57  [ТС]
И ведь верно. Вы сможете попробовать помочь?

Добавлено через 6 минут
Оказалось, что преподаватель рассматривал задания с нормальными коэффициентами для тех, кто и без курса в вузе умеет много чего прогать. А я оказался тем дурачком, который просто идет по курсу.

Добавлено через 7 часов 52 минуты
Цитата Сообщение от ФедосеевПавел Посмотреть сообщение
Правильно говорят - не торопись делать, много исправлять придётся.
Как вариант: "Чем круче джип, тем дальше за трактором идти"
Павел, хотя бы что-нибудь ответьте, пожалуйста, чтобы я знал, полагаться на что-то или идти вешаться.
0
Модератор
Эксперт по электронике
 Аватар для ФедосеевПавел
8679 / 4516 / 1670
Регистрация: 01.02.2015
Сообщений: 13,963
Записей в блоге: 14
14.12.2016, 01:04
Изучайте структуры на основе указателей - сначала списки, затем деревья.

Я не смогу выделить время для полноценного написания программы. Начальник меня спросит - "твоя трудовая где лежит?"

Подкорректировать - да, пожалуйста. На это время меньше уходит.

Если уж всё равно не успеете - берите с algolist.
0
78 / 3 / 2
Регистрация: 03.10.2015
Сообщений: 26
14.12.2016, 12:49  [ТС]
Еще раз здравствуйте!
Большое спасибо Вам за удаленное время и помощь. Я соединил в одно предложенные Вами решения и свои варианты, сделав рабочую программу, сжимаюзую любойкилобайтный файл в два раза. Для кдов использовал свой кривой алгоритм, но все остальное - Ваша заслуга, в особенности код по сабжу в сообщении 2. Огромное вам спасибо!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
14.12.2016, 12:49

Кодировка Хаффмана и энтропия
Приветствую форумчан! Есть готовый, полностью рабочий код кодировки Хаффмана, а так же и рабочий код функции расчета энтропии. Нужно...

Алгоритм Хаффмана
Ребят, подскажите как реализовать кодирование по алгоритму Хаффмана.. Может есть какие то идеи или исходники (желательно с пояснением)? ...

Алгоритм Хаффмана
Доброго времени суток.Если кто то может то объясните пожалуйста каким образом в приведённом ниже исходнике идёт построение дерева.Процедура...

Алгоритм Хаффмана
Возможно и наболевшая тема на форуме, но всё же есть реализация алгоритма Хаффмана. Допустим, у меня в файле есть следующая строка: ...

Алгоритм Хаффмана
Добрый вечер) Помогите пожалуйста написать прогу на дельфи - кодирование алгоритмом Хаффмана... Нужно, чтобы она выводила закодированный...


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

Или воспользуйтесь поиском по форуму:
35
Ответ Создать тему
Новые блоги и статьи
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru