код хафмана

Форум для изучающих FPC и их учителей.

Модератор: Модераторы

код хафмана

Сообщение tmpnikl » 05.05.2016 12:57:51

Чтоб разобраться в коде Хафмана, скопировал программу с инета и не могу понять некоторых деталей при реализации алгоритма Хафмана на паскаль, сам алгоритм понятен(как мне кажется), а вот с программным кодом туго...
Пока что у меня следующие вопросы...
почему, когда с текстового файла перегоняют символы в массив, запоминают аски код(во всех программах, которые встречал в инете), а не сам символ, почему в этом же массиве учитывается не частота появления символа в текстовом файле, а вероятность... и последнее, мне кажется в приведённом ниже коде есть ошибка в цикле вычисления вероятности в условии if (P[b+1].kol_symb <> 0) then ..., т.к. индекс b не определён, для этого цикла... но если индекс не b, то какой должен быть индекс...
Код: Выделить всё
Procedure Get_pseudo_table (fname: string;
                            var P: Pseudo_table;
                            var k: integer;
                            var flen: longint);
Var
   f: file;
   b: byte;
   i: integer;
   KS: longint;
Begin
      KS:= 0;           { кол-во встреч символа }
      k:= 0;
      For i:=1 to 256 do
        begin
          P[i].kol_symb:= 0;
          P[i].sum_ver:= 0;
          P[i].code:= NIL;
        end;
      Assign (f, fname);
      Reset (f, 1);
      while (not eof (f)) do
        begin
          BlockRead (f, b, 1);   { считывает 1 переменную из файла в перем b}
          if (P[b+1].kol_symb = 0) then {если в псевдосимволе
                                         кол-во символов=0} {1-ый раз встречается}
            begin
              inc (k);
              P[b+1].kol_symb:= 1;
              P[b+1].code:= New (PtrCode);
              P[b+1].code^.symb:= b;
              P[b+1].code^.len:= 0;         { длина в двоичном разряде:=0 }
              P[b+1].code^.next:= NIL;
              for i:=1 to 32 do
                P[b+1].code^.code[i]:= 0;   { весь двоичный код записываем нулями}
            end;
          P[b+1].sum_ver:= P[b+1].sum_ver+1; { если встреч не 1-ый раз, то}
          inc (KS);                          {увеличиваем кол-во этого эл-та в файле на 1}
        end;
      Close (f);
      For i:=1 to 256 do
--> индекс b должен быть или нет?        if (P[b+1].kol_symb <> 0) then       {   если псевдосимвол не пуст, т.е. там есть какие-то символы}
          P[i].sum_ver:= P[i].sum_ver / KS;       { вычисление вероятности появления}
      flen:= KS;
    End;       
tmpnikl
новенький
 
Сообщения: 15
Зарегистрирован: 18.11.2013 17:51:43

Re: код хафмана

Сообщение Дож » 05.05.2016 13:17:27

почему, когда с текстового файла перегоняют символы в массив, запоминают аски код(во всех программах, которые встречал в инете), а не сам символ

Программы не оперируют никакими «символами», они оперируют только кодами, которыми эти символы обозначаются. Назови тип хоть Char, хоть Byte, хоть AnsiChar. Какой тип выбрать программисту — вопрос удобства, вкуса, эстетики и т.д.

почему в этом же массиве учитывается не частота появления символа в текстовом файле, а вероятность...

В чём, по-вашему, отличие частоты от вероятности?

ниже коде есть ошибка в цикле вычисления вероятности в условии if (P[b+1].kol_symb <> 0) then ..., т.к. индекс b не определён, для этого цикла...

Понял вопрос, похоже, что там баг и вместо b+1 должно быть i.
Аватара пользователя
Дож
энтузиаст
 
Сообщения: 899
Зарегистрирован: 12.10.2008 16:14:47

Re: код хафмана

Сообщение tmpnikl » 05.05.2016 13:46:48

> Какой тип выбрать программисту — вопрос удобства
я думаю данная программа рассчитана на универсальность(сжатие не только текстовых, но и графических и т.д. файлов), поэтому и есть желание уйти от битов и перейти к char
>В чём, по-вашему, отличие частоты от вероятности?
Частота, это сколько раз символ встречается в тексте, вероятность это уже деление этой частоты на ( P[i].sum_ver:= P[i].sum_ver / KS; { вычисление вероятности появления})
>Программы не оперируют никакими «символами»
это вопрос философский, и тут можно долго флеймить, моё мнение языки верхнего уровня и создали, чтоб оперировать в удобоваримой форме, а дело компилятора преобразовывать всё это в коды... в данном случае я могу создать массив с типом char, это и будет в моём понимании массив символов...
Не подскажите, почему в лазарусе, когда я запускаю, чтоб пройти по шагам, в этой программе выскакивает окошко ассемблера, хотя в других простых программах, я иду по шагам по каждой строчке программы...
tmpnikl
новенький
 
Сообщения: 15
Зарегистрирован: 18.11.2013 17:51:43

Re: код хафмана

Сообщение Дож » 05.05.2016 14:09:38

> Какой тип выбрать программисту — вопрос удобства
я думаю данная программа рассчитана на универсальность(сжатие не только текстовых, но и графических и т.д. файлов), поэтому и есть желание уйти от битов и перейти к char

>Программы не оперируют никакими «символами»
это вопрос философский, и тут можно долго флеймить, моё мнение языки верхнего уровня и создали, чтоб оперировать в удобоваримой форме, а дело компилятора преобразовывать всё это в коды... в данном случае я могу создать массив с типом char, это и будет в моём понимании массив символов...

Но функциональной разницы никакой.

>В чём, по-вашему, отличие частоты от вероятности?
Частота, это сколько раз символ встречается в тексте, вероятность это уже деление этой частоты на ( P[i].sum_ver:= P[i].sum_ver / KS; { вычисление вероятности появления})

Ну, тогда нужно смотреть как эти заполненные данные далее используются. Если только для сравнения вероятностей символов одного текста друг с другом, то не имеет значения что сравнивать — количества или вероятность, а если сравниваются вероятности символа для разных текстов, то количества не годятся.
Аватара пользователя
Дож
энтузиаст
 
Сообщения: 899
Зарегистрирован: 12.10.2008 16:14:47

Re: код хафмана

Сообщение tmpnikl » 05.05.2016 17:30:11

спасибо
tmpnikl
новенький
 
Сообщения: 15
Зарегистрирован: 18.11.2013 17:51:43


Вернуться в Обучение Free Pascal

Кто сейчас на конференции

Сейчас этот форум просматривают: Google [Bot], Yandex [Bot] и гости: 12

Рейтинг@Mail.ru