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


تبليغات
سامانه ي پيامکي آز پي ان يو مقالات ISI
فروشگاه اينترنتي آز پي ان يو خريد شارژ آز پي ان يو

پروژه دانشگاهی :پیاده سازی الگوریتم فشرده سازی متن با یک زبان برنامه نویسیزمان کنونی: ۲۱-۹-۱۳۹۵، ۰۹:۲۹ :صبح
کاربرانِ درحال بازدید از این موضوع: 1 مهمان
نویسنده: sima
آخرین ارسال: sima
پاسخ: 6
بازدید: 3304

ارسال پاسخ 
 
امتیاز موضوع:
  • 43 رأی - میانگین امتیازات: 3.19
  • 1
  • 2
  • 3
  • 4
  • 5

پروژه دانشگاهی :پیاده سازی الگوریتم فشرده سازی متن با یک زبان برنامه نویسی

۷-۹-۱۳۹۰, ۰۸:۴۱ :عصر
ارسال: #1
پروژه دانشگاهی :پیاده سازی الگوریتم فشرده سازی متن با یک زبان برنامه نویسی
بنا به درخواست یکی از آشنایان برای پروژه درس طراحی الگوریتم در این قسمت میخوایم ابتدا ببینیم که این الگوریتم ها چگونه کار میکنن و نحوه پیاده سازیشو بررسی کنیم.
سعی نکن متفاوت باشی...
فقط خوب باش...
این روزا خوب بودن به اندازه کافی متفاوته ...
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس شده توسط Administrator ، Masoud Ebrahimi
۷-۹-۱۳۹۰, ۰۸:۴۳ :عصر
ارسال: #2
RE: پروژه دانشگاهی :پیاده سازی الگوریتم فشرده سازی متن با یک زبان برنامه نویسی
الگوریتم فشرده سازی هافمن را دیوید هافمن پروفسور دانشگاه MIT ( Massachusetts Institute of Technology ) آمریکا اختراع کرد. روش فشرده سازی هافمن الگوریتمی است که برای فشرده سازی متن مناسب می‌باشد.

الگوریتم هافمن جزو خانواده الگوریتمهایی است که طول کد متغییری دارند. این به آن معناست که نمادهای مجزا ( برای نمونه کاراکترهایی در یک فایل متنی ) با رشته بیت هایی که طول‌های مختلفی دارند تعویض می‌شود. بنابراین نمادهایی که زیاد در یک فایل تکرار می‌شوند یک رشته بیت کوتاه می‌گیرند در حالی که نمادهای دیگر که به ندرت دیده می شوند رشته بیت طولانی تری را می‌گیرند. یک مثال کاربردی، اجزای کار را به شما نشان می دهد.

• فرض کنید می‌خواهید تکه اطلاعات درون پرانتز رافشرده کنید : ( ACDABA )

از آنجایی که 6 کاراکتر داریم، این متن 6 بایت یا 48 بیت می باشد. با رمز گزاری هافمن، فایل برای بیشترین تکرار ظاهر شدن نمادها ( در این مثال نماد A سه بار تکرار می شود ) جستجو می شود و سپس یک درخت ساخته می شود که نماد ها را با رشته بیت های کوتاه تر جایگزین می کند. در این حالت خاص، الگوریتم از جدول جایگزینی زیر استفاده می‌کند :
( A=0 , B=10 , C=110 , D=111 )

اگر این کد برای فشرده سازی فایل استفاده شود، اطلاعات فشرده شده به صورت زیر در می آیند :
( 01101110100 )

این به این معنی است که 11 بیت به جای 48 بیت مصرف شد. در این مثال نسبت فشرده سازی 4 به 1 می باشد.

رمزگزاری هافمن به دو روش مختلف می‌تواند بهینه‌تر شود :

کد هافمن انطباقی ( Adaptive Huffman code ) به صورت پویا، کلمات کد را با توجه به تغییر احتمال وقوع نماد ها تغییر می دهد.
فشرده سازی گسترده هافمن ( Extended Huffman Compression ) می تواند گروهی از نماد ها را نسبت به یک نماد رمز، گزاری کند. این روش می‌تواند بین 20% تا 90% اطلاعات را فشرده کند.

این الگوریتم فشرده سازی ( Huffman Compression ) اساسا برای فشرده سازی متون و فایل های برنامه سودمند است. برای فشرده سازی فایل های عکس از الگوریتم های دیگری استفاده می شود.
سعی نکن متفاوت باشی...
فقط خوب باش...
این روزا خوب بودن به اندازه کافی متفاوته ...
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس شده توسط Administrator ، Masoud Ebrahimi
۷-۹-۱۳۹۰, ۰۹:۳۱ :عصر
ارسال: #3
RE: پروژه دانشگاهی :پیاده سازی الگوریتم فشرده سازی متن با یک زبان برنامه نویسی
در کامپیوتر برای هر کاراکتری، یک کد (با استاندارد اسکی) بین 0 تا 255 در نظر گرفته می شود.که به هفت بیت فضا نیاز دارد.مثلا برای نمایش حرف A از عدد 65 استفاده می شود.که در مبنای 2 به صورت 1000001درخواهد آمد و در نتیجه برای ذخیره شدن به 7 بیت فضا نیاز دارد.که در این صورت رشته AAAAAAAAکه متشکل از 8 حرف A است به فضایی معادل 8*7=56 بیت یا به بیان ساده تر 7 بایت نیاز دارد.

در استاندارد اسکی 254 کاراکتر مجاز دیگر به جز Aوجود دارد.اما در رشتهAAAAAAAAفقط یک نوع کاراکتر بکار رفته.می توان این کد را به طور قراردادی به کد کوتاهتری (مثلا1) تغییر دهیم. در این صورت رشته ی فوق در فضایی به طول 8*1=8 بیت یا به بیان ساده تر 1 بایت قابل ذخیره سازی است.

و اما اینکه چگونه کد جدید (در این مثال 1 به جای 65) را به دست بیاوریم توسط روش Huffman بیان میشود
سعی نکن متفاوت باشی...
فقط خوب باش...
این روزا خوب بودن به اندازه کافی متفاوته ...
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس شده توسط Administrator ، Masoud Ebrahimi
۷-۹-۱۳۹۰, ۰۹:۴۳ :عصر (آخرین ویرایش در این ارسال: ۷-۹-۱۳۹۰ ۰۹:۵۵ :عصر، توسط sima.)
ارسال: #4
RE: پروژه دانشگاهی :پیاده سازی الگوریتم فشرده سازی متن با یک زبان برنامه نویسی
1-روش هافمن بصورت توضیحی:

1- چگالی هر کاراکتر را محاسبه میکنیم (تعداد دفعات حضور کاراکتر در متن مورد نظر).

2- دو کاراکتر با کمترین میزان تکرار (چگالی) را انتخاب میکنیم.

3- کاراکتر های مرحله 2 را با کاراکتر جدیدی که دارای چگالی برابر با مجموع چگالی دو کاراکتر فوق است جایگزین میکنیم.

4- تا زمانی که فقط یک کاراکتر باقی مانده باشد، به مرحله 2 میرویم.

5- از عملیات فوق یک درخت حاصل می شود، بر روی این درخت هر مسیر به سمت چپ با 0 و هر مسیر به سمت راست با 1 وزن دهی میشود.

6- کد هر کاراکتر با کنار هم گذاشتن وزن ها از ریشه تا آن کاراکتر به دست می آید.

در ادامه با شکل بررسی میکنیم...
سعی نکن متفاوت باشی...
فقط خوب باش...
این روزا خوب بودن به اندازه کافی متفاوته ...
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس شده توسط Administrator ، Masoud Ebrahimi
۷-۹-۱۳۹۰, ۰۹:۵۴ :عصر (آخرین ویرایش در این ارسال: ۷-۹-۱۳۹۰ ۱۰:۰۹ :عصر، توسط sima.)
ارسال: #5
RE: پروژه دانشگاهی :پیاده سازی الگوریتم فشرده سازی متن با یک زبان برنامه نویسی
2-روش هافمن با شکل:

1-عددی که بالای هر کاراکتر نوشته شده است نشان دهنده تعداد دفعات تکرار آن کاراکتر در رشته مورد نظر است.
مهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.


2-m,w,c,h,u کمترین تکرار را دارند؛ ما مجازیم هرکدام از دو زوجی که کمترین مقدار را دارند دو به دو در نظر بگیریم..پس از این مرحله چگالی ها = 3-3-2-2-3-2-1-2-4خواهد بود(اعداد پر رنگ جایگزین جدید هستند)
مهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.


3-سپس چگالی ها 3-3-4-3-3-2-4خواهد شد.
مهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.


و سپس چگالی ها 6-7-5-4خواهد شد.
مهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.



(همینطور ادامه میدهیم....)؛ و تا مرحله پایانی ادامه می دهیم، پس از اتمام این مرحله تنها عدد 22 باقی خواهد ماند و دیگر نمیتوانیم جفتی برای ادامه دادن الگوریتم پیدا کنیم.

نکته: (هر حرکت به چپ 0 و هر حرکت به راست 1)
مهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.

با دنبال کردن مسیر از راس تا کاراکترها(ریشه تا برگ ها) کد های جدید به دست خواهند آمد؛ کدهای جایگزین به دست آمده برای این مثال به شکل زیر است:

E: 00
M: 0100
W: 0101
C: 0110
H: 01110
U: 01111
N: 100
I: 1010
T: 1011
_: 110
S: 111


در این روش کاراکتر‌های پرکاربرد تر با رشته‌های بیتی کوتاهتری نسبت به آن‌هایی که کاربردشان کمتر است، نشان داده می‌شوند.
همینطور که مشاهده می کنید.به حرف Eکه تعداد تکرار بیشتری داشته کد کوچکتر 00 اختصاص داده شده.و از این پس در این کد نوشته ای که به روش هافمن فشرده سازی شده حرف E با کد 00 شناخته می شود.نه با کدِ اسکی آن.
سعی نکن متفاوت باشی...
فقط خوب باش...
این روزا خوب بودن به اندازه کافی متفاوته ...
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس شده توسط Administrator ، Masoud Ebrahimi
۸-۹-۱۳۹۰, ۰۶:۵۲ :عصر
ارسال: #6
RE: پروژه دانشگاهی :پیاده سازی الگوریتم فشرده سازی متن با یک زبان برنامه نویسی
3-کد فشرده سازی هافمن:
این کد به زبان سی شارپه
منبع : دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.


فایل‌(های) پیوست شده
نام فایل : behafman-code-zip.zip
دفعات دانلود : 185
حجم فایل : 44.16 KB
ارسال کننده فایل : sima
نوع فایل : .zip
سعی نکن متفاوت باشی...
فقط خوب باش...
این روزا خوب بودن به اندازه کافی متفاوته ...
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس شده توسط Administrator ، Masoud Ebrahimi
ارسال پاسخ 


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
1 (2) پیاده سازی الگوریتم فلوید به صورت موازی؟؟ asiye 2 1,215 ۹-۱-۱۳۹۳ ۱۱:۵۳ :صبح
آخرین ارسال: mostafa2000
  اعتماد سازی سایت برای Eset Smart Security Ahmad 7 1,975 ۱۸-۱۱-۱۳۹۲ ۱۱:۳۶ :صبح
آخرین ارسال: farajourang
  فعال سازی Bluetooth لپ تاپ مدل Asus - U43JC farhad 10 7,640 ۱۳-۸-۱۳۹۱ ۰۸:۴۹ :عصر
آخرین ارسال: MostafA
  پروژه mahan 2 569 ۸-۴-۱۳۹۱ ۱۰:۳۱ :صبح
آخرین ارسال: MostafA
  سوال برنامه نویسی mahdi 3 924 ۳۰-۸-۱۳۹۰ ۰۸:۲۴ :عصر
آخرین ارسال: Masoud Ebrahimi

کسانی که از این موضوع بازدید کرده اند . . . ( آز پی ان یو )
15 کاربر زیر موضوع را خوانده اند:
خالدي (۵-۵-۱۳۹۲, ۱۰:۲۹ :صبح)، arezo (۱۰-۸-۱۳۹۲, ۰۲:۴۷ :صبح)، mahboub (۱۰-۴-۱۳۹۴, ۱۱:۱۹ :صبح)، ilyasr (۲۹-۷-۱۳۹۲, ۰۵:۳۹ :صبح)، mnbvc (۲۹-۱۰-۱۳۹۲, ۰۳:۵۴ :عصر)، Mozhani.sc (۹-۱۰-۱۳۹۲, ۰۶:۱۹ :عصر)، tarannompc20 (۲۶-۹-۱۳۹۲, ۱۰:۳۵ :عصر)، claudia_nlor (۲۷-۹-۱۳۹۲, ۰۹:۴۸ :عصر)، kamayestani (۳-۱۰-۱۳۹۲, ۱۱:۲۴ :عصر)، hamedkh11 (۱۱-۱۰-۱۳۹۲, ۰۵:۲۳ :عصر)، LORD90 (۱۳-۱۱-۱۳۹۲, ۰۱:۴۰ :صبح)، mahja (۲۰-۱-۱۳۹۳, ۱۲:۵۳ :صبح)، vahidzj (۱۶-۲-۱۳۹۳, ۰۹:۱۵ :صبح)، احسان 753357 (۲۴-۸-۱۳۹۳, ۱۰:۴۹ :صبح)، abbaschian (۲۵-۸-۱۳۹۳, ۰۴:۱۴ :عصر)

پرش به انجمن:


کاربرانِ درحال بازدید از این موضوع: 1 مهمان


آپلودسنتر آز پي ان يو تالار گفتمان آز پي ان يو
تبلیغات نیازمندی های استان چهارمحال و بختیاری