Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Експериментальне визначення ентропії повідомлення
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
О
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2024
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Теорія інформації та кодування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Звіт
з лабораторної роботи №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 Результат роботи пргграми
Висновок: я вивчив властивості ентропії як кількісної міри інформації.
14.10.2018 20:10-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора