در ساخت اين پروژه به راهنمايى نياز دارم [بایگانی] - سایت علمی نخبگان جوان

توجه ! این یک نسخه آرشیو شده میباشد و در این حالت شما عکسی را مشاهده نمیکنید برای مشاهده کامل متن و عکسها بر روی لینک مقابل کلیک کنید : در ساخت اين پروژه به راهنمايى نياز دارم

*FATIMA*

16th June 2013, 11:25 PM

١
پروژه درس ساختمان داده

Project : Huffman Coding

کد گذاری Huffman یک طرح است که کدبیت هایی با طول های متفاوت را به کاراکترها اختصاص میدهد.به طوری که طول کدها به تکرار کاراکترها در یک پیام معمولی بستگی دارد. به عنوان یک نتیجه، پیام های کد گذاری شده یا همان encoded messages به فضای کمترنیاز دارند. (در مقایسه با کد گذاری با طول ثابت ) از این رو کلماتی که بیشتر ظاهر میشن اغلب کدهای کوتاه تر به آن ها اختصاص داده شده است. این انجام میشه با اول ساختن درخت کد گذاری Huffman coding tree)Huffman )براساس یک سری تکرارهای داده شده. از درخت، کد بیت هایی برای هر کاراکتر تعیین می شود و سپس مورد استفاده برای رمزی کردن پیام قرار میگیرد. این درخت نیز استفاده می شود برای رمزگشایی پیام های کد گذاری شده به طوری که آن فراهم می کند یک راه برای تعیین اینکه کدام رشته بیت های ترجمه بر میگرده به یک کاراکتر.
انتساب:
برای این انتساب شما باید 3 برنامه بنویسید.
Buildtree: ساخت درخت: با در نظر گرفتن یک فایل که شامل توزیع فراوانی برای هر 26 حرف از حروف الفبا به علاوه سه کاراکترهای خاص (فضا، خط جدید، و پایان پیام)، ساخت درخت دو فایل تولید میکند: فایل کدگذاری هافمن درخت و یک فایل حاوی وظایف هر کد.
Encode :رمز گذاری: با توجه به فایل کد بیتی که توسط ساخت درخت تولید شده، و یک فایل متنی حاوی پیام،
رمز encode یک فایل باینری که حاوی پیام رمزی شده است تولید می کند.
Decode: رمزگشایی: با توجه به فایل کدگذاری هافمن درخت که توسط ساخت درخت تولید شده ، و پیام کد گذاری شده ی
ایجاد شده توسط رمزگذاری encode، رمزگشا پیام اصلی را دوباره تولید می کندو پیام رادر یک فایل متنی چاپ کند.

شما ممکن فرض کنید که پیام ها در حروف کوچک نوشته شده اند.فایل تکرار یک فایل متنی با 29 خط است، جایی که هر خط شامل یک حرف (و یا یک کاراکتر خاص) و به دنبال آن یک فضا space است.و یک عدد صحیح مثبت (رشته ای از ارقام).دراین فایل تکرار، برای کاراکترهای خاص کدها به شرح زیر است‘''برای فضای،‘!’خط جدید، و '+' برای پایان پیام.
فایل درخت نمایندگی متوالی از درخت ساخته شده درساخت درخت buildtree است تا خوانده شودوباز افرینی شود در رمزگشا decode.
فایل بیت کد 29 خط فایل متنی است. هر خط در این فایل حاوی یک حرف (یا کاراکترویژه) به دنبال آن فضا spaceو سپس رشته ای از 1 ها و 0 ها.ترتیب کاراکترهای این فایل به شرح زیر است.'A' تا 'Z'، فضا space، نقطه، خط جدید، پایان پیام.
فایل پیام متشکل از خطوط حاوی حروف کوچک ، فضاهای واقعی ( نه ‘-’)، ونقطه ها.هنگام تفسیر فایل پیام، یک کاراکتر تعویض خط در پایان هرخط به طور ضمنی است، و یک کاراکتر نهایی از پیام است که در انتهای فایل به طور ضمنی است.
فایل کد گذاری جریانی از بایت های است که بیت های متناظر را کد می کند. در صورتیکه نتیجه شمارش تعداد بیت ها مضربی از 8 نیست، اضافه کنید بیت به اندازه کافی (با مقدار 0) تا بیت نهایی را بسازید.
هنگامی که رمزگشا decode را اجرا میکنید، توجه کنید که کاراکتر پایان پیام مهم است چون مشخص میکند هنگامی را که باید رمز گذاری متوقف شودبه خصوص اگر بیت های باقی مانده در آخرین بایت ازپیام کد گذاری شده وجود داشته باشد.

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

Data Structures ساختمان های داده: شما باید از یک گره پویا برای پیاده سازی یک درخت دودویی برای نشان دادن کدگذاری هافمن درخت استفاده کنید. توجه داشته باشید که گره های داخلی و برگ در درخت حاوی اطلاعات مختلف است. برای سادگی،از درخت ساختمان داده شبیه هم برای ساخت درخت buildtree و رمزگشایی decode استفاده کنید.
ساختن درخت هافمن شامل ترکیب های متوالیی میشود دو گره ه با حداقل ارزش یا زیر درخت.در مورد روابط برای مقادیر حداقل، disambiguate با استفاده از قوانین زیر است:

•چند گره در زیردرخت subtrees مقدم بر گره تنها است.
•زیر درختی که به تازگی ایجاد شده مقدم بر سایر زیر درخت ها می باشد.
• یک گره منفرد که زودتر در لیست حروف الفبا ظاهر می شود اولویت ان بیش از گره های دیگر تنها است. فضا، نقطه، خط دید، پایان پیام (به همین ترتیب) در لیست حروف الفبا بعد از z قرار میگیرد.
ساده ترین راه برای اجرای قوانین داده شده در بالا این است که یک لیست از درختان طبقه بندی شده براساس وزن تنظیم کنیم . این لیست آغاز می شود به عنوان یک لیست از گره های تنهای مرتب شده براساس وزن، از ترتیب حروف الفبای گره ها در صورت مساوی بودن وزنشان استفاده کنید. شما سپس بارها و بارها دو مورد اول در لیست را باید حذف کنید وان ها را به شکل یک زیر درخت ترکیب کنید.زیر درخت نتیجه را دوباره در این لیست با توجه به وزن جدیدش قرار می دهیم. در صورتی که عناصر در لیست با همان وزن زیر درخت وجود دارد، زیر درخت را درست قبل از اولین مورد با ان وزن قرار دهید. بازنمودهای متوالی از یک درخت دودویی در بخش 6.5 (صفحات 208-210) از متن مورد بحث قرار گرفته است... شما مجاز به استفاده از هر یک از روش های پیشنهاد شده هستیدو فرمت فایل خود را اختراع کنید زمانی فایلی که شما تولید کردید یک فایل متنی قابل خواندن است که توسط TAS قابل تفسیرباشد. طبق معمول،برای شما ممکن نیست که از stl استفاده کنیداما این امکان وجود دارد که تقلید کنید از کد خودتان اگر کد موجود درکتاب درسی باشد.
Program Invocation:برنامه ها به شرح زیر استفاده می شود.
buildtree <frequencyfile> <treefile> <codefile>
encode <codefile> <messagefile> <encodedmessagefile>
decode <treefile> <encodedmessagefile> <messagefile>
اگر خط فرمان شامل استدلال کافی نباشد و یا در صورتی که هر یک از فایل های ورودی مشخص وجود ندارد، این برنامه باید یک پیغام خطا مناسب چاپ کندو خارج شود.
نمونه هایی از فایل های ورودی وخروجی:
frequency.txt
c ٤
d ٢
- ١٥
a ١١
b ٧
e ٢٠
! ٤
+ ١
f ٥
. ٠
z ٠
w 0
بقیه کلمات تکرارشان0 است))
codes.txt
a ١٠١
b ٠٠١
c ٠٠٠١
d ٠٠٠٠١
e ١١
f ١٠٠١
g ...
h ...
z ...
- ٠١
. ...
! ١٠٠٠
+ ٠٠٠٠٠١
message.txt
a bad
face
encodedmessage.bin
این یک فایل باینری 6 بیتی است))
١٠١٠١٠٠١ ١٠١٠٠٠٠١ ١٠٠٠١٠٠١ ١٠١٠٠٠١١ ١١٠٠٠٠٠٠
٠٠١٠٠٠٠٠

امـیـر بـیـگـی

17th June 2013, 01:38 AM