شرایط اینگونه است: سال ۱۹۸۴ میلادی است، وظیفه نوشتن یک Spellchecker برای یک نرمافزار Word proccessor در سیستمعامل MS-DOS به شما سپرده شده است، بعضی از کاربران و نه همه آنها ۶۴۰ کیلوبایت رم در کامپیوترهایشان دارند. شما باید سیستمهای با رم کمتر یعنی با کمتر از ۲۵۶ کیلوبایت رم را نیز ساپورت کنید، این یعنی با یک چهارم یک مگابایت یک نرمافزار ویرایش متن، محتوای در حال ویرایش و حافظه مورد نیاز برای سیستم عامل را تامین کنید. و البته که spellchecker!
برای مقایسه در مک بوک من، دیشکنری استاندار مورد استفاده برای غلطیابی در سیستم عامل در مسیر usr/share/dict/words
که شامل ۲۳۵٬۸۸۶ کلمه است دارای حجم ۲٬۴۹۳٬۱۰۹ بایت میباشد.
یکی از اولین و جذابترین راهحلهایی که به ذهن هر کسی میرسید پیدا کردن فرمتی بود که نسبت به متن خام فشردهتر باشد. دیکشنری UNIX برای مثال هم شامل stop هست هم شامل stopped و هم شامل stopping، بنابراین تعداد زیادی تکرار قابل حذف در اینجا داریم، شاید با پیادهسازی هوشمندانه یک trie بتوان این تریک را انجام داد... عاما! ما نیاز به کاهش حجم خیلی زیادی داشتیم که از بیشتر از دو مگابایت به چندصد کیلوبایت برسیم.
در حقیقت اگر ما بتوانیم هر کلمه را در دیکشنری غلطیاب را در صرفا یک بایت ذخیره کنیم، ما تقریبا به همه ۲۵۶ کیلوبایت رم یک کامپیوتر برای صرفا کار کردن غلط یاب نیاز داریم، و البته آدرسدهی هر کلمه با یک بایت امکانپذیر نخواهد بود. بنابراین نه تنها نگهداری کل دیکشنری در رم ناامیدکننده است بلکه نگهداشتن دیکشنری در دیسک و صرفا نگه داشتن یک فهرست (ایندکس) در رم هم به راهحل به درنخوری است.
میتوان بخشی از دیکشنری شامل کلمات مهم را انتخاب کرد و با فشردهسازی سنگین آن را در بخش کوچکی از حافظه نگه داشت، سپس روش کندتر و مبتنی بر دیسک (هارد دیسک و ...) برای جستجو در بقیه دیکشنری که در رم نیست را پیاده سازی کرد. یا شاید بتوان یک روش کاملا مبتنی بر دیسک با استفاده از یک دیتابیس اختصاصی را انتخاب کرد. (یاداوری: در سال دهه ۸۰ میلادی نمیتوان انتظار داشت هر کامپیوتری هارد دیسک داشته باشد، بنابراین دیکشنری هنوز باید بتواند در یک فلاپی ۳۶۰ کیلوبایتی جا بگیرد!)
به غیر از چالش پیاده سازی صرف ما نیاز داشتیم امکاناتی نظیر اضافه کردن کلمه جدید به دیکشنری توسط کاربر را نیز پیاده سازی میکردیم!
بله نوشتن یک غلطیاب در اواسط دهه هشتاد میلادی یک مسئله به شدت مشکل بود. برنامهنویسها برای حل چالش غلطیاب در آن دوران چندین روش فشرده سازی داده چشمگیر ارائه دادند. به همین ترتیب تعدادی ساختار داده (Data Structure) بسیار هوشمندانه برای یافتن سریع کلمات در یک فرهنگ لغت فشرده وجود داشت. این مشکلی بود که ممکن است حتی با تمرکز بالا هم ماهها طول بکشد تا بتوان برای حل آن تلاش کرد. (و برای مثال ، کاهش اندازه فرهنگ لغت از 200،000 به 50،000 یا حتی 20،000 کلمه ای گزینه معقولی بود ، اما حتی این کار کمک چندانی به حل این چالش نمیکرد و مشکلات قبلی پابرجا بود.)
امروز اما نوشتن برنامهای برای لود کردن usr/share/dict/words
در یک هشتیبل دو یا سه خط کد به زبان پایتون یا پرل یا ... میباشد. جستجوی هر کلمهای در این هش تیبل هم کاری بسیار پیش پا افتاده در این زبانها است ، معمولا هر زبانی بصورت نیتیو این نوع عملیات جستجو را دارد. با وجودی که شما می توانید چند روش برای کاهش زمان اجرا یا کاهش حافظه مورد استفاده ارائه دهید ، اما معمولا اصلا لازم نیست. در واقع پیاده سازی کامل همچین چالشی چنان پیش پا افتاده است که می تواند تمرینی برای هر کسی در اوایل آموزش پایتون باشد. خلاصه دنیا و کار ما عجیب پیشرفت کرده است.