LZW解碼(dictionary decoding)

延續上一篇文章
此程式為解碼用

BEGIN
s = NIL;
while not EOF
{
      k = next input code;
      entry = dictionary entry for k;
      if (entry == NULL) 
           entry = s + s[0];
      output entry;
      if (s != NIL)
           add string s + entry[0] to dictionary with a new code;
      s = entry;
}
END

input = 1 4 4 2 7 3 3
s         k       entry/output     code        string
--------------------------------------
                                                   1               A
                                                   2               B
                                                   3               C
--------------------------------------
NIL     1              A
A         4              A                    4                AA
A         4             AA                   5               AA
AA      2              B                     6               AAB
B         7              BB                  7                BB
BB      3              C                     8               BBC
C         3               C                    9               CC
C        eof

output = AAAABBBCC

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

int main( void )
{
    vector<int> code;            //向量code儲存碼 
    vector<string> str;          //向量str儲存string 
     
    string input,s,entry;
    char c;
    int j,i=1,search_result,k;
    stringstream input_num;
    
    fstream file1,file2;
    file1.open("input.txt");     //input為檔案資料輸入 
    file2.open("output.txt");    //output為檔案資料輸出 
    
    if(!file1 || !file2)
       cout << "檔案開啟失敗";     
    
    //先將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);
    
    //解碼開始 
    while(1)
    {
        while(1)  //讀取code 直到遇到空白停下 
        {    
           c = file1.get();
           if( c == ' ' || file1.eof() )
              break;                  
           else   
              input = input + c;     
        }    
        input_num << input;    //進行string轉成int的轉換 
        input_num >> k;
        input_num.clear();
        input.clear();
        
        search_result = 0;
        for(j=0;j<str.size();j++)
        {
            if( k == code[j] )
            {    
                search_result = 1;   //字典裡已有這個碼     
                entry = str[j];              
                break;
            }            
        }                             
        if( search_result == 0 )      //字典裡沒有這個碼   
            entry = s + s[0];  
        file2 << entry;  
        if( i != 1 ) 
        {
            str.push_back(s+entry[0]);
            code.push_back(code.size()+1);
        }  
        i=2;     
        s = entry;
        if(file1.eof())
           break;  
    }   
    //解碼結束 
    system("pause");
    return 0;
} 

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;
} 

RGB_YUV_Extraction

將一張大小為512*512的RAW檔裡的RGB值及YUV值抽取出來各成為一張圖片
其中RAW檔裡資料的排列方式為藍、綠、紅、藍、綠、紅....

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<cmath>

int main()
{
    int i;
    FILE *orimage=fopen("desert.raw", "rb");         //輸入檔為一張RAW檔
    unsigned char buffer[786432]; //512*512*3

    FILE *blue=fopen("desertRed.raw", "wb");
    FILE *green=fopen("desertGreen.raw", "wb");
    FILE *red=fopen("desertBlue.raw", "wb");
    FILE *y=fopen("deserty.raw","wb");
    FILE *u=fopen("desertu.raw","wb");
    FILE *v=fopen("desertv.raw","wb");

   for( i=0; i<786432; i++)
   {  
        buffer[i] = getc(orimage);  //依次讀一個 byte , 三個一組 , 依序存入紅綠藍 三檔案裡
        if( (i%3) == 0)
           putc(buffer[i],blue);  
        if( (i%3) == 1)   
           putc(buffer[i],green);
        if( (i%3) == 2)
        {  
           putc(buffer[i],red);
           putc( (buffer[i-2]*0.114 +  buffer[i-1]*0.587 +  buffer[i]*0.299),y);  //進行YUV矩陣換算
           putc( fabs(buffer[i-2]*0.437 +  buffer[i-1]*(-0.289) +  buffer[i]*(-0.148)),u);
           putc( fabs(buffer[i-2]*(-0.100) +  buffer[i-1]*(-0.515) +  buffer[i]*0.615),v);
        } 
   }
  
    system("pause");
    return 0;
}

Divide-and-Conquer for Maxima Finding

演算法:

