معجزة يونكس سبيل: التشغيل في 64 كيلوبايت من ذاكرة الوصول العشوائي
2025-01-19
في السبعينيات، واجه مُصحح الأخطاء الإملائية في يونكس تحديًا لا يُصدق: وهو وضع قاموس بحجم 250 كيلوبايت في 64 كيلوبايت فقط من ذاكرة الوصول العشوائي على جهاز كمبيوتر PDP-11. تضمنت الحلول المبتكرة من دوجلاس ماكيلروي نهجًا متعدد المراحل. في البداية، قدم مُرشح بلوم عمليات بحث سريعة، ولكن مع نمو القاموس، طور مخططًا جديدًا لضغط الهاش. من خلال إدراك أن الاختلافات بين رموز الهاش المُرتبة تتبع توزيعًا هندسيًا، واستخدام ترميز جولومب، حقق حدود ضغط قريبة من النظرية. وأخيرًا، قام بتقسيم البيانات المضغوطة لتحسين سرعة البحث أكثر. هذه القصة تُعد دراسة رئيسية في التحسين المقيد، حيث تُظهر كيف يمكن أن تتغلب الخوارزميات الذكية على القيود التي تبدو مستحيلة.