فصل 6: رشته‌ها در الگوریتم‌ها

ورودی:  ["dab", "cab", "fad", "bad", "dad", "ebb", "ace"]
خروجی: ["ace", "bad", "cab", "dab", "dad", "ebb", "fad"]

ورودی:  ["4PGC938", "2IYE230", "3CIO720", "1ICK750", "1OHV845", "4JZY524", "1ICK750", "3CIO720", "1OHV845", "1OHV845", "2RLA629", "2RLA629", "3ATW723"]
خروجی: ["1ICK750", "1ICK750", "1OHV845", "1OHV845", "1OHV845", "2IYE230", "2RLA629", "2RLA629", "3ATW723", "3CIO720", "3CIO720", "4JZY524", "4PGC938"]

ورودی:  ["she", "sells", "seashells", "by", "the", "sea", "shore", "the", "shells", "she", "sells", "are", "surely", "seashells"]
خروجی: ["are", "by", "sea", "seashells", "seashells", "sells", "sells", "she", "she", "shells", "shore", "surely", "the", "the"]

     (ریشه)
    /  |  \
   s   h   o
  / \     / \
 e   h   r   t
 |   |   |   |
 a   e   e   h
     |       |
     l       e
     |       |
     l       r
     |
     s

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

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

الگوی: "abracadabra"
خروجی: [13]

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

## عبارات منظم

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

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

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

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

- `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 است:

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

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

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

کدگذاری هافمن (Huffman Coding)
کدگذاری هافمن یک روش کدگذاری بهینه است که برای فشرده‌سازی داده‌ها استفاده می‌شود. این روش بر اساس فراوانی نمادها در داده‌های ورودی عمل می‌کند. نمادهای با فراوانی بیشتر به کدهای کوتاه‌تر و نمادهای با فراوانی کمتر به کدهای طولانی‌تر اختصاص داده می‌شوند.

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

پس از ساخت درخت، کد هر نماد با مسیر از ریشه به گره برگ مربوطه تعیین می‌شود، به طوری که شاخه چپ نماینده "0" و شاخه راست نماینده "1" است.

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

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

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

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

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

ایده اصلی 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] است که برای نمایش آن به تعداد کمتری بیت نیاز است.

فرآیند بازگشایی مشابه است، اما به صورت معکوس:

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

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

با وجود این محدودیت‌هااینجا ترجمه فارسی فایل مارک‌داون است. برای کد، فقط نظرات را ترجمه کنید، نه کد را.

## نتیجه‌گیری

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

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

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

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

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

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

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

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

```python
# این تابع یک رشته را به حروف بزرگ تبدیل می‌کند
def to_uppercase(text):
    return text.upper()

# این تابع یک رشته را به حروف کوچک تبدیل می‌کند
def to_lowercase(text):
    return text.lower()

# این تابع طول یک رشته را برمی‌گرداند
def get_length(text):
    return len(text)

# این تابع یک رشته را معکوس می‌کند
def reverse_string(text):
    return text[::-1]