Експериментальне визначення ентропії повідомлення. Звіт до лабораторної роботи з Теорія інформації та кодування. Робота № 530443

Експериментальне визначення ентропії повідомлення

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Факультет:

КН

Кафедра:

Кафедра ЕОМ

Інформація про роботу

Рік:

2018

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Теорія інформації та кодування

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки Національний університет „Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи №1 з дисципліни: “Теорія інформації та кодування” на тему: Експериментальне визначення ентропії повідомлення 2018 Мета: вивчення властивостей ентропії як кількісної міри інформації. Завдання: Для студентів, номер у списку групи яких є парним послідовності повідомлень джерела є текст, вірш, твір і т.д. (де повідомлення – кожен окремий символ). Варіант 8. Розробити програму для визначення ентропії повідомлення. В програмі передбачити наступні функції: - читання файлу; - сформувати список повідомлень і ймовірність їх появи; - підрахунок кількості інформації у кожному повідомленні; - підрахувати ентропію джерела повідомлень; - виконати кодування повідомлень алгоритмом Шеннона-Фано (для парних номерів у списку групи) або Алгоритмом Гаффмана (для непарних номерів у списку групи). (Для студентів які претендують на кращі оцінки виконати Арифметичне кодування!); - для виконаного кодування підрахувати середню к-ть символів на повідомлення (L) – ефективність кодування; - підрахувати за теоремою Шеннона-Фано нижню оцінку (межу) (L m ) для середньої кількості символів на повідомлення (L); Код програми: using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text; using System.Threading.Tasks; namespace TIK_lab1 { class Program { static void Main(string[] args) { string text = string.Empty; double AmountInformation = 0.0; double AverageOfSymbolsPerMessage = 0.0; string Code = string.Empty; string Decoded = string.Empty; using (StreamReader streamReader = new StreamReader("Text.txt", Encoding.Default)) { while (true) { string tmp = streamReader.ReadLine(); if (tmp == null) break; text += tmp; } } Console.WriteLine(text.Length); Console.WriteLine(text); Dictionary<char, int> CharacterCount = new Dictionary<char, int>(); foreach (char item in text) { if (!CharacterCount.ContainsKey(item)) CharacterCount.Add(item, 1); else CharacterCount[item] += 1; } int Characters = text.Count(); var Messages = CharacterCount.OrderBy(x => x.Value).Reverse(); Dictionary<char, double> Probability = new Dictionary<char, double>(); foreach (var item in Messages) Probability.Add(item.Key, (double)item.Value / Characters); foreach (var item in Probability.Zip(Messages, Tuple.Create)) { Console.WriteLine($"Message: {item.Item1.Key} \tFrenquence:{item.Item2.Value} " + $"\tProbability:{item.Item1.Value:f5}"); } AmountInformation = text.Distinct().Count() * Entropy(Probability); Console.WriteLine($"Entropy:{Entropy(Probability)}"); Console.WriteLine($"Information amount: {AmountInformation}"); List<KeyValuePair<double, char>> List = new List<KeyValuePair<double, char>>(); Dictionary<char, string> Codes = new Dictionary<char, string>(); foreach (KeyValuePair<char, double> item in Probability) List.Add(new KeyValuePair<double, char>(item.Value, item.Key)); Fano(List, Codes, 0, List.Count - 1); foreach (KeyValuePair<char, string> item in Codes) Console.WriteLine($"Message {item.Key} Code {item.Value}"); foreach (char item in text) Code += Codes[item]; DecodingText(Codes, Code, ref Decoded); foreach (var item in Probability.Zip(Codes, Tuple.Create)) AverageOfSymbolsPerMessage += (item.Item1.Value * item.Item2.Value.Length); Console.WriteLine($"Average of symbols per message:{AverageOfSymbolsPerMessage}"); Console.WriteLine($"Code:\n{Code}"); Console.WriteLine(Code.Length); Console.WriteLine($"\nDecoding:\n{Decoded}"); string BlockCode = string.Empty; string BlockDecoded = string.Empty; Dictionary<string, double> BlockMessages = new Dictionary<string, double>(); foreach (var item1 in Probability) { foreach (var item2 in Probability) { foreach(var item3 in Probability) { foreach(var item4 in Probability) { BlockMessages.Add($"{item1.Key}{item2.Key}{item3.Key}{item4.Key}", (double)(item1.Value * item2.Value * item3.Value * item4.Value)); } } } } //foreach (var item in BlockMessages) // Console.WriteLine($"Message:{item.Key} Prob:{item.Value:f5}"); List<KeyValuePair<double, string>> BlockList = new List<KeyValuePair<double, string>>(); Dictionary<string, string> BlockCodes = new Dictionary<string, string>(); var sortMessages = BlockMessages.OrderBy(x => x.Value).Reverse(); foreach (KeyValuePair<string, double> item in sortMessages) BlockList.Add(new KeyValuePair<double, string>(item.Value, item.Key)); Fano(BlockList, BlockCodes, 0, BlockList.Count - 1); //foreach (KeyValuePair<string, string> item in BlockCodes) // Console.WriteLine($"Message {item.Key} Code {item.Value}"); for (int i = 0; i < text.Length; i = i + 4) BlockCode += BlockCodes[text.Substring(i, 4)]; Console.WriteLine($"Code:\n{BlockCode}"); Console.WriteLine(BlockCode.Length); DecodingText(BlockCodes, BlockCode, ref BlockDecoded); Console.WriteLine($"\nDecoding:\n{BlockDecoded}"); Console.ReadKey(); } static double Entropy(Dictionary<char, double> probability) { double entropy = 0.0; foreach (var item in probability) entropy -= item.Value * (Math.Log(item.Value) / Math.Log(2)); return entropy; } //Функція декодування static void DecodingText(Dictionary<char, string> dictionary, string code, ref string Decoded) { for (int i = 0; i < code.Length; i++) { foreach (KeyValuePair<char, string> item in dictionary) { if (code.Substring(i, item.Value.Length) == item.Value) { Decoded += item.Key; i += item.Value.Length - 1; break; } } } } static int Dividing(List<KeyValuePair<double, char>> List, int L, int R) { double HalfProb = 0, PieceProb = 0; for (int j = L; j <= R; j++) HalfProb += List[j].Key; HalfProb /= 2; int i = 0; for (i = L; PieceProb < HalfProb && i <= R; i++) PieceProb += List[i].Key; return i - 1; } //Рекурсивна функція що реалізовує алгоритм Шенона Фано static void Fano(List<KeyValuePair<double, char>> Pairs, Dictionary<char, string> Codes, int L, int R) { if (R - L > 0) { int index = Dividing(Pairs, L, R); for (int i = L; i <= index; i++) { if (Codes.ContainsKey(Pairs[i].Value)) Codes[Pairs[i].Value] += "1"; else Codes.Add(Pairs[i].Value, "1"); } for (int i = index + 1; i <= R; i++) { if (Codes.ContainsKey(Pairs[i].Value)) Codes[Pairs[i].Value] += "0"; else Codes.Add(Pairs[i].Value, "0"); } Fano(Pairs, Codes, L, index); Fano(Pairs, Codes, index + 1, R); } } //Функція декодування static void DecodingText(Dictionary<string, string> dictionary, string code, ref string Decoded) { for (int i = 0; i < code.Length; i++) { foreach (KeyValuePair<string, string> a in dictionary) { if (code.Substring(i, a.Value.Length) == a.Value) { Decoded += a.Key; i += a.Value.Length - 1; break; } } } } static int Dividing(List<KeyValuePair<double, string>> List, int L, int R) { double HalfProb = 0, PieceProb = 0; for (int j = L; j <= R; j++) HalfProb += List[j].Key; HalfProb /= 2; int i = 0; for (i = L; PieceProb < HalfProb && i <= R; i++) PieceProb += List[i].Key; return i - 1; } //Рекурсивна функція що реалізовує алгоритм Шенона Фано static void Fano(List<KeyValuePair<double, string>> Pairs, Dictionary<string, string> BlockCodes, int L, int R) { if (R - L > 0) { int index = Dividing(Pairs, L, R); for (int i = L; i <= index; i++) { if (BlockCodes.ContainsKey(Pairs[i].Value)) BlockCodes[Pairs[i].Value] += "1"; else BlockCodes.Add(Pairs[i].Value, "1"); } for (int i = index + 1; i <= R; i++) { if (BlockCodes.ContainsKey(Pairs[i].Value)) BlockCodes[Pairs[i].Value] += "0"; else BlockCodes.Add(Pairs[i].Value, "0"); } Fano(Pairs, BlockCodes, L, index); Fano(Pairs, BlockCodes, index + 1, R); } } } } / Рис. 1 Результат роботи програми / Рис. 2 Результат роботи пргграми Висновок: я вивчив властивості ентропії як кількісної міри інформації.

Звіт до лабораторної роботи Теорія інформації та кодування

khortashko

14.10.2018 20:00

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись