LZW編碼(dictionary coding)

LZW編碼是資料壓縮的一種方法
以下是LZW的演算法及簡單實作出LZW編碼的程式

BEGIN
s = next input character;
while not EOF
{
       c = next input character;
       if s + c exists in the dictionary
             s = s + c;
      else
     {
             output the code for s;
             add string s + c to the dictionary with a new code;
             s = c;
      }
}
output the code for s;
END

input = ABABBABCABABBA

s        c      output      code     string
--------------------------------
                                      1           A
                                      2          B
                                      3          C
---------------------------------
A       B          1              4          AB
B       A          2              5          BA
A       B
AB    B          4              6           ABB
B       A
BA    B          5               7           BAB
B       C          2               8           BC
C       A          3               9           CA
A       B
AB    A          4              10          ABA
A       B
AB    B
ABB A          6               11           ABBA
A      EOF     1

output  = 1 2 4 5 2 3 4 6 1


#include <iostream>
#include <vector>
#include <string>
#include <fstream>
using namespace std;

int main( void )
{
    vector<int> code;          //向量code儲存碼 
    vector<string> str;        //向量str儲存string 
    
    string input,s,c,temp;
    int j,i=1,search_result;
    
    fstream file1,file2;
    file1.open("input.txt");     //input為檔案資料輸入 
    file2.open("output.txt");    //output為檔案資料輸出 
    
    if(!file1 || !file2)
       cout << "檔案開啟失敗";
    else
       file1 >> input;               //讀進檔案裡的資料後 寫入input      
    
    //先將A B C 寫入字典 
    str.push_back("A");
    code.push_back(1);
    str.push_back("B");
    code.push_back(2);
    str.push_back("C");
    code.push_back(3);
    
    //編碼開始 
    s = input[0];
    while(1)
    {
        c = input[i++];
        temp = s + c;
        for(j=0;j<str.size();j++)
        {
            if(temp == str[j])  //temp已在字典裡 
            {
               s = s + c;
               search_result = 1;  
               break;   
            }
            search_result = 0;  //temp不再字典裡 
        }
        if( search_result == 0 )     
        {
            for(j=0;j<str.size();j++)
            {
                if( s == str[j] )
                {   
                    file2 << code[j] << " ";
                    break;
                }
            }  
            str.push_back(temp);
            code.push_back(code.size()+1);
            s = c;
        }
        if( i == input.size() )
            break;
    }
    for(j=0;j<str.size();j++)
    {
        if( s == str[j] )
        file2 << code[j];
    }
    //編碼結束
     
    system("pause");
    return 0;
}