rust_algorithms/greedy/
huffman.rs

1//! Huffman kodlash — ochko'zlikning eng chiroyli qo'llanilishi (siqish algoritmi).
2
3use std::cmp::Reverse;
4use std::collections::{BinaryHeap, HashMap};
5
6/// Arena ichidagi daraxt tuguni.
7struct Node {
8    ch: Option<char>,
9    left: Option<usize>,
10    right: Option<usize>,
11}
12
13/// Huffman kodlari: har bir belgi uchun **o'zgaruvchan uzunlikdagi** ikkilik kod.
14///
15/// **G'oya:** tez-tez uchraydigan harfga **qisqa** kod, kam uchraydiganiga **uzun** kod
16/// beramiz. Ochko'z qadam: har safar **eng kam uchraydigan ikkita** tugunni birlashtiramiz.
17///
18/// ```text
19/// "abracadabra": a=5, b=2, r=2, c=1, d=1
20///
21///        (11)
22///       /    \
23///     a(5)   (6)
24///           /   \
25///         (2)   (4)
26///        /  \   /  \
27///      c(1) d(1) b(2) r(2)
28///
29///  a = 0, c = 100, d = 101, b = 110, r = 111
30/// ```
31///
32/// Kodlar **prefiksli** (prefix-free): birortasi ikkinchisining boshi bo'lmaydi —
33/// shuning uchun ajratuvchi belgisiz ham bir ma'noda o'qiladi.
34///
35/// - **Time:** O(n + k log k), bu yerda k — turli belgilar soni.
36/// - **Natija:** matn hajmi odatda 20–60% ga kamayadi (ZIP, JPEG, MP3 ichida ishlatiladi).
37///
38/// Bitta xil belgidan iborat matn uchun kod `"0"` bo'ladi.
39///
40/// # Misol
41/// ```
42/// use rust_algorithms::greedy::huffman_codes;
43///
44/// let kodlar = huffman_codes("abracadabra");
45/// assert_eq!(kodlar.len(), 5);
46/// // eng ko'p uchraydigan 'a' eng qisqa kodni oladi
47/// assert_eq!(kodlar[&'a'].len(), 1);
48/// assert!(kodlar[&'c'].len() > kodlar[&'a'].len());
49///
50/// // prefiks-erkinlik: hech bir kod boshqasining boshi emas
51/// let hammasi: Vec<&String> = kodlar.values().collect();
52/// for a in &hammasi {
53///     for b in &hammasi {
54///         if a != b {
55///             assert!(!b.starts_with(a.as_str()));
56///         }
57///     }
58/// }
59/// ```
60pub fn huffman_codes(text: &str) -> HashMap<char, String> {
61    let mut chastota: HashMap<char, u64> = HashMap::new();
62    for ch in text.chars() {
63        *chastota.entry(ch).or_insert(0) += 1;
64    }
65    if chastota.is_empty() {
66        return HashMap::new();
67    }
68    if chastota.len() == 1 {
69        let ch = *chastota.keys().next().unwrap();
70        return HashMap::from([(ch, "0".to_string())]);
71    }
72
73    // Barcha barglarni arenaga joylaymiz
74    let mut arena: Vec<Node> = Vec::new();
75    let mut heap: BinaryHeap<Reverse<(u64, usize)>> = BinaryHeap::new();
76
77    let mut tartib: Vec<(char, u64)> = chastota.into_iter().collect();
78    tartib.sort_unstable(); // deterministik natija uchun
79    for (ch, f) in tartib {
80        arena.push(Node {
81            ch: Some(ch),
82            left: None,
83            right: None,
84        });
85        heap.push(Reverse((f, arena.len() - 1)));
86    }
87
88    // Ochko'z birlashtirish: eng kam chastotali ikkitasi → yangi ota tugun
89    while heap.len() > 1 {
90        let Reverse((f1, i1)) = heap.pop().unwrap();
91        let Reverse((f2, i2)) = heap.pop().unwrap();
92        arena.push(Node {
93            ch: None,
94            left: Some(i1),
95            right: Some(i2),
96        });
97        heap.push(Reverse((f1 + f2, arena.len() - 1)));
98    }
99
100    let Reverse((_, ildiz)) = heap.pop().unwrap();
101    let mut kodlar = HashMap::new();
102    yigish(&arena, ildiz, String::new(), &mut kodlar);
103    kodlar
104}
105
106fn yigish(arena: &[Node], idx: usize, kod: String, out: &mut HashMap<char, String>) {
107    match arena[idx].ch {
108        Some(ch) => {
109            out.insert(ch, kod);
110        }
111        None => {
112            if let Some(l) = arena[idx].left {
113                yigish(arena, l, format!("{kod}0"), out);
114            }
115            if let Some(r) = arena[idx].right {
116                yigish(arena, r, format!("{kod}1"), out);
117            }
118        }
119    }
120}
121
122/// Matn Huffman bilan kodlanganda necha **bit** egallaydi.
123///
124/// Solishtirish uchun: oddiy ASCII da har belgi 8 bit.
125///
126/// # Misol
127/// ```
128/// use rust_algorithms::greedy::huffman_encoded_len;
129///
130/// let matn = "abracadabra";
131/// let huffman_bit = huffman_encoded_len(matn);
132/// let ascii_bit = matn.len() * 8;
133/// assert_eq!(huffman_bit, 23);
134/// assert!(huffman_bit < ascii_bit); // 23 < 88 — 74% siqildi
135/// ```
136pub fn huffman_encoded_len(text: &str) -> usize {
137    let kodlar = huffman_codes(text);
138    text.chars().map(|ch| kodlar[&ch].len()).sum()
139}
140
141#[cfg(test)]
142mod tests {
143    use super::*;
144
145    #[test]
146    fn bosh_matn() {
147        assert!(huffman_codes("").is_empty());
148        assert_eq!(huffman_encoded_len(""), 0);
149    }
150
151    #[test]
152    fn bitta_belgi() {
153        let k = huffman_codes("aaaa");
154        assert_eq!(k[&'a'], "0");
155        assert_eq!(huffman_encoded_len("aaaa"), 4);
156    }
157
158    #[test]
159    fn chastota_qancha_katta_bolsa_kod_shuncha_qisqa() {
160        let matn = "aaaaaaaaaabbbbbccccd"; // a=10, b=5, c=4, d=1
161        let k = huffman_codes(matn);
162        assert!(k[&'a'].len() <= k[&'b'].len());
163        assert!(k[&'b'].len() <= k[&'c'].len());
164        assert!(k[&'c'].len() <= k[&'d'].len());
165    }
166
167    #[test]
168    fn prefiks_erkin() {
169        let k = huffman_codes("bu matn huffman kodlash uchun namuna matn");
170        let kodlar: Vec<&String> = k.values().collect();
171        for (i, a) in kodlar.iter().enumerate() {
172            for (j, b) in kodlar.iter().enumerate() {
173                if i != j {
174                    assert!(!b.starts_with(a.as_str()), "{a} — {b} ning prefiksi");
175                }
176            }
177        }
178    }
179
180    #[test]
181    fn siqilish_asciidan_yaxshi() {
182        let matn = "mississippi river";
183        assert!(huffman_encoded_len(matn) < matn.len() * 8);
184    }
185
186    #[test]
187    fn deterministik() {
188        assert_eq!(huffman_codes("salom dunyo"), huffman_codes("salom dunyo"));
189    }
190}
rust_algorithms/greedy/huffman.rs

rust_algorithms/greedy/
huffman.rs
