ما معنى FFT (تحويل فورييه السريع) في الخوارزميات وهياكل البيانات؟
اختصار FFT يعني Fast Fourier Transform، أي «تحويل فورييه السريع». وهو ليس شيئًا جديدًا مختلفًا عن تحويل فورييه، بل هو خوارزمية ذكية تحسب «تحويل فورييه المنفصل» (DFT) بسرعة أكبر بكثير. الفكرة باختصار: بدل أن تحسب الناتج بطريقة مباشرة تكلّفك زمنًا يتناسب مع n² عملية، يعيد الـ FFT ترتيب الحساب ليصبح بزمن يتناسب مع n log n فقط. هذا الفارق هو كل السر، ولهذا كلمة «Fast» في الاسم.
إذا وصلت إلى هذه الصفحة من درس في الخوارزميات وهياكل البيانات (وليس من مادة معالجة الإشارات)، فالأرجح أنك تريد فهم شيء عملي واحد: كيف يساعدنا الـ FFT على ضرب كثيرات الحدود والأعداد الضخمة بسرعة. هذا هو الاستخدام الأشهر له في هذا المجال، وسنركّز عليه هنا.
ما الفرق بين DFT و FFT؟
كثيرون يخلطون بينهما، والتوضيح مهم:
- DFT (Discrete Fourier Transform) هو التعريف الرياضي: العملية التي تحوّل متتالية من الأرقام إلى مكوّناتها الترددية.
- FFT هو الخوارزمية التي تنفّذ هذه العملية بكفاءة.
بعبارة أخرى: DFT يخبرك ماذا تحسب، و FFT يخبرك كيف تحسبه بسرعة. النتيجة الرياضية واحدة تمامًا، لكن التكلفة الزمنية مختلفة جذريًا.
| المقارنة | الحساب المباشر لـ DFT | خوارزمية FFT |
|---|---|---|
| التعقيد الزمني | O(n²) | O(n log n) |
| المبدأ | جمع مباشر لكل حد | فرِّق تسُد (Divide & Conquer) |
| مناسب لـ | مدخلات صغيرة جدًا | مدخلات كبيرة وتطبيقات الزمن الحقيقي |
| الأشهر تطبيقًا | نادرًا ما يُستخدم مباشرة | الخيار الافتراضي عمليًا |
لتقريب الفارق: عند n = مليون عنصر، الطريقة المباشرة تحتاج نحو ألف مليار عملية، بينما FFT يحتاج نحو 20 مليون فقط. هنا يتحوّل حساب «مستحيل عمليًا» إلى حساب يتم في أجزاء من الثانية.
لماذا يُسمّى «سريعًا»؟ فكرة فرِّق تسُد
يعتمد الـ FFT على حيلة أنيقة: يقسم المتتالية إلى نصفين (عناصر المواقع الزوجية، وعناصر المواقع الفردية)، يحسب تحويل كل نصف على حدة، ثم يدمج النتيجتين. لأن كل مستوى من التقسيم يضاعف عدد الأجزاء ويُنصّف حجمها، يصبح عدد المستويات log n، وفي كل مستوى نقوم بعمل يتناسب مع n. حاصل الضرب هو n log n.
الصيغة الأشهر لهذه الفكرة تُعرف باسم خوارزمية Cooley–Tukey، وهي التي تجدها في معظم المكتبات والكتب. وهي تعمل بأبسط صورها عندما يكون طول المدخل قوة للعدد 2 (مثل 8، 16، 1024)، ولهذا كثيرًا ما «نُكمّل» المدخلات بأصفار حتى يصل طولها إلى أقرب قوة للعدد 2.
أهم استخدام في الخوارزميات: ضرب كثيرات الحدود
هذا هو الجزء الذي يهم طلاب الخوارزميات والمشاركين في المسابقات البرمجية:
- ضرب كثيري حدود بالطريقة المدرسية (كل حد في كل حد) يكلّف O(n²).
- لكن يمكن تمثيل كثير الحدود بـ قيمه عند نقاط محددة بدل معاملاته.
- في تمثيل القيم، يصبح الضرب مجرد ضرب نقطة بنقطة، أي O(n).
- الـ FFT هو الأداة التي تنقلنا بسرعة بين تمثيل المعاملات وتمثيل القيم (والعكس عبر ما يُسمى Inverse FFT).
النتيجة النهائية: ضرب كثيري حدود في زمن O(n log n) بدل O(n²). وبما أن ضرب الأعداد الصحيحة الضخمة ليس إلا ضرب كثيرات حدود (كل رقم هو معامل)، فإن المكتبات التي تتعامل مع أعداد بمئات الآلاف من الخانات تعتمد على الـ FFT أو أقاربه.
ملاحظة عملية مهمة: في المسابقات البرمجية حيث المعاملات أعداد صحيحة، كثيرًا ما يُفضَّل استخدام NTT (Number Theoretic Transform) بدل FFT العادي. السبب أن FFT يستخدم أعدادًا مركّبة وأرقامًا عشرية، وهذا يسبب أخطاء تقريب قد تُفسد النتيجة عند الأعداد الكبيرة. أما NTT فيعمل بحساب المقياس (modular arithmetic) ويعطي نتائج صحيحة تمامًا بلا أي خطأ عشري.
خطأ شائع يقع فيه المبتدئون
الخطأ الأكثر تكرارًا هو نسيان حجز طول كافٍ للناتج. عند ضرب كثيري حدود بدرجتين a و b، تكون درجة الناتج a + b، ويجب أن يكون طول المصفوفة المستخدمة في الـ FFT أكبر من مجموع الطولين (ثم يُقرَّب لأعلى إلى قوة للعدد 2). إن نسيت ذلك، «تلتفّ» المعاملات على بعضها (ظاهرة تُسمى الالتفاف الدائري) وتحصل على نتيجة خاطئة يصعب تفسيرها.
الأسئلة الشائعة
هل FFT و DFT شيء واحد؟ لا تمامًا. DFT هو العملية الرياضية المطلوبة، و FFT خوارزمية سريعة لتنفيذها. النتيجة واحدة، لكن FFT أسرع بكثير من الحساب المباشر لـ DFT.
متى أستخدم FFT في مسألة برمجية؟ عندما تحتاج إلى ضرب كثيرات حدود أو أعداد ضخمة، أو حساب «الالتفاف» (convolution) بين متتاليتين طويلتين. إن كانت المدخلات صغيرة (بضع عشرات)، فالطريقة المباشرة O(n²) أبسط وأسرع في التنفيذ ولا داعي لتعقيد الأمور.
لماذا يعطيني FFT نتائج بأرقام عشرية غريبة؟ لأنه يعمل بأعداد مركّبة وحسابات عشرية عائمة، فتظهر أخطاء تقريب صغيرة. عند الأعداد الصحيحة، قرِّب الناتج لأقرب عدد صحيح، أو استخدم NTT لتجنّب المشكلة من أساسها.
هل أحتاج إلى كتابة FFT من الصفر؟ للتعلّم، نعم، فكتابته مرة تُرسّخ الفكرة. أما في الاستخدام العملي، فمعظم اللغات توفّر مكتبات جاهزة ومُحسَّنة (مثل مكتبات الحساب العلمي)، والأفضل الاعتماد عليها في المشاريع الحقيقية.