Merhaba,

Bu müthiş algoritmayı kodlamadan evvel hazır bir C kodunu uyarlayım dedim. Şurada (http://www.programminglogic.com/implementing-huffman-coding-in-c/) çok güzel bir makaleye (by Daniel Scocco) denk geldim. Gerçi Türkçesi de var (-bknz. Huffman Kodu – Veri sıkıştırmanın temelleri (<www.yaksari.com/2009/04/huffman-kodu-veri-sikistirmanin-temelleri/>) - Bilg. Müh. Yiğitcan Aksarı) ama makale sonundaki kodun bağlantı adesi (kırık) maalesef erişim dışı...:)

Neyse, dil sorun değil sonuçta ama İngilizce ve C olması yeterliydi ama yine de şu aşağıdaki kodda (Daniel'in kodu) bir kaç hata (başlangıçta sadece 3 tane ama sonra 2 tane daha çıkmalı!) almaktayım. Çözemediğim için yardım ederseniz sevinirim:

import std.stdio, std.math;

struct node {
   int value;
   char letter;
   node *left, right;
}

alias node Node;

int[] englishLetterFrequencies = [ 81, 15, 28, 43, 128, 23, 20, 61, 71, 2, 1,
                                  40, 24, 69, 76, 20, 1, 61, 64, 91, 28, 10, 24, 1, 20, 1, 130 ];

int findSmaller (ref Node* array[], int differentFrom){
   int smaller;
   int i = 0;

   while(array[i].value == -1) i++;

   smaller = i;
   if(i == differentFrom)
   {
       i++;
       while (array[i].value == -1) i++;
       smaller = i;
   }

   for(i = 1; i < 27; i++)
   {
       if(array[i].value == -1) continue;
       if(i == differentFrom) continue;
       if(array[i].value < array[smaller].value) smaller = i;
   }
   return smaller;
}
void buildHuffmanTree(ref Node *tree){
   Node *temp;
   Node *array[27];
   int i, subTrees = 27;
   int smallOne, smallTwo;

   for(i = 1; i < 27; i++)
   {
       array[i] = new Node();
       array[i].value = englishLetterFrequencies[i];
       array[i].letter= cast(char)i;
       array[i].left  = null;
       array[i].right = null;
   }

   while (subTrees > 1)
   {
       smallOne = findSmaller(array, -1);
       smallTwo = findSmaller(array, smallOne);
       temp = array[smallOne];

       array[smallOne] = new Node();
       array[smallOne].value = temp.value + array[smallTwo].value;
       array[smallOne].letter= 127;
       array[smallOne].left  = array[smallTwo];
       array[smallOne].right = temp;
       array[smallTwo].value = -1;
       subTrees--;
   }
   tree = array[smallOne];
}
void fillTable(int[] codeTable, Node *tree, int Code){
   if(tree.letter < 27)
   {
       codeTable[cast(int)tree.letter] = Code;
   }
   else
   {
       fillTable(codeTable, tree.left,  Code * 10 + 1);
       fillTable(codeTable, tree.right, Code * 10 + 2);
   }
}
void compressFile(File input, File output, int[] codeTable){
   char bit, c, x = 0;
   int n, length, bitsLeft = 8;
   int originalBits = 0, compressedBits = 0;

   while((c=input.getc()) != 10){
       originalBits++;
       if(c == 32)
       {
           length = (cast(int)log10(codeTable[26])) + 1;
           n = codeTable[26];
       } else {
           length = (cast(int)log10(codeTable[c - 97])) + 1;
           n = codeTable[c - 97];
       }

       while(length > 0) {
           compressedBits++;
           bit = n % 10 - 1;
           n /= 10;
           x = x | bit;
           bitsLeft--;
           length--;
           if (bitsLeft == 0)
           {
               output.write(x);
               x = 0;
               bitsLeft = 8;
           }
           x = x << 1;
       }
   }
   if (bitsLeft != 8)
   {
       x = x << (bitsLeft - 1);
       output.write(x);
   }
   writeln(stderr, "Original bits = ",originalBits * 8);
   writeln(stderr, "Compressed bits = ", compressedBits);
   writeln(stderr, "Saved percent of memory = ", (cast(float) compressedBits / (originalBits * 8)) * 100);
}

void decompressFile (File input, File output, Node *tree){
   Node *current = tree;
   char c, bit;
   char mask = 1 << 7;
   int i;

   while(input.eof()){
       c = input.getc();
       for(i = 0; i < 8; i++) {
           bit = c & mask;
           c = c << 1;
           if(bit == 0) {
               current = current.left;
               if(current.letter != 127) {
                   if(current.letter == 26) output.write(32);
                   else output.write(current.letter + 97);
                   current = tree;
               }
           }
           else
           {
               current = current.right;
               if(current.letter != 127) {
                   if(current.letter == 26) output.write(32);
                   else output.write(current.letter + 97);
                   current = tree;
               }
           }
       }
   }
}
void invertCodes(int[] codeTable, int[] codeTable2){
   int i, n, copy;

   for(i = 0; i < 27; i++)
   {
       n = codeTable[i];
       copy = 0;
       while(n > 0) {
           copy = copy * 10 + n %10;
           n /= 10;
       }
       codeTable2[i] = copy;
   }
}

void main(){
   Node *tree;
   File input, output;
   char[] filename = new char[20];
   int[] codeTable = new int[27];
   int[] codeTable2 = new int[27];
   int compress;

   buildHuffmanTree(&tree);
   fillTable(codeTable, tree, 0);
   invertCodes(codeTable, codeTable2);

   writeln("Type the name of the file to process  :"); scanf("%s", filename);
   writeln("Type 1 to compress and 2 to decompress:"); scanf("%d", &compress);

   input = File(filename, "r");
   output = File("output.txt","w");

   if(compress == 1) compressFile(input, output, codeTable2);
   else decompressFile(input, output, tree);
}

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Cevabın için teşekkür ederim Ali hocam, önerilerin sayesinde malum kod çalışıyor...:)

Şöyle ki:

1- Bu bölümde çok takılmıştım ve aynı dediğin gibi yaptım ki kafadan iki hatayı eledim bile... ;-)

