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

[binyaz2003]

با سلام
لطفا اگر کسی از فشرده سازی کردن اطلاعی دارد بگه
صواب داره :lol:

[marandi]

در مورد ذخیره سازی اطلاعات...
تا اون جایی که من تحقیق کردم بیش از 50 روش Zip وجود داره که از معروفترین هاشون می توان به روشهای Huffman و LZSS و LZW و Aritmatic و ... نام برد که برخی برنامه های معروف مانند WinRar و WinZip نیز از نوعی از همین روشها بهره می برند.
البته در مورد توضیح خود الگوریتم ها باید بگم که در سواد بنده نمی گنجه چون واقعا بحث های پیچیده ای داره. :oops: :oops: :oops:

[B-Vedadian]

با سلام،

روشهای فشرده سازی به دو دسته با تلفات (Lossy) و بدون تلفات (Lossless) تقسیم می شوند که در روشهای بدون تلفات تنها الگوریتم اهمیت پیدا می کند ولی در روشهای با تلفات مانند فشرده سازی صوت بخش اعظم کار تحقیقات فیزیولوژیکی می باشد.

روش huffman: این روش در واقع یک الگوریتم است که براین پایه استوار است که تعداد تکرار داده های درون یک فایل با هم یکسان نیستند مثلا در مورد بانک داده های نمرات دانش آموزان که نمرات تعداد تکرار یکسان ندارند.

با این الگوریتم داده های با تعداد تکرار بیشتر کدهای کوتاهتر نسبت داده میشود و در نتیجه به داده های با تعداد تکرار کمتر کدهای بلند تر. برای مثال:

(الف) تعداد تکرار 5 (ب) تعداد تکرار 6 و (ج) تعداد تکرار 30 را در نظر بگیرید

برای نمایش 3 داده به 2 بیت نیاز است. بنا بر این فایل معمولی شامل 5*2+6*2+30*2 یعنی 82 بیت خواهد بود. اما با الگوریتم Huffman به (ج) کد 1 بیتی به (ب) کد 2 بیتی و به (الف) کد 2 بیتی نسبت داده می شود. لذا به 5*2+6*2+30*1 یعنی 52 بیت داده نیاز است.

http://www.byui.edu/ricks/employee/C...5/chap10.5.pdf

روش Run length: در این روش هم بنا بر تعداد تکرار غیر یکسان داده هاست، به این ترتیب که داده های تکراری که پشت سرهم نوشته شده باشند (مثلا داده «الف» 13 بار پشت سرهم تکرار شده باشد) ابتدا تعداد تکرار و بعد داده نوشته می شود (در همان مثال ابتدا 13 و بعد «الف» ذخیره میشود.)

روش LZW: این روش توسط دو دانشمند به نامهای Lempel و Ziv پایه گذاری شده و توسط Welch تکمیل گشت. این هم یک الگوریتم است که بر مبنای یافتن «الگو»های تکراری استوار است. الگوهای تکراری داده در فایل پیدا شده و به هر کدام یک کد نسبت داده می شود و به جای هر الگو تنها یک کد در فایل مقصد قرار می گیرد.

http://ginger.cs.uwp.edu/Cis580/LZWovrhd.pdf

روش Linear Prediction یا LP: این روش یک روش با تلفات است که بیشتر برای صدای انسان بکار میرود. پکیج های آماده Celp , Melp بر این مبنا کار میکنند.

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

برای خیشومی مانند خ و ش و ... یک نویز سفید (داده های تصادفی با انرژی ثابت برای تمام فرکانسها که یک نوع تابع آماری است و به راحتی تولید میشود) کافیست تا با مدل بالا تولید صدای دلخواه را بکند یعنی تعداد محدودی (معمولا 5 ضریب) عدد 4 بیتی برای 10 میلی ثانیه صوت داده های لازم را فراهم می کند. این 20 بیت را با 110.25 * 8 بیت که تقریبا حد اقل داده مورد نیاز برای صوت در 10 میلی ثانیه است مقایسه کنید.

روش JPEG: این روش که استاندارد حرفه ایهای فایلهای گرافیکی است باز هم با تلفات است و براین مبنا کار می کند که چشم انسان به تغییرات سریع شدت نور کمترین حساسیت را دارد. در این روش ابتدا داده های تصویری را با تبدیل DCT به حوزه فرکانس برده و سپس فرکانسهای بالا را با تعداد بیت بیشتر و پایین را با تعداد بیت کمتر ذخیره میکنند. نتایج کار دوباره به روش Huffman فشرده میشود.

[B-Vedadian]

با سلام،

در مورد کالبد شکافی الگوریتم ها منظور شما را نفهمیدم ولی اگر نمونه برنامه از Huffman یا بقیه الگوریتم ها بخواهید. ان شاءالله فردا یا پس فردا همین جا قرار خواهم داد. امیدوار بودم که لینک های ذیل هرکدام مفید بوده باشد.

در مورد روشهای با تلفات هم یک جزوه راجع به پیشگویی خطی (Linear Prediction) هست که تایپ کرده و در اختیارتان قرار خواهم داد. این مبحث و JPEG نیاز به اطلاعات اولیه راجع به پردازش سیگنال دارد که اگر دارید بهتر و اگر مطالعه نکرده اید کتاب پردازش سیگنال نوشته آلن اوپنهایم منبع بسیار خوبی است.

در این لحظه فقط می توانم این مستند عالی راجع به پیشگویی خطی را معرفی کنم:

http://www-ccrma.stanford.edu/~jos/SMAC03S/SMAC03S.pdf

[marandi]

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

در مورد برنامه های فشرده ساز من خودم هم برنامه هایی را دارم که حدود 60 الگوریتم را به صورت Open Source در اختیار گذاشته اند. حقیقتش من و خیلی از دوستان حوصله کنکاش به صورت خط به خط را نداریم ولی امیدوارم که یک معلم آگاه همانند شما که اطلاعات جامع ای از این روش ها دارد خیلی راحتتر بتوانید ما را در زمینه ساخت این الگوریتم ها کمک نمایید.

[B-Vedadian]

با سلام،

نخست من معلم آگاه نیستم!

دوما با توجه به این که برنامه نمونه دارید من فقط الگوریتم را می نویسم :

-«جدول» درخت دودویی جستجو با داده های زیر در گره
*مقدار:نوع مثلا کاراکتر
*فرکانس تکرار
- رابطه مقایسه گره ها همان مقایسه فرکانس تکرار.

-«لیست» یک لیست پویا با عناصر از نوع گره های درخت.

1- به تعداد انواع داده در فایل گره با مشخصات زیر بساز:
*فرزند چپ:پوج
*فرزند راست:پوچ
*فرکانس تکرار که مشخص است.
*مقدار:خود داده

2-گره های «جدول» را در لیست قرار بده.

3-گرههای «آ» و «ب» با کمترین تعداد تکرار را در «لیست» پیدا کن. (آ و ب به ترتیب صعودی)
4-گره جدیدی در «جدول» با مشخصات زیر بساز:
*فرزند چپ:«ب»
*فرزند راست:«آ»
*فرکانس تکرار: مجموع فرکانسهای تکرار «آ» و «ب»
*مقدار: مهم نیست.
5-والد «آ» و «ب» را گره جدید قرار بده.
6- گرههای «آ» و «ب» را از «لیست» حذف کن.
7- آیا فرکانس تکرار گره جدید برابر کل اندازه فایل است؟
> بلی: برو به 8
> خیر: برو به 3

8- برای گرههای آخرین لایه درخت (لایه ای که هیچ فرزندی ندارد) بصورت زیر کد نسبت بده:
:> با شروع از اولین لایه (گرهی که هیچ والدی ندارد) مسیری که به گره مورد نظر میرسد را طی کن. به ازای هر حرکت از «والد» به «فرزند چپ» یک صفر و به ازای حرکت از «والد» به «فرزند راست» یک به کد اضافه کن.

...

باقی ماجرا هم که پس از مشخص شدن کد هر داده معلوم است. حال توضیح:

در مرحله اول که باید تعداد تکرار داده های موجود در فایل را بیابیم که به هر کدام یک کد نسبت بدهیم.

در مرحله بعد سعی می کنیم درختی بسازیم که از ریشه آن با کمترین مسیر به داده ای برسیم که بیشترین تکرار را دارد. با ساختن این درخت مسیر از ریشه به هر داده مورد نظر ما کد آن داده باشد و لذا نتیجه دلخواه بدست آید.

روش ساختن این درخت این است که از لایه پایین شروع می کنیم و تا برای داده های با تعداد کمتر یال نزده ایم برای بقیه یال نمی زنیم تا به این ترتیب داده های با تعداد تکرار کمتر با بیشترین تداد یال به ریشه برسند.

حال کد هر داده با طی مسیر از ریشه به داده بدست می آید تنها نکته این است که برای سر درگم نشدن هنگام نسبت دادن چپ و راست به یالها، هر گره با یال چپ به گره فرزند با تعداد تکرار بیشتر و با یال چپ به فرزند با تعداد تکرار بیشتر میرسد.

امیدوارم مفید واقع شود.

[aspersica]

دوستان عزیز درست میگن!
روشهای زیادی وجود داره مثل Huffmann ! اما Huffmann فقط برای compress هست!
یه کارهایی هست که در واقع فایل رو کوچیک نمی کنن اما باعث میشن که huffmann بهتر کار کنه!
یکی از این روشها BWT هست( Burrows-Wheeler Transform )
این روش از 3 الگوریتم مختلف به دنبال هم استفاده میکنه!
1 - borrows -wheeler algorithm
2 - move to front coding algorithm
3 - huffman compresing

