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

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

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

انواع تراكم سازي ملاك عبارتند از :

متراكم سازي 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 خودش تعريف شده است ، بنابر اين هيچ فضاي اضافي براي ذخيره كردن اين شاخه ها نياز نداريم .

  1. متراكم سازي مي كند ابتدا با 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 از كسينوس معكوس گسسته ضرايب عوض مي كند .

يك بار كه اين كار انجام شد ، متراكم سازي واقعي مي تواند شروع شود . ابتدا نرم افزار متراكم سازي نگاه مي كند به كيفيت تصوير JPEG كه كاربر در خواست كرده است ( كيفيت متوسط و … ) و 2 جدول دائمي يكي براي روشنايي و يكي براي تركيب رنگ ايجاد مي كند .

كي مرتبه كه اين جدول ها ساخته شدند ، ثابتها از آن براي ساختن كسينوس معكوس گسسته ضرايب استفاده كنند . هر ضريب DCT به وسيله ثابت مربوط به آن در جدول كمي تقسيم مي شود و به نزديك ترين عدد صحيح به آ‎ن گرد مي شود . نتيجه محاسبه فرمولهاي ضرايب DCT اين است كه ضرايب كوچك تر كم اهميت تر با صفر جايگزين خواهند شد و ضرايب بزرگ تر دقت خود را از دست خواهند داد . اين گرد كردن ضرائب است كه باعث كاستي در كيفيت تصاوير مي شود .

داده نتيجه شده يك ليست از ضرايب DCT ساده شده است . آخرين قدم در اين مرحله اين است كه ضرايب را با به كاربردن يكي از دو روش هاف من يا طرح رمز كردن حسابي فشرده كند . معمولاً رمز كردن هاف من به كار مي رود . اين دومين متراكم سازي بي ضرر است كه به كار برده مي شود .

مزيتها

با بكار بردن دو الگوريتم فشرده سازي بر روي يكديگر JPEG به يك سيستمي فشرده سازي قابل توجهي مي رود . حتي براي قبل از فشرده سازي شما مي توانيد به آساني يك فايل را به اندازه يك پنجم اندازه اصلي اش فشرده كنيد . براي انتشارات مبادله ايميل در اينترنت حتي سرعت هاي بالا به ميزان 20 به 1 قابل دسترسي است .

خارج كردن يك فايل JPEG از حالت فشرده در زبان چاپ سطح 2 و سطح 3 در سيستم هاي RIP ضمانت شده است . اين به آن معنا است كه فايل هاي كوچك تر مي تواند از شبكه به RI P فرستاده شود كه ايستگاه فرستنده را سريعتر آزاد مي كند ، اورهدروي چاپگر سرور را كوچك تر مي كند و سرعت RIP را افزايش
مي دهد .

معايب :

عيب تراكم سازي JPEG اين است كه الگوريتم فقط براي تصاوير يا صدا طراحي شده است . ( بخاطر آوريد كه P در JPEG مخفف فتوگرافيك است ) . JPEG خودش را براي تصاويري با تغييرات سريع در صدا مناسب نمي داند . برخي از انواع تصاوير وجود دارند كه JPEG بايد از آنها دوري كند :

  • تصاويري كه سايه به آنها اضافه شده است در برنامه هاي كاربردي همانند فتوشاپ .
  • نمودارها يا صفحات خيالي
  • تركيب هايي كه در فتوشاپ ايجاد مي شود .
  • تصاويري كه شامل 256 يا كمتر رنگ هستند .
  • تصاويري كه به وسيله نرم افزار CAD – CAM يا برنامه هاي كاربردي سه بعدي ؟؟؟ همانند مايايا برايس ايجاد شده است .
  • تصاويري كه يك يا بيشتر از رنگ هاي پردازش را كم دارد .
  • برخي اوقات تصاويري ايجاد شده اند كه براي مثال فقط صفحه سياه و جوهر قرمز به كاربرده اند .
  • اگر چنين تصويري با استفاده از متراكم سازي JPEG فشرده شود شما ممكن است ببينيد كه محصول مصنوعي در صفحه زرد يا آبي تيره به وجود آمده باشد .

به علت خاصيت مضرش JPEG فقط بايد در مرحله قبل از فشرده سازي به كار
رود .

(‌ مشهور شدن ، ……. زبان چاپ يا PDF ) . درطي مراحل ايجاد شده وقتي كه تصاوير هنوز ويرايش مي شوند ، حاصل مي شوند و رنگ آنها تنظيم مي شود . هر فرمان ذخيره جديد باعث كاستي بيشتر در كيفيت تصوير مي شود وقتي كه JPEG به كار رفته است .

من سطوح قديمي تري از سيستم هاي RIP سطح 2 را ديده ام كه در خارج كردن از حالت فشرده فايل JPEG اشتباه زيادي كرده اند . به آساني دوباره فرستادن فايل مشكل را حل كرده است .

متراكم سازي JPEG كجا به كار رفته است .

متراكم سازي JPEG مي تواند در انواع قالب هاي فايل به كار رفته باشد .

  • فايل EPS
  • فايل هاي EPS – DCS
  • فايل هاي JPEG
  • فايل هاي PDF

تذكر ملاحظات : 2000 JPEG

كميته استاندارد ايزو يك نسخه جديد از فشرده سازي JPEG كه 2000 JPEG ناميده مي شود ايجاد كرده است . اين استاندارد قبلاً‌ منتشر شده است در ( ژانويه 2001 ) اما هنوز استفاده وسيع پيدا نكرده است . متراكم سازي 2000 JPEG ، 3 مسئله مهم را به استاندارد موجود اضافه كرده است .

  1. آن يك الگوريتم مبتني بر موج كوچك و الگوريتم هاي فشرده سازي JPEG موجود اضافه كرده است . اين الگوريتم انتقال موج كوچك پيشنهاد كيفيت بهبود يافته تصوير در سرعت هاي متراكم سازي خيلي بالا را مي دهد .
  2. 2000 JPEG به اندازه 20% بهبود پيدا مي كند در فشرده سازي قالب جاري JPEG
  3. آن همچنين يك وضعيت اختياري متراكم سازي بي ضرر ارائه مي كند . فايل هاي بدون كاستي 2000 JPEG در حدود نصف اندازه اصلي خواهد بود .

متراكم سازي 2000 JPEG به صورت اصلي براي استفاده در اينترنت طرح ريزي شده است . در نسب متراكم سازي زير 25 به 1 الگوريتم مبني بر موج كوچك جديد قالب هاي كمتري را ايجاد مي كند ، اما با اين وجود جزئيات تصاوير هم كمتر است . كه اين به آن معنا است كه آن هرگز واقع نشود . اضافه شدن يك وضعيت فشرده سازي بدون ضرر ممكن است در آينده براي ما قابل توجه باشد .

قسمت اول 4:

متراكم سازي هاف من

الگوريتم متراكم سازي هاف من مطابق مخترعش – ديويد هاف من ( پروفسور سابق در MIT ) – ناميده شده است . متراكم سازي هاف من يك الگوريتم متراكم سازي بي ضرر است كه براي متراكم كردن نوشتار يا فايل هاي برنامه ايده آل است . اين احتمالاً علت اينكه چرا آن در متراكم سازي برنامه هاي بسيار به كار مي رود را توجيه مي كند .

چگونه متراكم سازي هاف من كار مي كند .

متراكم سازي هاف من متعلق به يك خانواده از الگوريتم ها با اندازه كلمه كد متغير است . اين به آن معنا است كه فرد ( كاركترها و يك فايل نوشتاري ) با توالي بيتهايي كه اندازه هاي مشخصي دارند عوض شده اند . بنابر اين نمادهايي كه زياد در يك فايل اتفاق مي افتد يك توالي كوچك داده . در صورتي كه ديگراني كه به ندرت به كار رفته اند يك توالي بلند تر فراهم مي كردند .

يك مثال علمي اين قانون را به شما نشان خواهد داد : فرض كنيد شما مي خواهيد جزء داده زير را فشرده سازيد : ACDABA

از آنجايي كه اينها 6 كاراكتر هستند اين نوشتار 6 بايت يا 48 بيت طول دارد . با كد گذاري هاف من ، فايل براي سمبلهاي تكرار شده جستجو شده است . ( در اين وضعيت كاراكتر A 3 بار اتفاق افتاده ) و آنگاه يك شاخه ساخته مي شود كه سمبلها را با تواليهاي كوچك تر بيت ، جابه جا مي كند . در اين وضعيت ويژه ، الگوريتم جدول جابه جايي زير را به كار خواهد برد : A= 0 و B=10 و C=110 و D= 111

اگر اين كلمه هاي كد شده براي فشرده سازي فايل به كار برده شود ، داده به شكل زير به نظر مي رسد :

اين به معناي اين است كه 11 بيت به جاي 48 بيت به كار رفته اند .

01101110100 سمبلها – براي اين فايل به خصوص يك نسبت فشرده 4-1 به كار رفته است .

كدكردن هاي هاف من مي تواند به 2 روش بهينه شود :

  1. كد توافقي هاف من به گونه اي پويا كلمه هاي كد را مطابق تغيير احتمالات سمبلها تغيير مي دهد .
  2. متراكم سازي توسعه يافته هاف من مي تواند سمبلهاي گروهي سريعتر از سمبلهاي واحد رمز كند .

فوايد و معايب

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

فشرده سازي هاف من در كجا استفاده شده است .

فشرده سازي هاف من به طور عمده در متراكم سازي برنامه هايي همانند PKZIP , IHA , gz , ZOO, arg . آن همچنين درون متراكم سازي MPEG , gpEG به كار رفته است .

سمبلها را بر اساس نزولي دفعات مشخص مي كند .

يعني سمبلي كه تعداد دفعات تكرارش بيشتر است ابتداي ليست قرار مي گيرد و بعد رشته را به دو قسمت تقسيم مي كند به طوري كه هر قسمت تقريباً‌ نصف تواتر را دارا باشد و به صورت يك درخت دو دويي كدهاي آن را به هر حرف اختصاص مي دهد .

F

SAMBOL

3

A

1 B
1 C
1 D

CDB

A

3

3

نكته : 1- سمبل يا كاراكتري كه بيشترين تعداد دفعات تكرار را دارا است كوچكترين كد را در اختيار خود قرار مي دهد .

2- هيچ كاراكتري نمي توان يافت كه كد آن قسمتي از كد يك كاراكتر ديگر باشد .

در درخت دو دويي در برگها قرار دارند .

نحوه decode كردن به روش Hu Ffman :

از اولين بيت شروع مي كنيم و در كد حروف به دنبال كدي مي گرديم كه سمت چپ ترين بيت آن بيت مورد نظر باشد و به ترتيب بيتها را جستجو مي كنيم. براي كاراكترهاي ديگر و هر كدي كه با بيت مطابقت داشت با بيت ديگر مقايسه نمي كنيم .

قسمت 5 :

متراكم سازي LZW

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

لمپل وزيو يك سري از ورق هايي كه الگوريتم هاي فشرده سازي مختلف را توصيف مي كرد منتشر كردند . اولين الگوريتم آنها در 1977 انتشار يافت . بنابر اين نام آن LZVV است . اين الگوريتم فشرده سازي درون ديگشنري را نگهداري مي كند داده هايش .

در نظر بگيريد شما مي خواهيد رشته متني زير را فشرده كنيد :

the Quick brown fox jumps over the lazy dog .

كلمه the دو بار در فايل واقع شده است . بنابر اين داده مي تواند همانند اين فشرده شود .

the Quick brown fox jumps over << lazy dog .

كه در آن << يك اشاره گر به 4 كاراكتر اول در رشته است .

در 1978 لمپل وزيو دومين مقاله خود را پيرامون يك الگوريتم مشابه كه هم اكنون منتسب به 78 LZ است . اين الگوريتم يك ديگشنري جداگانه را نگهداري مي كند .

در نظر بگيريد كه شما يك بار ديگر مي خواهيد رشته متني زير را فشرده سازيد :

the Quick brown fox jumps over the lazy dog .

كلمه the دو بار در اين فايل واقع شده است . بنابر اين اين رشته در يك ايندكس كه به فايل فشرده شده اضافه شده است به شكل * شده است . آنگاه داده به اين شكل به نظر مي رسد .

* Quick brown fox jumps over * lazy dog .

LZW چگونه كار مي كند .

در 1984 ، تريولچ روي يك الگوريتم متراكم سازي براي كنترل كننده هاي ديسك با كارآيي بالا كار مي كرد . او يك الگوريتم نسبتاً‌ ساده ايجاد كرد كه بر اساس الگوريتم 78 LZ پايه ريزي شده بود و هم اكنون LZW خوانده
مي شود .

متراكم سازي LZW رشته هاي كاراكتر را با كدهاي واحد عوض مي كند . آن هيچ گونه تجزيه و تحليلي از نوشته وارد شده ارائه نمي دهد . در عوض آن فقط اضافه مي كند بر رشته جديد از كاراكترها را كه به يك جدول رشته ها شبيه است اضافه مي كند . متراكم سازي هنگامي رخ مي دهد كه يك كد واحد خروجي باشد ، به جاي يك رشته از كاراكترها كدي كه الگوريتم LZW خارج مي كند مي تواند در هر اندازه اختياري باشد . اما بايد بيتهاي بيشتري نسبت به يك كاراكتر واحد باشد . ابتدا 256 كد ( وقتي كاراكترهاي 8 بيتي استفاده مي كنيم ) .به صورت پيش فرض به دسته كاراكترهاي استاندارد اختصاص داده شده اند . كدهاي باقي مانده به رشته هايي به عنوان پيشرفت الگوريتم اختصاص داده مي شود . مثال بالا همان گونه كه نشان داده شده با 12 بيت كد اجرا مي شود. اين به معناي اين است كه كدهاي 0 تا 225 به بايتهاي منحصر به فرد مربوط مي شود . در صورتي كه كدهاي 256 تا 4095 به زير رشته ها مربوط مي شود .

فوايد و مطالب ها

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

متراكم سازي LZW سريع است .

حق الامتيازها بايد پرداخت شوند تا الگوريتم هاي متراكم سازي LZW درون برنامه هاي كاربردي استفاده شوند .

متراكم سازي LZW در كجا به كار رفته است .

متراكم سازي LZW مي تواند در قالب هاي گوناگون فايلها استفاده بشود .

فايل هاي TIFF

فايل هاي GIF

تذكر: برخي از نسخه هاي متراكم سازي LZW حق چاپ انحصاري دارند . از اين رو سالهاي متمادي صاحبان آنها ( يونيسيس ) حق امتيازهايي از هر كمپاني استفاده كننده الگوريتم آنها تقاضا مي كند . اين به صورتي جدي مانع از معروفيت متراكم سازي LZW شده است و در اجراي طولاني ما احتمالاً‌ خواهيم ديد كه آن با الگوريتم هاي كم ارزشتر ( بخوانيد : حجاتي ) جابه جا شده است . به عنوان يك كاربر حرفه اي شما نبايد نگران باشيد زيرا فقط سازندگان نرم افزار مجبور به پرداخت قيمت هاي اجازه نامه هستند . اما در نهايت شما پرداخت مي كنيد همچنين زيرا همه قيمت ها بايد تحت پوشش قيمت نرم افزار قرار گيرد .

قسمت 6 :

فشرده سازي RLE

RLE گرفته شده است از RLE نماينده كد كردن طول اجرا است . آن يك الگوريتم بي ضرر است كه فقط قسمتهاي متراكم سازي مناسب را براي انواع خاص داده ها ارائه مي كند .

RLE چگونه كار مي كند .

RLE احتمالاً راحت ترين الگوريتم فشرده سازي موجود است . آن يك رديف داده ها با مقدار مساوي درون يك فايل را با و يك مقدار واحد جايگزين
مي كند .

رشته داده زير را در نظر بگيريد ( 17 بايت ) كه مي خواهد فشرده بشود .

ABBBBBBBBB CDEEEEF

با بكار بردن متراكم سازي RLE ، فايل متراكم شده 100 بايت فضا اشغال مي كند و مي تواند شبيه به اين باشد .

A * 8B CD * 4F

همانگونه كه شما مي توانيد ببينيد ، رشته هاي تكراري از داده به وسيله يك كاراكتر كنترلي ( * ) كه به دنبال آن تعداد كاراكترهاي تكراري و خود كاراكتر مي آيد عوض شده اند . كاراكتر كنترلي ثابت نيست و مي تواند از يك پياده سازي تا پياده سازي ديگر اختلاف داشته باشد .

اگر كاراكتر كنترلي خودش در فايل ظاهر شود ، آنگاه يك كاراكتر اضافي كد شده است .

همچنين شما مي توانيد ببينيد ، رمز كردن RLE فقط هنگامي موثر است كه توالي اي از 4 يا 5 كاراكتر تكراري وجود داشته باشد زيرا 3 كاراكتر براي RLE استفاده شده است. همچنين كد گذاري مي كند 2 كاراكتر تكراري . حتي مي تواند باعث افزايش اندازه فايل بشود .

مهم است كه بدانيم طرحهاي RLE رمزگذاري مختلفي وجود دارند . مثال بالا فقط به اين علت بكار برده شده است تا اصل اساسي رمز كردن RLE را نشان دهد. برخي اوقات پياده سازي RLE مناسب براي نوعي از داده است كه متراكم مي شود.

فوايد و مصائب اين الگوريتم بسيار آسان اجرا مي شود و نيازمند توان زيادي از CPU نيست . متراكم سازي RLE فقط براي فايل هايي كه شامل داده هاي تكراري زيادي هستند موثر است . اينها مي توانند فايلهاي نوشتاري باشند . اگر شامل فضاهاي زيادي براي شناسايي داده باشند . اما براي تصاوير دورنگي كه شامل مناطق سياه يا سفيد بزرگي هستند به مراتب مناسبتر است . كامپيوتري كه تصاوير رنگي ايجاد مي كنند .

(‌براي مثال : طراحيهاي معماري ) همچنين مي تواند براي متراكم سازي نسبتاً خوب باشد .

متراكم سازي RLE مي تواند در قالبهاي فايلهاي زير بكار رود .

فايل هاي TIFF

فايل هاي PDF

 

خانم شهركي

 

درباره این مطلب نظر دهید !