家豪教學網工科賽程式設計教學 113 年第四題

參考題型範例 - 全國高級中等學校技藝競賽平台工業類
題目：英文字串壓縮程式
問題描述
本英文字串壓縮程式將依哈夫曼編碼檔( huffman.json) 對每一個英文字母進行編碼，如右圖所示，字母 s 編碼成 0000、字母 e 編碼成 001、字母 r 編碼成 11111。此 huffman.json 的編碼是依 Jane Austen 所寫的《傲慢與偏見》一書的 ASCII 文件，其原始文字的檔案大小為 704,175 字元(字母)，相當於 5,633,400 位元。統計完所有字元 (含大小寫英文字母、數字及符號) 的頻率後，得到了本題使用的哈夫曼編碼檔；頻率高的字元編碼較短，頻率低的字元編碼較長；本程式只對 88 個字元進行編碼，英文字串中若頻率高的字元居多就有較好的壓縮比。
程式執行狀態：程式不用處理輸入錯誤的問題 (如輸入中文字或符號)，將 txt 檔與 exe 執行檔放在同一資料夾內。

輸入檔名：程式一開始要求使用者 (你) 輸入一個 "內文為英文的檔名(.t×t)"，如右圖所示，輸入 s04.txt檔；
顯示該輸入檔的內容：其內容為 ship；
壓縮後的編碼：依 huffman.json 檔，輸入檔內容的編碼為 00000001 01000110 00；
壓縮比：為 0.75 (壓縮後儲存的總 Byte 數 / 壓縮前儲存的總 Byte 數 = 3/4)；
儲存壓縮檔：最後將壓縮後的 18bit 存入 s04.bin 中；其主檔名須相同於輸入檔的主檔名。

繳交檢查時，除源碼檔外，請同時提供 .exe 執行檔，測試資料不限所附 3 個 .txt 檔案。

因為題意不夠明確，在不影響題目情況下，略作補充。

補充資料：

將題目所附贈的 huffman.json 檔案加入專案中。

選擇 huffman.json，並將其加入專案。

輸入資料最好能顯示目前讀檔的路徑在哪裡。
因為版本不同，路徑也會有些微不同。使用 string currentDirectory = Directory.GetCurrentDirectory(); 找到目前執行檔路徑，再將 huffman.json 放到該路徑，或是使用 Directory.GetParent(currentDirectory).FullName 往上移動目前存取的路徑。
輸出碼時，按照題目畫面，應該每 8 bits 要隔一個空白。
壓縮比取至小數第二位，不足後位補零。

範例一：

範例二：

範例三：

程式碼下載

using System;
using System.Collections.Generic;
using System.IO;
using System.Text.Json;

namespace MyNamespace
{
    class My113Class
    {
        public static string[] ComplementCode = { "", "0", "00", "000", "1110", "11110", "111101", "1111010" };//編碼不足 8 碼後補碼
        static void Main()
        {
            string currentDirectory = Directory.GetCurrentDirectory();
            Console.Write($"目前檔案路徑：{currentDirectory}\n請輸入內文為英文的檔名（.txt）：");
            string inputFileName = Console.ReadLine();
            if (!File.Exists(inputFileName))
            {
                Console.WriteLine("檔案不存在！");
                return;
            }

            string content = File.ReadAllText(inputFileName); // 讀取文字內容
            Console.WriteLine($"{inputFileName} 的檔案內容：\n{content}\n");

            // 定義 Huffman 編碼的路徑 (檔案在 上上上上層，依照個人環境而定)
            string huffmanPath = Directory.GetParent(Directory.GetParent(Directory.GetParent(Directory.GetParent(currentDirectory).FullName).FullName).FullName).FullName + "\\" + "huffman.json";
            if (!File.Exists(huffmanPath))
            {
                Console.WriteLine("huffman.json 檔案不存在！");
                return;
            }
            var huffmanCodes = JsonSerializer.Deserialize<Dictionary<char, string>>(File.ReadAllText(huffmanPath));// 使用 System.Text.Json 讀取 Huffman 編碼
            int encodeLen;
            string encodedString = FormatEncodedString(EncodeContent(content, huffmanCodes), out encodeLen); // 將文字內容進行 Huffman 壓縮編碼
            Console.WriteLine($"壓縮後的編碼：\n{encodedString}");
            double compressionRatio = Math.Round((double)encodeLen / content.Length, 2); // 計算壓縮比
            Console.WriteLine($"壓縮比：{compressionRatio:F2}"); //小數第二位，不足補 0
            string outputFileName = Path.ChangeExtension(inputFileName, ".bin"); // 儲存壓縮後的檔案
            SaveToBinaryFile(encodedString, outputFileName);
        }

        static string EncodeContent(string content, Dictionary<char, string> huffmanCodes) //查表法編碼
        {
            var encoded = new System.Text.StringBuilder();
            foreach (char c in content)
            {
                if (huffmanCodes.TryGetValue(c, out string code))
                {
                    encoded.Append(code);
                }
                else
                {
                    Console.WriteLine($"警告：字元 '{c}' 未在 Huffman 編碼中定義，略過。");
                }
            }
            return encoded.ToString();
        }

        static void SaveToBinaryFile(string encodedString, string fileName) //存檔 + 顯示
        {
            // 分割字串為區塊並補碼
            string[] blocks = encodedString.Split(' ');
            if (blocks[blocks.Length - 1].Length < 8)
            {
                int complementIndex = 8 - blocks[blocks.Length - 1].Length;
                if (complementIndex < ComplementCode.Length)
                {
                    blocks[blocks.Length - 1] += ComplementCode[complementIndex];
                }
            }
            byte[] bytesV = new byte[blocks.Length];
            for (int i = 0; i < blocks.Length; i++)
            {
                bytesV[i] = (byte)Convert.ToInt32(blocks[i], 2); // 將二進位字串轉換為整數，並轉為 char
            }
            File.WriteAllBytes(fileName, bytesV);
            Console.WriteLine($"壓縮後的檔案名稱：{fileName}");
            Console.WriteLine($"存入壓縮檔的編碼：");
            for (int i = 0; i < blocks.Length; i++)
            {
                Console.Write(((i == 0) ? "" : " ") + blocks[i]);
            }
            Console.WriteLine();
        }

        static string FormatEncodedString(string encodedString, out int encodeLen) //組合每 8 個二進位為一字串中間+空白
        {
            var formatted = new System.Text.StringBuilder();
            int length = encodedString.Length;
            encodeLen = (int)Math.Ceiling(length / 8.0);
            for (int i = 0; i < length; i += 8)
            {
                // 使用 Substring 取得每 8 個字元
                int remainingLength = Math.Min(8, length - i); // 防止超出範圍
                formatted.Append(encodedString.Substring(i, remainingLength));
                if (i + 8 < length) formatted.Append(' '); // 除了最後一組，後面加空白
            }
            return formatted.ToString();
        }
    }
}