فصل 8: تکنیک‌های تحلیل الگوریتم

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

مدل‌های ریاضی و تحلیل

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

نوتاسیون بزرگ-او

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

در نوتاسیون بزرگ-او، عملکرد یک الگوریتم را به صورت تابعی از اندازه ورودی، که معمولاً با n نشان داده می‌شود، بیان می‌کنیم. به عنوان مثال، در تابع ساده زیر که مجموع n عدد مثبت اول را محاسبه می‌کند:

public static int sum(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

زمان اجرای این تابع به طور خطی با اندازه ورودی n افزایش می‌یابد. می‌توانیم این موضوع را با استفاده از نوتاسیون بزرگ-او به صورت O(n) بیان کنیم، که نشان می‌دهد زمان اجرا متناسب با اندازه ورودی است. این بدان معنی است که با افزایش اندازه ورودی، زمان اجرا نیز به همان نسبت افزایش می‌یابد.فایل مارک‌داون را به فارسی ترجمه کنید. برای کد، کامنت‌ها را ترجمه کنید، اما کد را ترجمه نکنید. اینجا فایل است:

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

نوتاسیون بزرگ-او به ما اجازه می‌دهد که عوامل ثابت و جملات مرتبه پایین‌تر را نادیده بگیریم و بر روی جمله غالب که نرخ رشد تابع را تعیین می‌کند، تمرکز کنیم. به عنوان مثال، به تابع زیر توجه کنید:

// این تابع مجموع مربع‌های اعداد از 1 تا n را محاسبه می‌کند
public static int sumOfSquares(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            sum += j;
        }
    }
    return sum;
}

زمان اجرای این تابع متناسب با مربع n است. به طور دقیق‌تر، تعداد دفعاتی که عبارت sum += j اجرا می‌شود، 1 + 2 + ... + N ~ N^2/2 است.

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

الگوریتم کنوت-موریس-پرات

الگوریتم کنوت-موریس-پرات (KMP) یک الگوریتم کارآمد برای جستجوی زیرشنی است که از یک "تابع شکست" پیش‌محاسبه‌شده استفاده می‌کند تا مقایسه‌های غیرضروری را اجتناب کند.

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

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

متن:    "abacadabrabracabracadabrabrabracad"
الگو: "abracadabra"
خروجی:  [13]

الگوریتم KMP زمان اجرای O(n + m) دارد، که آن را در مقایسه با روش پرزور بسیار کارآمدتر می‌کند.

الگوریتم بویر-مور

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

ایده کلیدی پشت بویر-مور استفاده از دو تابع پیش‌محاسبه‌شده است: "پسوند خوب"اینجا ترجمه فارسی فایل مارک‌داون است:

توابع "بد کاراکتر" و "بد کاراکتر". این توابع به ما امکان می‌دهند که در متن جلو برویم هنگامی که یک عدم تطابق پیدا می‌کنیم، مشابه با KMP.

اینجا مثالی از الگوریتم بویر-مور است:

متن:    "abacadabrabracabracadabrabrabracad"
الگو: "abracadabra"
خروجی:  [13]

بویر-مور بهترین حالت اجرای O(n/m) و بدترین حالت اجرای O(n * m) را دارد، اما در عمل، اغلب سریع‌ترین الگوریتم جستجوی زیرشاخه برای الفبای بزرگ است.

عبارات منظم

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

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

• . (نقطه) هر کاراکتر تک را تطابق می‌دهد.
• * (ستاره) صفر یا بیشتر تکرار کاراکتر یا گروه قبلی را تطابق می‌دهد.
• + (پلاس) یک یا بیشتر تکرار کاراکتر یا گروه قبلی را تطابق می‌دهد.
• ? (علامت سوال) صفر یا یک تکرار کاراکتر یا گروه قبلی را تطابق می‌دهد.
• ^ (کاشت) ابتدای خط را تطابق می‌دهد.
• $ (دلار) انتهای خط را تطابق می‌دهد.
• [] (کروشه) یک کلاس کاراکتر را تعریف می‌کند، که هر کاراکتر تک درون کروشه را تطابق می‌دهد.

اینجا چند مثال از عبارات منظم و الگوهایی که آنها تطابق می‌دهند آورده شده است:

• a.b هر رشته سه کاراکتری که با "a" شروع و با "b" پایان می‌یابد را تطابق می‌دهد، مانند "acb"، "a5b" یا "a b".

• a*b هر رشته‌ای که از صفر یا بیشتر کاراکتر "a" تشکیل شده و سپس یک "b" دارد را تطابق می‌دهد، مانند "b"، "ab"، "aab" یا "aaab".

• a+b هر رشته‌ای که از یک یا بیشتر کاراکتر "a" تشکیل شده و سپس یک "b" دارد را تطابق می‌دهد، مانند "ab"، "aab" یا "aaab"، اما نه "b".

• a?b یا "ab" یا "b" را تطابق می‌دهد.

• ^a هر رشته‌ای که با "a" شروع می‌شود را تطابق می‌دهد.اینجا ترجمه فارسی فایل مارک‌داون داده شده است. برای کد، فقط توضیحات را ترجمه کرده‌ایم و خود کد را تغییر ندادیم.

• a$ با هر رشته‌ای که با "a" پایان می‌یابد مطابقت دارد.

• [aeiou] با هر کاراکتر مصوت تک‌فردی مطابقت دارد.

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

فشرده‌سازی داده

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

رمزگذاری طول دنباله

رمزگذاری طول دنباله (RLE) یک تکنیک ساده فشرده‌سازی بدون‌تلفات است که دنباله‌های تکراری از نمادهای یکسان (دنباله‌ها) را با یک نمونه تک از نماد و شمارش تعداد دفعات تکرار آن جایگزین می‌کند.

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

ورودی:  "AAAABBBCCCDDDEEE"
خروجی: "4A3B3C3D3E"

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

کدگذاری هافمن

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

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

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

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

ورودی:  "AAAABBBCCCDDDEEE"
خروجی: "000010011001011100101"

درخت هافمن:
      (15)
     /    \
   (7)    (8)
   / \    / \
 (4) (3) (3) (5)
 /\  /\  /\  /\
A B  C D E

در این مثال، "A" به کد "00"، "B" به کد "01"، "C" به کد "10"، "D" به کد "110" و "E" به کد "111" اختصاص داده شده است. خروجی فشرده‌سازی‌شده با جایگزین کردن هر نماد در ورودی با کد مربوطه به دست می‌آید.

کدگذاری هافمن یک کد پیشوندی بهینه است، به این معنی که هیچ کدی پیشوند کد دیگری نیست. این امکان رمزگشایی بدون ابهام از داده‌های فشرده‌شده را فراهم می‌کند. کدگذاری هافمن در قالب‌های فایل و ابزارهای فشرده‌سازی مختلف مانند JPEG، MP3 و ZIP گسترده استفاده می‌شود.

فشرده‌سازی لمپل-زیو-ولچ (LZW)

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

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

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

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

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

1. دیکشنری را با "A" و "B" مقداردهی اولیه کنید.

2. طولانی‌ترین مطابقت "A" است. شاخص آن را به خروجی ارسال کنید و آن را از ورودی حذف کنید.اینجا ترجمه فارسی فایل مارک‌داون است. برای کد، فقط نظرات را ترجمه کنید، کد را ترجمه نکنید:

3. بلندترین تطابق "B" است. شاخص آن (1) را خروجی دهید و آن را از ورودی حذف کنید. دیکشنری اکنون شامل "A"، "B" و "AB" است.

4. بلندترین تطابق "B" است. شاخص آن (1) را خروجی دهید و آن را از ورودی حذف کنید. دیکشنری اکنون شامل "A"، "B"، "AB" و "BA" است.

5. بلندترین تطابق "AB" است. شاخص آن (2) را خروجی دهید و آن را از ورودی حذف کنید. دیکشنری اکنون شامل "A"، "B"، "AB"، "BA" و "ABA" است.

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

7. بلندترین تطابق "BA" است. شاخص آن (3) را خروجی دهید. ورودی اکنون خالی است.

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

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

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

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

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

نتیجه‌گیری

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

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

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

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

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

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

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

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