الگوریتم پریم جز الگوریتم های حریصانه است . همان طور که از نام الگوریتم های حریصانه پیداست، این الگوریتم ها حرص می زنند . از این الگوریتم برای فشرده سازی رشته ها نیز استفاده می شود . برای مثال می خواهیم رشته زیر را با استفاده از الگوریتم پریم فشرده کنیم.
AAAAABBBBBBBCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
در مرحله تخست باید تعداد هر کارکتر را پیدا کنیم .
تعداد کارکتر ها را به دست آوردیم .
- A = 5
- B = 7
- C = 10
- D = 15
- E = 20
- F = 45
پس از به دست آوردن تعداد کارکتر ها باید آن ها را به ترتیب تعدادشان از چپ به راست مرتب کنیم .
A ->B ->C->D->E->F
پس از مرتب کردن ، شروع به ساختن درخت پریم می کنیم :
وزن کارکترهای AوB می شود ۱۲ و درختی به صورت زیر می سازیم :
پس از هر مرحله باید کارکتر ها و اعداد به دست آمده به ترتیب وزن شان از چپ به راست مرتب شوند :
| F | E | D | * | C |
| 45 | 20 | 15 | 12 | 10 |
حال دوباره باید گره C با وزن ۱۰ را با گره با وزن ۱۲ جمع کنیم و درختی به صورت زیرایجاد کنیم . توجه داشته باشید گره هایی با وزن کمتر در سمت چپ قرار می گیرند :
باز دوباره باید گره ها را به ترتیب وزن شان از سمت چپ مرتب کنیم :
| F | * | E | D |
| 45 | 22 | 20 | 15 |
براساس گره های مرتب شده دوباره باید از سمت چپ همانند مراحل قبل درخت را کامل کنیم :
دوباره باید از سمت چپ گره ها را براساس وزن شان مرتب کنیم :
| F | * | * |
| 45 | 35 | 22 |
درخت پریم ما تا حدودی کامل شده است و فقط گره F با وزن ۴۵ باقی مانده و باید به این درخت بالایی پیوند بخورد .
درخت پریم براساس رشته داده شده کامل شد . حال باید به کمک این درخت رشته را فشرده کنیم .
به یال های سمت چپ درخت عدد صفر نسبت می دهیم و به یال های سمت راست آن عدد یک . با این کار برای هر کارکتر عددی به دست می آید :
| F | E | D | C | B | A |
| 0 | 111 | 110 | 100 | 1011 | ۱۰۱۰ |
حال به جای رشته داده شده اعداد بالا ذخیره می شوند .
خسته نباشید ممنون به خاطر این مطلب زیبا
سلام.وبسایت جالبی دارید.واقعا ممنونم
سلام.واقعا وبسایت خوبی دارید
عاشق این وبسایت شدم من.عالی هستید شما