c++ - LZW 解码的 C++ 问题

Question

我正在编写 LZW 算法，但在解码编码文件时遇到问题。编码功能工作正常，据我所知，问题是在解码功能中构建字典。编辑：解码字典的大小比编码字典大 1。此外，解码字典似乎不包含任何超过 2 个字符的字符串值。为了测试，我使用了爱丽丝梦游仙境的 .txt 文件，前几个词没问题，但之后一切都出错了

我的编码功能：

void encode(char* path, int vel_s){
    unordered_map<string,int>dict; //dictionary
    int bit_size = ceil(log2(vel_s + 1)); //size of codes - x bits
    //init dictionary
    for(int i = 0; i < 256; i++){
        string k = "";
        k.push_back((unsigned char)i);
        dict[k] = i;
    }
    int count = 256, maxVel = pow(2, bit_size); //counter and max value in bits
    BinReader reader(path);//text to encodede
    BinWriter writer("out.bin");//output file
    string P = "";
    P.push_back(reader.readByte());//read first char
    while(!reader.f.eof()){
        char C = reader.readByte(); //read next char
        if(dict.find(P + C) != dict.end()){ //if in dictionary
            P+=C;
        }else{ //if not in dictionary
            if(count >= maxVel){
                count = 0;
            }
            int out = dict[P]; //int code of P
            string binString = toBinary(out, bit_size); //binary value of out
            for(int i = 0; i<binString.size();i++){ //write bits
                if(binString[i]=='1'){
                    writer.writeBit(true);
                }else{
                    writer.writeBit(false);
                }
            }
            dict[P + C] = count; //write P+C to dictionary
            count++;
            P = C; //overwrite P
        }
    }
    //write last output
    int out = dict[P];
    string binString = toBinary(out, bit_size);
    for(int i = 0; i<binString.size();i++){
        if(binString[i]=='1'){
            writer.writeBit(true);
        }else{
            writer.writeBit(false);
        }
    }
}

这是解码功能：

void decompress(char* path, int vel_s){//file path + dictionary max size
    unordered_map<int,string>dict; //dictionary
    int bit_size = ceil(log2(vel_s + 1));//max number of bits in code
    for(int i = 0; i < 256; i++){ //init dictionary
        dict[i] = (unsigned char) i;
    }
    int count = 256; //counter
    vector<bool>B;
    BinWriter writer("out_d.txt"); //output file
    BinReader reader(path); //input file
    int newI, oldI; //new and old value
    for(int i = 0; i < bit_size; i++){ //read code from encoded file of size bit_size
        B.push_back(reader.readBit());
    }
    oldI = convertToInt(B); //convert to integer
    string S = dict[oldI]; //String is dictionary value of old value
    writer.writeByte(S[0]); //write first letter
    string C = ""; //init C
     C =S[0]; //C is first character of S
    int maxVel = pow(2, bit_size); //max value of encoded code
    while(!reader.f.eof()){
        B.clear();//clear vector B for reading bits
        for(int i = 0; i < bit_size; i++){
            B.push_back(reader.readBit());//read next code
        }
        newI = convertToInt(B); //convert bits to int
        if(dict.find(newI) == dict.end()){ //if new value not in dictionary
            S = dict[oldI]; //S is value of old code
            S += C; //concat C to S
        }else{
            S = dict[newI]; //S is value of new code
        }
        for(int k = 0; k < S.size(); k++){ //write S to file
            writer.writeByte(S[k]);
        }
        C = "";
        C += S[0]; //C is first character of S
        dict[count] = dict[oldI] + C; //new input in dictionary
        count++;
        oldI = newI; //old value is new value
    }

还有我用来寻求帮助的 toBinary() 和 convertToInt() 函数

string toBinary(int x, int l){
    string temp;
    while(x!=0){
        temp =(x%2==0 ? "0":"1")+temp;
        x/=2;
    }
    while(temp.length() != l){
        temp = "0"+temp;
    }
    return temp;
}


int convertToInt(vector<bool>B){
    int power= B.size()-1,res= 0;
    for(int i = 0; i < B.size(); i++){
        if(B[i]){
            res+=pow(2, power);
        }
        power--;
    }
    return res;
}

标签： c++algorithm