Forum: Projeler dkv RSS
Veri Sıkıştırma Modülü
Sayfa:  1  2  3  sonraki 
Kadir Can #1
Üye Haz 2010 tarihinden beri · 413 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Konu adı: Veri Sıkıştırma Modülü
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());
}
acehreli (Moderatör) #2
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4391 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Ç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
Avatar
huseyin #3
Üye Haz 2012 tarihinden beri · 355 mesaj · Konum: Isparta
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
KadirCan sen projeyi ilerlette bizim veritabanlarına ekleyelim :)
Huseyin
Kadir Can #4
Üye Haz 2010 tarihinden beri · 413 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Tavsiyeler için teşekkür ederim. Özellikle eşleme tablosunda kontrol olmaması hoş bir özellikmiş.
@huseyin325325;
En kısa zamanda bitireceğim.
Avatar
Salih Dinçer #5
Üye Ock 2012 tarihinden beri · 1880 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Eline sağlık Kadir, bilmiyorum şuradaki girişimimi 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.
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #6
Üye Ock 2012 tarihinden beri · 1880 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
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]
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Kadir Can #7
Üye Haz 2010 tarihinden beri · 413 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
@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.
Avatar
Salih Dinçer #8
Üye Ock 2012 tarihinden beri · 1880 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Kadir Can:
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.
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ş...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Kadir Can #9
Üye Haz 2010 tarihinden beri · 413 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Belirttiğin için teşekkür ederim. Ben denediğimde her harf için ayrı kod üretmişti. Bir elden geçirmeliyim.
Kadir Can #10
Üye Haz 2010 tarihinden beri · 413 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
@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);
    }
}
Avatar
Salih Dinçer #11
Üye Ock 2012 tarihinden beri · 1880 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Bu durumda çıktısı aşağıdaki gibi oluyor. Öyleyse decompress olayına girsek de katmerlesek mi...:)

d:00000000
a:00000001
dabc:00000000
b:00000010
c:00000011
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
zafer #12
Üye Tem 2009 tarihinden beri · 687 mesaj · Konum: Ankara
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Kadir eline sağlık, senin kodlamaların hoşuma gidiyor. Bir itirafta bulunmak gerekirse Huffman konusunu Salih ilk açtıgında bende kodlamayı denemiştim ama becerememiştim  :blush:

Bence çözme (decompress) olayından sonra bu kodlardan deneysel küçük bir program bile çıkar ;)
https://github.com/zafer06 - depo
Kadir Can #13
Üye Haz 2010 tarihinden beri · 413 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Şimdi sıkıştırma özelliğini de ekledim ama çıkan sonuç çok şaşırtıcı; programa verilen metin dosyasının boyutunu yaklaşık olarak 3 kat artırıyor. :( Acaba gözden kaçan bir nokta mı var?
module huffman.d;
import std.stdio;
import std.conv;
import std.algorithm;
struct HuffmanTree
{
    private
    {
        uint[string] compressTable_;
        string[uint] decompressTable_;
        Node top_;
        File fileToCompress_;
        File compressedFile_;
        string fileName_;
    }
 
    public this(string fileName)
    {
        fileToCompress_.open(fileName ~ ".txt", "r");
        compressedFile_.open(fileName ~ "compressed" ~ ".txt", "w");
        fileName_ = fileName ~ ".txt";
    }
 
    ~this()
    {
        auto tables = File("tables.had", "w");
        tables.writeln(compressTable_);
        tables.writeln(decompressTable_);
        fileToCompress_.close();
        compressedFile_.close();
    }
 
    public void setTables(Node top)
    {
        compressTable_ = top_.returnTable;
        foreach(key, value; compressTable_){
            decompressTable_[value] = key;
        }
    }
 
    public void compressFile()
    {
        string lines;
        while(!fileToCompress_.eof()){
            lines ~= fileToCompress_.readln();
        }
        auto nodes = searchLetters(lines);
        top_ = createTree(nodes);
        top_.setBinaryCodes();
        setTables(top_);
        foreach(letter; lines){
            compressedFile_.writef("%b",compressTable_[to!string(letter)]);
        }
    }
}
 
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() const @property
    { 
        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;
                } 
            }
        }
        foreach(index, value; result){
            if(index.length != 1){
                result.remove(index);
            }
        }
        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 fileName = "text";
    auto tree = HuffmanTree(fileName);
    tree.compressFile();
}
Bu mesaj Kadir Can tarafından değiştirildi; zaman: 2012-07-11, 16:01.
acehreli (Moderatör) #14
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4391 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Bu program binary sonucu metin halinde yazdırıyor:

11011110110101111101111101111001111100011100

Oysa onları sekizer sekizer kullanarak baytlar halinde yazdırmalı. Örneğin ilk sekizli olan 11011110'ın karşılığı olan değer (sanırım 255 - 32 - 1 = 222) yazılmalı. vs.

Ali
Kadir Can #15
Üye Haz 2010 tarihinden beri · 413 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Teşekkürler, sanırım ben algoritmalardaki o kısmı atlamışım.
Yarın açma işlemlerini de hazırlayıp yeni veritabanı çalışmamıza göndermiş olurum.
Doğrulama Kodu: VeriCode Lütfen resimde gördüğünüz doğrulama kodunu girin:
İfadeler: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Özel Karakterler:
Sayfa:  1  2  3  sonraki 
Forum: Projeler dkv RSS
Bağlı değilsiniz. · Şifremi unuttum · ÜYELİK
This board is powered by the Unclassified NewsBoard software, 20100516-dev, © 2003-10 by Yves Goergen
Şu an: 2017-04-30, 15:26:09 (UTC -07:00)