مقايضات المساحة والوقت
تستكشف هذه الوحدة تقنيات تصميم الخوارزميات التي تقايض المساحة (الذاكرة) بالوقت (السرعة)، مع التركيز على الفرز بالعد وخوارزميات مطابقة السلاسل النصية المتقدمة مثل Horspool و Boyer-Moore.
Space and Time Trade-Offs
This module explores algorithm design techniques that trade space (memory) for time (speed), focusing on counting sort and advanced string matching algorithms like Horspool and Boyer-Moore.
أهداف التعلم
- وصف مقايضات المساحة والوقت في تصميم الخوارزميات.
- التعبير عن خوارزمية الفرز بالعد وتطبيقها.
- إثبات وفهم تحسين المُدخلات في مطابقة السلاسل النصية.
- Describe Space and Time Trade-Offs.
- Express Sorting by Counting.
- Demonstrate Input Enhancement in String Matching.
1 مقايضات المساحة والوقت
1 Space-for-time Tradeoffs
استخدام ذاكرة إضافية لتسريع تنفيذ الخوارزمية، مثل حفظ إجابات مسبقة لتجنب إعادة حسابها.
Using extra memory to speed up algorithm execution, like memorizing answers to avoid recalculating.
في تصميم الخوارزميات، تعتبر مقايضة المساحة بالوقت تقنية شائعة جداً، وهي أكثر انتشاراً من مقايضة الوقت بالمساحة.
تنقسم هذه التقنية إلى نوعين رئيسيين: تحسين المُدخلات (Input Enhancement) حيث يتم معالجة المُدخلات مسبقاً لتخزين معلومات تُستخدم لاحقاً (مثل الفرز بالعد ومطابقة السلاسل)، والهيكلة المسبقة (Prestructuring) حيث يتم إعادة هيكلة المُدخلات لتسهيل الوصول إليها (مثل الجداول المجزأة Hashing وأشجار B-trees).
In algorithm design, trading space for time is a well-known and prevalent technique.
It has two principal varieties: Input Enhancement, which preprocesses the input to store info used later (e.g., counting sorts, string searching), and Prestructuring, which preprocesses the input to make accessing its elements easier (e.g., hashing, indexing schemes like B-trees).
الأساس النظري يعتمد على أن الذاكرة أصبحت رخيصة ومتاحة مقارنة بقوة المعالجة في بعض السياقات.
تحسين المُدخلات يركز على استخراج خصائص من البيانات (مثل جداول الإزاحة في السلاسل)، بينما الهيكلة المسبقة تغير بنية البيانات بالكامل لتغيير تعقيد البحث من خطي إلى لوغاريتمي أو ثابت.
The theoretical basis relies on memory being relatively cheap and abundant.
Input enhancement focuses on extracting properties from the data (like shift tables in strings), whereas prestructuring completely changes the data structure to alter search complexity from linear to logarithmic or constant time.
| Input Enhancement | Prestructuring | |
|---|---|---|
| الهدف الأساسيPrimary Goal | استخراج وتخزين معلومات إضافية من المُدخلاتExtract and store additional info from input | تغيير هيكل البيانات لتسهيل الوصولChange data structure to facilitate access |
| أمثلةExamples | الفرز بالعد، خوارزميات مطابقة السلاسلCounting sorts, String searching algorithms | الجداول المجزأة (Hashing)، أشجار BHashing, B-trees |
لماذا نفضل غالباً مقايضة المساحة بالوقت وليس العكس في الحوسبة الحديثة؟ Why do we often prefer trading space for time rather than time for space in modern computing?
لأن سعة الذاكرة (RAM) زادت بشكل هائل وأصبحت رخيصة، بينما يظل وقت استجابة المعالج وتجربة المستخدم (السرعة) هو العامل الحاسم في جودة البرمجيات.
Because memory (RAM) capacity has increased massively and become cheap, while processor response time and user experience (speed) remain the critical factors in software quality.
2 الفرز بالعد والمقارنة
2 Comparison-Counting Sort
خوارزمية فرز تقوم بحساب عدد العناصر الأصغر من كل عنصر لتحديد مكانه النهائي في المصفوفة المفرزة.
A sorting algorithm that counts the number of elements smaller than each element to determine its final position in the sorted array.
تطبيق لتقنية تحسين المُدخلات على مشكلة الفرز.
الفكرة هي: لكل عنصر في القائمة، نحسب إجمالي عدد العناصر الأصغر منه ونسجل النتائج في جدول (مصفوفة Count). هذه الأرقام تشير مباشرة إلى المواضع النهائية للعناصر في القائمة المفرزة.
بعد ذلك، ننسخ العناصر إلى مواضعها الصحيحة في مصفوفة جديدة.
An application of the input-enhancement technique to the sorting problem.
The idea is: for each element of a list, count the total number of elements smaller than this element and record the results in a table (Count array). These numbers indicate the positions of the elements in the sorted list.
Finally, copy the elements to their appropriate positions in a new, sorted list.
رغم بساطتها، إلا أن كفاءتها ليست مثالية. الخوارزمية تقوم بنفس عدد المقارنات التي يقوم بها الفرز بالاختيار (Selection Sort)، وهو O(n^2).
العيب الرئيسي هو أنها تتطلب مساحة إضافية خطية O(n) لتخزين مصفوفة العد والمصفوفة الناتجة، مما يجعلها غير مفضلة مقارنة بخوارزميات الفرز الموضعي (In-place) مثل QuickSort.
Despite its simplicity, its efficiency is not optimal. The algorithm makes the same number of key comparisons as Selection Sort, which is O(n^2).
The main drawback is that it requires a linear amount of extra space O(n) to store the count array and the output array, making it less favorable compared to in-place sorting algorithms like QuickSort.
ALGORITHM ComparisonCountingSort(A[0..n-1])
//Sorts an array by comparison counting
for i <- 0 to n-1 do Count[i] <- 0
for i <- 0 to n-2 do
for j <- i+1 to n-1 do
if A[i] < A[j]
Count[j] <- Count[j] + 1
else
Count[i] <- Count[i] + 1
for i <- 0 to n-1 do S[Count[i]] <- A[i]
return Sهل خوارزمية الفرز بالعد والمقارنة مستقرة (Stable)؟ Is the Comparison-Counting Sort algorithm stable?
في صيغتها الأساسية الموضحة، قد لا تكون مستقرة إذا لم يتم التعامل مع العناصر المتساوية بحذر (يجب تعديل الشرط لضمان الاستقرار).
In its basic form shown, it might not be stable unless equal elements are handled carefully (the condition needs adjustment to ensure stability).
3 مطابقة السلاسل بالقوة الغاشمة
3 String Searching by Brute Force
مقارنة النمط مع النص حرفاً بحرف من اليسار لليمين، وإزاحة النمط بمقدار حرف واحد عند كل عدم تطابق.
Comparing the pattern with the text character by character from left to right, shifting the pattern by one position upon mismatch.
خوارزمية القوة الغاشمة تقوم بمحاذاة النمط (Pattern) في بداية النص (Text). تتحرك من اليسار إلى اليمين وتقارن كل حرف.
إذا تطابقت كل الحروف، ينجح البحث. إذا حدث عدم تطابق، يتم إزاحة النمط بمقدار موضع واحد فقط إلى اليمين وتتكرر العملية.
The brute force algorithm aligns the pattern at the beginning of the text. It moves from left to right, comparing each character.
If all characters match, the search is successful. If a mismatch is detected, the pattern is shifted exactly one position to the right, and the process repeats.
هذه الطريقة لا تستفيد من أي معلومات تم اكتسابها خلال المقارنات السابقة.
التعقيد الزمني في أسوأ الحالات هو O(mn) حيث m هو طول النمط و n هو طول النص. يحدث هذا السيناريو الأسوأ عندما يتطابق النمط تقريباً في كل مرة حتى الحرف الأخير (مثل البحث عن 'AAAAB' في 'AAAAAAAAAB').
This method does not utilize any information gained during previous comparisons.
The worst-case time complexity is O(mn) where m is pattern length and n is text length. This worst-case scenario occurs when the pattern almost matches every time up to the last character (e.g., searching for 'AAAAB' in 'AAAAAAAAAB').
متى تكون خوارزمية القوة الغاشمة كافية ولا نحتاج لخوارزميات معقدة؟ When is the brute force algorithm sufficient, making complex algorithms unnecessary?
عندما يكون النمط قصيراً جداً، أو عندما تكون الأبجدية كبيرة جداً بحيث تكون احتمالية عدم التطابق في الحرف الأول عالية جداً، مما يجعل الأداء الفعلي قريباً من O(n).
When the pattern is very short, or when the alphabet is very large so the probability of mismatch on the first character is very high, making the practical performance close to O(n).
4 خوارزمية هورسبول
4 Horspool’s Algorithm
نسخة مبسطة من Boyer-Moore تقارن من اليمين لليسار وتستخدم جدول إزاحة واحد لتخطي عدة أحرف دفعة واحدة.
A simplified version of Boyer-Moore that compares right-to-left and uses a single shift table to skip multiple characters at once.
تعتمد خوارزمية هورسبول على تحسين المُدخلات من خلال المعالجة المسبقة للنمط لإنشاء جدول إزاحة (Shift Table).
تقارن الخوارزمية أحرف النمط مع النص من اليمين إلى اليسار. عند حدوث عدم تطابق، تحدد الخوارزمية مقدار الإزاحة بناءً على حرف النص (c) الذي تمت محاذاته مع آخر حرف في النمط، وذلك بالرجوع إلى جدول الإزاحة.
Horspool's algorithm relies on input enhancement by preprocessing the pattern to generate a shift table.
The algorithm compares pattern characters to the text from right to left. When a mismatch occurs, it determines the shift amount based on the text's character (c) aligned with the last character of the pattern, using the shift table.
هناك 4 حالات لتحديد الإزاحة:
- الحرف c غير موجود في النمط: إزاحة بطول النمط m.
- الحرف c موجود ولكن ليس الأخير: محاذاة أقصى ظهور له من اليمين.
- الحرف c هو الأخير ولا يوجد غيره: إزاحة بطول m.
- الحرف c هو الأخير ويوجد غيره: محاذاة أقصى ظهور له ضمن أول m-1 حرف.
هذا يجعل الخوارزمية سريعة جداً عملياً، رغم أن تعقيدها في أسوأ الحالات يظل O(mn).
There are 4 cases for shifting:
- c is not in pattern: shift by m.
- c is in pattern but not last: align its rightmost occurrence.
- c is last and no other occurrences: shift by m.
- c is last and has other occurrences: align rightmost occurrence among first m-1 characters.
This makes it very fast in practice, though worst-case is still O(mn).
ALGORITHM ShiftTable(P[0..m-1])
for i <- 0 to size-1 do Table[i] <- m
for j <- 0 to m-2 do Table[P[j]] <- m - 1 - j
return Table| Horspool's Algorithm | Boyer-Moore Algorithm | |
|---|---|---|
| عدد الجداول المستخدمةNumber of Tables Used | جدول واحد (الإزاحة / الرمز السيئ)One table (Shift / Bad-symbol) | جدولان (الرمز السيئ واللاحقة الجيدة)Two tables (Bad-symbol and Good-suffix) |
| التعقيد الزمني (أسوأ حالة)Worst-case Time Complexity | O(mn)O(mn) | O(n+m)O(n+m) |
لماذا نتجاهل الحرف الأخير عند بناء جدول الإزاحة في خوارزمية هورسبول؟ Why do we ignore the last character when building the shift table in Horspool's algorithm?
لأننا إذا قمنا بتضمين الحرف الأخير وكانت قيمته 0، فإن الخوارزمية قد تعلق في حلقة مفرغة (إزاحة بمقدار صفر) عند حدوث عدم تطابق في ذلك الحرف.
Because if we included the last character and its shift value became 0, the algorithm could get stuck in an infinite loop (shifting by zero) when a mismatch occurs on that character.
5 خوارزمية بوير-مور
5 Boyer-Moore Algorithm
خوارزمية مطابقة متقدمة تقارن من اليمين لليسار وتستخدم جدولين (الرمز السيئ واللاحقة الجيدة) لتحديد أقصى إزاحة ممكنة.
An advanced matching algorithm that compares right-to-left and uses two tables (bad-symbol and good-suffix) to determine the maximum possible shift.
تعتمد خوارزمية Boyer-Moore على فكرتين: مقارنة الأحرف من اليمين إلى اليسار، وحساب الإزاحة مسبقاً في جدولين.
جدول الرمز السيئ (Bad-symbol table) يحدد الإزاحة بناءً على حرف النص الذي تسبب في عدم التطابق.
جدول اللاحقة الجيدة (Good-suffix table) يحدد الإزاحة بناءً على الجزء الذي تطابق بنجاح من النمط (اللاحقة)، مستفيداً من البنية الدورية للنمط.
الخوارزمية تختار الإزاحة الأكبر بين الجدولين.
The Boyer-Moore algorithm is based on two ideas: comparing characters right to left, and precomputing shift sizes in two tables.
The bad-symbol table indicates how much to shift based on the text's character causing the mismatch.
The good-suffix table indicates how much to shift based on the matched part (suffix) of the pattern.
The algorithm shifts by the maximum value of the two.
قاعدة اللاحقة الجيدة d2(k) تبحث عن أقرب تكرار للاحقة المتطابقة داخل النمط نفسه، بشرط ألا يسبقها نفس الحرف الذي تسبب في الفشل.
إذا لم يوجد تكرار كامل، تبحث عن أطول بادئة (prefix) تتطابق مع نهاية اللاحقة.
التعقيد الزمني في أسوأ الحالات هو O(n+m)، مما يجعلها من أكفأ الخوارزميات نظرياً وعملياً.
The good-suffix rule d2(k) looks for the rightmost occurrence of the matched suffix within the pattern, provided it's not preceded by the same character that caused the mismatch.
If no such occurrence exists, it matches the longest prefix of the pattern with a suffix of the matched part.
The worst-case time complexity is O(n+m), making it highly efficient both theoretically and practically.
لماذا نأخذ القيمة القصوى (Max) بين إزاحة الرمز السيئ واللاحقة الجيدة بدلاً من جمعهما؟ Why do we take the maximum (Max) between the bad-symbol and good-suffix shifts instead of adding them?
لأن كلا الجدولين يقدمان ضماناً مستقلاً بأن النمط لن يتطابق في المسافات التي يتم تخطيها. أخذ القيمة القصوى يضمن أطول قفزة آمنة دون تفويت أي تطابق محتمل.
Because both tables provide an independent guarantee that the pattern will not match in the skipped distances. Taking the maximum ensures the longest safe jump without missing any potential match.