همه چیز درباره ی الگوریتم های فشرده سازی

[darknes666]

سلام دوستان علت زدن این تاپیک مشخصه و در اینجا سعی میکنیم گام به گام با این موضوع آشنا بشیم.
لطفا اسپم ندین و اگر میخوایین مطلب آموزشی بزارین قبلش به من پیام بدین تا ببینم چقدر با مطالب من هماهنگی داره,تا با ترتیب بهتری مطالبو قرار بدیم.
اگر چیزی رو اشتباه نوشتم بازم بهم پیام بدین.

فشرده سازی رو میشه به دو شاخه ی با اتلاف یا lossy و بدون اتلاف یا lossless تقسیم کرد.
خب حالا بریم یک مقدار درمورد بدون اتلاف صحبت کنیم:
در این روش فایل هیچ داده ای رو از دست نمیده یعنی چی؟
یعنی داده های اصلی و داده های بعد از فشرده شدن دقیقا یکی هستند چون الگوریتم ها دقیقا معکوس هم دیگه عمل میکنن.
در این روش داده های زاید حذف میشن و بعدا دوباره به اون اضافه میشن.
روش هافمن,LZW,LZ77,RLE,LZ78 از جمله روش های بدون اتلاف هستن.
حالا بریم سراغ با اتلاف:
در این روش فایل ذخیره شده خود فایل اصلی نیست درواقع شبیه فایل اصلیه و اطلاعاتی رو از دست میده.از روش با اتلاف برای فشرده سازیه فایل های تصویری و گرافیک و صوتی و مولتی مدیا استفاده میشه.

روش بدون اتلاف یکسری محدودیت هایی داره.
یکیش اینهکه در این روش هیچ تضمینی برای داده ها نیست.به عبارت دیگه فایلی حتما وجود داره که با این الگوریتم حجم بیشتری پیدا کنه.

تا اینجا رو داشته باشین فعلا تا بقیشم بگم.

[darknes666]

خيلي ها با واژه آنتروپي روبرو شدين و اصولا ميدونين معنيش.
آنتروپي به معناي بي نظميه.حالا در حوزه ي کاري ما,آنتروپي اطلاعات مطرح ميشه که ما بهش ميگم آنتروپي شانون که مربوط به يک رخداد تصدفي هست و اون رو به صورت توابع رياضي بيان ميکنه.بزارين بيشتر درگيرتون کنم.
شانون از فيزيک استاتيک الهام گرفت و واژه آنتروپي رو وارد بحث ما کرد به طوري که آنتروپي به معناي شانسي بودن يا اختلال در يک سيستم هست.به ويژه در يک سيستمي که فرض شده ميتونه يکي از حالات احتمالي رو در اختيار داشته باشه و در يک زمان مشخص احتمال توزيع شدن در اون موقعيت ها وجود داشته باشه.
با این تعاریف برای آنتروپی داریم:
132798
که در اون S مجموعه حالت های ممک هستش و ( p(s احتمال رخداد زیرمجوعه ی s هست به طوری که s عضو S هستش.
شانون در این تعاریف به سادگی کلمه ی وضعیت یا موقعیت رو با کلمه ی پیام تعویض کرد.پس S مجموعه ی احتمالات پیام و ( p(s احتمال رویداد پیام s به طوری که s زیر مجموعه ی S باشه حساب میشه.
همچنین شانون مفهوم اطلاعات خود یک پیام رو به صورت زیر نوشت:
132797
این اطلاعات خودی نشان دهنده ی تعداد بیت هایی است که شامل اطلاعات میشن و معمولا به مفهوم تعداد بیتهایی است که ما برای اینکود کردن پیام استفاده میکنیم.
تعریف اطلاعات خودی نشون میده که پیامی با احتمال بیشتر اطلاعات کمتری رو در بر میگیره.
در نتیجه آنتروپی به سادگی احتمال متوسط یک رویداد از یک پیام خودی برای هر پیام هستش.
بنابر این متوسط تعداد بیتهای شامل اطلاعات در یک پیام از یک احتمال توزیع برداشته میشه.
آنتروپی های بزرگتر,متوسط اطلاعات بزرگتری رو نشون میدن و شاید برخلاف تصور پیام های تصادفی بیشتر,مقدار متوسط اطلاعات بیشتری رو شامل بشن.

این توضیحات فعلا کافیه. این نوشته ها رو تو پست بعد با مثال براتون جا منیدازم.

[darknes666]

حالا سعی میکنم با یک مثال کوتاه موارد بالا رو جا بندازم.
خب اول یک مجموعه از احتمال رویدادهارو در نظر میگیریم:(حتما یادتون هست که مجموع احتمال رویداد ها باید برابر 1 بشه)
133514
حالا آنتروپی رو به صورت زیر حساب میکنیم:
133515
و حالا بریم به ادامه ی مطالب برسیم.:لبخندساده:
حالا ممکنه یک سوالی برای خواننده پیش بیاد.اونم اینه که چرا باید از لگاریتم احتمال معکوس برای اندازه گیری درست اطلاعات خودی پیام استفاده بشه؟:متفکر:
خب هرچند من سعی خواهم کرد در بخش های بعدی آنتروپی و اطلاعات خودی رو به طول پیام ربط بدم و به طور رسمی روش بحث کنم اما بیاین تا سعی کنیم مقداری بینش نسبت به این موضوع پیدا کنیم :چشمک: .
اول,در یک مجموعه از 133520 احتمال برابری پیام ها احتمال رویداد هر عضو 133526 هست. همچنین ما میدونیم که اگر طول همه رشته ها یکسان باشه در اینصورت به 133527 بیت برای اینکود هر پیام نیاز دیاریم.خب این دقیقا اطلاعات خودی هست چون 133528. یکی دیگه از ویژگی هاییی که ما داریم اطلاعاتی هست که توسط دو پیام غیر وابسطه داده میشه,در واقع حاصل جمع اطلاعاتی هست که هر کودوم به ما میده :چشمک: .
در این مورد اگر دو پیام A و B دو پیام غیر وابسطه به هم دیگه باشن احتمال ارسال یکی پس از دیگری 133529 هستش و اطلاعاتی که اونا در بر میگیرن میشه: lg=log
133530
در واقع لگاریتم ساده ترین تابعی هست که این ویژگی رو داره.
خب فعلا تا اینجا رو داشته باشین دوستان بقیشم تو راهه :چشمک: .

[darknes666]

خب بریم سراغ ادامه ی مطلب.البته قبلش بگم اگر بخش قبلی رو خوب نفهمیدین عیبی نداره تو بخش های بعدی بهتر روش بحث میکنیم فقط خواستم یه بینشی نسبت به این موضوع پیدا کرده باشیم :چشمک:.
خب بحث جدید آنتروپی زبان اینگیلیسی هستش.
ممکنه بعضی ها علاقه مند بشن که زبان اینگیلیسی چه مقدار اطلاعاتی رو شامل میشه :متفکر: .
این ممکنه به ما کمک کنه تا بفهمیم که زبان اینگیلیسی رو تا چه حدی میشه فشرده کرد همچنین ممکنه به ما اجازه بده تا تراکم زبان ها ی متفاوت رو باهم دیگه مقایسه کنیم. یکی از راه هایی که میشه با اون اطلاعات موجود رو اندازه گرفت عدد بیتها به ازای هر کاراکتر از نظر متوسط هستش.اگر ما احتمال برابر رو برای همه ی کاراکتر ها در نظر بگیریم و یک کد جداگانه به هر کاراتر نسبت بدیم در این صورت 96 کاراکتر قابل چاپ شدن وجود داره(کلید های روی کیبورد) پس بنابر این هر کارکتر 133532 بیت نیاز داره.همچینین آنتروپی احتمال 6/6 بیت به ازای هر کاراکتر رو در نظر میگیره. اگر مااحتمال توزیع رو برای هر کاراکتر در نظر بگیریم اونوقت آنتروپی به عدد 4.5 بیت به ازای هر کاراکتر کاهش پیدا میکنه.اگر شما نوشته رو به بلوک های 8 کاراکتری بشکونین,شما با اندازه گیری آنتروپی اون بلوکها به عددی در حدود 19 دست پیدا میکنین.وقتی ما 8 کاراکتر رو در یک زمان کود میکنیم آنتروپی به عدد 2/4 میرسه همچنین وقتی ما دسته ها رو بزرگتر و بزرگتر میکنیم متوجه میشیم که آنتروپی به عدد 1/3 میل میکنه(یا مقدار کمتر).در واقع این غیرممکنه که این رو اندازه بگیریم چرا که مقدار بسیار زیادی رشته ی احتمالی برای اجرا شدن در آمار وجود داره و هیچ بخشی به اندازه ی کافی بزرگ نیست.در واقع عدد 1/3 اطلاعات موجود در زبان اینگیلیسی رو نشون میده و به ما میگه که تا چه حد میشه اون رو فشرده کرد.
اینم از این قسمت ادامه دارد....:لبخند:

[darknes666]

خب بعد یه مدت اومدم که ادامه بدم.
فشرده سازی چیز ساده ای نیست که بگیم فقط به کد نویسی و الگوریتم ختم میشه.تو پست بعدی یه مثال خوب در این رابطه براتون میزنم.
اما فعلا بریم سراغ فشرده سازی به روش هافمن.در این روش شما میاین میزان تکرار هر حرف رو پیدا میکنین و براش درخت هافمن رو میسازین و بعد با استفاده از دستور هافمن و درخت نوشته رو کد میکنین.بزارین یه مثال بزنم تا بیشتر روشن شین.
فرض کنین شما یه متنی دارین که فقط توش عدد هست حالا جدول زیر رو براش تشکیل میدیم:
حرف-----تکرار
1 5
2 7
3 10
4 15
5 20
6 45
خب حلال از روی این جدول درخت هافمن رو تشکیل میدیم.
به این صورت که 2تا مقدار اول جدولو بر میداریم و دو راس گراف قرار میدیم و ارcش راس سوم رو مجموع این دو راس قرار میدیم به شکل زیر.
12:*
\ /
5:1 7:2
بعد دو مقدار اول جدولو پاک میکنیم و به جاش مجموع اون دوتا رو مینویسیم وجدول رو بر اساس میزان تکرار مرتب میکنیم یعنی:
10:3
12:*
15:4
20:5
45:6
حالا دوباره مراحل بالا رو تکرار میکنیم تا فقط یک مقدار باقی بمونه.حالا ما میایم از رو گراف ماتریس مجاورت رو تشکیل میدیم و بر اساس دستور هافمن کدینگ میکنیم.

یه کد مختصرهم میزارم که ماتریس مجاورت رشته ی مرتب شده رو تشکیل میده.کد مرتب نیست و فقط برای این هست که شما دیدی به مساله پیدا کنین.
#include <iostream>
using namespace std;
void huffman_tree_genrator(long int [],int,long int []);
void gsrt_f_t(long int [2][500],int,int);
void make_it_true(long int [2][500],int);
int main() {
long int s[10]={1,2,3,4,5,6,7,8,9,11},bc[10]={1,2,3,4,5,6,7,8,9,11};
huffman_tree_genrator(s,9,bc);
return 0;
}
void huffman_tree_genrator(long int a[],int k,long int back[])
{
int seed=0,r=0,d_g[200][200]={0},q=1,d,count;
long int sum,m_r[200][200]={0},graph[2][500]={0};
int i=0,j;
count=2*(k+1)-1;
d=k;
for(i;i<=k;i++)
{
graph[0][i]=a[i];
}
while(count>=0)
{
sum=graph[0][r]+graph[0][r+1];
if(graph[1][r]==0)
{
graph[1][r]=q;
q=q+1;
}
if(graph[1][r+1]==0)
{
graph[1][r+1]=q;
q=q+1;
}
graph[0][d+1]=sum;
if(graph[1][d+1]==0)
{
graph[1][d+1]=q;
q=q+1;
}
d++;
r=r+2;
gsrt_f_t(graph,r,d);
count--;
}
i=0;
count=2*(k+1)-1;
make_it_true(graph,count);
for(i;i<=count-1;i+=2)
{
j=i+2;
for(j;j<=count-1;j++)
if(graph[0][i]+graph[0][i+1]==graph[0][j] && graph[2][j]!=-1)
{
d_g[graph[1][i]][graph[1][j]]=1;
d_g[graph[1][j]][graph[1][i]]=1;
d_g[graph[1][i+1]][graph[1][j]]=1;
d_g[graph[1][j]][graph[1][i+1]]=1;
graph[2][j]=-1;
j=count+1;
}

}
i=1;
for(i;i<=count;i++)
{
j=1;
for(j;j<=count;j++)
{
cout<<d_g[i][j]<<" ";
}
cout<<endl;
}

}
void gsrt_f_t(long int x[2][500],int p,int z)
{
int i,j;
long int t;
i=p;
for(i;i<=z;i++)
{
j=i;
for(j;j<=z;j++)
{
if(x[0][i]>x[0][j])
{
t=x[0][i];
x[0][i]=x[0][j];
x[0][j]=t;
t=x[1][i];
x[1][i]=x[1][j];
x[1][j]=t;
}
}

}
}
void make_it_true(long int x[2][500],int k)
{
long int tmp;
int j;
j=1;
for(j;j<=k-1;j++)
{
if(x[0][j-1]==x[0][j] && x[1][j-1]>x[1][j])
{
tmp=x[1][j-1];
x[1][j-1]=x[1][j];
x[1][j]=tmp;
}

if(x[0][j+1]==x[0][j] && x[1][j+1]<x[1][j])
{
tmp=x[1][j+1];
x[1][j+1]=x[1][j];
x[1][j]=tmp;
}
}
}
یه توضیح کوچولو بدم که تابع gsrt_f_t گراف ما رو ازیک خونه ی دلخواه تا یه خونه ی دلخواه دیگه از کوچیک به بزرگ مرتب میکنه.
تابع make_it_true برای اینه که از انجام کار اطمینان حاصل بشه آخه بعضی وقتا کامپایلر هایی مثل codeblocks گیج بازی در میارن دستوراتو درست انجام نمیدن(سر خودم اومده که میگم).
شما حالا رشتتو توی sوbc قرار میدی رشته bc در مراحل بعدی کدینگ استفاده میشه و عملیات رو s انجام میشه.بعد به تابع huffman_tree_genrator مقدار دهی میکنین مقدار دوم برابر طول رشتست که باید یک واحد ازش کم کنین یعنی اگر طول 10 هست باید بهش 9 داده بشه.