LZ78算法

压缩

#include "Dictionary.h"
#include <iostream>
#include <fstream>
#include <string>  

int main(int argc, char* argv[])
{
    std::ifstream file("test.txt");
    std::ofstream out("test2.lzw");
    char ch;
    std::string perfix = "";
    Dictionary dict;

    while (!file.eof())
    {
        file>>ch;
        if (dict.is_exist(perfix+ch))
        {
            perfix += ch;
        }
        else
        {
            out<<dict.get_mask(perfix)<<ch;
            dict.add(perfix+ch);
            perfix = "";
        }
    }

    if (perfix != "")
    {
        out<<dict.get_mask(perfix);
    }

    file.close();
    out.close();
    std::cout<<"conpress success!"<<std::endl;
    return 0;
}

解压

#include <fstream>
#include <string>
#include "Dictionary.h"


int main(int argc, char* argv[])
{
    std::ifstream file("test2.lzw");
    std::ofstream out("test2.txt");
    std::string prefix = "";
    char ch;
    long mask;
    Dictionary dict;
    
    while (!file.eof())
    {
        file>>mask>>ch;
        std::string temp = dict.get_perfix(mask)+ch;
        out<<temp;
        dict.add(temp);
    }

    std::cout<<"decompress success"<<std::endl;
    return 0;
}

字典实现

#include <map>
#include <string>

class Dictionary  
{
public:
    std::string get_perfix(long mask);
    long get_mask(const std::string perfix);
    bool is_exist(const std::string member);
    void add(const std::string word);
    Dictionary();
    virtual ~Dictionary();

private:
    long index;
    std::map<std::string, long> store; 
};

Dictionary::Dictionary()
{
    index = 0;
}

Dictionary::~Dictionary()
{
}

void Dictionary::add(const std::string word)
{
    this->store[word] = ++index;
}

bool Dictionary::is_exist(const std::string member)
{
    std::map<std::string, long>::iterator pos;
    pos = this->store.find(member);
    if (pos != store.end())
    {
        return true;
    }
    else
    {
        return false;
    }
}

long Dictionary::get_mask(const std::string perfix)
{
    if ((index==0) || (perfix==""))
    {
        return 0;
    }
    else
    {
            std::map<std::string, long>::iterator pos;
            pos = this->store.find(perfix);
            if (pos != store.end())
            {
                return pos->second;
            }
            else
            {
                return 0;
            }
    }
}

std::string Dictionary::get_perfix(long mask)
{
    if (mask != 0)
    {
        std::map<std::string, long>::iterator pos;
        for (pos = this->store.begin(); pos != store.end(); pos++)
        {
            if (pos->second == mask)
            {
                return pos->first;
            }
        }
    }
    return "";
}

检验比较

#include <iostream>
#include <fstream>

int main(int argc, char* argv[])
{
    std::ifstream file_first("test.txt");
    std::ifstream file_second("test2.txt");

    char ch_first;
    char ch_second;

    while (!file_first.eof() && !file_second.eof())
    {
        file_first>>ch_first;
        file_second>>ch_second;
        if (ch_first != ch_second)
        {
            std::cout<<"do not complete "<<std::endl;
            return 0;
        }
    }
    std::cout<<"complete"<<std::endl;
    return 0;
}