2- Üçüncü hata olan 83. satırı da dediğin komut, aşağıda gibi adeta cuk oturdu. Çünkü hiç dosyadan bayt okuma tecrübem yoktu ve 'std.stream''daki 'getc()''nin olabileceğini zanettim. Bu vesileyle sormak isterim 'std.cstream' ile diğeri arasındaki fark nedir? Biri C uyumlu mu demek?

while(input.readf("%c", &c), c!= 10){

3- İşte bu aşamadan sonra bir dizi hata (herhalde 10 tane çıkmıştır!) karşılaştım ki tam pes etmek üzereydim 'cast(...)' çiftli kullanımı imdadıma yetişti ve şu iki satırı bu şekilde hallettim:

: : :
x = cast(char) (cast(int) x << 1);
: : :
x = cast(char) (cast(int) x << (bitsLeft - 1));

Zaten 'ubyte' macerasına girseydim işin içinden çıkamazdım. Çünkü bir yerlerde eksili değerleri gördüm. Sanırım 'char' türü -127 ile 127 arasında değerle alıyor. Son olarak halledemediğim ama kısmen yerine isim yazarak uyarladığım 183. satırdaki hata ise şu:

input = File("input.txt", "r");

Alıntı:

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Şu anda zamanım olmadığı için daha fazla inceleyemiyorum ama hiç olmazsa derleme hatalarının bazılarını giderebildim.

1. Sabit uzunluklu dizilerle dilimlerin farklı olduklarını biliyoruz. Dilimler sabit uzunluk dizilerin elemanlarına erişim sağlayabilirler ama ta kendileri gibi davranamazlar. Öte yandan ref ise varolan bir değişkenin takma ismi demek oluyor.

Sonuçta, findSmaller()'ın 'ref Node*[]' parametresi 'Node*[27]' dizisine uymuyor. Burada şu olur:

int findSmaller (Node* array[], int differentFrom){

2. std.stdio.File'ın getc() diye işlevi yok. Onun için de şu olur:

input.readf("%c", &c);

Ama sonraki while() döngüsünün de düzenini değiştirmek gerekecek. Hem okumak hem de denetlemek aynı anda readf() ile olmayacak, çünkü readf()'in okuduğu karakteri döndürdüğünü sanmıyorum.

3. Daha sonra da x=x<<1 konusunda hata çıkacak. char değişken yerine ubyte değişkenin bit işleminde kullanılmasını öneririm.

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Alıntı (Salih Dinçer):

std.cstream, C giriş+çıkış akımlarını D akımları gibi gösteren bir modüldü. Emekliye ayrılacak. Onu unutun. D.ershane'ye başladığımda onu kullanmıştım ama sonra onu kullanan bütün örnekleri std.stdio kullanacak biçimde değiştirmiştim. :)

Alıntı:

Eğer C'de diyorsan, char'ın değer aralığı belirsizdir. C'de üç tür karakter vardır: 'unsigned char', 'signed char', ve onlardan birisi gibi işlemek zorunda olan 'char'. O yüzden C'de char'ın değer aralığı [0,255] de olabilir.

Ama D'de char'a bakışımızı değiştirmeliyiz. char, bir UTF-8 kod birimidir. Başka bir şey değil. (Kusura bakma, bunu çok tekrarlıyorum çünkü benim de bu gerçeği görmem uzun zaman aldı.)

Yani char Unicode standartlarıyla ilgili bir kod türü. :)

O yüzden Huffman kodlamasında geçmesi yanlış olur. Doğru sonuç veriyorsa tamam ama yine de garip karşılamalıyız.

Bence işaretli olacaksa byte, işaretsiz olacaksa da ubyte olmalı. char'dan daha karışık da olmaması gerek; çünkü char'ın bu programdaki kullanımlarına uyar o türler.

Alıntı:

> input = File("input.txt", "r");
> ```

> Alıntı:
> > huffman.d(181): Error: constructor std.stdio.File.this (string name, const(char[]) stdioOpenmode = "rb") is not callable using argument types (char[],string)
> > huffman.d(181): Error: cannot implicitly convert expression (filename) of type char[] to string
>

Bence öyle "input.txt" yazdığın zaman oluyor da 'filename' olmuyor. File'ın kurucusu string istiyor. .idup ile olabilir:

input = File(filename.idup, "r");

Veya to!string() ile:

import std.conv;
// ...
input = File(to!string(filename), "r");

Sonuçta 'Segmentation fault' almayı başardık galiba. :) (Hatanın nerede olduğuna bakmadım.)

Ali

-- 
[ Bu gönderi, <http://ddili.org/forum>'dan dönüştürülmüştür. ]

Alıntı (Ali Çehreli):

Sanırım 'char' türünden kaynaklı bir taşma hatası var ama programı parçalara bölüp bugün derinlemesine test edeceğim. Sanırım çalışma hatasına yol açan uyumsuzluğu giderebiliriz; bu kadar çok hatanın üstesinden geldiğimize göre. Olmadı yeniden yazarız ama benim önce şu bağlı liste olaylarına iyice hakim olmam lazım.

Sonuç aldığımda burada dillendireceğim inşaallah...

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Hocam teşekkürler, ~gdb çok çok iyimiş...:)

Görünüşe göre hata buildHuffmanTree (tree=0xbffff2e8 at huffman.d:37) içinde, daha doğrusu 'for()' ile kütüphaneden (englishLetterFrequencies) verileri çekip yerleştirdikten sonra' findSmaller()' içinde ne oluyorsa oluyor:

51	    while (subTrees > 1)
(gdb) s
53	        smallOne = findSmaller(array, -1);
(gdb) s
huffman.findSmaller (differentFrom=-1, array=13835042919817412635) at huffman.d:15
15	    int smaller;
(gdb) s
16	    int i = 0;
(gdb) s
18	    while(array[i].value == -1) i++;
(gdb) s

Program received signal SIGSEGV, Segmentation fault.
0x08085e46 in huffman.findSmaller (differentFrom=-1, array=13835042919817412635) at huffman.d:18

Sanırım halledilmeyecek bir şey değil, yakında kod hazır olur...:)

Sevgiler, saygılar...

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Bu noktada gdb'den yararlanabiliriz. Hatırlatma olarak şu konu vardı:

http://ddili.org/forum/thread/447

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

İpucu: buildHuffmanTree() içindeki array'in ilklenmemiş elemanı var.

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Alıntı (acehreli:1330381479):

for (i=0;i<27;i++) { array[i] = malloc(sizeof(Node)); ...

Hangi akla hizmet, nasıl böyle olduğunu bilmemekle (!) beraber 'int' 'findSmaller()' işlevi içindeki döngüler i=1 olmak zorunda; sanırım ana kökü ifade ettiği için. Ayrıca dosyadan okunan veri UTF8 ise 'char' kullanmamızın mantıklı görünmekte. Tabi dosyanın kodlamasına göre bu değişeceğinden, ('size_T' idi zannedersem?) otomatik bir değer türü kullanmalıyız.

Bu arada birden fazla kod ve yöntemi inceleyerek, bu güzel, nadide algoritmayı, en sade nasıl yapılabileceği üzerine çalışırken Knoth'un LiteratePrograms (http://en.wikipedia.org/wiki/Literate_programming)'ı ile tanıştım. Beraberinde MIT/X11 lisansı altında yayınlanan ve her dilden (D dili de var ama içinde bir tane bile kod yok!) algoritma parçaları olan vikisi (http://en.literateprograms.org/) ile karşılaştım. Sanırım burası official değil ve Knoth'un çizgisinden uzaklaşmış görünüyor. Açıkçası A.Çehreli'nin, kod yazmayı yeni öğrenenlere geliştirdiği yöntem çok daha güzel. Beraberinde D dili de tüm dünyadaki insanları programcı yapabilecek bir kucaklayıcılığa sahip olduğunu düşünüyorum. Neyse, sanırım çok uzayacak...:)

Bu konuyu D Dili'ni Yayma ve Tanıtma Faaliyetleri (http://ddili.org/forum/thread/707) başlığında tartışmayı öneriyorum. Son olarak, yukarıda bahsettiğim vikiden aldığım CPP kodunu paylaşmalıyım. Bildiğim kadarıyla D'de şablonları destekliyor ama ben henüz bu dersi (http://ddili.org/ders/d/sablonlar.html) öğrenmediğim için şimdilik aşağıdakini rafa kaldırıyorum ama yukarıda ilk paylaştığım üzerinde denemelere devam ettiğimi belirtmeliyim...

#include <vector>
#include <map>
#include <queue>

template<typename DataType, typename Frequency> class Hufftree {
   public:
       template<typename InputIterator>
        Hufftree(InputIterator begin, InputIterator end);

     ~Hufftree() {
       delete tree;
     }

     template<typename InputIterator>
      std::vector<bool> encode(InputIterator begin, InputIterator end);

     std::vector<bool> encode(DataType const& value) {
       return encoding[value];
     }

     template<typename OutputIterator>
      void decode(std::vector<bool> const& v, OutputIterator iter);

   private:
     class Node;
     Node* tree;

     typedef std::map<DataType, std::vector<bool> > encodemap; encodemap encoding;

     class NodeOrder;
};
template<typename DataType, typename Frequency>
 struct Hufftree<DataType, Frequency>::Node {
 Frequency frequency;
 Node* leftChild;

 union {
   Node* rightChild; // if leftChild != 0
   DataType* data;  // if leftChild == 0
 };

 Node(Frequency f, DataType d): frequency(f),
 leftChild(0), data(new DataType(d)) { }

 Node(Node* left, Node* right): frequency(left->frequency + right->frequency),
 leftChild(left), rightChild(right) { }

 ~Node() {
   if(leftChild) {
     delete leftChild;
     delete rightChild;
   } else {
     delete data;
   }
 }

 void fill(std::map<DataType, std::vector<bool> >& encoding, std::vector<bool>& prefix)
 {
   if(leftChild) {
     prefix.push_back(0);
     leftChild->fill(encoding, prefix);
     prefix.back() = 1;
     rightChild->fill(encoding, prefix);
     prefix.pop_back();
   } else {
     encoding[*data] = prefix;
   }
 }
};

template<typename DataType, typename Frequency>
template<typename InputIterator> Hufftree<DataType,
Frequency>::Hufftree(InputIterator begin, InputIterator end): tree(0) {

 std::priority_queue<Node*, std::vector<Node*>, NodeOrder> pqueue;
 while(begin != end) {
   Node* dataNode = new Node(begin->second, begin->first);
   pqueue.push(dataNode);
   ++begin;
 }

 while(!pqueue.empty()) {
   Node* top = pqueue.top();
   pqueue.pop();
   if(pqueue.empty()) {
     tree = top;
   } else {
     Node* top2 = pqueue.top();
     pqueue.pop();
     pqueue.push(new Node(top, top2));
   }
 }
 std::vector<bool> bitvec;
 tree->fill(encoding, bitvec);
}

template<typename DataType, typename Frequency>
 struct Hufftree<DataType, Frequency>::NodeOrder {

 bool operator()(Node* a, Node* b) {
   if(b->frequency < a->frequency)    return true;
   if(a->frequency < b->frequency)    return false;
   if(!a->leftChild && b->leftChild)  return true;
   if(a->leftChild && !b->leftChild)  return false;
   if(a->leftChild && b->leftChild) {
     if((*this)(a->leftChild, b->leftChild))  return true;
     if((*this)(b->leftChild, a->leftChild))  return false;
     return (*this)(a->rightChild, b->rightChild);
   }
   return *(a->data) < *(b->data);
 }
};

template<typename DataType, typename Frequency>
template<typename InputIterator> std::vector<bool> Hufftree<DataType,
Frequency>::encode(InputIterator begin, InputIterator end) {

 std::vector<bool> result;
 while(begin != end) {
   typename encodemap::iterator i = encoding.find(*begin);
   result.insert(result.end(), i->second.begin(), i->second.end());
   ++begin;
 }
 return result;
}

template<typename DataType, typename Frequency>
template<typename OutputIterator>
void Hufftree<DataType, Frequency>::decode(std::vector<bool> const& v, OutputIterator iter)
{
 Node* node = tree;
 for(std::vector<bool>::const_iterator i = v.begin(); i != v.end(); ++i) {
   node = *i? node->rightChild : node->leftChild;
   if(!node -> leftChild) {
     *iter++ = *(node->data);
     node = tree;
   }
 }
}

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Malum, hatalar insanlar için...:)

Robot olsaydık hata da yapmayacağımız için sanırım hiç bir şeyden tad alamayacaktık. Örneğin bu yanlışlık ve senin düzeltmen, Knuth'u yeni tanımaya ve hayat hikayesini okumaya sebep oldu! Allah uzun ömür versin; hala yaşıyor olmalı?

Kitabını gördükten sonra çok fazla araştırma gereği duymadım. Ama zannedersem en az Huffman (1999'da kanserden kaybetmişiz!) kadar değerli bir kişiymiş. Biz Türkler'den yazılım dünyasında ses getirecek birileri çıksa ne iyi olurdu? Yani bir Cahit Arf ve Oktay Sinanoğlu gibi kişiliklerden bahsediyorum. Sizce Türkler'den, bu sektörün duayenleri kimlerdir. Aslında bunu Ceviz Forumu'nda tartışmalı...

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]