رمزگذاری طول اجرا

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

رمزگذاری طول اجرا (RLE) یک شکل بسیار ساده از فشرده سازی داده است که در آن جریانی از داده به عنوان ورودی داده می شود (یعنی “AAABBCCCC”) و خروجی دنباله ای از تعداد مقادیر متوالی داده در یک ردیف است (یعنی ” 3A2B4C”). این نوع فشرده‌سازی داده‌ها بدون تلفات است، به این معنی که هنگام فشرده‌سازی، تمام داده‌های اصلی هنگام رمزگشایی بازیابی می‌شوند. سادگی آن در هر دو رمزگذاری (فشرده سازی) و رمزگشایی (فشرده سازی) یکی از جذاب ترین ویژگی های الگوریتم است.

در اینجا می توانید یک مثال ساده از یک جریان (“اجرای”) از داده ها را به شکل اصلی و رمزگذاری شده آن مشاهده کنید:

داده های ورودی:

AAAAAAFDDCCCCCCCAEEEEEEEEEEEEEEEEE

داده های خروجی:

6A1F2D7C1A17E

در این مثال ما توانستیم داده ها را از 34 کاراکتر به 13 فشرده کنیم.

همانطور که ممکن است متوجه شده باشید، هر چه مقادیر متوالی در یک ردیف بیشتر باشد، فضای بیشتری در فشرده سازی حاصل صرفه جویی می کنیم. از سوی دیگر، اگر دنباله ای از داده ها دارید که به طور مکرر بین مقادیر تغییر می کند (به عنوان مثال “BEFEFADED”) در این صورت اصلاً فضای زیادی ذخیره نمی کنیم. در واقع، ما حتی می‌توانیم اندازه داده‌های خود را افزایش دهیم زیرا یک نمونه از یک کاراکتر منجر به 2 کاراکتر (یعنی “A” تبدیل به “1A”) در خروجی رمزگذاری می‌شود.

به همین دلیل، RLE فقط برای انواع خاصی از داده ها و برنامه ها مناسب است. به عنوان مثال دوربین پیکسی، که یک دوربین روباتیک است که به شما کمک می کند اشیا را به راحتی ردیابی کنید، از RLE برای فشرده سازی داده های ویدیویی برچسب زده شده قبل از انتقال آن از دستگاه دوربین تعبیه شده به یک برنامه خارجی استفاده می کند. به هر پیکسل یک برچسب “بدون شی”، “شی 1″، “شی 2″، و غیره داده می شود. این رمزگذاری عالی برای این برنامه به دلیل سادگی، سرعت، و توانایی آن در فشرده سازی داده های برچسب آنتروپی پایین است.

رمزگذاری

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

در زیر یک پیاده سازی ساده در پایتون پیدا خواهید کرد:

def rle_encode(data):
    encoding = ''
    prev_char = ''
    count = 1

    if not data: return ''

    for char in data:
        
        
        if char != prev_char:
            
            
            if prev_char:
                encoding += str(count) + prev_char
            count = 1
            prev_char = char
        else:
            
            
            count += 1
    else:
        
        encoding += str(count) + prev_char
        return encoding

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

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

encoded_val = rle_encode('AAAAAAFDDCCCCCCCAEEEEEEEEEEEEEEEEE')
print(encoded_val)

و خروجی:

$ python rle-encode.py
6A1F2D7C1A17E

رمزگشایی

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

در اینجا الگوریتم پیاده سازی شده در پایتون آمده است:

def rle_decode(data):
    decode = ''
    count = ''
    for char in data:
        
        if char.isdigit():
            
            count += char
        else:
            
            
            
            decode += char * int(count)
            count = ''
    return decode

ما می توانیم این کد را اجرا کنیم روی همان خروجی ای که از رمزگذاری خود گرفتیم:

decoded_val = rle_decode('6A1F2D7C1A17E')
print(decoded_val)

و خروجی همان ورودی اصلی ما به تابع رمزگذاری است:

$ python rle-decode.py
AAAAAAFDDCCCCCCCAEEEEEEEEEEEEEEEEE

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