چطوری میشه bit به bit توی یه فایل خروجی نوشت؟

[combo_ci]

سلام
پروژه این ترم ما huffman هست که بالاخره نوشتمش ...اما یه کار ازش مونده....استادمون گفته فایل خروجی باید به صورت bit نوشته بشه که انگار حجم فایل خروجی کم بشه ....کسی میتونه کمکم کنه که چطوری bit به bit توی یه فایل بنویسم

[someCoder]

بیت ها رو جمع کن تا بشه بایت، بعد بنویس. کمتر از یک بایت نمیتونی بنویسی.

[emad_67]

بیت ها رو جمع کن تا بشه بایت، بعد بنویس. کمتر از یک بایت نمیتونی بنویسی.
این سوال برای من هم هست. یعنی بیشتر مشکل من اینه که میشه متغیری رو تعریف کرد که مثلا معادل باینری عدد 2 رو در خودش نگه داره؟

[illegalyasync]

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


بیخود گفته . برای نوشتن تو فایل باید از API استفاده کنی و نوشتن بیت یا بایت حجم فایل رو مشخص نمیکنه بسته به سایر فایل خود ویندوز Allignment انجام میده



میشه متغیری رو تعریف کرد که مثلا معادل باینری عدد 2 رو در خودش نگه داره؟


Byte

[emad_67]

Byteمن از Byte استفاده کردم ولی اصلا کامپایلر اونو نمیشناسه.

[someCoder]

من از Byte استفاده کردم ولی اصلا کامپایلر اونو نمیشناسه.

از char استفاده کن.
البته شاید راه اصولیترش استفاده از BitField باشه: http://publications.gbdirect.co.uk/c_book/chapter6/bitfields.html

[illegalyasync]

من از Byte استفاده کردم ولی اصلا کامپایلر اونو نمیشناسه

windows .h

[emad_67]

از char استفاده کن.از char هم استفاده کردم ولی char ظاهرا عدد مبنای 2 رو نگه نمیداره. مثلا وقتی که صورت باینری عدد 2 رو ه این صورت به متغیر char میدم:


char s=00110010;
cout<<int(s);
در اینجا عدد 8 چاپ میشه که در واقع 00110010 رو به صورت مبنای 8 در نظر گرفته. به هر حال من نتونستم که یه عدد باینری رو در یه char ذخیره کنم. میشه بیشتر توضیح بدی؟

البته شاید راه اصولیترش استفاده از BitField باشهدر این مورد هم من درست متوجه نشدم که bitfield چیه و چیکار میکنه و چه جوری میشه ازش استفاده کرد. اگه میشه در این مورد هم توضیح بده.
با تشکر

windows .hاین هدر رو هم وارد کردم ولی بازم نمیشناسه.

[Nima_NF]

در اینجا عدد 8 چاپ میشه که در واقع 00110010 رو به صورت مبنای 8 در نظر گرفته. .....

وقتی شما می نویسید S=00110010 به معنی آن است که عدد مورد نظر را به صورت Octal ذخیره کن ، (چون قبل عدد ، صفر گذاشته اید این معنی را می دهد).
شما وقتی عددی را در char یا هر متغیر دیگری ذخیره می کنید ، در پایین ترین سطح واقع باینری آن ذخیره می شود (معادل hex آن به اسمبلی برای ارسال به رجیستر ها)، پس یک راه کنترل روی بیت ها و ذخیره سطح پایین تر hex است یعنی بنویسید :
char c= 0x32 و یا oct (که گفتم) یا dec که می دانید نه باینری .

مثلا یک راه دیگر: ذخیره عدد به صورت رشته (dec) و سپس تبدیل و نمایش آن به صورت باینری با استفاده از توابعی مثل : strtoul با تنظیم آرگومان base آن به عدد 2.


این هدر رو هم وارد کردم ولی بازم نمیشناسه.منظورشان BYTE بود نه Byte که در ویندوز معادل همان unsigned char می باشد و در windows.h.

[emad_67]

با تشکر
خوب حالا برای این کد هافمن باید چیکار کرد یعنی 0 و 1 هایی که از درخت به دست میاد رو چه جوری توی فایل بنویسم؟ یا همون طور که جناب somecoder گفتن:

بیت ها رو جمع کن تا بشه بایت، بعد بنویس. کمتر از یک بایت نمیتونی بنویسی.من باید بیت ها رو در یه جایی ذخیره کنم و بعد 1 بایت رو در فایل ذخیره کنم. سوالم اینه که چه جوری این بیت ها رو در یک متغیر نگه دارم؟
اگر میشه با یه کد به صورت کوتاه توضیح بدین.

[Nima_NF]

روش های مختلفی وجود دارد :
1) استفاده از توابع STL ( البته سریع ترین راه ، اما نیاز به تمرین دارد ) ، مثل <bitset> که با آن می توانید متغیر هایی برای ذخیره تک تک بیت ها و غیره داشته باشید و با استفاده از توابع و اعمال داخلی ان شیفت دهید و یا بیت خاصی را به راحتی تست کنید. (حتی مثل آرایه ها) و در انتها آن ها را به صورت رشته باینری و یا عدد صحیح ذخیره کنید.

2) یا خودتان به صورت دستی این کار را انجام دهید ، مثلا برای عمل جمع یک بیت با عدد دیگر ( 0010 + 0100) , در صورتی که فقط بخواهیم بیت مورد نظر را در عددی اضافه کنیم و به carry جمع کاری نداشته باشیم ، از طریق معادل hex آن ها جمع کنید :
(0x4 | 0x2 ) و این عمل را در متغیر بایت خود ذخیره کنید : یا unsigned char یا BYTE در ویندوز.


BYTE myBits = 0x4 | 0x2 ;
| برای or بیتی و & برای and بیتی و >> و << برای شیفت ها و ...

برای تست هم به همان صورت یعنی مثلا برای تست بیت دوم عددی : 0010 | xxxx به صورت hex آن این کار را انجام دهید.

موفق باشید

[Nima_NF]

یک نمونه کد برای وقتی که می خواهید به صورت دستی بیت ها را از درختی بخوانید و به متغیر بایتی اضافه کنید :



myBits = 0; // 0000 0000

for ( i = 0 ; i <= 7 ; i++ )
{
getmyBoolFromTree(myTreeState);

myBits = myBits | (( myTreeState ? 1 : 0 ) << i) ;
}

کد فوق را به صورت =| ننوشتم تا قابل فهم باشد.
تابع getBoolFromTree توسط خودتان باید نوشته شود که مثلا bool را دریافت می کنید و بعد آن را به ترتیب در بیت مورد نظر قرار می دهید.

[emad_67]

خیلی ممنون نیما جان
میشه این قسمت رو توضیح بدی:


(( myTreeState ? 1 : 0 ) << i)

الان اینجا myTreeState همون متغیر bool هست؟
و >> هم میخواستم بدونم چیکار میکنه؟

[someCoder]

الان اینجا myTreeState همون متغیر bool هست؟ظاهرا بله

و >> هم میخواستم بدونم چیکار میکنه؟عدد 1 یا 0 (خروجی عملگر ?) را i واحد به چپ شیفت میده.

[emad_67]

عدد 1 یا 0 (خروجی عملگر ?) را i واحد به چپ شیفت میده.
خوب یعنی چی i واحد به چپ شیف میده؟ اصلا در اینجا چه نقشی رو ایفا میکنه؟

[Nima_NF]

خوب یعنی چی i واحد به چپ شیف میده؟ اصلا در اینجا چه نقشی رو ایفا میکنه؟شما می خواهید از درخت به ترتیب وضعیت های صفرو و یک آن را بخوانید و به ترتیب در یک بایت ذخیره کنید (8 بیت را) که مثلا با استفاده از myTreeState که یک bool است و وضعیت 1 , 0 خوانده شده را مشخص می کند ،یعنی در نمونه کد فوق شما تک به تک بیت ها را عدد قرار می دهید ( به عبارت دیگر state کنونی خوانده شده را با عدد های زیر که توسط حلقه for و شیفت درست شده است ، OR بیتی می کنید و به این شکل هر state خوانده شده در یک بیت متغیر شما ذخیره می شود ، توجه کنید که عدد شما در ابتدا 0000 0000 می باشد):



0000 0001 <-- i = 0
0000 0010 <-- i = 1
0000 0100 <-- i = 2
0000 1000 <-- i = 3
0001 0000 <-- i = 4
0010 0000 <-- i = 5
0100 0000 <-- i = 6
1000 0000 <-- i = 7

[emad_67]

خیلی خیلی ممنون دوست عزیز
یه سوال دیگه:
مثلا فرض کن از درخت یه همچین نتایجی برای 3 حرف a و b و c به دست اومده


a 1100
b 00
c 101
در این حالت 4 بیت از a و 2 بیت از b و 2 بیت هم از c در یک بایت جا میشن یعنی 1 بیت از c باقی میمونه. حالا سوالم اینه که اون یک بیتی که از c باقی مونده رو باید در مرحله بعد و همراه با نتایج دیگه ای که از درخت به دست میاد ذخیره کنیم؟
سوال دیگم هم اینه که بعد از اینکه کلیه بیت ها رو در فایل ذخیره کردیم برای باز یابی این بیت ها و به رسیدن به داده اصلی باید چیکار کنم؟

[Nima_NF]

بستگی به پیاده سازی الگوریتم شما دارد ،
شما باید یک جدول ایندکس هم داشته باشید (و آن را همراه فایل ذخیره کنید) ، حال این ایندکس یا اشاره گری به شروع هر کدام از حرف ها a , b ,.. می باشد ، یا تعداد بیت های هر دسته از حروف را به ترتیب نگه می دارد.
مثلا یک روش خوب : اگر می دانید که نهایتا هر حرف شما ماکسیمم 4 بیت دارد ، به شکل مناسب و بهینه یک جدول تعریف کنید که از هر دو بیت پشت سر هم تعداد بیت های ذخیره شده برای هر حرف فهمیده شود:



00 <-- 1 bit
01 <-- 2 bits
10 <-- 3 bits
11 <-- 4 bits

مثلا با ذخیره یکسری کد به عنوان جدول ایندکس شما مثل 0011 ... که به معنی آن است که حرف a دارای 4 بیت است و سپس حرف b دارای 1 بیت است و .... و یا هر روشی مانند آن.
با این روش شما در هنگام ذخیره باید جدول ایندکس خود را کامل کنید و همچنین می توانید در هنگام خواندن بیت های ذخیره شده ، بدانید که کدام بیت ها متعلق به کدام حرف است.

ضمنا از آنجایی که درخت تعداد نامعلوم بیت ممکن است داشته باشد (یا حتی معلوم) بهتر است یک حافظه به شکل پویا در نظر گرفته شود تا به ترتیب عمل ذخیره را در یک سری از بیت ها ذخیره کنیم و به این شکل (با داشتن جدول ایندکس) روش بهینه این است که از همان یک بیت باقیمانده هم که اشاره کردید ، استفاده کنید.

[max_15s]

برای پیاده سازی کد هافمن از "کاراکتر" استفاده کردم یک تابع از توی فایل یک کاراکتر می خوند و به صفر و یک تبدیل می کرد و در صف می ذاشت و بعد یک تابع دیگه از صف می خوند و کد رو با کاراکتر (از جدول ایندکس) مطابقت می داد و اگر به صفر و یک بیشتری برای کد نیاز داشت تابع یک کاراکتر دیگه رو می خوند و به صف اضافه می کرد ، فقط نباید یادت بره که eof رو باید به عنوان یک کاراکتر جدا تعریف کنی مثلا با کد 256 و به عنوان آخرین کد در نظر بگیری و وقتی خوندیش کار تمومه ، اگه این کار رو نکنی تابع توی آخرین کاراکتر خطا داره ، چون ممکنه از آخرین کاراکتر فقط سه بیت رو مصرف کنی ، و پنج بیت با هرچی پر بشه خطاست.
فایل هافمنت می شه یه فایل با کاراکتر های درهم .

که توی پروژه ما باید یک فایل متن می خوندی و کد می کردی و خط اول جدول ایندکس رو به ازای بیست و شش کاراکتر و ... به ترتیب می نوشتی (یعنی ترجمه خط اول می شد ...ABCD) و بعد هم برنامه ات باید فایل کد شده رو به فایل متنی تبدیل می کرد که به روش بالا بود.
اما برای کد کردن ، باز هم یک صف بود که به ازای هر کاراکتر صفر و یک های معادل رو تی صف می ذاشتیم و از صف هشت تا هشتا می خوندیم و کاراکتر معادل رو در فایل چاپ می کردیم و وقتی توی فایل ورودی به eof می رسیدیم کد معادل رو که به عنوان آخرین عضو جدول ایندکس تعریف می کردیم می نوشتیم و بقیه بایت رو اگر لازم بود با صفر پر می کردیم ، اما حین خوندن فقط تا کد eof می خوندیم و بقیه رو نادیده می گرفتیم.

[emad_67]

مثلا یک روش خوب : اگر می دانید که نهایتا هر حرف شما ماکسیمم 4 بیت دارد ، به شکل مناسب و بهینه یک جدول تعریف کنید که از هر دو بیت پشت سر هم تعداد بیت های ذخیره شده برای هر حرف فهمیده شود:


00 <-- 1 bit

01 <-- 2 bits
10 <-- 3 bits
11 <-- 4 bits


مثلا با ذخیره یکسری کد به عنوان جدول ایندکس شما مثل 0011 ... که به معنی آن است که حرف a دارای 4 بیت است و سپس حرف b دارای 1 بیت است و .... و یا هر روشی مانند آن.

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


من این روش رو درست متوجه نشدم یعنی باید هر 2 بیت رو معادل 1 بیت فرض کنم؟ آیا باید همون 2 بیت رو در فایل ذخیره کنم یا 1 بیت رو؟ میشه همین روش رو برای رشته "abcd" توضیح بدی که چه جوری میشه؟ به فرض ماکزیمم تعداد بیت ها برای هر حرف 4 بیت باشه و مثلا تعداد بیت ها به این شکل:


a 11
b 00
c 100
d 0100



اما برای کد کردن ، باز هم یک صف بود که به ازای هر کاراکتر صفر و یک های معادل رو تی صف می ذاشتیم و از صف هشت تا هشتا می خوندیم و کاراکتر معادل رو در فایل چاپ می کردی
یعنی توی روش شما هر کاراکتر معادل 8 بیت بود؟
یه سوال دیگه هم بحث تداخل این بیت ها با هم هست یعنی مثلا اگه تعداد بیت ها برای abcd به شکلی که در بالا گفتم باشه وقتی اونا رو در فایل ذخیره کنیم به این شکل میشه:


11 00 100 0100


حالا موقع خوندن من باید چند بیت چند بیت خونم؟

[Nima_NF]

11 00 100 0100

حالا موقع خوندن من باید چند بیت چند بیت خونم؟

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

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



11 00 100 0100 <-- "abcd"

ایندکس برای بیت های فوق می شود:

01 01 10 11 <---- 2 bits , 2 bits , 3 bits , 4 bits

که ابتدا همان 4 قانونی را که در پست قبل ذکر کردم را تعریف می کنید، و بعد مثل فوق در جدول ایندکس هم ذخیره می کنید (01 به معنی داشتن 2 بیت است و این یعنی دو بیت بخوان و به همین ترتیب ... )
اگر هم علاوه بر بیت ها نیاز به تعریف حروف در جدول ایندکس هم دارید ، که کار خود را سخت نکنید و به راحتی هر کارکتر را در یک بایت و سپس تعداد بیت های آن را هم در بایت بعد آن قرار دهید و فقط در همان ذخیره 0 و 1 درخت صرفه جویی کنید.

[emad_67]

میشه در مورد این جدول ایندکس یه توضیحی بدی.
نمیدونم درست فهمیدم یا نه ولی مثلا اگه از درخت 0100 به دست اومد چون دارای 4 بیت هست من باید در جدول ایندکس 11 رو بنویسم؟ و برای خوندن هم باید ابتدا از جدول ایندکس 2 بیت 2 بیت بخونم و مثلا اگه 11 بود یعنی اینکه باید 4 بیت از فایل کد گذاری شده بخونم؟
یه چیز دیگه اینکه این جدول ایندکس رو باید بهتره تو یه فایل مجزا قرار بدم یا در همون فایل کد گذاری شده؟

[max_15s]

میشه در مورد این جدول ایندکس یه توضیحی بدی.
نمیدونم درست فهمیدم یا نه ولی مثلا اگه از درخت 0100 به دست اومد چون دارای 4 بیت هست من باید در جدول ایندکس 11 رو بنویسم؟ و برای خوندن هم باید ابتدا از جدول ایندکس 2 بیت 2 بیت بخونم و مثلا اگه 11 بود یعنی اینکه باید 4 بیت از فایل کد گذاری شده بخونم؟

به همین صورت درسته اما اگر تمام کاراکتر های الفبا اومده باشن 2 بیت جواب نمی ده ولی 4 بیت کامله



یه چیز دیگه اینکه این جدول ایندکس رو باید بهتره تو یه فایل مجزا قرار بدم یا در همون فایل کد گذاری شده؟
ما درخت رو با استفاده از همین روش اول فایل می نوشتیم و برای دیکد کردن ازش استفاده می کردیم به این ترتیب که اول حروف الفبا بعد اعداد و بعد وایت اسپیس ها را به ترتیب می نوشتیم و در ساخت مجدد درخت استفاده می کردیم(که البته من دوباره درخت نمی ساختم:عصبانی++:)
به این ترتیب مثلا


a 11
b 00
c 100
d 0100
در اول فایل به صورت
001011001000001110001000100و الی آخر دخیره می کردیم که اول یک چهار بیت رو می خوندیم مثلا 0010 و این نشون می داد که باید بعد از اون دو بیت را برای کاراکتر a بخوانیم پس 11 را می خواندیم
و کاراکتر هایی که در متن نیامده بودند با 1111111111111110 و eof را با 1111111111111111 نشان می دادیم که از آنها صرفنظر می کردیم که البته در یک متن کوتاه حجم افزایش می یابد
اما می تونی کد هر حرف رو بدست بیاری
به قولی فایل رو هیدر دار می کردیم
البته اگر بخوای فشرده سازی رو نمایش بدی بهتره که این فایل جدا باشه اما در کل باز هم هر دوفایل رو باهم لازم داری





من این روش رو درست متوجه نشدم یعنی باید هر 2 بیت رو معادل 1 بیت فرض کنم؟ آیا باید همون 2 بیت رو در فایل ذخیره کنم یا 1 بیت رو؟ میشه همین روش رو برای رشته "abcd" توضیح بدی که چه جوری میشه؟ به فرض ماکزیمم تعداد بیت ها برای هر حرف 4 بیت باشه و مثلا تعداد بیت ها به این شکل:


a 11
b 00
c 100
d 0100


یعنی توی روش شما هر کاراکتر معادل 8 بیت بود؟
یه سوال دیگه هم بحث تداخل این بیت ها با هم هست یعنی مثلا اگه تعداد بیت ها برای abcd به شکلی که در بالا گفتم باشه وقتی اونا رو در فایل ذخیره کنیم به این شکل میشه:


11 00 100 0100

حالا موقع خوندن من باید چند بیت چند بیت خونم؟


در اینجا باید یک بیت یک بیت بخونی "در کد هافمن هیچ کاراکتری به عنوان بخش ابتدایی کد هیچ کاراکتری دیگری نیست"
با توجه به این من بعد از بدست آوردن کد هر کاراکتر ، اونها رو توی یک وکتور (به صورت رشته صفر و یک) می ریختم و یک تابع match ایجاد کرده بودم که کد دو رشته را از ابتدا با هم مقایسه می کرد .

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

البته به این روش هم می شه عمل کرد (در ضمیمه)

اون "هشت بیت هشت بیت" مربوط به انکد بود یعنی یک صف دارم ، و رشته "abcd" حالا a رو می خوندم و دوتا یک توی صف می ذارم (11) بعد b و صف به صورت 1100 بعد c و صف به صورت 1100100 و بعد d و صف به صورت 11001000100 حالا هشت تا از اول می خونم (11001000) و کاراکتری با این نمایش باینری و کد اسکی 200 که ╨ می باشد رو در فایل خروجی چاپ می کنم ، و صف به 100 خواهد بود و منتظر خواندن کاراکتر های بعدی و درج آنها و ...
یعنی کد شده رشته "abcd" به صورت "♦╨" خواهد بود

[SMRAH1]

سلام
برای دستکاری بیتی میتونی از BitFeild ه ماستفاده کنید مثلا ساختار زیر رو در نظر بگیرید:

struct BYTEBIT{
unsigned Bit1 : 1;
unsigned Bit2 : 1;
unsigned Bit3 : 1;
...
unsigned Bit8 : 1;
}
که برای استفاده مثل عناصر ساختمان هاست مثلا

struct BITBYTE a;
a.Bit1 = 1;
....

[emad_67]

با تشکر


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

در اول فایل به صورت کد:
001011001000001110001000100
و الی آخر دخیره می کردیم که اول یک چهار بیت رو می خوندیم مثلا 0010 و این نشون می داد که باید بعد از اون دو بیت را برای کاراکتر a بخوانیم پس 11 را می خواندیم
چرا اول فایل 0010 را مینوشتین؟ اصلا 0010 چی هست و از کجا به دست اومده؟

در اینجا باید یک بیت یک بیت بخونی "در کد هافمن هیچ کاراکتری به عنوان بخش ابتدایی کد هیچ کاراکتری دیگری نیست"
من باخره نفهمیدم که چند بیت باید بخونم چون در یه قسمت هم گفتین که :

اول یک چهار بیت رو می خوندیم مثلا 0010 و این نشون می داد که باید بعد از اون دو بیت را برای کاراکتر a بخوانیم پس 11 را می خواندیم
در کل من درست متوجه نشدم که چه جوری باید این جدول ایندکس رو تشکیل بدم در فایل ضمیمه هم که گذاشته بودین نیاز به بازیابی درخت بود. آیا اصلا میشه مجددا درخت رو بازیابی کرد؟ البته من نمیخوام که مجددا درخت رو بازیابی کنم چون فکر کنم خیلی سخت میشه.
من تقریبا الگوریتمی که آقا نیما گفتن رو فهمیدم و چون از جدول ایندکس 2 بیت 2 بیت میخونیم فکر میکنم راه راحت تری باشه چون تعداد بیت هایی که قراره بخونیم ثابت هست. ولی مشکل من در بازیابی اون هست مثلا اگه از جد.ل ایندکس 11 رو خوندم یعنی اینکه باید 4 بیت از فایل کد گذاری شده بخونم و حالا مثلا اگه اون 4 بیت 0100 باشه من از کجا بفهمم که این کد مربوط به کدوم کاراکتر هست؟ البته آقا نیما در انتهای صحبتشون یه اشاره ای کردن ولی درست متوجه نشدم

اگر هم علاوه بر بیت ها نیاز به تعریف حروف در جدول ایندکس هم دارید ، که کار خود را سخت نکنید و به راحتی هر کارکتر را در یک بایت و سپس تعداد بیت های آن را هم در بایت بعد آن قرار دهید و فقط در همان ذخیره 0 و 1 درخت صرفه جویی کنید.
یعنی من اگه بخوام کاراکتر ها رو هم در جدول ایندکس قرار بدم باید ابتدا اون کاراکتر و بعد مقدار کدی که از درخت به دست اومده رو در بایت کناری اون قرار بدم؟

[max_15s]

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


ببین دو تا مبحث جدا داریم : انکد و دیکد
وقتی انکد می کنی باید طریقه دیکد رو به خاطر بسپاری ، در اینجا مثلا باید بدونی هر کاراکتر با چه کدینگی به کار رفته ، یعنی درخت هافمنت رو هم ذخیره کنی .

طول کد ها برای کاراکتر های مختلف متفاوته ، و یکی از روشهای خوندن چنین داده ای اینه که طول کد رو اولش ذخیره کنیم تا حدودش معلوم شه ،

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


a 11 ---> 0010,11 ---> 0010 برای طول
b 00 ---> 0010,00 طول در اینجا 2 است لذا طول 2 را نمایش می دهیم
c 100 ---> 0011,100 طول 3
d 0100 ---> 0100,0100یعنی برای دیکد کردن نیاز به درخت دارم پس کدینگ هر حرف را همراه با یک پیشوند ثابت چهار بیتی در خط اول فایلی که فشرده شده ی فایل ورودی است چاپ می کنم . و با خوندن این خط کدینگ هر حرف بدست می یاد که میشه در دیکد استفاده کرد

خط اول رو که خوندم ، درخت تشکیل و برای دیکد استفاده می شه. (که من با حذف از وکتور کار کردک)

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

حالا توی دیکد:
اول باید درخت رو بخونی ، که در اول فایل ذخیره شده ، برای این کار اول یک چهار بیت رو می خونی ، این چهار بیت نشان دهنده ی طول کاراکتر اول است مثلا

001011001000001110001000100

چهار بیت اول برای حرف a (اول حروف بعد اعداد بعد ... یا هر ترتیبی که مساله می خواد)
0010 : یعنی دو ، پس دو بیت بعدی یعنی کدینک a در درخت هافمن
یعنی 11
بعد یه چهار بیت دیگه برای حرف b :
0010 : یعنی دو بیت بعدی کدینگ b رو نشون می ده
یعنی 00
و ... الی آخر:
0010,11,0010,00,0011,100,0100,0100

حالا خط دوم فایل کد شده رو می خونی:

مثلا
11001000100
یک بیت به یک بیت شروع به خوندن می کنی و هر جا با یکی از کدینگ ها مچ شد ، کاراکتر مربوط رو چاپ می کنی ، از خوندن خط اول مثلا این نتیجه حاصل شد:
a 11
b 00
c 100
d 0100
بیت اول رو می خونی (1) با هچ کدوم مچ نیست ، اما b , d از لیست حذف می شن (چون با یک شروع نشده بودند) بیت دوم رو می خونی (1 و در کل داری 11) با a مچ شد پس a رو چاپ می کنی و دوباره از نو .

یک بیت رو می خونی (0) با هیچ کدوم مچ نیست اما a و c از لیست حذف می شن ، بیت بعدی رو می خونی (0 و در کل داری 00) با b مچ شده پس b رو چاپ می کنی

یک بیت می خونی (1) و b و d از لیست حذف می شن ، بیت بعدی (0 و در کل 10 ) و a‌ هم حدف می شه ، بیت بعدی (0 و در کل 100) با c مچ می شه پس c رو چاپ می کنی

و ...


در صورتی که ماکزیمم تعداد بیت ها 4 بیت باشه قاعدتا نباید مشکلی در 2 بیت هم پیش بیاد

کاملا حق با توئه اما به شرطی که توی شرایط ذکر شده باشه


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

البته با این روش درخت رو هم بازیابی کردیم فقط برای زیر 40 کاراکتر حتی افزایش حجم خواهد داشت و ...
اصلا مگه می شه دیکد کرد بدون داشتن درخت؟ لطفا



همین دیگه :متفکر:


یا اینکه می تونی از اون درخت و روشی که توی فایل ضمیمه گفته شده بود برای دیکد استفاده کنی که همین بهتره!!!
و یک مطلب که الان به ذهنم رسید اینکه حین انکد برای کاراکتر هایی که در متن نیومدن طول 0000 رو قرار بدی که خود به خود نادیده گرفته بشن

[SMRAH1]

سلام
دوستان گرامی آقایان عماد67 و Max_15s :
گمانم در درک الگوریتم هافمن و جدول ایندکسی که استادمون آقا نیما مطرح کردند کمی به خطا رفته اید.بهتره قبل از ادامه مطلب، اول اون pdf که Max_15s گذاشته بودند رو لطفا دوباره نگاه کنید.
در الگوریتم هافمن ابتدا فراوانی هر کاراکتر در فایل محاسبه می شود.مثلا فرض کنید تمام کاراکتر های فایلی که می خواهیم فشرده نماییم،از کاراکتر های eوnوaوtوs که در همان pdf استفاده شده، تشکیل شده اند و فراوانی هر کاراکتر به ترتیب از بیشترین به کمترین ،حروف e بعد a بعد t بعد n و در نهایت s باشد.در این صورت به هر کاراکتر به ترتیب رشته ای از بیت های صفر و یک رو به شکل زیر تخصیص می دهیم (برای درک کامل روش تخصیص به pdf مراجعه کنید) :

e = 0
a = 10
t = 110
n = 1110
s = 1111
توجه کنید که در هر ردیف با فرض اینکه حداکثر تعداد بیت ها 4 تا است،هر رشته از یک سری بیت یک تشکیل شده و به صفر ختم می شود.با این اوصاف کد کردن کلمه sane به شکل زیر است:

sane = 11111011100
برای Decode کردن رشته صفر و یک بالا (یعنی 11111011100) نیاز به دو اطلاعات از طریقه کد کردن داریم:
اول اینکه حداکثر تعداد بیت مصرفی چند تا است (در مثال ما این تعداد 4 بیت است)
دوم اینکه جدول تخصیص بیت ها چگونه است.به عبارت دیگر همان جدولی که در آن e=0،a=10و...
حالا با فرض داشتن این اطلاعات داریم:
1. بیت اول را می خوانیم ،چون یک است بیت دوم را می خوانیم.چون یک است بیت سوم را می خوانیم و چون یک است بیت چهارم را می خوانیم ولی این بار به دلیل اینکه به حداکثر تعداد بیت رسیدیم پس دیگر بیتی را نخوانده و همین عبارت 1111 معادل یک کاراکتر است.با مراجعه به جدول حرف s را می یابیم.
2 . بیت بعدی را می خوانیم و چون یک است بیت بعدش را می خوانیم.در این جا چون این بیت 0 است یعنی ما به انتهای بیت های کد شده رسیده ایم یعنی 10 خود یک حرف معادل دارد که با توجه به جدول حرف a را می یابیم.
3. الگوریتم بالا حرف بعدی را به شکل 1110 یافته که می شود n .
4 . با الگوریتم بالا هر حرف بعدی یعنی 0 یا همان حرف e را می یابیم.
5 . با رسیدن به انتهای فایل ، عبارت را سرهم می کنیم یعنی sane.

همانطور که متوجه شدید عدد صفر کار یک جدا کننده را انجام می دهد.(البته به همراه حداکثر 4 رقم).و همانطور که آقای Max_15s فرمودند بهتر است یک کاراکتر جداکننده هم در نظر بگیرید تا انتهای فایل را راحت متوجه شوید (البته این یک راه حل از هزاران است!!!).

حالا میرسیم به آن جدولی که اقا نیما فرمودند.با توجه به اینکه کاراکترها در جدول کد کردن به صورت افزایشی هستند (اولی یک بیت دومی دو بیت و .. ) می شه به جای ذخیره تمام جدول بالا (به خصوص در جداول بزرگتر) تعداد هر بیت مصرفی را بگذاریم مثلا با استفاده از 2 بیت ،حرف e عدد 0 (معادل تعداد یک های به کار رفته در کد e یعنی 0).حرف a عدد1 و .. حرف s عدد 4 را ذخیره می کند.(این کار فضای کمتری برای ذخیره مصرف می کند).

در آخر هم دو نکته را تاکید می کنم:
اول اینکه روش کد کردن هافمن یا برای کد گذاری روی فایل استفاده می کنند و اگر برای فشرده کردن هم باشد باید 7 کاراکتر با بالاترین فراوانی در کاراکتر های فایل،درصد بسیار بالایی (بستگی به فراوانی آنها و دیگر کاراکترها دارد).شما می توانید 90 درصد را ملاک قرار دهید (ولی باز هم تاکید می کنم که تا بعد از فشرده کردن یا انجام محاسبات کامل نمی توان فشرده شدن را مشخص کرد).در غیر اینصوت حجم فایل به اصطلاح فشرده شده، بالاتر از فایل اصلی است.
دوم اینکه آن رشته هایی که آقاعماد مثال زده بودند یعنی a معادل 11 ، b معادلش 00 و ... اصلا رشته بیتی که توسط الگوریتم هافمن تولید شود نیست.(توجه کنید که در این الگوریتم تعداد 1 به یک 0 ختم می شود)

موفق و سربلند باشید.

[max_15s]

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


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


برای Decode کردن رشته صفر و یک بالا (یعنی 11111011100) نیاز به دو اطلاعات از طریقه کد کردن داریم:
اول اینکه حداکثر تعداد بیت مصرفی چند تا است (در مثال ما این تعداد 4 بیت است)
دوم اینکه جدول تخصیص بیت ها چگونه است.به عبارت دیگر همان جدولی که در آن e=0،a=10و...
حالا با فرض داشتن این اطلاعات...محور صحبت های من دقیقا همین نکته بوده است

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

در مورد چگونگی دیکد و فایل ضمیمه هم

یا اینکه می تونی از اون درخت و روشی که توی فایل ضمیمه گفته شده بود برای دیکد استفاده کنی که همین بهتره!!!همچنان همین حرف رو می زنم و البته هیچ مشکلی هم نداره ، در حقیقت بر گرفته از همونه ، یه روش استاندارد وجود داره ، و نتایجش

(البته این یک راه حل از هزاران است!!!).
در ضمن من کاراکتر آخر فایل رو به عنوان جدا کننده!! عنوان نکرده بودم ، فقط به خاطر خطایی که در آخرین کاراکتر رخ می ده استفاده کرده بودم (چون هشت بیت رو می خونیم (یک کاراکتر) و ممکنه فقط یک بیت رو استفاده کنیم ، به همین دلیل eof رو هم به عنوان یک کاراکتر با فراوانی یک در نظر می گیرم ، و خوندنش رو شرط پایان کار قرار می دم)

با تشکر

[emad_67]

با تشکر از آقایان SMRAH1 و Max_15s

مثلا فرض کنید تمام کاراکتر های فایلی که می خواهیم فشرده نماییم،از کاراکتر های eوnوaوtوs که در همان pdf استفاده شده، تشکیل شده اند و فراوانی هر کاراکتر به ترتیب از بیشترین به کمترین ،حروف e بعد a بعد t بعد n و در نهایت s باشد.در این صورت به هر کاراکتر به ترتیب رشته ای از بیت های صفر و یک رو به شکل زیر تخصیص می دهیم (برای درک کامل روش تخصیص به pdf مراجعه کنید) :


e = 0
a = 10
t = 110
n = 1110
s = 1111
یعنی توی این روش شما درخت رو تشکیل نمیدی و فقط از روی فراوانی حرف بیت ها رو اختصاص میدی؟ یعنی مثلا اگه e بالاترین الویت رو داشت به e فقط یک بیت 0 و به الوت بعدی بیت های 10 و .... رو اختصاص میدی؟ در این صورت مشکالی پیش نمیاد؟ یعنی مثلا اگه در بالا علاوه بر کاراکتر هایی که گفتین مثلا حرف h و دارای کمترین فراوانی هم بود اون وقت برای h نحوه قرار گرفتن بیت ها چه جوری میشه؟ آیا اینجوری مجبور نیستیم برای هر حرفی که اضافه میشه تعداد ماکزیمم بیت ها رو هم زیاد کنیم؟

توجه کنید که در هر ردیف با فرض اینکه حداکثر تعداد بیت ها 4 تا است،هر رشته از یک سری بیت یک تشکیل شده و به صفر ختم می شود.
دوم اینکه آن رشته هایی که آقاعماد مثال زده بودند یعنی a معادل 11 ، b معادلش 00 و ... اصلا رشته بیتی که توسط الگوریتم هافمن تولید شود نیست.(توجه کنید که در این الگوریتم تعداد 1 به یک 0 ختم می شود)در درختی که من می سازم همه بیت ها از 1 شروع و به 0 ختم نمیشن یعنی ممکنه برای یک کاراکتر 00 هم داشته باشیم.(البته نحوه ساخت این درخت رو توی دانشگاه به ما گفتن و نمیدونم درسته یا غلط) و اون کاراکتر هایی رو هم که مثال زدم کدش رو از روی همون درختی که به دست اوردم گذاشتم. ولی شما چه جوری درخت رو میسازی؟
یه سوال از جناب Max_15s:
در ختی که توی فایل pdf بود رو شما بر چه اساسی درخت رو رسم کردی و تعداد فراوانی هر حرف چند در نظر گرفته شده؟ چون من هم با همین روش فراوانی ها درخت رو می سازم که درخت حاصل با درختی که شما رسم کردی و روشی که جناب SMRAH1 گفتن( بیت ابتدا 1 و انتها 0) فرق میکنه.

[SMRAH1]

سلام
جناب max_15s شاید اشتباه برداشت از من بوده است.
آقا عماد:
1) اگر فرض کند که فابلی از تمام کاراکتر های حرفی (26 کاراکتر بزرگ حروف انگلیسی) استفاده کرده باشد و کاراکتر دیگری هم استفاده نشده باشد و حرف h (مثلا) حداقل فراوانی را داشته باشد،در این صورت به جای حرف h از معادل رشته بیتی با 24 تا یک و یک صفر استفاده می شود (به درخت pdf توجه کنید کاملا متوجه می شوید).که همانطور که ملاحظه می شود تعداد بیت مصرفی بیش از 3 بایت خواهد بود،به عبارت دیگر یک بایت شامل h را گرفته و سه بایت به اصطلاح فشرده شده بر می گردد.به همین دلیل عرض کردم که حتما در فایل فشرده نشده باید فراوانی 7 کاراکتر اول با بیشترین فراوانی ، خیلی بالا (چیزی بیش از 90 درصد فایل) باشد.
2) در الگوریتم هافمن ،همانطور که در pdf ملاحظه می کنید و من توضیح دادم ،حتما عدد 0 باید جدا کننده باشد و ان جدولی که مثال زده اید قطعا توسط الگوریتم هافمن بدست نمی آید.شاید برای الگوریتم دیگری چنین جدول معادلی ایجاد شود ولی قطعا در الگوریتم هافمن آنها تولید نمی شوند.در این زمینه بهترین راهنما همان pdf است که به صورت بسیار ساده و بصری در این مورد توضیح داده است.

موفق باشید

[max_15s]

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


n 10
s 20
t 25
a 35
e 85
البته خیلی وقت نداشتم ، اما می شه.


حرف h (مثلا) حداقل فراوانی را داشته باشد،در این صورت به جای حرف h از معادل رشته بیتی با 24 تا یک و یک صفر استفاده می شوداین هم در بد ترین شرایط ، که همون اول بحثش رو کردیم که توی صورت سوال گفته شده طول کد حداکثر چهار خواهد بود


در درختی که من می سازم همه بیت ها از 1 شروع و به 0 ختم نمیشن یعنی ممکنه برای یک کاراکتر 00 هم داشته باشیم.(البته نحوه ساخت این درخت رو توی دانشگاه به ما گفتن و نمیدونم درسته یا غلط)درخت هایی که من هم می سازم به همین صورته و حتما به صفر ختم نمی شن ، و اینکه اگر یک کاراکتر کد 00 و یکی کد 0100 را داشته باشد ، در روش هافمن در 000100 هیچ تداخلی وجود ندارد. این خاصیته هافمنه که اونرو از کاراکتر جداکننده بی نیاز می کنه

برای داشتن اون کد ها هم (00 و 0100 و ...) فقط کافی است درختی شبیه به فایل ضمیمه داشته باشیم (البته خطا به علت کمی وقت ممکنه اما شدنیه) (نقطه چین یعنی زیر درخت های بقیه حروف که در اینجا لازم نیستند)


شما بر چه اساسی درخت رو رسم کردیکد گذاریه هافمن (http://en.wikipedia.org/wiki/Huffman_coding)

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