algorithms_fourth 0.1.10

//! Huffman 霍夫曼压缩算法
//!
//! # 使用
//! ```
//!     use algorithms_fourth::string::huff_man::HuffmanDecode;
//!     use algorithms_fourth::string::huff_man::HuffmanEncode;
//!
//!         let txt = r#"abcdefgabcdefg1287abcdefgabcdefg128799abcdefgabcdefg1287abcdefgabcdefg1287abcdefgabcdefg128
//!         cdefgabcdefg128799abcdefgabcdefg1287abcdefgabcdefg1287abcdefgabcdefg128
//!         cdefgabcdefg128799abcdefgabcdefg1287abcdefgabcdefg1287abcdefgabcdefg128
//!         aaaaaa799abcdefgabcdefg128799abcdefgabcdefg1287abcdefgabcdefg128799abcdefgabcdefg1287aaaaaaaaaaaaaaaaaaaaaa9"#.to_string();
//!         let encode = HuffmanEncode::new();
//!         let compress = encode.compress(&txt);
//!         let origin_len = txt.as_bytes().len();
//!         let compress_len = compress.len();
//!         let rate = compress_len * 100 / origin_len;
//!         println!(
//!             "len txt :{},compress:{},rate:{}",
//!             origin_len, compress_len, rate
//!         );
//!         let mut decode = HuffmanDecode::new(compress);
//!         assert_eq!(decode.expand(), txt);
//!
//! ```
//!
//! # 原理
//!

use crate::{
    io::{reader::BinaryReader, writer::BinaryWriter},
    priority_queue::PQ,
};

const R: usize = 256;
pub struct HuffmanEncode {
    writer: BinaryWriter,
}
pub struct HuffmanDecode {
    reader: BinaryReader,
}
fn char_at(c: u8) -> usize {
    c as usize
}
type Link = Option<Box<Node>>;
type C = u8;
struct Node {
    ch: C,
    freq: usize,
    left: Link,
    right: Link,
}
impl Node {
    pub fn new(ch: C, freq: usize) -> Self {
        Node {
            ch,
            freq,
            left: None,
            right: None,
        }
    }
    pub fn is_leaf(&self) -> bool {
        self.left.is_none() && self.right.is_none()
    }
}
impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        self.freq.partial_cmp(&other.freq)
    }
}
impl PartialEq for Node {
    fn eq(&self, other: &Self) -> bool {
        self.ch == other.ch
            && self.freq == other.freq
            && self.left == other.left
            && self.right == other.right
    }
}
impl HuffmanEncode {
    pub fn new() -> Self {
        HuffmanEncode {
            writer: BinaryWriter::new(64),
        }
    }
    /// 1. 通过频率构造单词树
    ///
    /// 2. 通过单词树对字符从新编码
    ///
    /// 3. 将转换字符为新的编码
    pub fn compress(mut self, txt: &str) -> Vec<u8> {
        let chars = txt.as_bytes();
        let mut freq = [0usize; R];
        // 统计频率
        for &c in chars {
            freq[char_at(c)] += 1;
        }
        let root = self.build_trie(freq);
        let mut st = [""; R].map(|f| f.to_string());
        Self::build_code(&mut st, &root, String::new());
        self.write_trie(&root);
        // 记录字符总数，因为填充位的关系，如果没有总数，就不知道某个位置究竟是填充位，
        // 还是编码位
        self.write_usize(chars.len() as u32);
        for &p in chars.iter() {
            for &c in st[char_at(p)].as_bytes() {
                self.write_bool(c == b'1');
            }
        }
        self.writer.close()
    }

    /// 原理：字符作为叶子结点，字符出现的频率越小，则其到根节点的路径也就越长。
    /// 不断频率最小的树合并，直到只剩一个树，就是目标
    fn build_trie(&self, freq: [usize; R]) -> Node {
        let mut pq = PQ::new_min_pq();
        // 这里其实有冗余，0频率的字符其实必出现在树中
        (0..R).for_each(|c| {
            if freq[c] > 0 {
                pq.push(Node::new(c as C, freq[c]));
            }
        });
        while pq.size() > 1 {
            let x = pq.pop().unwrap();
            let y = pq.pop().unwrap();
            let mut parent = Node::new(b'\0', x.freq + y.freq);
            parent.left = Some(Box::new(x));
            parent.right = Some(Box::new(y));
            pq.push(parent);
        }
        pq.pop().unwrap()
    }
    /// st存储对应位置字符的二进制编码的字符串表示,
    /// 编码规则:左节点为0，右节点为1
    fn build_code(st: &mut [String; R], x: &Node, s: String) {
        if x.is_leaf() {
            st[x.ch as usize] = s;
        } else {
            Self::build_code(st, x.left.as_deref().unwrap(), format!("{}0", s));
            Self::build_code(st, x.right.as_deref().unwrap(), format!("{}1", s));
        }
    }

    /// 原理:1. 前序遍历，非叶子结点记false，叶子结点true，并且记录对应的字符。
    /// 只要证明非叶子结点的左右子节点一定不为空，即可证明可靠性。
    /// 证明方法则是通过单词树的构造方法，由下往上构造，且两树作为左右子节点合并。
    /// 该方法的简洁性在于每个节点只用一个bite位。
    fn write_trie(&mut self, x: &Node) {
        if x.is_leaf() {
            self.write_bool(true);
            self.write_char(x.ch);
        } else {
            self.write_bool(false);
            self.write_trie(x.left.as_deref().unwrap());
            self.write_trie(x.right.as_deref().unwrap());
        }
    }

    fn write_usize(&mut self, len: u32) {
        self.writer.write_u32(len)
    }

    fn write_bool(&mut self, j: bool) {
        self.writer.writer_bool(j)
    }

    fn write_char(&mut self, ch: C) {
        self.writer.writer_u8(ch);
    }
}
impl HuffmanDecode {
    pub fn new(data: Vec<u8>) -> Self {
        HuffmanDecode {
            reader: BinaryReader::new(data),
        }
    }
    /// 1. 解析单词树
    ///
    /// 2. 通过单词树获取字符的编码
    ///
    /// 3. 获取字符的长度并解码字符
    pub fn expand(&mut self) -> String {
        let mut ans = String::new();
        let mut root = self.read_trie();
        let n = self.reader.read_u32();
        for _ in 0..n {
            let mut x = &mut root;
            while !x.is_leaf() {
                let a = if self.reader.read_bool() {
                    x.right.as_deref_mut()
                } else {
                    x.left.as_deref_mut()
                };
                x = a.unwrap();
            }
            ans.push(char::from(x.ch));
        }
        ans
    }
    fn read_trie(&mut self) -> Node {
        if self.reader.read_bool() {
            Node::new(self.reader.read_u8(), 0)
        } else {
            let mut ans = Node::new(b'\0', 0);
            ans.left = Some(Box::new(self.read_trie()));
            ans.right = Some(Box::new(self.read_trie()));
            ans
        }
    }
}
#[cfg(test)]
mod test {
    use crate::string::huff_man::HuffmanDecode;

    use super::HuffmanEncode;

    #[test]
    fn test() {
        let txt = r#"abcdefgabcdefg1287abcdefgabcdefg128799abcdefgabcdefg1287abcdefgabcdefg1287abcdefgabcdefg128
        cdefgabcdefg128799abcdefgabcdefg1287abcdefgabcdefg1287abcdefgabcdefg128
        cdefgabcdefg128799abcdefgabcdefg1287abcdefgabcdefg1287abcdefgabcdefg128
        aaaaaa799abcdefgabcdefg128799abcdefgabcdefg1287abcdefgabcdefg128799abcdefgabcdefg1287aaaaaaaaaaaaaaaaaaaaaa9"#.to_string();
        let encode = HuffmanEncode::new();
        let compress = encode.compress(&txt);
        let origin_len = txt.as_bytes().len();
        let compress_len = compress.len();
        let rate = compress_len * 100 / origin_len;
        println!(
            "len txt :{},compress:{},rate:{}",
            origin_len, compress_len, rate
        );
        let mut decode = HuffmanDecode::new(compress);
        assert_eq!(decode.expand(), txt);
    }
}