اگه کسی خواست به من اطلاع بده که اونها رو بیشتر توضیح بدم!

[aspersica]

توضیح بده اخوی که مشتاقیم

باز هم سلام !‏

از اونجایی که مقدار بحث ها زیاده به نظرم اگه قسمت قسمت بشه بحث خیلی بهتره!‏
خوب از باروز-ویلر شروع کنیم!‏

الگوریتم باروز ویلر در سال 98 به اثبات رسید و در واقع از 1986 داشت روش کار می شد. مقاله های زیادی در ‏مورد اون هست. در واقع خود الگوریتم نتیجه ای است از یک مقاله تحقیقاتی که در سال 1986 ارائه شد ( توسط ‏باروز و ویلر ) اما خوب اثبات بهینه بودنش در سال 1998 به اتمام رسید.‏

و اما خود الگوریتم!‏
الگوریتم ما یک رشته میگیره و یک رشته دیگه بر میگردونه به اضافه یک عدد! رشته دوم درست به اندازه رشته ‏اصلی طول داره و تعداد تکرار هر کاراکتر هم مثل رشته اصلیه! در نتیجه نه تنها اطلاعات کم نمیشه! که بر ‏عکس اضافه هم میشه! ‏
حالا سوال اینه که ما می خواستیم سایز مون کوچیک تر بشه! این که بزرگتر شد!‏

اما می دونید چیه! در واقع ما رشته اصلی رو به هم میریزیم یه طوری که بهترین حالت برای قسمت های بعده!‏
این تغییر اونقدر به صرفه است که اون عدد رو ناچیز میگیریم!‏

فرض کنید یه رشته مثل ‏abnshdbswd‏ داشته باشیم! ‏
اونچیزی که بر میگرده رشته ی ‏dadwhsbnbs‏ و عدد 2 خواهد بود!‏

اما چطوری؟؟
یه جدول مثل جدول زیر در نظر بگیرید:‏
‏1 - ‏abnshdbswd
‏2 - ‏bnshdbswda
‏3 - ‏nshdbswdab
‏4 - ‏shdbswdabn
‏5 - ‏hdbswdabns
‏6 - ‏dbswdabnsh
‏7 - ‏bswdabnshd
‏8 - ‏swdabnshdb
‏9 - ‏wdabnshdbs
‏10 - ‏dabnshdbsw


خوب چه اتفاقی افتاد؟‎ ‎ما رشته اولیه مون رو در واقع یه دونه یه دونه ‏rotate ‎‏ دادیم! همین!‏
حالا همین رشته ها رو با همین شماره ها شون به ترتیب حروف الفبا می کنیم! ‏

نتیجه اینه :‏
‏1 - ‏abnshdbswd
‏2 – ‏bnshdbswda
‏7 – ‏bswdabnshd
‏10 – ‏dabnshdbsw
‏6 – ‏dbswdabnsh
‏5 – ‏hdbswdabns
‏3 - ‏nshdbswdab
‏4 - ‏shdbswdabn
‏8 - ‏swdabnshdb
‏9 - ‏wdabnshdbs

آهان ! حالا شد! حالا همه ی حروف آخر ها رو که پشت سر هم بذاری میشه چی؟ می شه همون رشته ی جواب! ‏عدده هم که تابلو ! عدد یه که اونجا حرف آخر اولین حرف رشته است!‏

این کل الگوریتم ایه که اونهمه سال روش فکر شد! حالا چون نمی خوام خودم و شما ها خسته شین! بقیه اش رو ‏میذارم برای بعد! ‏

آهان یه چیزی! روی ‏reverse ‎اش فکر کنید! خیلی آسونه! ‏

دفعه بعد ‏reversesh ‎‏ رو میگم!‏

فعلا! ‏

[hamidhws]

با سلام خدمت دوستان عزیز
اول لازمه بدونید که من در حدود 8 سال هست که شاید بیشتر وقتمو صرف کار روی الگوریتمای فشرده سازی کردم
من مقاله های زیادی در مورد الگوریتم های زیپ خوندم و الگوریتمایی که در حال حاظر استفاده میشه اکثرا از نوع هافمن یا مشابه هستن و من این روش هارو حدود 6 7 سال پیش تست کردم (نمیدونم اونموقع الگوریتم هافمن ساخته شده بود یا نه) ولی هدف من چیز دیگه ای بود و هست و به نظر من الگوریتم های فشرده سازی در حال حاظر نوعی شوخی هستند و الگوریتمای بسیار پیش پا افتاده و ساده ای رو استفاده میکنند(قصد توهین به هیچ شخص حقیقی یا حقوقی رو ندارم و صرفا نظرم رو گفتم)
نکته 1-هیچکدام از روش های زیپ (تا اونجایی که میدونم) قادر به اعمال فشرده سازی پیاپی رو ندارند (یعنی نمیتونن یه فایل زیپو دوباره زیپ کنن) و این یعنی هیچکدوم با بیت ها سرو کار ندارند و الگوریتم های اونها صرفا روی کارکتر متمرکزه
نکته 2 - هیچکدوم ازروش های زیپ فعلی قادر نیستن یک فایل تصویری رو به روش unless فشرده کنن
و چنتا نکته و یا نقطه ضعف دیگه که الان به ذهنم نمیرسه
دوستان همه اینا بخاطر اینه که همگی روش های فعلی بر کاراکتر متمرکزه و هیچکدوم بر روی بیت ها کار نمیکنن !

