الفصل 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]

خوارزمية KMP لها وقت تشغيل بمعدل O(n + m)، مما يجعلها أكثر كفاءة بكثير من النهج القائم على القوة البرية للنصوص والأنماط الكبيرة.

### خوارزمية Boyer-Moore

خوارزمية Boyer-Moore هي خوارزمية بحث فرعي أخرى فعالة تعمل عن طريق معالجة مسبقة لسلسلة النمط. على عكس KMP، والتي تبدأ المقارنات من بداية النمط، تبدأ Boyer-Moore من النهاية وتعمل للخلف.

الفكرة الرئيسية وراء Boyer-Moore هي استخدام وظيفتين محسوبتين مسبقًا: وظيفة "السفيرة الجيدة" ووظيفة "الحرف السيئ". تسمح هاتان الوظيفتان لنا بتخطي النص عندما نجد عدم تطابق، مشابه لـ KMP.

هنا مثال على خوارزمية Boyer-Moore:

النص: "abacadabrabracabracadabrabrabracad"
النمط: "abracadabra"
الناتج: [13]

تتميز Boyer-Moore بوقت تشغيل أفضل حالة بمعدل 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]` يطابق أي حرف صائت واحد.

التعبيرات النظامية مدعومة من قبل العديد من لغات البرمجة والأدوات، بما في ذلك Java و Python والأدوات النمطية في Unix مثل grep و sed. وهي مستخدمة على نطاق واسع لمهام مثل التحقق من صحة البيانات وتجهيز النصوص وتحليل السجلات.

## ضغط البيانات

ضغط البيانات هو عملية ترميز المعلومات باستخدام عدد أقل من البتات من التمثيل الأصلي. وهذا مفيد لتقليل متطلبات التخزين وأوقات الإرسال. هناك نوعان رئيسيان من الضغط: اللاخسارة والخسارة. يسمح الضغط اللاخسارة بإعادة بناء البيانات الأصلية بشكل كامل من البيانات المضغوطة، بينما يسمح الضغط الخسارة بفقدان بعض المعلومات مقابل نسب ضغط أكبر.

### ترميز طول التكرار

ترميز طول التكرار (RLE) هو تقنية ضغط لاخسارة بسيطة تستبدل التسلسلات المتكررة من الرموز المتطابقة (التكرارات) بنسخة واحدة من الرمز وعدد مرات تكراره.

إليك مثال على RLE:

RLE فعال للبيانات ذات التكرارات الطويلة، مثل الصور الرسومية البسيطة. ومع ذلك، يمكن أن يزيد حجم البيانات إذا كان هناك القليل من التكرارات أو لا يوجد منها.

### ترميز هوفمان

ترميز هوفمان هو خوارزمية ضغط لاخسارة تخصص رموزًا ذات أطوال متغيرة للرموز بناءً على تكرارهاهذا هو الترجمة العربية للملف:

ترميز هافمان (Huffman Coding)

ترميز هافمان هو تقنية ضغط بيانات تستخدم تكرار الرموز في البيانات المدخلة. الرموز الأكثر تكرارًا يتم تعيين رموز أقصر لها، بينما الرموز الأقل تكرارًا يتم تعيين رموز أطول لها.

يعمل الخوارزمية من خلال بناء شجرة ثنائية، تُسمى شجرة هافمان، من الأسفل إلى الأعلى. كل عقدة ورقية تمثل رمزًا وتكراره، بينما كل عقدة داخلية تمثل مجموع تكرارات أطفالها. يتم بناء الشجرة من خلال دمج العقدتين ذات أقل التكرارات حتى يتبقى عقدة واحدة فقط.

بمجرد بناء الشجرة، يتم تحديد رمز كل رمز عن طريق المسار من الجذر إلى العقدة الورقية المقابلة، حيث يمثل الفرع الأيسر "0" والفرع الأيمن "1".

هنا مثال على ترميز هافمان:

في هذا المثال، تم تعيين الرمز "00" للحرف "A"، والرمز "01" للحرف "B"، والرمز "10" للحرف "C"، والرمز "110" للحرف "D"، والرمز "111" للحرف "E". يتم الحصول على الناتج المضغوط عن طريق استبدال كل رمز في المدخل بالرمز المقابل له.

ترميز هافمان هو رمز بادئة مثالي، مما يعني أن أي رمز ليس بادئة لأي رمز آخر. هذا يسمح بفك ترميز البيانات المضغوطة بشكل واضح. يُستخدم ترميز هافمان على نطاق واسع في تنسيقات الملفات وأدوات الضغط المختلفة، مثل JPEG و MP3 و ZIP.

### ضغط LZW

ضغط Lempel-Ziv-Welch (LZW) هو خوارزمية ضغط قائمة على القاموس تبني قاموسًا (أو دفتر الرموز) من السلاسل أثناء ضغط المدخل. يُستخدم LZW على نطاق واسع في أدوات ضغط الملفات وتم استخدامه في تنسيق صور GIF.

الفكرة الرئيسية وراء LZW هي استبدال سلاسل الأحرف بأكواد فردية. إنه يقرأ سلسلة المدخل حرفًا تلو الآخر ويرمز السلسلة إلى تمثيل مضغوط عن طريق استبدال كل رمز ثابت الطول برمز متغير الطول. كلما كانت السلسلة أطول، كلما تم توفير المزيد من المساحة عن طريق ترميزها كرقم واحد.

هنا مثال علىهذا هو الترجمة العربية للملف:

خطوات شرح كيفية عمل ضغط LZW:

1. قم بتهيئة القاموس ليحتوي على جميع السلاسل ذات الحرف الواحد.
2. ابحث عن أطول سلسلة W في القاموس التي تتطابق مع الإدخال الحالي.
3. أرسل فهرس القاموس لـ 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 بسيط وسريع، مما يجعله خيارًا جيدًا لكثير من التطبيقات. ومع ذلك، فإنه لديه بعض القيود. يمكن أن ينمو حجم القاموس بشكل كبير، مما يستهلك كمية كبيرة من الذاكرة. بالإضافة إلى ذلك، يتم إعادة تعيين القاموس بعد كل كتلة من الإدخال، مما قد يقلل من نسبة الضغط للملفات الصغيرة.

على الرغم من هذه القيودهنا هو الترجمة العربية لهذا الملف:

## الخاتمة

في هذا الفصل، استكشفنا العديد من خوارزميات معالجة السلاسل المهمة، بما في ذلك فرز السلاسل، والمحاولات، والبحث عن السلاسل الفرعية، والتعبيرات النظامية، والضغط البيانات. تشكل هذه الخوارزميات أساس العديد من التطبيقات الحقيقية وهي أدوات أساسية لأي مبرمج يعمل مع البيانات النصية.

بدأنا بمناقشة فرز السلاسل، وهي خوارزميات فرز محسّنة تستفيد من الخصائص الخاصة للسلاسل. توفر العد المفتاحي المؤشر، وفرز القاعدة الأقل داخليًا، وفرز القاعدة الأكثر داخليًا طرقًا فعالة لفرز السلاسل على أساس أحرفها الفردية.

بعد ذلك، فحصنا المحاولات، وهي بنية بيانات شجرية لتخزين واسترجاع السلاسل. تمكّن المحاولات من المطابقة السريعة للبادئات وتستخدم بشكل شائع في تطبيقات مثل الإكمال التلقائي وجداول توجيه بروتوكول الإنترنت.

تسمح خوارزميات البحث عن السلاسل الفرعية، مثل خوارزميات كنوث-موريس-برات وبويير-مور، بالبحث الفعال عن الأنماط داخل السلاسل الأكبر. لهذه الخوارزميات العديد من التطبيقات في تحرير النصوص والبيولوجيا الحاسوبية واسترجاع المعلومات.

توفر التعبيرات النظامية طريقة قوية ومرنة لوصف أنماط السلاسل. ناقشنا البناء الأساسي للتعبيرات النظامية وكيفية استخدامها لمطابقة الأنماط والتلاعب بالسلاسل في مختلف لغات البرمجة والأدوات.

أخيرًا، استكشفنا خوارزميات ضغط البيانات، والتي تقلل من حجم البيانات من خلال استغلال التكرار والأنماط داخل المدخلات. غطينا ترميز طول التكرار، وترميز هوفمان، وضغط ليمبل-زيف-ويلش، حيث لكل منها نقاط قوة وتطبيقات خاصة به.

فهم هذه الخوارزميات وهياكل البيانات لمعالجة السلاسل أمر حاسم لأي شخص يعمل مع البيانات النصية. مع استمرار نمو كمية البيانات غير المهيكلة، تصبح القدرة على التلاعب والبحث والضغط بكفاءة أمرًا بالغ الأهمية.Here is the Arabic translation of the provided text, with the code comments translated:

الضغط على السلاسل سيصبح أكثر قيمة. من خلال إتقان التقنيات المغطاة في هذا الفصل، ستكون مجهزًا جيدًا للتعامل مع مجموعة واسعة من تحديات معالجة السلاسل في مشاريعك وتطبيقاتك الخاصة.

# String Manipulation

```python
# This function takes a string as input and returns the reverse of that string
def reverse_string(input_string):
    return input_string[::-1]

# This function takes a string as input and returns the string with all characters in uppercase
def to_uppercase(input_string):
    return input_string.upper()

# This function takes a string as input and returns the string with all characters in lowercase
def to_lowercase(input_string):
    return input_string.lower()

# This function takes a string as input and returns the string with the first character of each word capitalized
def capitalize_words(input_string):
    return input_string.title()

# This function takes a string as input and returns the string with all occurrences of a specified character replaced with another character
def replace_character(input_string, old_char, new_char):
    return input_string.replace(old_char, new_char)

# This function takes a string as input and returns the length of the string
def get_length(input_string):
    return len(input_string)

# This function takes a string as input and returns a list of all the words in the string
def split_string(input_string):
    return input_string.split()

# This function takes a list of strings as input and returns a single string with all the strings concatenated
def join_strings(string_list):
    return ' '.join(string_list)