# 計算機概論筆記
[compiler](https://hackmd.io/@Zero871015/compiler)
# 9
1. 原始碼
2. 詞法分析 (Lexical Analysis)掃描字元並將他們分組，形成tokens，
舉例，現在有一行程式為`position = initial + rate * 60`
經過scan，將其轉為`<id, position> = <id, initial> + <id, rate> * 60`
其中`<id, position>` `=` `<id, initial>` `+` `<id, rate>` `*` `60`都各是一個token

3. 文法分析(Syntax Analysis)
將tokens組合成語法
4. 語義分析 (Semantic Analysis)
辨識語法錯誤和型別問題
5. 代碼生成器(code generator)
生成組合語言，機械語言等低階語言

[簡介](https://hackmd.io/@Zero871015/compiler-1)

## 物件導向程式設計 (object-oriented paradigm)
* 方法Methods(在物件裡的funtioin)
* 繼承Inheritance(如果有寫好的類別模板，直接繼承再改，不用再重寫一遍)
* 多型Polymorphism(就是寫好的函式可以用在任何型別上，譬如int+int，float+int，運算子多載、樣板)

# 15 資料壓縮

## Huffman Coding 霍夫曼编码
算法目的，讓出越多次的字用越短的編碼，越不常使用的用長編碼。

| A | B | c | d | E |
|:---:|:---:|:---:|:---:|:---:|
| 17 | 12 | 12 | 27 | 32 |

一個node要儲存的資料，還要設定一個空字元，這裡假定" "空白
| node | node |
|:------------:|:------------:|
| 使用次數 | 符號或是字元 |
| 左節點記憶體 | 右節點記憶體 |

第一步先取兩個不常用的編碼

digraph LR { 
// rankdir=LR;
        "24|" ->"12|B" 
		"24|" -> "12|C"
		"17|A"
        "27|D"
        "32|E"
	} 

再取兩個不常用的節點編碼

digraph LR { 
// rankdir=LR;
        "24| " ->"12|B" 
		"24| " -> "12|C"
		"41| "->"17|A"
        "41| "->"24| "
        "27|D"
        "32|E"
	} 

一直取兩個不常用的節點編碼

digraph LR { 
// rankdir=LR;
        "24| " ->"12|B" 
		"24| " -> "12|C"
		"41| "->"17|A"
        "41| "->"24| "
        "59| "->"27|D"
        "59| "->"32|E"
        "100| "->"41| "
        "100| "->"59| "
	} 

然後我們尋訪時，0走左，1走右，來編碼。
所以ABCDE的編碼
| A | B | c | d | E |
|:---:|:---:|:---:|:---:|:---:|
| 01 | 000 | 001 | 10 | 11 |

ADABCDE -> 0110010000011011
然後解碼回來就是造著樹走，走道根就輸出
01

| 10 | 01 | 000 | 001 | 10 | 11 |
|:---:|:---:|:---:|:---:|:---:|:---:|
| A | D | A | B | C | D |

# Dictionary-Based Compression

要建造一個字典Dictionary、或說映射表map，讀入一個字，沒看過就加進去字典，給編號，有看過繼續加字，變成片語(至少兩個單字)，這個片語沒看過，片語有n個字，n-1個字看過，就編碼+第n字。
`BAABABBBAABBBBAA`
1. B ->B
2. A ->A
3. AB ->2B
4. ABB ->3B
5. BA ->1A
6. ABBB ->4B
7. BAA ->5A

最終編碼是
`B A 2B 3B 1A 4B 5A`

#include<iostream>
#include<string>
#include<map>

using namespace std;

//Function to compress string using Dictionary-Based Compression 
string DictionaryCompression(string s)
{
    //String to hold compressed string 
    string compressedString = "";

    //Map to store pattern and its code
    map<string, int> code;

    //Starting code value
    int codeValue = 1;

    //Variable to store last pattern
    string lastPattern;

    //Iterate over each character of the string
    for(int i=0; i<s.length(); i++)
    {
        //Store current pattern
        string currentPattern = s.substr(i, 1);

        //Check if the pattern is already present in the map
        if(code.find(currentPattern) == code.end())
        {
            //Pattern not found
            //Insert pattern and its code in the map
            code[currentPattern] = codeValue;

            //Append code to the compressed string
            compressedString += to_string(codeValue);

            //Increment code value
            codeValue++;

            //Store the current pattern as last pattern
            lastPattern = currentPattern;
        }
        //Pattern found
        else
        {
            //Append code of the pattern to compressed string
            compressedString += to_string(code[currentPattern]);

            //Store pattern as last pattern
            lastPattern = currentPattern;
        }
    }

    //Return compressed string
    return compressedString;
}

//Main function
int main()
{
    //String to compress
    string s;

    cout<<"Enter the string to compress: ";
    cin>>s;

    //Call DictionaryCompression function
    string compressedString = DictionaryCompression(s);

    //Print the compressed string
    cout<<"Compressed String: "<<compressedString<<endl;

    return 0;
}