aculnaig's questions

Estou escrevendo um codificador e decodificador simples de uma árvore de Huffman que produz códigos clássicos e canônicos depois que a árvore é construída.

Mas não importa o que aconteça, dada uma entrada, ela sempre produz o mesmo resultado tanto para o clássico quanto para o canônico:[1, 1, 0], [0], [1, 0], [1, 0], [0], [1, 1, 1], [0]

A entrada é CANNATA.

O código é o seguinte:

use std::{collections::HashMap, fmt::Debug, hash::Hash};

pub enum HuffmanNode<T> {
    Leaf {
        symbol: T,
        frequency: u32,
    },
    Internal {
        left: Box<HuffmanNode<T>>,
        right: Box<HuffmanNode<T>>,
        frequency: u32,
    },
}

impl<T: Eq + Ord + Copy> HuffmanNode<T> {
    pub fn frequency(&self) -> u32 {
        match self {
            HuffmanNode::Leaf { frequency, .. } => *frequency,
            HuffmanNode::Internal { frequency, .. } => *frequency,
        }
    }
}

impl<T: Eq + Ord + Copy> PartialEq for HuffmanNode<T> {
    fn eq(&self, other: &Self) -> bool {
        self.frequency() == other.frequency()
    }
}

impl<T: Eq + Ord + Copy> Eq for HuffmanNode<T> {}

impl<T: Eq + Ord + Copy> PartialOrd for HuffmanNode<T> {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.frequency().cmp(&other.frequency()))
    }
}

impl<T: Eq + Ord + Copy> Ord for HuffmanNode<T> {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        match (self, other) {
            (HuffmanNode::Leaf { symbol: s1, frequency: f1}, HuffmanNode::Leaf { symbol: s2, frequency: f2 }) => {
                f1.cmp(f2).then(s1.cmp(s2))
            }
            _ => self.frequency().cmp(&other.frequency()),
        }
    }
}

pub struct HuffmanTree<T> {
    pub root: Option<HuffmanNode<T>>,
    pub codes: HashMap<T, Vec<u8>>,
    pub canonical_codes: HashMap<T, Vec<u8>>,
}

impl<T: Eq + Ord + Clone + Hash + Copy + Debug> HuffmanTree<T> {
    pub fn new(input: &[T]) -> HuffmanTree<T> {
        let mut frequency_map = std::collections::BTreeMap::new();
        for symbol in input {
            *frequency_map.entry(symbol).or_insert(0) += 1;
        }

        let mut heap = std::collections::BinaryHeap::new();
        for (symbol, frequency) in frequency_map {
            heap.push(std::cmp::Reverse(HuffmanNode::Leaf {
                symbol: symbol.clone(),
                frequency,
            }));
        }

        while heap.len() > 1 {
            let std::cmp::Reverse(left) = heap.pop().unwrap();
            let std::cmp::Reverse(right) = heap.pop().unwrap();
            let frequency = left.frequency() + right.frequency();
            heap.push(std::cmp::Reverse(HuffmanNode::Internal {
                left: Box::new(left),
                right: Box::new(right),
                frequency,
            }));
        }

        let mut huffman_tree = HuffmanTree {
            root: heap.pop().map(|std::cmp::Reverse(node)| node),
            codes: HashMap::new(),
            canonical_codes: HashMap::new(),
        };

        huffman_tree.generate_codes();
        huffman_tree.generate_canonical_codes();

        huffman_tree
    }
    
    fn generate_codes(&mut self) {
        let mut codes = HashMap::<T, Vec<u8>>::new();

        if let Some(root) = &self.root {
            Self::generate_codes_recursive(root, vec![], &mut codes);
        }
        
        self.codes = codes;
    }

    fn generate_codes_recursive(node: &HuffmanNode<T>, prefix: Vec<u8>, codes: &mut HashMap<T, Vec<u8>>) {
        match node {
            HuffmanNode::Internal { ref left, ref right, .. } => {
                let mut left_prefix = prefix.clone();
                left_prefix.push(0);
                Self::generate_codes_recursive(left, left_prefix, codes);

                let mut right_prefix = prefix;
                right_prefix.push(1);
                Self::generate_codes_recursive(right, right_prefix, codes);
            }
            HuffmanNode::Leaf { symbol, .. } => {
                codes.insert(*symbol, prefix);
            }
        }
    }

    fn generate_canonical_codes(&mut self) {
        let mut canonical_codes = self
            .codes
            .iter()
            .map(|(symbol, code)| (*symbol, code.len()))
            .collect::<Vec<_>>();

        canonical_codes.sort_by_key(|&(symbol, len)| (len, symbol));

        let mut current_code = vec![0; canonical_codes.first().map_or(0, |&(_, len)| len)];
        let mut current_length = current_code.len();

        for (symbol, length) in canonical_codes {
            if length > current_length {
                while current_code.len() < length {
                    current_code.push(0);
                }
                current_length = length;
            }

            self.canonical_codes.insert(symbol, current_code.to_vec());

            Self::add_one(&mut current_code);
        }
    }

    fn add_one(code: &mut Vec<u8>) {
        let mut carry = 1;

        for bit in code.iter_mut().rev() {
            let sum = *bit + carry;
            *bit = sum % 2;
            carry = sum / 2;

            if carry == 0 {
                break;
            }
        }

        if carry == 1 {
            code.insert(0, 1);
        }
    }
}

fn main() {
    let input = "CANNATA".as_bytes();

    let tree = HuffmanTree::new(input);

    for symbol in input {
        if let Some(code) = tree.codes.get(symbol) {
            println!("{:?}", code);
        }
    }

    for symbol in input {
        if let Some(code) = tree.canonical_codes.get(symbol) {
            println!("{:?}", code);
        }
    }
}

Parece que sua postagem é composta basicamente de código; adicione mais alguns detalhes.