Алгорим Хаффмана на Delphi. Проблема
Вообщем суть в том что есть алгоритм кодирования, сообщения методом Хаффмана, любое сообщение кодирует, и выводит сам код, но если ввести допустим строку "аааааа", то выдает только кол-во букв, а код невыдает...
Листинг:
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.
Помогите, пожалуйста! Подскажите где что исправить, или добавить чтобы работал, и выводил код для сообщение например "аааааа"
алгоритм Хаффмана это не кодирование, а сжатие информации.
принцип работы такой:
1) для каждого кода символа посчитать сколько раз он встречается.
2) для каждого кода символа сгенерировать битовую последовательнось. Для наиболее частых символов более короткую, а для остальных более длинную.
3) заменить каждый символ на соответствующую ему последовательность битов.
Твой код делает нечто совсем иное, и я не понимаю что.
алгоритм Хаффмана это не кодирование, а сжатие информации
Вы, батенька, заблуждаетесь.
Алгоритм Хаффмана какраз таки кодирование. На выходе алгоритма получаем коды Хаффмана для входного потока информации.
Эти коды обладают свойством оптимальности, имеется в виду, что если некоторый символ встречается во входном потоке чаще всего, он будет представляться самым коротким кодом, для самого редкого символа будет противопоставлен самый длинный код. В силу этого критерия оптимальности, мы будем иметь самое короткое представление входного сообщения, но повторю - это не будет сжатием информации!
Ну почему не будет сжатием?
По моему сжатие - это и есть самое короткое возможное представление входного сообщения.
Или я ошибаюсь?
Это будет оптимальным кодированием.
Сжатие подразумевает выполнение некоторых действий над входным сообщением, результатом которых является новое сообщение (короче входного), при том такое, что потеряно взаимооднозначное соответствие символов входного и выходного сообщений.
Но я не спорю, если понимать сжатие, как выполнение нетривиальных действий для предствления входного сообщения в более короткой форме (меньше байтов занимает), то вы правы.
Для топикстартера прикрепил вложение, тоже когда-то выполнял подобное упражнение =)