الفصل 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)، مما يشير إلى أن وقت التشغيل متناسب مع حجم المدخلات. هذا يعني أنه كلما زاد حجم المدخلات، سيزداد وقت التشغيل بنفس النسبة.هذا هو الترجمة العربية للملف:

حجم المدخلات يزداد، فإن وقت تشغيل الخوارزمية يزداد بحد أقصى خطي.

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

public static int sumOfSquares(int n) {
    // قم بتهيئة المجموع إلى 0
    int sum = 0;
    // قم بالتكرار من 1 إلى n
    for (int i = 1; i <= n; i++) {
        // قم بالتكرار من 1 إلى i
        for (int j = 1; j <= i; j++) {
            // أضف j إلى المجموع
            sum += j;
        }
    }
    // أرجع المجموع
    return sum;
}

وقت تشغيل هذه الدالة متناسب مع مربع N. بدقة، عدد المرات التي يتم فيها تنفيذ العبارة sum += j هو 1 + 2 + ... + N ~ N^2/2.

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

خوارزمية كنوث-موريس-برات

خوارزمية كنوث-موريس-برات (KMP) هي خوارزمية بحث فرعي فعالة تستخدم "دالة الفشل" مسبقة الحساب لتجنب المقارنات غير الضرورية.

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

فيما يلي مثال على خوارزمية KMP:

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

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

خوارزمية بويير-مور

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

الفكرة الرئيسية وراء بويير-مور هي استخدام دالتين مسبقتي الحساب: "السفيد الجيد"هذا هو الترجمة العربية للملف:

وظيفة "الحرف السيئ" وظيفة. تسمح لنا هذه الوظائف بالتخطي إلى الأمام في النص عندما نجد عدم تطابق، مشابه لـ KMP.

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

النص:    "abacadabrabracabracadabrabrabracad"
النمط: "abracadabra"
الإخراج:  [13]

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

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

ضغط البيانات

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

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

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

فيما يلي مثال على RLE:

المدخل:  "AAAABBBCCCDDDEEE"
المخرج: "4A3B3C3D3E"

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

ترميز هوفمان

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

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

بمجرد بناء الشجرة، يتم تحديد رمز كل رمز عن طريق المسار من الجذر إلىهذا هو الترجمة العربية للملف:

العقدة الورقية المقابلة، مع فرع أيسر يمثل "0" وفرع أيمن يمثل "1".

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

المدخل:  "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.

ضغط Lempel-Ziv-Welch (LZW)

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

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

فيما يلي وصف خطوة بخطوة لكيفية عمل ضغط LZW:

1. قم بتهيئة القاموس ليحتوي على جميع السلاسل ذات الحرف الواحد.
2. ابحث عن أطول سلسلة W في القاموس التي تطابق المدخل الحالي.
3. أرسل فهرس القاموس لـ W إلى الإخراج وأزل W من المدخل.
4. أضف W متبوعًا بالرمز التالي في المدخل إلى القاموس.
5. انتقل إلى الخطوة 2.

لنأخذ مثالاً. لنفترض أننا نريد ضغط السلسلة "ABABABABA" باستخدام LZW.

1. قم بتهيئة القاموس ليحتوي على "A" و"B".

2. أطول تطابق هو "A". أرسل فهرسههذا هو الترجمة العربية للملف المذكور:

3. أطول تطابق هو "B". أصدر فهرسه (0) وأزله من المدخل. القاموس الآن يحتوي على "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]، والذي يتطلب عددًا أقل من الأبت لتمثيله مقارنة بالتمثيل الأصلي بالأحرف الإنجليزية.

إعادة الفك تعمل بشكل مماثل، ولكن بالعكس:

1. قم بتهيئة القاموس بحيث يحتوي على جميع السلاسل ذات الحرف الواحد.
2. اقرأ رمزًا X من المدخل.
3. أخرج السلسلة لـ X من القاموس.
4. إذا كان الرمز السابق موجودًا، أضف السلسلة السابقة مع الحرف الأول من السلسلة لـ X إلى القاموس.
5. انتقل إلى الخطوة 2.

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

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

الخاتمة

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

بدأنا بمناقشة فرز النصوص، والتي هيهنا الترجمة العربية للملف:

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

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

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

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

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

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