Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Алгорим Хаффмана на Delphi. Проблема

24K
13 декабря 2007 года
One Bad
12 / / 16.04.2007
У меня маленькая проблема, но как решить её не могу понять.
Вообщем суть в том что есть алгоритм кодирования, сообщения методом Хаффмана, любое сообщение кодирует, и выводит сам код, но если ввести допустим строку "аааааа", то выдает только кол-во букв, а код невыдает...

Листинг:
Код:
unit Unit1;
interface
uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, Grids, StdCtrls, ExtCtrls;
type
  TForm1 = class(TForm)
    Edit1: TEdit;
    Button1: TButton;
    SG1: TStringGrid;
    Edit2: TEdit;
    Label1: TLabel;
    Label2: TLabel;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;
  type rMainRecord=record
       strSymbol:string;
       iCountSymbol:integer;
       end;
var
  Form1: TForm1;
  strMainString:string;
  iCount:integer;
  aMainArray: array of rMainRecord;
implementation

{$R *.dfm}

procedure SortArray;
var bFlag1:boolean;
    i:integer;
    typBuffer:rMainRecord;
begin
  bFlag1:=true;
    while bFlag1 do
  begin
     bFlag1:=false;
     for i:=0 to iCount-2 do
        begin
          if aMainArray.iCountSymbol<aMainArray[i+1].iCountSymbol then
            begin
              typBuffer:=aMainArray;
              aMainArray:=aMainArray[i+1];
              aMainArray[i+1]:=typBuffer;
              bFlag1:=true;
            end;
        end;
  end;
end;
procedure TForm1.Button1Click(Sender: TObject);
  var i,j,iCommonCount:integer;
      bFlag:boolean;
begin
  strMainString:=edit1.text;
    iCount:=1;
    SG1.Cells[0,0]:=strMainString[1];
    SG1.Cells[1,0]:='1';
      for i:=2 to length(strMainString) do
        begin
          bFlag:=true;
            for j:=0 to iCount-1 do
              begin
                if strMainString=SG1.cells[0,j] then
                  begin
  SG1.Cells[1,j]:=inttostr(strtoint(SG1.Cells[1,j])+1);
  bFlag:=false;

                  end;
              end;
    if bFlag then
  begin
    inc(iCount);
      SG1.rowcount:=iCount;
      SG1.Cells[0,iCount-1]:=strMainString;
       SG1.Cells[1,iCount-1]:='1';
  end;
end;
SetLength(aMainArray,iCount);
for i:=0 to iCount-1 do
begin
    aMainArray.strSymbol:=SG1.Cells[0,i];
    aMainArray.iCountSymbol:=strtoint(SG1.Cells[1,i]);
end;
  SortArray;
  iCommonCount:=iCount;
while iCount<>1 do
begin
    for i:=1 to length(aMainArray[iCount-1].strSymbol) do
      begin
        for j:=0 to iCommonCount-1 do
        if SG1.Cells[0,j]=aMainArray[iCount-1].strSymbol then //poisk simvola v Str-id
          begin
            SG1.Cells[2,j]:='1'+SG1.Cells[2,j];
            SG1.Refresh;
            Break;
          end;
      end;
  for i:=1 to length(aMainArray[iCount-2].strSymbol) do
  begin
    for j:=0 to iCommonCount-1 do
      if SG1.Cells[0,j]=aMainArray[iCount-2].strSymbol then
        begin
          SG1.Cells[2,j]:='0'+SG1.Cells[2,j];
          SG1.Refresh;
          Break;
        end;
  end;
aMainArray[iCount-2].strSymbol:= aMainArray[iCount-2].strSymbol+aMainArray[iCount-1].strSymbol;
aMainArray[iCount-2].iCountSymbol:=aMainArray[iCount-2].iCountSymbol+aMainArray[iCount-1].iCountSymbol;
dec(iCount);
SortArray;
end;
    for i:=1 to length(strMainString) do
    for j:=0 to iCommonCount-1 do
    if SG1.Cells[0,j]=strMainString then
  begin
    Edit2.text:=Edit2.Text+SG1.Cells[2,j];
    break;
  end;
end;

end.



Помогите, пожалуйста! Подскажите где что исправить, или добавить чтобы работал, и выводил код для сообщение например "аааааа"
360
14 декабря 2007 года
P*t*
474 / / 15.02.2007
Ты что-то путаешь:
алгоритм Хаффмана это не кодирование, а сжатие информации.
принцип работы такой:
1) для каждого кода символа посчитать сколько раз он встречается.
2) для каждого кода символа сгенерировать битовую последовательнось. Для наиболее частых символов более короткую, а для остальных более длинную.
3) заменить каждый символ на соответствующую ему последовательность битов.

Твой код делает нечто совсем иное, и я не понимаю что.
5
16 декабря 2007 года
hardcase
4.5K / / 09.08.2005
Цитата: P*t*
Ты что-то путаешь:
алгоритм Хаффмана это не кодирование, а сжатие информации


Вы, батенька, заблуждаетесь.
Алгоритм Хаффмана какраз таки кодирование. На выходе алгоритма получаем коды Хаффмана для входного потока информации.
Эти коды обладают свойством оптимальности, имеется в виду, что если некоторый символ встречается во входном потоке чаще всего, он будет представляться самым коротким кодом, для самого редкого символа будет противопоставлен самый длинный код. В силу этого критерия оптимальности, мы будем иметь самое короткое представление входного сообщения, но повторю - это не будет сжатием информации!

360
16 декабря 2007 года
P*t*
474 / / 15.02.2007
Цитата: hardcase
В силу этого критерия оптимальности, мы будем иметь самое короткое представление входного сообщения, но повторю - это не будет сжатием информации!



Ну почему не будет сжатием?
По моему сжатие - это и есть самое короткое возможное представление входного сообщения.

Или я ошибаюсь?

5
16 декабря 2007 года
hardcase
4.5K / / 09.08.2005
Цитата: P*t*
Ну почему не будет сжатием?


Это будет оптимальным кодированием.
Сжатие подразумевает выполнение некоторых действий над входным сообщением, результатом которых является новое сообщение (короче входного), при том такое, что потеряно взаимооднозначное соответствие символов входного и выходного сообщений.

Но я не спорю, если понимать сжатие, как выполнение нетривиальных действий для предствления входного сообщения в более короткой форме (меньше байтов занимает), то вы правы.

Для топикстартера прикрепил вложение, тоже когда-то выполнял подобное упражнение =)

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог