دانلود مقاله الگوریتم های متراکم سازی

بخشی از مقاله

الگوريتم هاي متراكم سازي

فايلهاي قبل از چاپ اغلب بزرگ هستند .بنابر اين ، اين يك امر منطقي است كه داده اغلب فشرده شده است . تعداد كاملاً كمي الگوريتم وجود دارد كه بتواند هم براي نوشتار و هم براي تصاوير استفاده كرد . يك دانش ابتدايي درباره اينكه چگونه الگوريتم هاي متفاوت كار مي كنند مي تواند ارزنده باشد . اين اوراق يك ديد كلي از الگوريتم هاي تراكم سازي گوناگون كه در صنعت پيش چاپ استفاده مي شود ارائه خواهد كرد . آن به هيچ وجه يك ديد كلي كامل از همه الگوريتم هاي موجود نيست .
انواع تراكم سازي ملاك عبارتند از :

متراكم سازي CCITT ‌ گروه 3 و 4 ( هم اكنون در حال ساخت )
• متراكم سازي Flate / deflate
• متراكم سازي JPEG
• متراكم سازي LZW
• متراكم RLE

انواع الگوريتم هاي متراكم سازي
الگوريتم هاي بالا مي توانند به 2 بخش جداگانه تقسيم شوند آنها يا بي فايده هستند و يا بافايده .
الگوريتم هاي بي ضرر محتواي يك فايل را تغيير نمي دهند . اگر شما يك فايل را متراكم سازيد و آنگاه آن را گسترده كنيد ، آن تغيير نكرده است . الگوريتم هاي زير بي ضرر هستند :

• متراكم سازي CCITT ‌ گروه 3 و 4 ( هم اكنون در حال ساخت )
• متراكم سازي Flate / deflate
• متراكم سازي Huffman
• متراكم سازي LZW
• متراكم RLE

الگوريتم هاي مضر نرخ تراكم بهتري را به وسيله خلاص شدن از برخي اطلاعات گزيده در فايل حاصل مي آيند . چنين الگوريتم هايي مي توانند براي تصاوير يا فايل هاي صدا و نه براي داده هاي برنامه يا نوشتاري استفاده بشوند. الگوريتم هاي زير مضر هستند :

• متراكم سازي JPEG
كدام الگوريتم بهترين است ؟
متاسفانه پاسخ قاطعي براي آن سوال وجود ندارد . آن همه اش بستگي به نوع فايلي كه بايد فشرده بشود ، همچنين مفهوم واقعي فايل و اين سوال كه آيا شما مايل به پذيرش يك الگوريتم مضر براي آن فايل ويژه هستيد يا نه ، دارد .
به عنوان يك قانون عمومي قبل از فشرده سازي افراد موارد زير را در نظر
مي گيرند :

نوشتار
ارزش فشرده سازي ندارد برخي اوقات RLE به كار رفته است .
تصاوير تك رنگ LZW
داده هاي سينمايي و هنري تك رنگ CCITT گروه 4
تصاوير فانتري LZW براي فايل هايي كه جزئيات خيلي زيادي را دربرنمي‌گيرند. تصاوير رنگي JPEG اگر متراكم سازي با ضرر مطلوب باشد .
كشيدن خط به وسيله برنامه هاي كاربردي حمايت نشده است .

پايان شماره 1
متراكم سازي Flate / deflate
الگوريتم متراكم سازي بدون اتلاف deflate بر مبناي 2 الگوريتم متراكم سازي ديگر است :
رمز كردن هاف من و متراكم سازي LZVV . شما بايد بدانيد كه اين دو الگوريتم چگونه كار مي كنند به منظور درك فشرده سازي Flate / deflate چگونه كار مي كند . deflate يك الگوريتم باهوش است كه مبتني با روشي كه داده را به داده اصلي خودشان فشرده مي كند . 3 روش فشرده سازي كه موجود هستند :
1- هيچ گاه فشرده نشده باشد . اين يك انتخاب هوشمند است براي داده اي كه قبلاً فشرده بوده است مي باشد . داده ذخيره شده در اين وضعيت به مقدار كمي گسترش خواهد يافت ، اما نه آنقدر كه اگر قبلاً‌ فشرده باشد و يكي از روشهاي ديگر فشرده سازي بر روي آن انجام شده باشد توسعه نمي يابد .
2- فشرده سازي مي كند ابتدا با lzvv و سپس با يك نسخه كمي اصلاح شده كد كردن هاف من .

شاخه هايي كه براي فشرده سازي اين وضعيت به وسيله مشخصه deflate خودش تعريف شده است ، بنابر اين هيچ فضاي اضافي براي ذخيره كردن اين شاخه ها نياز نداريم .
3- متراكم سازي مي كند ابتدا با LZVV و سپس با نسخه كمي تغيير يافته از كد گذاري هاف من با شاخه هايي كه فشرده ساز ايجاد مي كند و در طول داده ذخيره مي شود .
داده ها به بلوك ها شكسته مي شود و هر بلوك يك روش واحد از متراكم فشرده سازي را به كار مي برد . اگر فشرده ساز بخواهد از ذخيره غير فشرده به فشرده سازي با شاخه هايي ويژه تغيير وضعيت دهد يا به متراكم سازي با شاخه هاي هاف من مشخص كند يا به متراكم سازي با يك جفت متفاوت از شاخه هاي هاف من تغيير وضعيت دهد بلوك جاري بايد پايان يابد و يك بلوك جديد شروع شده باشد .

من نظري ندارم . براي من بفرستيد اگر شما چيزي درباره نفع و ضررها مي دانيد متراكم سازي Flate / deflate در كجا به كار رفته اند . من فقط از يك كاربرد قبل از فشرده سازي عمومي كه مبتني بر متراكم سازي Flate كه Adobe Acrobat هست مطلع هستم . متراكم سازي Flate يك خاصيت استاندارد از قالب فايل PDF كه Acrobat مي تواند به كار برد ، است .

فشرده سازي JPEG
JPEG گرفته شده از گروه ماهر عكاسي است ، كه يك كميته استاندارد است . همچنين الگوريتم متراكم سازي به وسيله اين كميته ايجاد شده است .
دو الگوريتم فشرده سازي JPEG وجود دارند : قديمي ترين آن به عنوان JPEG درون اين صفحه به سادگي به كار مي رود . الگوريتم جديد تر 2000 JPEG در پايين اين صفحه مطرح شده است . لطفاً توجه كنيد كه شما بايد بين الگوريتم فشرده سازي JPEG – كه درون اين صفحه مطرح شده – و متناظر با آن قالب بندي فايل JFIF ( كه خيلي از مردم آن را با نام فايل هاي JPEG مي شناسند ) .

JPEG يك الگوريتم فشرده سازي پر اتلاف است كه ايجاد شده است تا اندازه طبيعي فايل تصاوير رنگي شبيه عكاسي به اندازه ممكن بدون تاثير بر كيفيت تصاوير همانگونه كه به وسيله موتور درك انساني تجربه شده كاهش دهد . ما تغييرات كوچك در روشنايي را آسانتر از تغييرات كوچك در رنگ درك مي كنيم . آن ، اين جنبه از آگاهي ماست كه فشرده JPEG از آن بهره برده و تلاش مي كنند تا اندازه فايل را كاهش دهد .
JPEG چگونه كار مي كند .

JPEG :
يك الگوريتم فشرده سازي مضر يا پر اتلاف است كه براي كاهش سايز فايل از يك عكس طبيعي مانند رنگ هاي حقيقي و يا بيشتر از آن چيزي كه امكان دارد ايجاد خواهد شد . محتويات فايل تصوير بر اساس تشابه رنگ به پيكسل هاي كنار هم ذخيره مي شود . در اين روش اطلاعات يك تصوير را بر اساس اهميت آنها مرتب مي كند و اطلاعاتي را كه از اهميت كمتري برخوردارند حذف مي كنند .
در يك تصوير آن چه كه از همه مهمتر است عبارتند از :
شدت رنگ – شفافيت – خود رنگ – از آنجا كه تنوع رنگ ها 16 ميليون رنگ است ، در نتيجه كار مشكل مي شود . شدت رنگ و شفافيت رنگ از 0 تا 225 است .
الگوريتم هاي JPEG در 4 مرحله عمل فشرده سازي را انجام مي دهند :

1 ـ Initialication
2 ـ DCT
3 ـ Quan tization
4 ـ Compresion

الگوريتم JPEG ابتدا يك تصوير را به بلوك هاي جداگانه به اندازه 8*8 تقسيم مي كند.
داده هاي تصوير به فضاي رنگي نور و رنگ تبديل مي شود . از آنجايي كه روشنايي مهمتر از تركيب رنگ در سيستم بصري ما مي باشد . الگوريتم بيشتر روشنايي را در فايل فشرده ، حفظ مي كند .

قدم بعدي به كار بردن جدول DCT براي تامي بلاك ها است . DCT يك مرحله پيچيده است كه رنگ هاي واقعي داده را براي هر پيكسل به ازاء مقاديري كه وابسته به ميانگين كل ماتريس است را جايگزين مي كند.
اين عمل فايل را فشرده نمي كند بلكه به سادگي مقادير پيكسل هاي 8*8 را با يك ماتريس 8*8 ضريب DCT عوض مي كند .

cr = رنگ cb= روشنايي y = شدت رنگ
DCT = 1 (N); IF i=
For ci = I<8; I++ )

For ( j= ; j<8; j++ )
Q [ I ] [j ] = 1+ ( (1+I+j) * q )
13 11 q 7 5 3
15 15 11 q 7 5
14 15 13 11 q 7

نتيجه محاسبه فرمول هاي ضرايب DCT اين است كه ضرايب كوچك تر كم اهميت تر با صفر جايگزين مي شوند و ضرايب بزرگتر از بين مي روند . اين گرد كردن تصاوير است كه باعث كاستي در كيفيت تصاوير مي شود .
فشرده سازي Jpcg مي تواند در انواع قالبهاي زير به كار رود .

فايل هاي EPS ، فايل هاي PDF – YFIF - EPS-DCS
آخرين قدم اين است كه ضرايب را با به كاربردن روش Hu FFman يا رمزگذاري رياضي فشرده كند . كه اغلب روش Hu Ffman به كار مي رود .
الگوريتم هاي JPEG در 4 مرحله عمل متراكم سازي را انجام مي دهد :
اول ، الگوريتم هاي JPEG ابتدا يك تصوير را به بلوك هاي جداگانه 8*8 پيكسل تقسيم مي كند . از آنجايي كه اين قالب بر مبتني بر درك نور و رنگ است ، آن مقادير رنگي RGB يا CMYK را تحليل نمي كند . اما در عوض داده رنگي را به يك فضاي رنگي نور و رنگ همانند YUV تبديل مي كند . اين كار به ما اجازه مي دهد براي فشرده سازي جداگانه از اين دو عامل از آنجايي كه روشنايي مهمتر از تركيب رنگ در سيستم بصري ما مي باشد الگوريتم بيشتر روشنايي را درفايل فشرده شده مي كند .

قدم بعدي در مرحله پردازه فشرده سازي به كار بردن يك كسينوس معكوس گسسته ( DCT ) براي تمام بلاك ها مي باشد . DCT يك مرحله پيچيده است كه اجازه آزادي به هر يك از پيكسل هاي منحصر به فرد را مي دهد . رنگ هاي واقعي داده را براي هر پيكسل به ازاء مقاديري كه وابسته به ميانگين كل ماتريس كه آناليز تجزيه شده است جايگزين مي كند . اين عمل فايل را فشرده نمي كند آن به سادگي مقادير پيكسل هاي 8*8 را با يك ماتريس 8*8 از كسينوس معكوس گسسته ضرايب عوض مي كند .