Abstract

We present work-optimal PRAM algorithms for Burrows–Wheeler compression and decompression of strings over a constant alphabet. For a string of length n  , the depth of the compression algorithm is O(log2 n, and the depth of the corresponding decompression algorithm is O(logn) . These appear to be the first polylogarithmic-time work-optimal parallel algorithms for any standard lossless compression scheme. The algorithms for the individual stages of compression and decompression may also be of independent interest: (1) a novel - O(logn) time, O(n)-work PRAM algorithm for Huffman decoding; (2) original insights into the stages of the BW compression and decompression problems, bringing out parallelism that was not readily apparent, allowing them to be mapped to elementary parallel routines that have - O(logn) time, O(n)-work solutions, such as: (i) prefix-sums problems with an appropriately-defined associative binary operator for several stages, and (ii) list ranking for the final stage of decompression. Follow-up empirical work suggests potential for considerable practical speedups on a PRAM-driven many-core architecture, against a backdrop of negative contemporary results on common commercial platforms

چکیده

ما الگوریتمهای PRAM  کار-بهینه را برای فشرده سازی و بازکردن Burrows–Wheeler رشته ها روی یک مجموعه ثابت ارائه میدهیم. برای یک رشته باطول n  ،عمق الگوریتم فشرده سازی O(log2 n)و عمق الگوریتم بازگشایی ان O(logn) است.این به نظر میرسد که اولین الگوریتم موازی کار-بهینه زمان-پلی لگاریتمی برای هر برنامه فشرده سازی بدون اتلاف استاندارد باشد.این الگوریتمها برای مراحل منحصر بفرد فشرده سازی و بازگشایی ممکن است از منافع مستقل باشند:
1.یک الگوریتم  PRAM جدید با زمان  O(logn) وکار  (O(n  برای رمزگشایی هافمن.2.دیدگاههای اصلی به مراحل مسائل فشرده سازی و بازگشایی BW ،که موازی بودن را که به اسانی اشکار نبود واضح تر میسازد، به انها اجازه میدهد تا به روالهای موازی ابتدایی منطبق شوند که دارای راه حلهای O(logn) –زمان و (O(n-کار هستند،مانند :((i مسائل پیشوند-مجموع با یک عملگر باینری شرکت پذیر به طور مناسب تعریف شده برای چندین مرحله،(ii) فهرست رتبه بندی برای مرحله نهایی بازگشایی.کار تجربی تکمیلی  ،پتانسیلی را برای افزایش عملی قابل توجه روی معماری چند هسته   PRAM محور پیشنهاد میکند،در مقابل یک پس زمینه از نتایج معاصر منفی برروی پلتفرمهای تجاری معمول.

1-مقدمه

فشرده سازی داده بدون اتلاف ،یک تابع استاندارد مکررا استفاده شده در تعداد زیادی از سیستمهای کامپیوتری است. یک تابع فشرده سازی بدون اتلاف یک تابع C(·) معکوس پذیر است،که یک رشته S  به طول n را به عنوان ورودی  روی مجموعه Σدریافت میکند و یک رشته C(S) روی مجموعه Σ پریم را برمیگرداند،به طوریکه در برخی مدلهای اماری تعداد بیتهای کمتری نسبت به S برای نمایش C(S) لازم است.یک الگوریتم فشرده سازی بدون اتلاف برای یک تابع فشرده سازی داده شده یک الگوریتم است که S  را به عنوان ورودی دریافت میکند و (S) را به عنوان خروجی تولید میکند.الگوریتم بازگشایی بدون اتلاف مربوطه C(S) را برای S  به عنوان ورودی میپذیرد و S را به عنوان خروجی تولید میکند.بعضی از شناخته شده ترین استانداردها الگوریتم فشرده سازی gzip [1]وbzip 2[2] هستند.استاندارد bzip2  الگوریتم فشرده سازی Burrows–Wheeler را پیاده سازی میکند…