ما هو تحويل فورييه السريع (FFT)؟ شرح مبسّط في سياق الخوارزميات وهياكل البيانات
إذا صادفتَ مصطلح Fast Fourier Transform (اختصارًا FFT) وأنت تدرس الخوارزميات وهياكل البيانات، فالجواب المباشر هو: FFT ليس مجرّد أداة في معالجة الإشارات، بل هو خوارزمية ذكية تحسب «تحويل فورييه المتقطّع» (DFT) بسرعة هائلة — بزمن قدره O(n log n) بدلًا من O(n²) الذي تحتاجه الطريقة المباشرة. وفي سياق علوم الحاسب تحديدًا، تشتهر هذه الخوارزمية بقدرتها على ضرب متعدّدات الحدود والأعداد الضخمة في زمن شبه خطّي، وهو ما يجعلها أداة أساسية في البرمجة التنافسية والحوسبة العلمية، لا في تحليل الصوت فقط كما قد يوحي التعريف الشائع.
أولًا: ما الفرق بين DFT و FFT؟
كثيرون يخلطون بين الاثنين. الفكرة بسيطة:
- DFT (تحويل فورييه المتقطّع) هو ماذا نريد حسابه: أخذ متتالية من n قيمة وتحويلها إلى n معامل ترددي.
- FFT هو كيف نحسبه بسرعة. إنه ليس تحويلًا مختلفًا، بل عائلة من الخوارزميات (أشهرها Cooley–Tukey) تعطي النتيجة نفسها تمامًا لكن بعدد عمليات أقل بكثير.
بعبارة أخرى: DFT سؤال، وFFT إجابة سريعة عليه.
| المعيار | الطريقة المباشرة (DFT) | تحويل فورييه السريع (FFT) |
|---|---|---|
| التعقيد الزمني | O(n²) | O(n log n) |
| الفكرة الجوهرية | حساب كل معامل على حدة | «فرّق تسُد» (تقسيم زوجي/فردي) |
| عند n = مليون | ~10¹² عملية | ~2×10⁷ عملية |
| شرط شائع | يعمل لأي n | الأمثل عندما n قوّة للعدد 2 |
| النتيجة | صحيحة | مطابِقة تمامًا لكن أسرع |
الفرق ليس تجميليًا: عند n كبيرة، الفارق بين O(n²) و O(n log n) هو الفرق بين برنامج يتجمّد وآخر ينتهي في أجزاء من الثانية.
كيف يعمل FFT؟ فكرة «فرّق تسُد»
جوهر خوارزمية Cooley–Tukey أنها تلاحظ أن حساب DFT لمتتالية طولها n يمكن تفكيكه إلى حسابين أصغر، ثم دمجهما بذكاء. الخطوات:
- جهّز المدخل: تأكد أن طول المتتالية قوّة للعدد 2 (مثل 8، 16، 1024)؛ وإن لم يكن، أضِف أصفارًا حتى أقرب قوّة (zero-padding).
- قسّم: افصل العناصر ذات المؤشرات الزوجية عن العناصر ذات المؤشرات الفردية، فتحصل على متتاليتين نصف الحجم.
- كرّر تعاوديًا: طبّق FFT على كل نصف على حدة (recursion) حتى تصل إلى متتاليات طول كل منها عنصر واحد.
- ادمج: أعِد تجميع النتائج باستخدام جذور الوحدة (roots of unity) عبر عملية تُسمّى «الفراشة» (butterfly)، وهي التي تُعيد استخدام كل حساب مرتين فتوفّر نصف العمل.
سرّ السرعة هنا: عمق التعاود هو log₂n مستوى، وكل مستوى يتطلب عملًا خطّيًا O(n)، فيصبح الإجمالي O(n log n).
لماذا يهمّ FFT في الخوارزميات وهياكل البيانات؟
هنا يكمن التطبيق الذي غالبًا ما يبحث عنه دارس علوم الحاسب، وهو مختلف عن تطبيقات الصوت والصورة:
- ضرب متعدّدات الحدود (Polynomial Multiplication): ضرب متعدّدَي حدود بالطريقة المدرسية يكلّف O(n²). أما مع FFT فنُقيّم كلًّا منهما عند نقاط محدّدة (تقييم)، نضرب القيم نقطة بنقطة O(n)، ثم نعيد بناء الناتج عبر FFT العكسي (interpolation). المحصّلة: O(n log n).
- ضرب الأعداد الضخمة: العدد الكبير ما هو إلا متعدّد حدود في أساس معيّن، لذا تُستخدم متغيّرات من FFT في مكتبات الأعداد الكبيرة لضرب أعداد بملايين الأرقام بكفاءة.
- التلافيف (Convolution) عمومًا: من مطابقة النصوص إلى الإحصاء والعدّ، أي مسألة تُصاغ على شكل التفاف يمكن تسريعها بـ FFT.
نصيحة عملية وخطأ شائع
عند التطبيق باستخدام الأعداد المركّبة وdouble، انتبه إلى أخطاء الدقة العائمة (floating-point)؛ فمع n كبيرة قد تنحرف النتائج قليلًا وتحتاج إلى تقريب. الحل الاحترافي في البرمجة التنافسية عندما تكون المعاملات أعدادًا صحيحة هو استخدام NTT (Number Theoretic Transform / تحويل فورييه العددي)، الذي يجري الحساب بحساب المقياس (modulo عدد أوّلي) فيعطي نتائج دقيقة تمامًا بلا أي خطأ عائم.
أما الخطأ الأكثر شيوعًا للمبتدئين فهو نسيان توسيع الحجم: لضرب متعدّدَي حدود، يجب أن يتّسع المصفوف لطول الناتج (تقريبًا ضعف الطول) وأن يكون قوّة للعدد 2، وإلا «التفّت» النتائج على بعضها وخرجت غلطًا.
الأسئلة الشائعة
هل FFT و DFT الشيء نفسه؟ لا. DFT هو التحويل الرياضي (الهدف)، وFFT هو خوارزمية سريعة لحسابه (الوسيلة). النتيجة متطابقة، لكن FFT أسرع بمراتب.
هل يجب أن يكون طول المدخل قوّة للعدد 2؟ النسخة الأبسط (radix-2) تشترط ذلك، والحل العملي إضافة أصفار حتى أقرب قوّة. توجد نسخ متقدّمة (mixed-radix وخوارزمية Bluestein) تعمل لأي طول.
ما الفرق بين FFT و NTT؟ كلاهما يحسب التحويل نفسه، لكن NTT يعمل بحساب المقياس على عدد أوّلي، فيتجنّب أخطاء الأعداد العائمة ويعطي نتائج صحيحة مضبوطة — وهو المفضّل للمعاملات الصحيحة.
أين أستفيد من FFT عمليًا؟ في تسريع ضرب متعدّدات الحدود، وضرب الأعداد الضخمة، وحساب التلافيف ومسائل العدّ في المسابقات، إضافة إلى معالجة الإشارات والصوت والصورة خارج نطاق الخوارزميات النظرية.