LA COMPRESIÓN DE DATOS Y SUS TIPOS
La compresión de datos, también conocida como código fuente, es el proceso de codificación o conversión de datos de tal manera que consume menos espacio de memoria. La compresión de datos reduce la cantidad de recursos necesarios para almacenar y transmitir datos.
Se puede hacer de dos maneras: compresión sin pérdida y compresión con pérdida. La compresión con pérdida reduce el tamaño de los datos al eliminar información innecesaria, mientras que no hay pérdida de datos en la compresión sin pérdida.
¿QUÉ ES LA CODIFICACIÓN DE SHANNON FANO?
El algoritmo de Shannon Fano es una técnica de codificación de entropía para la compresión de datos multimedia sin pérdidas. Nombrado en honor a Claude Shannon y Robert Fano, asigna un código a cada símbolo en función de sus probabilidades de ocurrencia. Es un esquema de codificación de longitud variable, es decir, los códigos asignados a los símbolos serán de longitud variable.
¿COMO FUNCIONA?
Los pasos del algoritmo son los siguientes:
- Cree una lista de probabilidades o recuentos de frecuencia para el conjunto de símbolos dado, de modo que se conozca la frecuencia relativa de aparición de cada símbolo.
- Ordene la lista de símbolos en orden decreciente de probabilidad, los más probables a la izquierda y los menos probables a la derecha.
- Divida la lista en dos partes, con la probabilidad total de que ambas partes estén lo más cerca posible entre sí.
- Asigne el valor 0 a la parte izquierda y 1 a la parte derecha.
- Repita los pasos 3 y 4 para cada parte, hasta que todos los símbolos se dividan en subgrupos individuales.
Los códigos de Shannon se consideran precisos si el código de cada símbolo es único.
EJEMPLO:
La tarea dada es construir códigos de Shannon para el conjunto de símbolos dado utilizando la técnica de compresión sin pérdidas de Shannon-Fano.
Paso:
Árbol:
Solución:
1. Al ordenar los símbolos en orden decreciente de probabilidad:
P(D) + P(B) = 0,30 + 0,2 = 0,58
y,
P(A) + P(C) + P(E) = 0,22 + 0,15 + 0,05 = 0,42
Y dado que la mesa se divide casi por igual, la mayoría se divide, la tabla blockquote esblockquote
{D, B} y {A, C, E}
y asígneles los valores 0 y 1 respectivamente.
Paso:
Árbol:
2. Ahora, en el grupo {D, B},
P(D) = 0,30 y P(B) = 0,28
lo que significa que P(D)~P(B) , entonces divide {D, B} en {D} y {B} y asigna 0 a D y 1 a B.
Paso:
Árbol:
3. En el grupo {A, C, E},
P(A) = 0,22 y P(C) + P(E) = 0,20
Entonces el grupo se divide en
{A} y {C, E}
y se les asignan los valores 0 y 1 respectivamente.
4. En el grupo {C, E},
P(C) = 0,15 y P(E) = 0,05
Así que divídelos en {C} y {E} y asigna 0 a {C} y 1 a {E}
Paso:
Árbol:
Nota: La división ahora se detiene ya que cada símbolo está separado ahora.
Los códigos de Shannon para el conjunto de símbolos son:
Como se puede ver, todos estos son únicos y de diferentes longitudes.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for Shannon Fano Algorithm
// include header files
#include <bits/stdc++.h>
using namespace std;
// declare structure node
struct node {
// for storing symbol
string sym;
// for storing probability or frequency
float pro;
int arr[20];
int top;
} p[20];
typedef struct node node;
// function to find shannon code
void shannon(int l, int h, node p[])
{
float pack1 = 0, pack2 = 0, diff1 = 0, diff2 = 0;
int i, d, k, j;
if ((l + 1) == h || l == h || l > h) {
if (l == h || l > h)
return;
p[h].arr[++(p[h].top)] = 0;
p[l].arr[++(p[l].top)] = 1;
return;
}
else {
for (i = l; i <= h - 1; i++)
pack1 = pack1 + p[i].pro;
pack2 = pack2 + p[h].pro;
diff1 = pack1 - pack2;
if (diff1 < 0)
diff1 = diff1 * -1;
j = 2;
while (j != h - l + 1) {
k = h - j;
pack1 = pack2 = 0;
for (i = l; i <= k; i++)
pack1 = pack1 + p[i].pro;
for (i = h; i > k; i--)
pack2 = pack2 + p[i].pro;
diff2 = pack1 - pack2;
if (diff2 < 0)
diff2 = diff2 * -1;
if (diff2 >= diff1)
break;
diff1 = diff2;
j++;
}
k++;
for (i = l; i <= k; i++)
p[i].arr[++(p[i].top)] = 1;
for (i = k + 1; i <= h; i++)
p[i].arr[++(p[i].top)] = 0;
// Invoke shannon function
shannon(l, k, p);
shannon(k + 1, h, p);
}
}
// Function to sort the symbols
// based on their probability or frequency
void sortByProbability(int n, node p[])
{
int i, j;
node temp;
for (j = 1; j <= n - 1; j++) {
for (i = 0; i < n - 1; i++) {
if ((p[i].pro) > (p[i + 1].pro)) {
temp.pro = p[i].pro;
temp.sym = p[i].sym;
p[i].pro = p[i + 1].pro;
p[i].sym = p[i + 1].sym;
p[i + 1].pro = temp.pro;
p[i + 1].sym = temp.sym;
}
}
}
}
// function to display shannon codes
void display(int n, node p[])
{
int i, j;
cout << "\n\n\n\tSymbol\tProbability\tCode";
for (i = n - 1; i >= 0; i--) {
cout << "\n\t" << p[i].sym << "\t\t" << p[i].pro << "\t";
for (j = 0; j <= p[i].top; j++)
cout << p[i].arr[j];
}
}
// Driver code
int main()
{
int n, i, j;
float total = 0;
string ch;
node temp;
// Input number of symbols
cout << "Enter number of symbols\t: ";
n = 5;
cout << n << endl;
// Input symbols
for (i = 0; i < n; i++) {
cout << "Enter symbol " << i + 1 << " : ";
ch = (char)(65 + i);
cout << ch << endl;
// Insert the symbol to node
p[i].sym += ch;
}
// Input probability of symbols
float x[] = { 0.22, 0.28, 0.15, 0.30, 0.05 };
for (i = 0; i < n; i++) {
cout << "\nEnter probability of " << p[i].sym << " : ";
cout << x[i] << endl;
// Insert the value to node
p[i].pro = x[i];
total = total + p[i].pro;
// checking max probability
if (total > 1) {
cout << "Invalid. Enter new values";
total = total - p[i].pro;
i--;
}
}
p[i].pro = 1 - total;
// Sorting the symbols based on
// their probability or frequency
sortByProbability(n, p);
for (i = 0; i < n; i++)
p[i].top = -1;
// Find the shannon code
shannon(0, n - 1, p);
// Display the codes
display(n, p);
return 0;
}
Python3
# Python3 program for Shannon Fano Algorithm
# declare structure node
class node :
def __init__(self) -> None:
# for storing symbol
self.sym=''
# for storing probability or frequency
self.pro=0.0
self.arr=[0]*20
self.top=0
p=[node() for _ in range(20)]
# function to find shannon code
def shannon(l, h, p):
pack1 = 0; pack2 = 0; diff1 = 0; diff2 = 0
if ((l + 1) == h or l == h or l > h) :
if (l == h or l > h):
return
p[h].top+=1
p[h].arr[(p[h].top)] = 0
p[l].top+=1
p[l].arr[(p[l].top)] = 1
return
else :
for i in range(l,h):
pack1 = pack1 + p[i].pro
pack2 = pack2 + p[h].pro
diff1 = pack1 - pack2
if (diff1 < 0):
diff1 = diff1 * -1
j = 2
while (j != h - l + 1) :
k = h - j
pack1 = pack2 = 0
for i in range(l, k+1):
pack1 = pack1 + p[i].pro
for i in range(h,k,-1):
pack2 = pack2 + p[i].pro
diff2 = pack1 - pack2
if (diff2 < 0):
diff2 = diff2 * -1
if (diff2 >= diff1):
break
diff1 = diff2
j+=1
k+=1
for i in range(l,k+1):
p[i].top+=1
p[i].arr[(p[i].top)] = 1
for i in range(k + 1,h+1):
p[i].top+=1
p[i].arr[(p[i].top)] = 0
# Invoke shannon function
shannon(l, k, p)
shannon(k + 1, h, p)
# Function to sort the symbols
# based on their probability or frequency
def sortByProbability(n, p):
temp=node()
for j in range(1,n) :
for i in range(n - 1) :
if ((p[i].pro) > (p[i + 1].pro)) :
temp.pro = p[i].pro
temp.sym = p[i].sym
p[i].pro = p[i + 1].pro
p[i].sym = p[i + 1].sym
p[i + 1].pro = temp.pro
p[i + 1].sym = temp.sym
# function to display shannon codes
def display(n, p):
print("\n\n\n\tSymbol\tProbability\tCode",end='')
for i in range(n - 1,-1,-1):
print("\n\t", p[i].sym, "\t\t", p[i].pro,"\t",end='')
for j in range(p[i].top+1):
print(p[i].arr[j],end='')
# Driver code
if __name__ == '__main__':
total = 0
# Input number of symbols
print("Enter number of symbols\t: ",end='')
n = 5
print(n)
i=0
# Input symbols
for i in range(n):
print("Enter symbol", i + 1," : ",end="")
ch = chr(65 + i)
print(ch)
# Insert the symbol to node
p[i].sym += ch
# Input probability of symbols
x = [0.22, 0.28, 0.15, 0.30, 0.05]
for i in range(n):
print("\nEnter probability of", p[i].sym, ": ",end="")
print(x[i])
# Insert the value to node
p[i].pro = x[i]
total = total + p[i].pro
# checking max probability
if (total > 1) :
print("Invalid. Enter new values")
total = total - p[i].pro
i-=1
i+=1
p[i].pro = 1 - total
# Sorting the symbols based on
# their probability or frequency
sortByProbability(n, p)
for i in range(n):
p[i].top = -1
# Find the shannon code
shannon(0, n - 1, p)
# Display the codes
display(n, p)
Enter number of symbols : 5
Enter symbol 1 : A
Enter symbol 2 : B
Enter symbol 3 : C
Enter symbol 4 : D
Enter symbol 5 : E
Enter probability of A : 0.22
Enter probability of B : 0.28
Enter probability of C : 0.15
Enter probability of D : 0.3
Enter probability of E : 0.05
Symbol Probability Code
D 0.3 00
B 0.28 01
A 0.22 10
C 0.15 110
E 0.05 111
Publicación traducida automáticamente
Artículo escrito por shaleenahuja28 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA