Алгоритм сжатия Хаффмана - C# (178440)
Формулировка задачи:
помогите пожалуйста с данным алгоритмом, моя программа работает, вот только не сжимет, а наоборот, размер становится больше! Этот алгоритм не эффективен для маленьких размеров, но пробовал с большими, один толк. Помогите, может чё в коде неправильно.
HuffmanTree.cs
Node.cs
Program.cs
или вот программа
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; namespace ConsoleApplication1 { class HuffmanTree { private List<Node> nodes = new List<Node>(); public Node Root { get; set; } public Dictionary<char, int> Frequencies = new Dictionary<char, int>(); public void Build(string source) { for (int i = 0; i < source.Length; i++) { if (!Frequencies.ContainsKey(source[i])) { Frequencies.Add(source[i], 0); } Frequencies[source[i]]++; } foreach (KeyValuePair<char, int> symbol in Frequencies) { nodes.Add(new Node() { Symbol = symbol.Key, Frequency = symbol.Value }); } while (nodes.Count > 1) { List<Node> orderedNodes = nodes.OrderBy(node => node.Frequency).ToList<Node>(); if (orderedNodes.Count >= 2) { List<Node> taken = orderedNodes.Take(2).ToList<Node>(); Node parent = new Node() { Symbol = '*', Frequency = taken[0].Frequency + taken[1].Frequency, Left = taken[0], Right = taken[1] }; nodes.Remove(taken[0]); nodes.Remove(taken[1]); nodes.Add(parent); } this.Root = nodes.FirstOrDefault(); } } public BitArray Encode(string source) { List<bool> encodedSource = new List<bool>(); for (int i = 0; i < source.Length; i++) { List<bool> encodedSymbol = this.Root.Traverse(source[i], new List<bool>()); encodedSource.AddRange(encodedSymbol); } BitArray bits = new BitArray(encodedSource.ToArray()); return bits; } public string Decode(BitArray bits) { Node current = this.Root; string decoded = ""; foreach (bool bit in bits) { if (bit) { if (current.Right != null) { current = current.Right; } } else { if (current.Left != null) { current = current.Left; } } if (IsLeaf(current)) { decoded += current.Symbol; current = this.Root; } } return decoded; } public bool IsLeaf(Node node) { return (node.Left == null && node.Right == null); } } }
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication1 { class Node { public char Symbol { get; set; } public int Frequency { get; set; } public Node Right { get; set; } public Node Left { get; set; } public List<bool> Traverse(char symbol, List<bool> data) { // Leaf if (Right == null && Left == null) { if (symbol.Equals(this.Symbol)) { return data; } else { return null; } } else { List<bool> left = null; List<bool> right = null; if (Left != null) { List<bool> leftPath = new List<bool>(); leftPath.AddRange(data); leftPath.Add(false); left = Left.Traverse(symbol, leftPath); } if (Right != null) { List<bool> rightPath = new List<bool>(); rightPath.AddRange(data); rightPath.Add(true); right = Right.Traverse(symbol, rightPath); } if (left != null) { return left; } else { return right; } } } } }
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; using System.IO; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { StreamReader file = new StreamReader("D:/input.txt"); string s = file.ReadToEnd(); HuffmanTree huffmanTree = new HuffmanTree(); huffmanTree.Build(s); BitArray encoded = huffmanTree.Encode(s); StreamWriter file2 = new StreamWriter("D:/Huffman.txt"); foreach (bool bit in encoded) { file2.Write((bool)bit ?1:0); } file2.Close(); } } }
Решение задачи: «Алгоритм сжатия Хаффмана»
textual
Листинг программы
byte[] bytes = new byte[(int)Math.Ceiling((double)encoded.Length / sizeof(byte))]; encoded.CopyTo(bytes, 0); File.WriteAllBytes("D:/Huffman.txt", bytes);
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д