و همین موجب شده که مدت ها وقتمو روی کار با بیت ها و ساخت الگوریتمای فشرده سازی کنم
هدف من خیلی بزرگه و چون هنوز جای کار داره شاید اگه بخوام مطرحش کنم خیلی ها براشون غیر قابل باور و نشدنی برسه درست مثل اینه که یه جهش زمانی کنی و به به زمانی که هنوز کالسکه اختراع نشده بود بری و بخوای از بوئینگ 747 بگی

[Babak.Hassanpour]

درست مثل اینه که یه جهش زمانی کنی و به به زمانی که هنوز کالسکه اختراع نشده بود بری و بخوای از بوئینگ 747 بگی

علی الحساب که پنج سال برگشتی عقب.(سه شنبه 18 اسفند 1383 16:32 عصر)

[hamidhws]

علی الحساب که پنج سال برگشتی عقب.(سه شنبه 18 اسفند 1383 16:32 عصر)

خوب اینم یه جور جهش زمانیه دیگه
مثل سریال لاست

ولی از تذکرت ممنون داداش راستشو بخوای اصلا حواسم به زمانش نبود معذرت

[goli jon]

دوستان عزیز درست میگن!
روشهای زیادی وجود داره مثل Huffmann ! اما Huffmann فقط برای compress هست!
یه کارهایی هست که در واقع فایل رو کوچیک نمی کنن اما باعث میشن که huffmann بهتر کار کنه!
یکی از این روشها BWT هست( Burrows-Wheeler Transform )
این روش از 3 الگوریتم مختلف به دنبال هم استفاده میکنه!
1 - borrows -wheeler algorithm
2 - move to front coding algorithm
3 - huffman compresing

اگه کسی خواست به من اطلاع بده که اونها رو بیشتر توضیح بدم!

لطفا بیشتر در مورد الگوریتم هافمن توضیح دهید اصلا هافمن الگوریتم فشرده سازی هست یا نه؟

[nima898]

نکته 2 - هیچکدوم ازروش های زیپ فعلی قادر نیستن یک فایل تصویری رو به روش unless فشرده کنن

میشه یه فایل تصویری رو بدون توجه به نوعش و بدون تلفات با winrar فشرده کرد

لطفا بیشتر در مورد الگوریتم هافمن توضیح دهید اصلا هافمن الگوریتم فشرده سازی هست یا نه؟

پاسخ آقای aspersica مربوط به پنج سال قبله

[Behrooz_CS]

اول لازمه بدونید که من در حدود 8 سال هست که شاید بیشتر وقتمو صرف کار روی الگوریتمای فشرده سازی کردم
من مقاله های زیادی در مورد الگوریتم های زیپ خوندم و الگوریتمایی که در حال حاظر استفاده میشه اکثرا از نوع هافمن یا مشابه هستن و من این روش هارو حدود 6 7 سال پیش تست کردم

سلام

من هم مثل شما توی فکر نوشتم همچین چیزی بودم
از سال 81
بارها الگوریتم و برنامه تستی نوشتم که با شکست مواجه شدم !
آخرین بار تونستم در حد زیپ فشرده کنم البته بدون توجه به کاراکترها و فقط از روی ترتیب بیت ها ! این موفقت خوبی بود و به خودم افتخار می کنم اما مشکل اینجاست که این کار رو قبلا انجام دادن !
من اینو 4 ماه پیش فهمیدم و خیلی توی ذوقم خورد !
اینو ببین ! امیدوارم شما هم مثل من دپرس نشی !!!
http://www.nosltd.com/index.php/prod...-mac-and-linux

اگر تونستی نرم افزارشو گیر بیاری برای من هم بفر ستی ممنونم می شم
موفق باشی

[hamidhws]

سلام

من هم مثل شما توی فکر نوشتم همچین چیزی بودم
از سال 81
بارها الگوریتم و برنامه تستی نوشتم که با شکست مواجه شدم !
آخرین بار تونستم در حد زیپ فشرده کنم البته بدون توجه به کاراکترها و فقط از روی ترتیب بیت ها ! این موفقت خوبی بود و به خودم افتخار می کنم اما مشکل اینجاست که این کار رو قبلا انجام دادن !
من اینو 4 ماه پیش فهمیدم و خیلی توی ذوقم خورد !
اینو ببین ! امیدوارم شما هم مثل من دپرس نشی !!!
http://www.nosltd.com/index.php/prod...-mac-and-linux

اگر تونستی نرم افزارشو گیر بیاری برای من هم بفر ستی ممنونم می شم
موفق باشی

دوست عزیز مرجع فارسی نداره ؟

میشه یکم بیشتر توضیح بدید ؟

مثلا آیا قادره همه فایل ها رو بدون توجه به پسوند فشرده کنه؟
و چند درصد؟ آیا توی همه فایل ها به یک اندازه هست؟

مثلا 100 مگابایت رو در چه مدت زمانی چقدر میکنه؟

با تشکر

[Behrooz_CS]

دوست عزیز مرجع فارسی نداره ؟

میشه یکم بیشتر توضیح بدید ؟

مثلا آیا قادره همه فایل ها رو بدون توجه به پسوند فشرده کنه؟
و چند درصد؟ آیا توی همه فایل ها به یک اندازه هست؟

مثلا 100 مگابایت رو در چه مدت زمانی چقدر میکنه؟

با تشکر

سایت خودش همه چیز را توضیح داده
یه سر بزن عکس هایی را که گذاشته را هم ببین
خودت متوجه می شی

[hamidhws]

سایت خودش همه چیز را توضیح داده
یه سر بزن عکس هایی را که گذاشته را هم ببین
خودت متوجه می شی

100 مگابایت شده 50 مگابایت؟

[Behrooz_CS]

100 مگابایت شده 50 مگابایت؟

همین دیگه ! منم مخم سوت کشید !!!
هرچی دودو تا 4 تا می کنم درک نمی کنم !!
نمونه عملیش هم هست می تونی ببینی ! من این نرم افزارو می دونی چطوری پیدا کردم ؟
داشتم یه روز Acrobat Reader نصب می کردم رفتم توی Temp ببینم Extract می کنه چقدر می شه دیدم Setup که 20 مگ هست شده 70 مگابایت !!!! بعد 70 مگا بایت را RAR و 7z و ZIP کردم دیدم از 40 و 45 مگابایت کمتر نمی شه !!! اونجا بود که فهمیدم این یه فشرده ساز معمولی نیست !! بابا خیلی خفنه !!
نرم افزارش هیچ جا نیست تا دانلود کنیم ! نامرد حتی DEMO هم نزاشته
ببین راهی نیست دانلودش کرد

تازه توی یه عکس دیگه گفته 100% فایل zip یا rar را می کنه 20% !!!!!!!!

[hamidhws]

سلام

دوست عزیز خیالمو راحت کردی
چون فهمیدم این روش فشرده سازی هم مثل بقیه فاقد کار برو روی بیت هاست

قبول دارم تا همینجاشم این برنامه چیز کمی نیست

اما بنده هدف خیلی بزرگتری داشتمو دارم که شاید با گفتنش خیلی از دوستان به شوخی بگیرن اما کاملا جدی و شدنیه

ببین دوست عزیز مبحث فشرده سازی خیلی خیلی خیلی پیچیدس و غیر از مبحث compress و
decompres باید زمان عملیات رو هم مد نظرداشت که در مجموع این 3 مولفه اگه بخواهیم به حداکثر نتیجه برسیم شاید یکی از سخت ترین فرضیات علمی در طول تاریخ بشر رو حل کرده باشیم!

خب حالا کاری که بنده در پی انجامش هستم و به نتایجی هم رسیدم اما نه 100% >> فشرده سازی فایل ها تا مرز 0 و تبدیل اونها به ارقام 10 تا 100 رقمی (هنوز تعداد به طور قطع مشخص نیست)

میدونم خیلی ها اصلا براشون این مساله قابل درک نیست که مثلا یه فایل (نوع فایل مهم نیست) 100 مگابایتی بشه یه کد 20 30 رقمی !

اما لازمه بگم حدود 50% کار طی این نزدیک به 1 دهه کار مداوم به نتیجه رسیده و هدف و کار هم کاملا برنامه ریزی شده و مشخصه و خیلی خوش بینم که تا چند سال دیگه به لطف خدا به نتیجه اصلی برسم

انشالله تا اونموقع همچین کاری نشه
اونایی که روی همچین مسائلی زمان زیادی میزارن منظورمو بهتر میفهمن

به امید سرافرازی ایرانی

[مصطفی ساتکی]

شما 3 سال وقت واسه چی می خای.اگر ایدتون پایه علمی داره همین حالا یه paper بفرستید برای IEEE وگرنه وقت تلف کنی.

[hamidhws]

شما 3 سال وقت واسه چی می خای.اگر ایدتون پایه علمی داره همین حالا یه paper بفرستید برای IEEE وگرنه وقت تلف کنی.

عرض کردم کار هنوز تکمیل نشده به محض تکمیل شدن حتما

این زمانو هم حدودی دادم به عنوان حد اکثر چون تو این کار مشکلات غیر قابل پیش بینی زیاد هست

[مصطفی ساتکی]

البته به شما بگم الان فشرده سازی ها 700 مگابایتو به 20 کیلو بایت تبدیل می کنند ولی زمان گیره شما بایستی این زمان یا این حجمو کاهش بدید

[hamidhws]

البته به شما بگم الان فشرده سازی ها 700 مگابایتو به 20 کیلو بایت تبدیل می کنند ولی زمان گیره شما بایستی این زمان یا این حجمو کاهش بدید

میشه بفرمایید این مطلبو از کجا آوردید

[مصطفی ساتکی]

ای بابا.این تو سی دی king هم پیدا میشه پس شما به روز نیستی

[hamidhws]

ای بابا.این تو سی دی king هم پیدا میشه پس شما به روز نیستی

چشم بنده به روز نیستم شما که به روز هستی میشه لطفا اسم این برنامه یا جایی که در موردش اطلاعات هست رو بفرمایید؟


به هر حال اگه شما نرم افزار فشرده سازی رو پیدا کردید که یه فایل تصویری رو بدون کاهش کیفیت نصف کنه (حالا 20 کیلو بایت هم نخواستیم) بنده شخصا برنامه نویسی رو کنار میزارم
توجه : منظور بنده فایل هایی از قبیل mkv ,.. نیست

در بالا منظور بنده فشرده سازی فایل بدون توجه به پسوند و نوع فایل بود که در غیر این صورت بعضی از فایل ها مثلا یا پسوند bin خیلی زیاد فشرده میشن که اینم به خاطر نوع تکرار بیت هاست (کاراکترها)

به همین دلیل هست که در مورد فایل های تصویری به دلیل درصد پایین تکراری بودن به نسبت درصد فشرده سازی هم با الگوریتم های موجود(معمولا هافمن) پایین میاد


و در آخر اگر منظور شما همون برنامه فشرده سازی هست که مایکروسافت زده و آفیس رو کم حجم کرده خدمتتون عرض کنم این برنامه چیزی جز یه جوک نیست و بیشتر جنبه تبلیغاتی داشته

به هر حال توصیه میکنم هر چیزی رو دیدید یا شنیدید قبول نکنید

با تشکر

[Behrooz_CS]

البته به شما بگم الان فشرده سازی ها 700 مگابایتو به 20 کیلو بایت تبدیل می کنند ولی زمان گیره شما بایستی این زمان یا این حجمو کاهش بدید

آقا منم شدیدا مشتاق شدم بدونم اون برنامه چیه ؟
مطمئنم سر کاریه !! احتمالان می خوای بگی KGB هست

[مصطفی ساتکی]

نرم افزار KGB می تونید برید تو سایتش http://kgbarchiver.net
یه نگاهی به UHARC compressed هم بیاندازید

[hamidhws]

نرم افزار KGB می تونید برید تو سایتش http://kgbarchiver.net
یه نگاهی به UHARC compressed هم بیاندازید

باز هم میگم با این الگوریتم ها فقط میشه بعضی از فایل های خاص که تعدادشون هم زیاد نیست روبه مقدار زیاد فشرده کرد (مثل فایل های bin یا از این قبیل که معمولا در نسل قبلی بازی های تحت کنسول استفاده میشد)

اگه اشتباه نکنم KGB همونه که آفیس رو کم حجم کرده بودن باهاش ؟ اگه این باشه شخصا میگم خودشو مسخره کرده و همچنین مردمو

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

با تشکر

[MIDOSE]

دوستان؛

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

اسم تایپیک بیان گر محتوای اون هست؛ایده ها یا نظرات خود را یا از طریق پیغام خصوصی یا در چت روم ها مطرح کنید و با سایر بحث ها سبب اف شدن تایپیک نشوید.

پ.ن:تایپیک پاک سازی شد.

موفق باشید.

[khamse]

سلام میشه اطلاعات بیشتری درباره ی الگوریتم زیپ در اختیار من بزارید من سمینار دارم

[khamse]

سلام
من ی سمینار درباره ی الگوریتم زیپ دارم میشه اطلاعات جدید بیشتری در اختیارم بزارین
ممنون میشم

[Behrooz_CS]

منبع فارسی من سراغ ندارم ! باید بری زبان اصلی بخونی ، در این زمینه کتاب های زیادی نوشته شده
می تونی خیلی راحت توی آمازون پیداشون کنی و از جاهای دیگه مثل رپید شیر دانلودشون کنی
Data Compression را توی آمازون جستجو کن

[khamse]

اینو که خودم هم بلد بودم.سمینار من 3 هفته ی دیگه......
وقتم خیلی کمه دنبال یکی میگردم که اطلاعات بروزی رو در اختیارم بزاره و یا حداقل ی منبع معتبر و به روز بهم معرفی کنه.لطفا...

[EbiPenMan]

سلام بر همگی

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

سوالم اینکه باید روی چه الگوریتمی کار کنم؟ هافمن

هافمن فکر کنم خوب نباشه اگه هم خوب باشه ترکیبی با الگوریتم دیگه ای خوبه.

بعدش ام این برنامه ای که به سفارش همراه اول و همکاری دانشگاه شریف و شرکت آسان افزار
نوشته شده تو دربارهش نوشته که با الگوریتم " پروتکل ابرمتن فارسی انتقال پذیر، جهت بسترهای ارتباطی محدود" استفاده کردن.

می خوام ببینم که این پروتکل قضیه اش چیه؟ من درآوردی هست یا میشه چیزی در موردش تو اینترنت پیدا کرد ( من که هرچی گشتم نبود)

کسی می تونه کمک کنه؟

[fakher]

سلام بر همگی
راستش تا امروز فکر می کردم اگه تنها یک دیوونه تو این دنیا در مورد نرم افزار و فایل و غیره وجود داشته باشه اونم منم . اما امروز پس از مطالعه این تاپیک دیدم نه بابا از ما دیوونه تر هم هست. البته قصد توهین به هیچ کس رو ندارم اما مطالب دوستمان را که می خوندم چندین بار به اسم نگاه کردم که من کی این حرفا رو اینجا نوشتم. باور کنین من الان 4 سال تمام است بدنبال این ادعا که (( می شه کل اطلاعات دنیا رو که در هارد وغیره هستند فقط در حجمی کمتر از یک بند انگشت قرار داد.)) از خونه و زندگی افتادم.
حساب کنین این یعنی فشرده سازی 100 در صد.

اگه یه فایلی رو با نرم افزار 7z فشرده کنین و دوباره بخواین اونو با هر نرم افزاری فشرده کنین ملاحظه خواهید کرد که دیگه جیزی از سایز فایل کم نمی شود و حتی در برخی از موارد سایز فایل فشرده شده ثانویه چند بایت هم از سایز فایل قبلی بیشتر می شه. به نظر می توان الگوریتمی طراحی کرد که بدون در نظر گرفتن نوع و پسوند فایل فایلها را چنان فشرده کرد که بدون تلف شدن حتی یک بیت از داده اصلی آنرا در چندین بایت ناقابل خلاصه نمود.

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

موفق باشید و پیروز

[soorena]

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

فقط يه چند تا چيزه کوچولو هم ميخواستم بگم :

باور کنین من الان 4 سال تمام است بدنبال این ادعا که (( می شه کل اطلاعات دنیا رو که در هارد وغیره هستند فقط در حجمی کمتر از یک بند انگشت قرار داد.)) از خونه و زندگی افتادم.
حساب کنین این یعنی فشرده سازی 100 در صد.

اول اينکه همينطور که همه اساتيد ميدونن طبق قضيه شانون فانو فشرده سازی يه حد پايينی داره که همون
رابطه محتوی اطلاعات هستش که ديگه هممون بلديم.
دوم اينکه يه hard بسازن که همه اطلاعات دنيا توش باشه يه بحث ديگس ولی خوب چيزی به اسم فشرده سازی 100 درصد نداريم.

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

خوب يه چيزی که خيلی مهمه اينه که هيچ نوع فشرده ساز عمومی وجود نداره و اينکه داده های تصادفی هم قابل فشرده سازی نيس.پس هيچ وقت نبايد دنبال همچين الگوريتمی بود.
راستی من يه وب سايت هم دارم ميزنم که بيشتره مطالبش در مورد همين فشرده سازی هستش خوشحال ميشمگه کسی علاقمند باشه و اگه مطلبی يا هر کری تو اين ضمينه کرده بفرسته .
اينم ادرسش http://www.maroofi.persiangig.com

[Behrooz_CS]

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

فقط يه چند تا چيزه کوچولو هم ميخواستم بگم :

اول اينکه همينطور که همه اساتيد ميدونن طبق قضيه شانون فانو فشرده سازی يه حد پايينی داره که همون
رابطه محتوی اطلاعات هستش که ديگه هممون بلديم.
دوم اينکه يه hard بسازن که همه اطلاعات دنيا توش باشه يه بحث ديگس ولی خوب چيزی به اسم فشرده سازی 100 درصد نداريم.

خوب يه چيزی که خيلی مهمه اينه که هيچ نوع فشرده ساز عمومی وجود نداره و اينکه داده های تصادفی هم قابل فشرده سازی نيس.پس هيچ وقت نبايد دنبال همچين الگوريتمی بود.
راستی من يه وب سايت هم دارم ميزنم که بيشتره مطالبش در مورد همين فشرده سازی هستش خوشحال ميشمگه کسی علاقمند باشه و اگه مطلبی يا هر کری تو اين ضمينه کرده بفرسته .
اينم ادرسش http://www.maroofi.persiangig.com

من با نظر شما کاملا موافق هستم !
حداقل بعد از چند سال که دنبال این قضیه رفتم دیگه مطمئن هستم که همچین کاری امکان پذیر نیست !

[nima898]

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

من با نظر شما کاملا موافق هستم !
حداقل بعد از چند سال که دنبال این قضیه رفتم دیگه مطمئن هستم که همچین کاری امکان پذیر نیست !

من هم کاملا موافقم به هیچ وجه داده تصادفی قابلیت فشرده سازی نداره

[soorena]

خوب البته اين يک امر کاملا واضح هستش چون ما تا وقتی که نتونيم برای داده مون يه مدل بدست بياريم نميتونيم اونو فشرده کنيم و هرچه مدل ما بهتر باشه فشرده سازی بهتر خواهد بود.
اگر برای دوستان جالب هستش ميتونيد يه سری به سايت hutter prize بزنيد. اينم ادرسش (prize.hutter1.net) اينجا همين طور که ميبينيد يه رقابت برای فشرده سازی بيشتر تحت زمان و حافظه محدود هستش و جايزه هم داره!!!!!!!!!!! ميدونيد چه قد؟؟؟ 50000 يورو آره درسته به پول ما از 50 ميليون هم بيشتر ميشه.البته محاسبش فرمول داره و همه پول رو به کسی نميدن ولی به هر حال اگه دوس داشتيد بريد بخونيد.
راستی تو رنکينگ های جهانی در حال حاضر کمپرسور های سری PAQ که توسط matt mahoney اولين بار نوشته شد از همه قويترن ولی خوب مشکل اصليشون سرعت و حافظه هستش برای اطلاعات بيشتر بريد به (http://mattmahoney.net/dc) و ضمناً يک کتاب خوب هم به صورت online اينجا هست که به خوندنش ميارزه.
ممنون از تحملتون

[soorena]

خب حالا کاری که بنده در پی انجامش هستم و به نتایجی هم رسیدم اما نه 100% >> فشرده سازی فایل ها تا مرز 0 و تبدیل اونها به ارقام 10 تا 100 رقمی (هنوز تعداد به طور قطع مشخص نیست)

میدونم خیلی ها اصلا براشون این مساله قابل درک نیست که مثلا یه فایل (نوع فایل مهم نیست) 100 مگابایتی بشه یه کد 20 30 رقمی !

اما لازمه بگم حدود 50% کار طی این نزدیک به 1 دهه کار مداوم به نتیجه رسیده و هدف و کار هم کاملا برنامه ریزی شده و مشخصه و خیلی خوش بینم که تا چند سال دیگه به لطف خدا به نتیجه اصلی برسم

با عرض سلام خدمت دوست عزيز
جسارت نباشه بالاخره شما 1 دهه زحمت کشيدی عمرتو رو اين قضيه گذاشتی ولی خوب نميدونم يا من خيلی از معامله دورم يا شما !!!
تا جايی که من اطلاعات دارم همينطور که ميدونيد و البته اگه يه نگاهی به اين لينک بندازيد (http://mattmahoney.net/dc/dce.html#Section_12) متوجه ميشين که فشرده سازی حد پايين داره يعنی bounded هستش و از همه مهمتر اينکه :

Information theory places hard limits on what can and cannot be compressed losslessly, and by how much:

There is no such thing as a "universal" compression algorithm that is guaranteed to compress any input, or even any input above a certain size. In particular, it is not possible to compress random data or compress recursively.
Given a model (probability distribution) of your input data, the best you can do is code symbols with probability p using log2 1/p bits.

خوب همينطور که دارين ميبينيد البته اين نقل قول از طرف matt mahoney استاد دانشگاه florida و البته پيشتاز در علم فشرده سازی هستش و ديگه فک کنم واضح تو کتابش گفته که هيچ نوع الگوريتمی وجود نداره و نخواهد داشت که بتونه تضمين بکنه که هر فايلی رو بتونه به يه سايز مشخص برسونه و باز از همه مهمتر اينکه هيچ الگوريتمی به صورت بازگشتی(recursive) وجود نداره.اين قضيه از نظر رياضی کاملا اثبات شده پس فکر کنم اگه بيخيال اين پرژه بشين خيلی بهتر باشه.بازم هر جور که صلاح هستش.
حالا منظور از بازگشتی چيه؟؟؟
با يه مثال ميگم.اگه شما بتونی از تو هر 100 byte يک byte رو کم کنيد يعنی اگه هر 100 byte رو بتونيد بکنيد 99 byte، اونوقت هر نوع فايلی رو با هر حجمی ميتونيد تبديل به 99 byte بکنيد!!!(گرفتين قضيه چی شد؟؟؟) .به اين ميگن الگوريتم recursive که البته با اون recursive توی برنامه نويسی يه کمی معنيش فرق داره.
عزيزان اين کار امکان پذير نيست و حد اکثر کاری که ميتونيد بکنيد اين هستش که يک مدل خوب برای داده مون پيدا کنيم