Veri sıkıştırma modülünü yazmaya başladım, şu an için doğru çalışıyor gibi görünüyor, en kısa zamanda birim testleri ekleyeceğim. Şu haliyle nasıl görünüyor?

module huffman;
import std.algorithm;
import std.stdio;
import std.conv;
struct Node
{
	private
	{
		dstring value_;
		int binaryCode_;
		int frequence_;
		Node* right_;
		Node* left_;
	}

	public this(const int frequence, dstring value)
	{
		value_ = value;
		frequence_ = frequence;
	}

	public int opCmp(Node another) const
	{
		return (frequence_ - another.frequence_);
	}

	public dstring toString() const
	{
		dstring result;
		result ~= "Binary code: " ~ to!dstring(binaryCode_) ~ "\n";
		result ~= "Letter: " ~ value_ ~ "\n";
		return result;
	}

	public void setBinaryCodes()
	{
		if(right_ && left_)
		{
			right_.binaryCode_ = binaryCode_;
			left_.binaryCode_ = binaryCode_;
			right_.binaryCode_ <<= 1;
			left_.binaryCode_ <<= 1;
			left_.binaryCode_ |= 1;
			right_.setBinaryCodes();
			left_.setBinaryCodes();
		}
	}

	public int[dstring] returnTable()
	{
		int[dstring] result;
		result[value_] = binaryCode_;
		if(right_ && left_)
		{
			foreach(index, value; left_.returnTable()){
				result[index] = value;
			}
			foreach(index, value; right_.returnTable()){
				result[index] = value;
			}
		}
		return result;
	}
}

Node[] searchLetters(dstring text)
{
	int[dchar] letters;
	Node[] result;
	foreach(character; text){
		if(character in letters){
		    ++letters[character];
		} else {
			letters[character] = 1;
		}
	}
	foreach(index, value; letters){
		result ~= Node(value, to!dstring(index));
	}
	return result;
}

Node createTree(Node[] nodes)
{
	while(nodes.length > 1)
	{
		nodes.sort();
		auto newNode = Node((nodes[0].frequence_ + nodes[1].frequence_), (nodes[0].value_ ~ nodes[1].value_));
		newNode.left_ = &nodes[0];
		newNode.right_ = &nodes[1];
		nodes ~= newNode;
		nodes = nodes[2 .. $];
	}
	return nodes[0];
}

void main()
{
	dstring text = "Hello World";
	auto top = createTree(searchLetters(text));
	top.setBinaryCodes();
	writeln(top.returnTable());
}

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

KadirCan sen projeyi ilerlette bizim veritabanlarına ekleyelim :)

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

Çok hızlıca:

• toString geleneksel olarak string döndürüyor. Bence şu daha kolay olabilir:

   public string toString() const
   {
       return format("Binary code: %s\nLetter: %s\n", binaryCode_, value_);
   }

• dstring yerine string de kullanılabilir çünkü Huffman rasgele erişim gerektirmez.

• Histogramı hesaplarken hiç tabloda olup olmadıklarına bakmadan arttırabilirsin:

   foreach(character; text){
       ++letters[character];
   }

Eğer 'character' tabloda yoksa letter[character] yazıldığı anda .init değeriyle eklenir.

• Önemsiz olarak, frequence da doğru ama hemen her zaman frequency kullanılıyor.

Ali

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

Tavsiyeler için teşekkür ederim. Özellikle eşleme tablosunda kontrol olmaması hoş bir özellikmiş.
@huseyin325325;
En kısa zamanda bitireceğim.

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

@Salih;
Oradaki kodlardan haberim yoktu, teşekkür ederim. İnceleyeceğim. :)
O kısım hata değil, sanırım sen sıklığı yazdırdığını düşündün. Orada harf için kullanılacak ikili kodu yazdırıyor.

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

Eline sağlık Kadir, bilmiyorum şuradaki girişimimi (http://ddili.org/forum/thread/734) okudun mu? Belki oradaki kodlar farklı bakış açıları verebilir. Ayrıca sıkıştırma algoritması olarak buna bir şey daha eklemeli. Tek başına bazı durumlarda işe yaramadığını duymuştum.

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

Sanırım çok küçük bir hata olmalı...

Eğer tek karakterden oluşan (örn. 23 adet a harfi) bir metin yazarsak çıktı şu şekilde oluyor:

'["a":0]'

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

Alıntı (Kadir Can):

Peki nasıl decompress etmeyi düşünüyorsun? Örneğin veri "abbcccdddd" ise senin kod şunu üretiyor:

'["cab":0, "c":1, "a":1, "d":1, "b":0, "dcab":0, "ab":0]'

Huffman ağacı olarak da şöyle ifade edilebiliyormuş:

'10{d:4[0]},
6{c:3[11]},
3{a:1[100],
b:2[101]}
'
Yani binary kodu a için 100, b için 101, c için 011 ve d için 000 eşleştirmiş...

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

Belirttiğin için teşekkür ederim. Ben denediğimde her harf için ayrı kod üretmişti. Bir elden geçirmeliyim.

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

@Salih,
Sorunu aştım, sebep çok ilginç; opCmp işlecini yüklerken sadece sıklıkları göz önüne aldığım için aynı sıklıktaki değerleri her seferinde farklı sıralayarak ağacın yanlış oluşmasına neden oluyordu. cmp() işlevini kullanarak düzelttim.
Son hali;

module huffman.d;
import std.algorithm;
import std.stdio;
import std.conv;
struct Node
{
	private
	{
		string value_;
		uint binaryCode_;
		uint frequency_;
		Node* right_;
		Node* left_;
	}

	public this(const uint frequence, string value)
	{
		value_ = value;
		frequency_ = frequence;
	}

	public uint opCmp(Node another) const
	{
		return frequency_ == another.frequency_ ? cmp(value_, another.value_) : frequency_ - another.frequency_ ;
	}

	public string toString() const
	{
		string result;
		result ~= "Binary code: " ~ to!string(binaryCode_) ~ "\n";
		result ~= "Letter: " ~ value_ ~ "\n";
		return result;
	}

	public void setBinaryCodes()
	{
		if(right_ && left_)
		{
			right_.binaryCode_ = binaryCode_;
			left_.binaryCode_ = binaryCode_;
			right_.binaryCode_ <<= 1;
			left_.binaryCode_ <<= 1;
			right_.binaryCode_ |= 1;
			right_.setBinaryCodes();
			left_.setBinaryCodes();
		}
	}

	public uint[string] returnTable()
	{
		uint[string] result;
		result[value_] = binaryCode_;
		if(right_ && left_)
		{
			foreach(index, value; left_.returnTable()){
				if(index.length==1){
				    result[index] = value;
				}
			}
			foreach(index, value; right_.returnTable()){
				if(index.length==1){
					result[index] = value;
				}
			}
		}
		return result;
	}
}

Node[] searchLetters(string text)
{
	uint[char] letters;
	Node[] result;
	foreach(character; text){
		if(character in letters){
		    ++letters[character];
		} else {
			letters[character] = 1;
		}
	}
	foreach(index, value; letters){
		result ~= Node(value, to!string(index));
	}
	return result;
}

Node createTree(Node[] nodes)
{
	while(nodes.length > 1)
	{
		nodes.sort();
		auto newNode = Node((nodes[0].frequency_ + nodes[1].frequency_), (nodes[0].value_ ~ nodes[1].value_));
		newNode.left_ = &nodes[0];
		newNode.right_ = &nodes[1];
		nodes ~= newNode;
		nodes = nodes[2 .. $];
	}
	return nodes[0];
}

void main()
{
	string text = "abbcccdddd";
	auto top = createTree(searchLetters(text));
	top.setBinaryCodes();
	foreach(index, value; top.returnTable()){
		writefln("%s:%.8b",index,value);
	}
}

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