فصل 9: الگوریتم‌های طراحی پارادایم‌ها

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

در این فصل، ما سه پارادایم طراحی الگوریتم اساسی را بررسی خواهیم کرد: تقسیم و حل، الگوریتم‌های حریصانه و برنامه‌ریزی پویا. این پارادایم‌ها رویکردهای کلی برای حل مسئله را ارائه می‌دهند که می‌توانند برای حل طیف وسیعی از مسائل تطبیق داده شوند. با درک این پارادایم‌ها، می‌توانیم به ساختار الگوریتم‌ها بینش پیدا کنیم و الگوریتم‌های جدیدی برای مسائلی که با آن‌ها مواجه می‌شویم، طراحی کنیم.

تقسیم و حل

پارادایم تقسیم و حل یک رویکرد قدرتمند و گسترده‌ استفاده برای طراحی الگوریتم‌های کارآمد است. ایده اصلی این است که مسئله را به زیرمسائل کوچک‌تر تقسیم کنیم، این زیرمسائل را به صورت بازگشتی حل کنیم و سپس راه‌حل‌های آن‌ها را ترکیب کنیم تا مسئله اصلی را حل کنیم.

یک الگوریتم تقسیم و حل معمولی از سه مرحله تشکیل شده است:

1. تقسیم: اگر مسئله به اندازه کافی کوچک باشد که به طور مستقیم حل شود، آن را حل کنید. در غیر این صورت، مسئله را به زیرمسائل کوچک‌تر تقسیم کنید.
2. حل: به صورت بازگشتی هر زیرمسئله را حل کنید.
3. ترکیب: راه‌حل‌های زیرمسائل را ترکیب کنید تا راه‌حل مسئله اصلی را به دست آورید.

اثربخشی الگوریتم‌های تقسیم و حل از توانایی آن‌ها در کاهش اندازه مسئله به یک عامل ثابت در هر مرحله بازگشتی ناشی می‌شود. این اغلب منجر به الگوریتم‌هایی با زمان اجرای لگاریتمی یا چند لگاریتمی می‌شود.

مرتب‌سازی ادغامی: یک الگوریتم تقسیم و حل کلاسیک

یکی از مشهورترین مثال‌های یک الگوریتم تقسیم و حل، مرتب‌سازی ادغامی است که در فصل 2 به طور مفصل مورد بررسی قرار گرفت. به یاد داشته باشید که مرتب‌سازی ادغامی یک آرایه را با تقسیم آن به دو نیمه، مرتب‌سازی بازگشتی هر نیمه و سپس ادغام نیمه‌های مرتب‌شده حل می‌کند.

اینجا توصیف کلی از ماینجا ترجمه فارسی فایل مارک‌داون است:

الگوریتم مرج‌سورت:

function mergesort(array):
    # اگر طول آرایه کمتر یا مساوی 1 باشد، آرایه را برگردان
    if array.length <= 1:
        return array
    else:
        # محاسبه وسط آرایه
        mid = array.length / 2
        # تقسیم آرایه به دو نیمه چپ و راست
        left = mergesort(array[0:mid])
        right = mergesort(array[mid:])
        # ادغام دو نیمه مرتب‌شده
        return merge(left, right)

تابع merge دو آرایه مرتب‌شده را به یک آرایه مرتب‌شده واحد ادغام می‌کند:

function merge(left, right):
    # ایجاد آرایه نتیجه
    result = []
    # ادغام دو آرایه تا زمانی که یکی از آن‌ها خالی شود
    while left is not empty and right is not empty:
        # اگر عنصر اول آرایه چپ کوچک‌تر یا مساوی عنصر اول آرایه راست باشد
        if left[0] <= right[0]:
            # اضافه کردن عنصر اول آرایه چپ به آرایه نتیجه و حذف آن از آرایه چپ
            append left[0] to result
            remove left[0] from left
        else:
            # اضافه کردن عنصر اول آرایه راست به آرایه نتیجه و حذف آن از آرایه راست
            append right[0] to result
            remove right[0] from right
    # اضافه کردن عناصر باقی‌مانده در آرایه چپ به آرایه نتیجه
    append remaining elements of left to result
    # اضافه کردن عناصر باقی‌مانده در آرایه راست به آرایه نتیجه
    append remaining elements of right to result
    # برگرداندن آرایه نتیجه
    return result

استراتژی تقسیم و حل به مرج‌سورت امکان می‌دهد تا در بدترین حالت زمان اجرای O(n log n) را داشته باشد، که آن را به یکی از کارآمدترین الگوریتم‌های مرتب‌سازی عمومی تبدیل می‌کند.

قضیه استاد

زمان اجرای بسیاری از الگوریتم‌های تقسیم و حل را می‌توان با استفاده از قضیه استاد تحلیل کرد، که یک فرمول کلی برای رکوردهای به شکل زیر ارائه می‌دهد:

T(n) = aT(n/b) + f(n)

در اینجا، a تعداد تماس‌های رکورسیو، n/b اندازه هر زیرمسئله، و f(n) هزینه تقسیم مسئله و ترکیب نتایج است.

قضیه استاد بیان می‌کند که راه‌حل این رکورد به شرح زیر است:

1. اگر f(n) = O(n^(log_b(a) - ε)) برای مقداری ثابت ε > 0 باشد، آنگاه T(n) = Θ(n^log_b(a)).
2. اگر f(n) = Θ(n^log_b(a)) باشد، آنگاه T(n) = Θ(n^log_b(a) * log n).
3. اگر f(n) = Ω(n^(log_b(a) + ε)) برای مقداری ثابت ε > 0 باشد و اگر af(n/b) ≤ cf(n) برای مقداری ثابت c < 1 و تمام n بزرگ‌تر از یک مقدار باشد، آنگاه T(n) = Θ(f(n)).

برای مرج‌سورت، ما a = 2 (دو تماس رکورسیو)، b = 2 (هر زیرمسئله نصف اندازه اصلی است)، و f(n) = Θ(n) (مرحله ادغام زمان خطی دارد). از آنجایی که log_2(2) = 1، ما در مورد 2 قضیه استاد هستیم و زمان اجرا Θ(n log n) است.

سایر الگوریتم‌های تقسیم و حل

بسیاری از الگوریتم‌های دیگر نیز با استفاده از استراتژی تقسیم و حل پیاده‌سازی می‌شوند.اینجا ترجمه فارسی فایل مارک‌داون است. برای کد، فقط نظرات را ترجمه کرده‌ایم و خود کد را ترجمه نکرده‌ایم:

الگوریتم‌ها می‌توانند با استفاده از پارادایم تقسیم و حل طراحی شوند. برخی از نمونه‌های برجسته شامل موارد زیر است:

• مرتب‌سازی سریع: مانند مرتب‌سازی ادغامی، مرتب‌سازی سریع یک الگوریتم مرتب‌سازی تقسیم و حل است. این الگوریتم آرایه را حول یک عنصر محوری تقسیم می‌کند، زیرآرایه‌ها را به طور بازگشتی در سمت چپ و راست محور مرتب می‌کند و نتایج را ترکیب می‌کند.

• جستجوی دودویی: الگوریتم جستجوی دودویی برای یافتن یک عنصر در یک آرایه مرتب‌شده را می‌توان به عنوان یک الگوریتم تقسیم و حل در نظر گرفت. این الگوریتم مقدار هدف را با عنصر میانی آرایه مقایسه می‌کند و به طور بازگشتی در نیمه چپ یا راست جستجو می‌کند، بسته به نتیجه مقایسه.

• ضرب کاراتسوبا: این یک الگوریتم تقسیم و حل برای ضرب دو عدد n رقمی در زمان O(n^log_2(3)) ≈ O(n^1.585) است، که سریع‌تر از الگوریتم سنتی O(n^2) است.

• ضرب ماتریس استراسن: الگوریتم استراسن دو ماتریس n × n را در زمان O(n^log_2(7)) ≈ O(n^2.807) ضرب می‌کند، که بهتر از الگوریتم ساده O(n^3) است.

این مثال‌ها انعطاف‌پذیری و قدرت پارادایم تقسیم و حل را برای طراحی الگوریتم‌های کارآمد نشان می‌دهند.

الگوریتم‌های حریصانه

الگوریتم‌های حریصانه یک دسته از الگوریتم‌ها هستند که در هر مرحله بهترین گزینه محلی را انتخاب می‌کنند با امید به یافتن راه‌حل بهینه جهانی. این الگوریتم‌ها اغلب برای مسائل بهینه‌سازی استفاده می‌شوند که در آن راه‌حل به طور تدریجی با انجام یک سری انتخاب‌ها ساخته می‌شود، که هر کدام در آن لحظه بهترین به نظر می‌رسد.

ویژگی‌های کلیدی الگوریتم‌های حریصانه عبارتند از:

1. آنها در هر مرحله بهترین گزینه محلی را انتخاب می‌کنند، بدون نگرانی از پیامدهای آینده.
2. آنها فرض می‌کنند که یک انتخاب بهینه محلی منجر به یک راه‌حل بهینه جهانی خواهد شد.
3. آنها هرگز انتخاب‌های قبلی را مجدداً در نظر نمی‌گیرند.

الگوریتم‌های حریصانه اغلب ساده برای درک و پیاده‌سازی هستند و می‌توانند بسیار کارآمد باشند. با این حال، آنها همیشه راه‌حل بهینه را تولید نمی‌کنند، زیرا انتخاب‌های بهینه محلی ممکن است منجر به راه‌حل بهینه جهانی نشوند.

کدگذاری هافمن: یک الگوریتم حریصانه برای فشرده‌سازی داده

هافمناینجا ترجمه فارسی فایل مارک‌داون است:

کدنویسی، که در فصل ۵ با آن آشنا شدیم، الگوریتم حریص برای ساخت یک کد بهینه بدون پیشوند برای فشرده‌سازی داده است. این الگوریتم یک درخت دودویی را از پایین به بالا می‌سازد و به کاراکترهای با فراوانی بیشتر توالی‌های بیتی کوتاه‌تری اختصاص می‌دهد.

اینجا توصیف کلی از الگوریتم کدگذاری هافمن آمده است:

۱. یک گره برگ برای هر کاراکتر ایجاد کنید و آن را به یک صف اولویت اضافه کنید. ۲. تا زمانی که در صف بیش از یک گره وجود داشته باشد:

• دو گره با کمترین فراوانی را از صف حذف کنید.
• یک گره داخلی جدید با این دو گره به عنوان فرزندان و با فراوانی برابر با مجموع فراوانی دو گره ایجاد کنید.
• گره جدید را به صف اولویت اضافه کنید. ۳. گره باقی‌مانده ریشه درخت است و درخت کامل است.

انتخاب حریصانه ادغام دو گره با کمترین فراوانی است. این انتخاب بهینه محلی منجر به یک کد بهینه بدون پیشوند می‌شود.

اینجا مثالی از کدگذاری هافمن آمده است:

فرض کنید فراوانی کاراکترها به صورت زیر باشد:

d: 1
e: 1

درخت هافمن برای این مثال به صورت زیر است:

      (15)
     /    \
   (7)    (8)
   / \    / \
 (4) (3) (3) (5)
 /\  /\  /\  /\
A B  C D E

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

A: 00
B: 01
C: 10
D: 110
E: 111

بنابراین رشته اصلی "AAAABBBCCCDDDEEE" به صورت زیر کدگذاری می‌شود:

00000000010101101010110110110111111111

کدگذاری هافمن با اختصاص کدهای کوتاه‌تر به کاراکترهای با فراوانی بیشتر، فشرده‌سازی را انجام می‌دهد. کدها بدون پیشوند هستند، یعنی هیچ کدی پیشوند کد دیگری نیست، که امکان رمزگشایی بدون ابهام را فراهم می‌کند.

فشرده‌سازی LZW

فشرده‌سازی لمپل-زیو-ولچ (LZW) یک الگوریتم فشرده‌سازی مبتنی بر دیکشنری است که در حین فشرده‌سازی ورودی، دیکشنری (یا کتاب‌کد) از رشته‌ها را می‌سازد. LZW در ابزارهای فشرده‌سازی فایل گسترده استفاده می‌شود و در قالب تصویر GIF نیز استفاده شده است.

ایده کلیدی LZW جایگزینی رشته‌های کاراکتر با کدهای تک‌بیتی است. این الگوریتم ورودی را کاراکتر به کاراکتر می‌خواند و با جایگزینی هر رشته ثابت با یک کد، آن را به یک نمایش فشرده‌تر تبدیل می‌کند.اینجا ترجمه فارسی فایل مارک‌داون است. برای کد، فقط توضیحات را ترجمه کنید، کد را ترجمه نکنید:

کد متغیر-طول با کد متغیر-طول. هرچه رشته طولانی‌تر باشد، فضای بیشتری با رمزگذاری آن به عنوان یک عدد تک نگاشته می‌شود.

اینجا توضیح مرحله‌به‌مرحله نحوه کار فشرده‌سازی LZW:

1. فرهنگ لغت را با همه رشته‌های تک‌کاراکتری مقداردهی اولیه کنید.
2. طولانی‌ترین رشته W را در فرهنگ لغت که با ورودی کنونی مطابقت دارد، پیدا کنید.
3. شاخص فرهنگ لغت برای W را به خروجی ارسال کنید و W را از ورودی حذف کنید.
4. W را همراه با نماد بعدی در ورودی به فرهنگ لغت اضافه کنید.
5. به مرحله 2 بروید.

بیایید یک مثال را در نظر بگیریم. فرض کنید می‌خواهیم رشته "ABABABABA" را با استفاده از LZW فشرده کنیم.

1. فرهنگ لغت را با "A" و "B" مقداردهی اولیه کنید.
2. طولانی‌ترین تطبیق "A" است. شاخص آن (0) را ارسال کنید و آن را از ورودی حذف کنید. فرهنگ لغت اکنون شامل "A"، "B" و "AB" است.
3. طولانی‌ترین تطبیق "B" است. شاخص آن (1) را ارسال کنید و آن را از ورودی حذف کنید. فرهنگ لغت اکنون شامل "A"، "B"، "AB" و "BA" است.
4. طولانی‌ترین تطبیق "AB" است. شاخص آن (2) را ارسال کنید و آن را از ورودی حذف کنید. فرهنگ لغت اکنون شامل "A"، "B"، "AB"، "BA" و "ABA" است.
5. طولانی‌ترین تطبیق "ABA" است. شاخص آن (4) را ارسال کنید و آن را از ورودی حذف کنید. فرهنگ لغت اکنون شامل "A"، "B"، "AB"، "BA"، "ABA" و "ABAB" است.
6. طولانی‌ترین تطبیق "BA" است. شاخص آن (3) را ارسال کنید. ورودی اکنون خالی است.

بازنمایش فشرده "ABABABABA" بنابراین توالی شاخص‌ها[1] است که برای نمایش آن تعداد بیت‌های کمتری نیاز است تا نمایش اصلی ASCII.

بازگشایی فشرده‌سازی به همین شکل اما به صورت معکوس انجام می‌شود:

1. فرهنگ لغت را با همه رشته‌های تک‌کاراکتری مقداردهی اولیه کنید.
2. یک کد X را از ورودی بخوانید.
3. رشته مربوط به X را از فرهنگ لغت خروجی کنید.
4. اگر کد قبلی وجود داشته باشد، رشته قبلی را همراه با اولین کاراکتر رشته مربوط به X به فرهنگ لغت اضافه کنید.
5. به مرحله 2 بروید.

فشرده‌سازی LZW ساده و سریع است و برای بسیاری از کاربردها گزینه خوبی است. با این حال، محدودیت‌هایی نیز دارد. اندازه فرهنگ لغت می‌تواند بسیار بزرگ شود و مقدار قابل توجهی از حافظه را مصرف کند. همچنین،اگرچه این محدودیتها وجود دارد، LZW همچنان به عنوان یک الگوریتم فشرده‌سازی محبوب و موثر باقی می‌ماند، به ویژه برای کاربردهایی که سرعت از اهمیت بیشتری نسبت به رسیدن به بالاترین نسبت فشرده‌سازی ممکن برخوردار است.

نتیجه‌گیری

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

ما ابتدا به بحث در مورد مرتب‌سازی رشته‌ها پرداختیم، که الگوریتم‌های مرتب‌سازی بهینه‌شده‌ای هستند که از ویژگی‌های خاص رشته‌ها استفاده می‌کنند. شمارش کلیدی-شاخص‌دار، مرتب‌سازی رادیکس LSD و مرتب‌سازی رادیکس MSD روش‌های کارآمدی برای مرتب‌سازی رشته‌ها بر اساس کاراکترهای فردی آنها ارائه می‌دهند.

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

الگوریتم‌های جستجوی زیررشته، مانند الگوریتم‌های کنوت-موریس-پرات و بویر-مور، به ما امکان جستجوی کارآمد الگوها در رشته‌های بزرگ‌تر را می‌دهند. این الگوریتم‌ها کاربردهای متعددی در ویرایش متن، زیست‌شناسی محاسباتی و بازیابی اطلاعات دارند.

عبارات منظم راهی قدرتمند و انعطاف‌پذیر برای توصیف الگوهای رشته‌ای فراهم می‌کنند. ما نحوه پایه‌ای عبارات منظم و چگونگی استفاده از آنها برای تطبیق الگو و دستکاری رشته‌ها در زبان‌های برنامه‌نویسی و ابزارهای مختلف را بررسی کردیم.

در نهایت، به بررسی الگوریتم‌های فشرده‌سازی داده‌ها پرداختیم، که اندازه داده‌ها را با بهره‌گیری از افزونگی و الگوهای موجود در ورودی کاهش می‌دهند. ما به پوشش‌دهی طول‌دار، کدگذاری هافمن و فشرده‌سازی لمپل-زیو-ولچ پرداختیم، که هر کدام نقاط قوت و کاربردهای خاص خود را دارند.

درک این الگوریتم‌ها و ساختارهای داده‌ای پردازش رشته‌ای برای هر کسی که با داده‌های متنی کار می‌کند، حیاتی است.Here is the Persian translation of the provided markdown file, with the code comments translated:

کار با داده های متنی

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

# این تابع یک رشته را به عنوان ورودی دریافت می کند و تعداد کلمات آن را برمی گرداند
def word_count(text):
    words = text.split()
    return len(words)
 
# این تابع یک رشته را به عنوان ورودی دریافت می کند و تعداد کاراکترهای منحصر به فرد آن را برمی گرداند
def unique_chars(text):
    return len(set(text))
 
# این تابع یک رشته را به عنوان ورودی دریافت می کند و بسامد هر کلمه را برمی گرداند
def word_frequency(text):
    words = text.split()
    freq = {}
    for word in words:
        if word in freq:
            freq[word] += 1
        else:
            freq[word] = 1
    return freq
 
# این تابع یک رشته را به عنوان ورودی دریافت می کند و آن را به صورت معکوس برمی گرداند
def reverse_string(text):
    return text[::-1]