VPF::[Алгоритм]Кодирование и декодирование информации

SergXP

Дата 7.3.2009, 23:24 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 150
Регистрация: 16.4.2008

Репутация: нет
Всего: нет

Здраствуйте.

Имеется задание:
Для обеспечения сохранности информации при хранении ее часто шифруют различными способами. Напишите программу, шифрующую информацию и программу – дешифратор.

Мы прошли темы "Деревья и графы".

Скажите пожалуйста, какой алгоритм выбрать?
Если я не ошибаюсь, то подойдет метод Хаффмана.

С Уважением.

--------------------

База IMEI-номеров украденных и утерянных мобильных телефоновhttp://imeis.net.ru/

zim22

Дата 8.3.2009, 09:17 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69

XOR-шифрование

--------------------

C++ FAQ Lite

SergXP

Дата 8.3.2009, 10:09 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 150
Регистрация: 16.4.2008

Репутация: нет
Всего: нет

zim22, а это не слишком примитивно? Все-таки это задание на курсовую работу.

--------------------

База IMEI-номеров украденных и утерянных мобильных телефоновhttp://imeis.net.ru/

Kakadu

Дата 8.3.2009, 10:14 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 273
Регистрация: 19.3.2008

Репутация: 7
Всего: 7

Вы проходили какое-нибудь шифрование? если нет, и если в задании не оговорено, то логично выбрать самое простое в написании.

--------------------

Добрые мариносы долго кормили украдкой маленьких зерлингов. От этой украдки зерлинги пухли и дохли

zim22

Дата 8.3.2009, 10:38 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69

Цитата(SergXP @ 8.3.2009, 10:09

)

а это не слишком примитивно?

примитивней некуда.

хотите посложней - выбирайте любой алгоритм и реализовуйте.
http://ru.wikipedia.org/wiki/Симметричные_криптосистемы

--------------------

C++ FAQ Lite

SergXP

Дата 8.3.2009, 10:52 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 150
Регистрация: 16.4.2008

Репутация: нет
Всего: нет

Kakadu, нет, у нас небыло тем по шифрованию. Если я правильно понял, необходим алгоритм, который использует "Деревья"

zim22, спс, счас почитаю.

--------------------

База IMEI-номеров украденных и утерянных мобильных телефоновhttp://imeis.net.ru/

zim22

Дата 8.3.2009, 10:58 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69

Цитата(SergXP @ 8.3.2009, 10:52

)

. Если я правильно понял

вы поняли по одному, профессор по другому. лучше уточнитесь.

--------------------

C++ FAQ Lite

SergXP

Дата 8.3.2009, 11:07 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 150
Регистрация: 16.4.2008

Репутация: нет
Всего: нет

zim22, дык, вот у меня как раз не получается с ним связаться.
И по данной теме подходит только Алгоритм Хаффмана

http://ru.wikipedia.org/wiki/%D0%90%D0%BB%...%B0%D0%BD%D0%B0

Код


Результат работы для строки «to be or not to be?». Выводятся: символ, его вес и двоичный код. Далее закодированная строка и результат декодирования.

e  2  000
?  1  0010
n  1  0011
o  4  01
   5  10
t  3  110
r  1  1110
b  2  1111
11001101111000100111101000110111010110011011110000010
to be or not to be?
-----------------------------------------------------------------------
110 01 10 1111 000 10 01 1110 10 0011 01 110 10 110 01 10 1111 000 0010
t   o     b    e      o  r       n    o  t      t   o     b    e   ?
Итого:
53 бита
19 знаков (с пробелами)
2,79 бит/знак
Соответствующее дерево Хаффмана.

       root
      /    \
     0      1
    / \    / \
  00   o "_"  11
 /  \        /  \
e   001     t   111
    / \         /  \
   ?   n       r    b

--------------------

База IMEI-номеров украденных и утерянных мобильных телефоновhttp://imeis.net.ru/

zim22

Дата 8.3.2009, 11:22 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69

У вас задание называется:

Цитата(SergXP @ 7.3.2009, 23:24

)

Для обеспечения сохранности информации при хранении

если под информацией вы понимаете исключительно текстовые данные(т.е. алфавит) то Хаффман подойдёт
если же необходимо кодировать любые данные, а не только текст, то Хаффман в пролёте.

Алгоритм Хаффмана (англ. Huffman) — адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью

--------------------

C++ FAQ Lite

SergXP

Дата 8.3.2009, 11:29 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 150
Регистрация: 16.4.2008

Репутация: нет
Всего: нет

Ну в общем-то да, кодирование текста.
Ну и дополнительно сделаю кодирование файлов.
а xor подойдет же для файлов?

--------------------

База IMEI-номеров украденных и утерянных мобильных телефоновhttp://imeis.net.ru/

zim22

Дата 8.3.2009, 11:33 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69

Цитата(SergXP @ 8.3.2009, 11:29

)

а xor подойдет же для файлов?

xor работает с битами. следовательно подходит для всего.

--------------------

C++ FAQ Lite

SergXP

Дата 8.3.2009, 12:33 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 150
Регистрация: 16.4.2008

Репутация: нет
Всего: нет

zim22, спасибо за помощь! Буду пробывать! smile

--------------------

База IMEI-номеров украденных и утерянных мобильных телефоновhttp://imeis.net.ru/

zim22

Дата 8.3.2009, 12:49 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69

SergXP, незачто. удачи в написании алгоритма.

--------------------

C++ FAQ Lite

SergXP

Дата 8.3.2009, 17:03 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 150
Регистрация: 16.4.2008

Репутация: нет
Всего: нет

Эх, теперь возникла другая проблема. :(

Вот алгоритм Хаффмана на Делфи:

Код


unit CHuffman;
 
interface
 
uses
  SysUtils, Classes, Dialogs;
 
const
  ALPHABETSIZE = 256;
 
type
  TTree = class;
  THuffman = class;
 
  TTree = class(TObject)
  private
    fchild0 : TTree;      // потомки "0" и "1"
    fchild1 : TTree;
    fleaf : Boolean;      // признак листового дерева
    fcharacter : Integer; // входной символ
    fweight : Integer;    // вес этого символа
  public
    procedure Tree(character, weight : integer; leaf : boolean);
    procedure traverse(code : string; h : THuffman);
    property child0 : TTree read fchild0 write fchild0;
    property child1 : TTree read fchild1 write fchild1;
    property leaf : Boolean read fleaf write fleaf;
    property character : Integer read fcharacter write fcharacter;
    property weight : Integer read fweight write fweight;
  end;
 
  THuffman = class(TObject)
  private
    // поля :)
    fweights : array [0..ALPHABETSIZE-1] of Integer;// веса символов
    fcode : array [0..ALPHABETSIZE-1] of String;// коды Хаффмана
    ftree : array [0..ALPHABETSIZE-1] of TTree;// рабочий массив деревьев
    // методы доступа к массиву :)
    function GetCodeValue(Index: Integer): String;
    function GetTreeValue(Index: Integer): TTree;
    function GetWeightValue(Index: Integer): Integer;
    procedure SetCodeValue(Index: Integer; const Value: String);
    procedure SetTreeValue(Index: Integer; const Value: TTree);
    procedure SetWeightValue(Index: Integer; const Value: Integer);
  public
    // методы :)
    procedure makeCode;
    procedure growTree(var data : array of Integer);
    function getLowestTree(used : integer) : integer;
    function coder(var data : array of integer) : string;
    function decoder(data : string) : string;
    // свойства :)
    property weights[Index: Integer] : Integer read GetWeightValue write SetWeightValue;
    property code[Index: Integer] : String read GetCodeValue write SetCodeValue;
    property tree[Index: Integer] : TTree read GetTreeValue write SetTreeValue;
  end;
 
var
  Huffman : THuffman;
 
implementation
 
{ TTree }
 
procedure TTree.Tree(character, weight: integer; leaf: boolean);
begin
  fleaf := leaf;
  fcharacter := character;
  fweight := weight;
end;
 
(*  Обход дерева с генерацией кодов
    1. "Распечатать" листовое дерево и записать код Хаффмана в массив
    2. Рекурсивно обойти левое поддерево (с генерированием кода).
    3. Рекурсивно обойти правое поддерево. *)
procedure TTree.traverse(code: String; h: THuffman);
begin
  if leaf then
  begin
    h.code[Ord(character)] := code;
    ShowMessage('Символ: ' + Chr(character) +'  '+'Вес: '+IntToStr(weight) +'  '+'Двоичный код: '+ code);
  end;
  if child0 <> nil then child0.traverse(code + '0', h);
  if child1 <> nil then child1.traverse(code + '1', h);
end;
 
{ THuffman }
 
(* ищем самое "легкое" дерево *)
function THuffman.getLowestTree(used: integer): integer;
var
  min, i : Integer;
begin
  min := 0;
  for i:=1 to used-1 do if tree[i].weight < tree[min].weight then min := i;
  Result := min;
end;
 
(* кодирует данные строкой из 1 и 0 *)
function THuffman.coder(var data: array of Integer): String;
var
  str : String;
  i : Integer;
begin
  str := '';
  for i:=0 to High(data) do str := str + code[data[i]];
  Result := str;
end;
 
function THuffman.decoder(data : string): string;
var
  str : String;
  c : Integer;
begin
  str := '';
  while(length(data) > 0) do
  begin
    for c:=0 to ALPHABETSIZE-1 do
    if (weights[c] > 0) AND (code[c] = copy(data, 1, length(code[c]))) then
    begin
      data := copy(data, length(code[c])+1, length(data));
      str := str + chr(c) + ' - ' + code[c] + #13;
    end;
  end;
  Result := str;
end;
 
(* растим дерево *)
procedure THuffman.growTree(var data: array of Integer);
var
  i, c, w, min, used, weight0 : Integer;
  temp : TTree;
begin
  for i:=0 to ALPHABETSIZE-1 do weights[i] := 0;
  for i:=0 to High(data) do weights[data[i]] := weights[data[i]] + 1; // считаем веса символов
  //  заполняем массив из "листовых" деревьев
  //  с использованными символами
  used := 0;
  for c:=0 to ALPHABETSIZE-1 do
  begin
    w := weights[c];
    if w <> 0 then
    begin
      inc(used);
      tree[used-1] := TTree.Create;
      tree[used-1].Tree(c, w, true);
    end;
  end;
  while used > 1 do                             // парами сливаем легкие ветки
  begin
    min := getLowestTree(used);                 // ищем 1 ветку
    weight0 := tree[min].weight;
    temp := TTree.Create;                       // создаем новое дерево
    temp.child0 := tree[min];                   // и прививаем 1 ветку
    dec(used);
    tree[min] := tree[used];                    // на место 1 ветки кладем
                                                // последнее дерево в списке
    min := getLowestTree(used);                 // ищем 2 ветку и
    temp.child1 := tree[min];                   // прививаем ее к нов.дер.
    temp.weight := weight0 + tree[min].weight;  // считаем вес нов.дер.
    tree[min] := temp;                          // нов.дер. кладем на место 2 ветки
  end;                                          // все! осталось 1 дерево Хаффмана
end;
 
(* запускаем вычисление кодов Хаффмана *)
procedure THuffman.makeCode;
begin
  tree[0].traverse('', self);
end;
 
function THuffman.GetCodeValue(Index: Integer): String;
begin
  Result := fcode[Index];
end;
 
function THuffman.GetTreeValue(Index: Integer): TTree;
begin
  Result := ftree[Index];
end;
 
function THuffman.GetWeightValue(Index: Integer): Integer;
begin
  Result := fweights[Index];
end;
 
procedure THuffman.SetCodeValue(Index: Integer; const Value: String);
begin
  fcode[Index] := Value;
end;
 
procedure THuffman.SetTreeValue(Index: Integer; const Value: TTree);
begin
  ftree[Index] := Value;
end;
 
procedure THuffman.SetWeightValue(Index: Integer; const Value: Integer);
begin
  fweights[Index] := Value;
end;
 
end.

Немогу никак перевести на С++ под Builder 6 верхнюю часть кода.
Как объявить процедуры и сформировать класс?

Вот начал переделывать:

Код


const ALPHABETSIZE = 256;

class TTree;
class THuffman;

class TTree {

 private:
    TTree* fchild0;      // ïîòîìêè "0" è "1"
    TTree* fchild1;
    bool fleaf;      // ïðèçíàê ëèñòîâîãî äåðåâà
    int fcharacter; // âõîäíîé ñèìâîë
    int fweight;    // âåñ ýòîãî ñèìâîëà
  public:
    void __fastcall Tree(int character, int weight, bool leaf);
    void __fastcall traverse(char code[400], THuffman h);
    TTree property child0 (read fchild0 write fchild0);
    property child1 : TTree read fchild1 write fchild1;
    property leaf : Boolean read fleaf write fleaf;
    property character : Integer read fcharacter write fcharacter;
    property weight : Integer read fweight write fweight;
  //end;
};

class THuffman {
  private:
    // ïîëÿ :)
    int fweights[ALPHABETSIZE-1];// âåñà ñèìâîëîâ
    char fcode[ALPHABETSIZE-1];// êîäû Õàôôìàíà
    TTree ftree[ALPHABETSIZE-1];// ðàáî÷èé ìàññèâ äåðåâüåâ
    // ìåòîäû äîñòóïà ê ìàññèâó :)
    char GetCodeValue(int Index);
    TTree GetTreeValue(int Index);
    int GetWeightValue(int Index);
    void __fastcall SetCodeValue(int Index, const char Value[200]);
    void __fastcall SetTreeValue(int Index, const TTree Value);
    void __fastcall SetWeightValue(int Index, const int Value);
  public:
    // ìåòîäû :)
    void __fastcall makeCode;
    void __fastcall growTree(int data[]);
    int getLowestTree(int used);
    char coder(int data[]);
    char decoder(char data[400]);
    // ñâîéñòâà :)
    //property weights[Index: Integer] : Integer read GetWeightValue write SetWeightValue;
    //property code[Index: Integer] : String read GetCodeValue write SetCodeValue;
    //property tree[Index: Integer] : TTree read GetTreeValue write SetTreeValue;
 // end;
};


void __fastcall TTree::Tree(int character, int weight, bool leaf){
  fleaf = leaf;
  fcharacter = character;
  fweight = weight;
}

/*  Îáõîä äåðåâà ñ ãåíåðàöèåé êîäîâ
    1. "Ðàñïå÷àòàòü" ëèñòîâîå äåðåâî è çàïèñàòü êîä Õàôôìàíà â ìàññèâ
    2. Ðåêóðñèâíî îáîéòè ëåâîå ïîääåðåâî (ñ ãåíåðèðîâàíèåì êîäà).
    3. Ðåêóðñèâíî îáîéòè ïðàâîå ïîääåðåâî. */

void __fastcall TTree::traverse(char code[400], THuffman h)
{
  if (h::leaf) {

    h.code[Ord(character)] = code;
    ShowMessage('Ñèìâîë: ' + Chr(character) +'  '+'Âåñ: '+IntToStr(weight) +'  '+'Äâîè÷íûé êîä: '+ code);
  }
  if child0 <> nil then child0.traverse(code + '0', h);
  if child1 <> nil then child1.traverse(code + '1', h);
end;

--------------------

База IMEI-номеров украденных и утерянных мобильных телефоновhttp://imeis.net.ru/

zim22

Дата 8.3.2009, 19:19 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69

SergXP, алгоритм Хаффмана на С можете скачать отсюда: http://sourceforge.net/projects/huffman
я проверил. всё работает отлично.

--------------------

C++ FAQ Lite

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »