Posted By admin Posted On Comment (4)

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

 الگوریتم پریم جز الگوریتم های حریصانه است . همان طور که از نام الگوریتم های حریصانه پیداست، این الگوریتم ها حرص می زنند . از این الگوریتم برای فشرده سازی رشته ها نیز استفاده می شود . برای مثال می خواهیم رشته زیر را با استفاده از الگوریتم پریم فشرده کنیم.
AAAAABBBBBBBCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

در مرحله تخست باید تعداد هر کارکتر را پیدا کنیم .

تعداد کارکتر ها را به دست آوردیم .

  • A = 5
  • B = 7
  • C = 10
  • D = 15
  • E = 20
  • F = 45

پس از به دست آوردن تعداد کارکتر ها باید آن ها را به ترتیب تعدادشان از چپ به راست مرتب کنیم .

A ->B ->C->D->E->F

پس از مرتب کردن ، شروع به ساختن درخت پریم می کنیم :

وزن کارکترهای AوB می شود ۱۲ و درختی به صورت زیر می سازیم :

1

پس از هر مرحله باید کارکتر ها و اعداد به دست آمده به ترتیب وزن شان از چپ به راست مرتب شوند :

F E D * C
45 20 15 12 10

 حال دوباره باید  گره C با وزن ۱۰ را با گره با وزن  ۱۲ جمع کنیم و درختی به صورت زیرایجاد کنیم . توجه داشته باشید گره هایی با وزن کمتر در سمت چپ قرار می گیرند :

2

باز دوباره باید گره ها را به ترتیب وزن شان از سمت چپ مرتب کنیم :

F * E D
45 22 20 15

براساس گره های مرتب شده دوباره باید از سمت چپ همانند مراحل قبل درخت را کامل کنیم :

3

دوباره باید از سمت چپ گره ها را براساس وزن شان مرتب کنیم :

F * *
45 35 22

4

درخت پریم ما تا حدودی کامل شده است و فقط گره F با وزن 45 باقی مانده و باید به این درخت بالایی پیوند بخورد .

5

درخت پریم براساس رشته داده شده کامل شد . حال باید به کمک این درخت رشته را فشرده کنیم .

6

به یال های سمت چپ درخت عدد صفر نسبت می دهیم و به یال های سمت راست آن عدد یک  . با این کار برای هر کارکتر عددی به دست می آید :

 F E D C B A
0 111 110 100 1011  1010

حال به جای رشته داده شده اعداد بالا ذخیره می شوند .

Comments (4)

  • دیدگاهتان را بنویسید

    نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *