Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.95/21: Рейтинг темы: голосов - 21, средняя оценка - 4.95
0 / 0 / 0
Регистрация: 01.03.2013
Сообщений: 46
1

Алгоритм сжатия Хаффмана

09.03.2013, 01:21. Просмотров 3975. Ответов 2
Метки нет (Все метки)


помогите пожалуйста с данным алгоритмом, моя программа работает, вот только не сжимет, а наоборот, размер становится больше! Этот алгоритм не эффективен для маленьких размеров, но пробовал с большими, один толк. Помогите, может чё в коде неправильно.


HuffmanTree.cs
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
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);
        }
    }
}



Node.cs
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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;
                }
            }
        }
    }
}



Program.cs
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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();
        }
    }
}

или вот программа
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.03.2013, 01:21
Ответы с готовыми решениями:

Алгоритм сжатия Хаффмана
Может кто сталкивался с таким алгоритмом? Может у кого нибудь есть исходник, или подробный...

Алгоритм Хаффмана
Помогите пожалуйста с реализацией алгоритма хаффмана. Я зык C#

Алгоритм сжатия данных
Помогите пожалуйста, необходимо создать программное приложение сжатия данных алгоритмом LZ77

Алгоритм сжатия RLE
Здравствуйте, очень нужна помощь в задании! Просто очень срочно, пожалуйста! Написать программу...

2
Эксперт .NET
14840 / 11227 / 2947
Регистрация: 17.09.2011
Сообщений: 18,811
09.03.2013, 11:08 2
Цитата Сообщение от myself Посмотреть сообщение
C#
1
2
3
4
foreach (bool bit in encoded) 
{ 
   file2.Write((bool)bit ?1:0); 
}
Размер целого числа — 4 байта, в то время как размер символа в кодировке UTF16 — строго 2 байта.
То есть писать просто символы было бы в два раза дешевле по памяти.

Вместо этого копируйте массив бит в массив байт и пишите в файл уже байты:
C#
1
2
3
4
byte[] bytes = new byte[(int)Math.Ceiling((double)encoded.Length / sizeof(byte))];
encoded.CopyTo(bytes, 0);
 
File.WriteAllBytes("D:/Huffman.txt", bytes);
Ну и таблицу символов для декодирования тоже бы в файл не помешало вложить.
0
0 / 0 / 0
Регистрация: 11.12.2016
Сообщений: 16
17.05.2017, 12:31 3
добрый день, а вы не могли бы поделиться программной реализацией?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.05.2017, 12:31

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Алгоритм Хаффмана, реализация
Всем здравствуйте, нужна помощь в реализации алгоритма Хаффмана. Приведу пример с с++ : есть класс...

Алгоритм Хаффмана (количество информации)
Здравствуйте коллеги. Тут пытаюсь решить такую задачку! 1 У нас есть файл (пусть для начало...

Реализовать алгоритм шифрования Хаффмана
2. Шифрование Хаффмана namespace System.Algorithm { public static class Huffman { ///...

Алгоритм сжатия PPM - нужен пример
Доброго времени суток.. Ребята, у кого есть реализованный алгоритм сжатия pрm на С++/С# поделитесь...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.