定義: P1(x1,y1) dominate P2(x2,y2)  if only if x1  >= x2 and y1 >= y2

A point is called a max point if no other point dominate it 

輸入:一些平面上的點

輸出:THE MAXIMAL points

1. if 只有一點, 回傳它就是 max point 
    不然找一直線L垂直X軸 並且分割S成一半 SL and SR

2. 持續遞迴直到剩下兩點或一點， 進行比較

3. 開始merge， 在SR裡找到一點有最大的Y值，記錄它，
    並且在SL裡判斷所有的點的Y值有沒有小於這點的Y，
    如果有，刪除這點

程式碼實作如下

#include <stdio.h>
#include <stdlib.h>

struct vertex  //座標資料 
{
    int x;     //紀錄X位置 
    int y;     //紀錄Y位置 
    int max_point;    //紀錄是否為max_point 
};

void per( struct vertex *vertex_arr1, int init, int end) //per函式將所有點一分為二 init為初始注標 end為結尾注標 
{   
    int i,maxy=0,maxx=0;
    if( init == end )  //if分割到只勝一點 將這點指派為max_point 
       vertex_arr1[init].max_point = 1;
    else 
    {
       per(vertex_arr1, init, (init + end )/2);  //分割後 前半段帶入遞迴 
       
       //開始merge 
       for(i=(init + end )/2+1;i<=end;i++)  // 找後半段的最大y值的點   
       {
           if( maxy < vertex_arr1[i].y )
           { 
              maxx = vertex_arr1[i].x; 
              maxy = vertex_arr1[i].y;                     
           } 
       }
       
       for(i=init;i<=(init + end)/2;i++)   // 前半段的點若為max_point 則判斷此點x y值 若小於maxx maxy 則為不合的點 
       {
           if( vertex_arr1[i].max_point == 1 && vertex_arr1[i].x < maxx && vertex_arr1[i].y < maxy )
              vertex_arr1[i].max_point = 0;                    
       }
       
       per(vertex_arr1, (init + end )/2+1, end); //分割後 後半段帶入遞迴 
    }   
}

int main(void)
{
    int i,max=0,j,temp;
    char c[10];
    FILE *fp;
    fp = fopen("input.txt","r+"); 
    
    i=0;
    while(1)    //讀檔 
    {
       i++;
       if( fgets(c,10,fp) == NULL )
         break;
    }
    max = i-1; // 算有幾個點
    
    fseek(fp,0L,SEEK_SET); //移回檔頭 
    
    struct vertex *vertex_arr = malloc( max * sizeof(struct vertex) );
    for(i=0;i<max;i++)  //初始化 
    {
       vertex_arr[i].x = -1;
       vertex_arr[i].y = -1;
       vertex_arr[i].max_point = 0;             
    }
    
    i=0;
    while(1)    //讀檔 並放入vertex 結構 
    {
       fscanf( fp,"%d,%d",&(vertex_arr[i].x) ,&(vertex_arr[i].y) );
       i++;
       if( getc(fp) == EOF )
         break;
    }
     
    //先按照X值由小到大排列 
    for(i=0;i<max;i++)
    {
       for(j=i+1;j<max;j++)
       {             
          if( vertex_arr[i].x > vertex_arr[j].x )
          {    
              temp = vertex_arr[i].x;
              vertex_arr[i].x = vertex_arr[j].x;
              vertex_arr[j].x = temp;
              
              temp = vertex_arr[i].y;
              vertex_arr[i].y = vertex_arr[j].y;
              vertex_arr[j].y = temp;
          }
       }             
    }
    
    per(vertex_arr,0,max-1); //開始遞迴 
    
    for(i=0;i<max;i++) //印出max_point 
    {
        if( vertex_arr[i].max_point == 1 )             
          printf("%d,%d\n",vertex_arr[i].x ,vertex_arr[i].y);                      
    }
    system("pause");
    return 0;
} 

輸入請以讀入檔案方式。
例如：以下檔案內容，代表5個平面座標點
2,3
4,5
6,7
8,9
10,11