وقتی نوشته‌ای را تایپ می‌کنیم،ممکن است حرفی را از قلم بیاندازیم و یا حرفی را اضافه ترقراردهیم ویا املایش را درست ندانیم مثلا ندانیم که کلمه ی قسطنطنیه با کدام ت در زبان فارسی نوشته میشود وبین دو حرف «ت» و «ط» شک داشته باشیم.این دسته از خطاهای انسانی اجتناب ناپذیر است وتشخیص و تصحیح دستی آنها سخت و زمان‌بر خواهد بود علی الخصوص اگر متن نوشته شده طولانی باشد.لذا نیاز به یک سامانه تشخیص هوشمند خطاهای املائی در متن احساس شده است.
مقدمه
مسئله ی پیدا کردن خطا های املایی توسط ماشین از جمله مسائل مورد بحث در پردازش زبان های طبیعی است. پس از به وجود آمدن علوم رایانه ای و مسائل هوش مصنوعی ، پردازش زبان های طبیعی مورد توجه بسیار قرار گرفت. به طور کلی پردازش زبان‌های طبیعی،یکی از زیرشاخه‌های بااهمیت در حوزه گسترده هوش مصنوعی است. تلاش عمده در این زمینه ماشینی کردن فرایند درک و برداشت مفاهیم بیان گردیده با یک زبان طبیعی انسانی توسط ماشین است. با فراگیر شدن پدیده اینترنت و گسترش متون الکترونیکی این علم اهمّیت ویژه ای پیدا کرده است که از جمله نتایج آن می توان به استخراج اطلاعاتی خاص از یک متن، ترجمه یک متن به زبانی دیگر، یافتن مستنداتی خاص در یک پایگاه داده نوشتاری ، سیستم های پرسش و پاسخ انسان با کامپیوتر، سرویس های اتوماتیک ارتباط با مشتری از طریق تلفن و سیستم های کنترلی توسط صدا اشاره کرد. همچنین پیاده سازی انواع خطایاب های املایی ، مترجمین هوشمند ماشینی، نرم افزارهای پردازش و تشخیص گفتار و نرم افزارهای تبدیل متن به صدا از جمله تلاش ها در این زمینه بوده است.
در رابطه با خطایابی املایی ، مسئله ی تشخیص خودکار و تصحیح خطاهای املایی موجود در انواع متن از دهه ی ۶۰ میلادی مطرح بوده است و تا به امروز نیز پیدا کردن الگوریتم ها ی بهینه برای این کار مورد توجه بوده است و ﻣﺴﺌﻠﻪ ی اﺧﺘﺮاع اﻟﮕﻮرﻳﺘﻢ ﻫﺎ و روش ﻫﺎی ﺗﺼﺤﻴﺢ ﺧﻮدﻛﺎر ﻛﻠﻤﺎت در ﻣﺘﻦ ﺑﻪ ﻳﻚ ﭼﺎﻟﺶ ﺑﺎﻟﻘﻮه ی ﺗﺤﻘﻴﻘﺎﺗﻲ ﺗﺒﺪﻳﻞ ﺷﺪه اﺳﺖ چنانچه استفاده از سامانه‌های تشخیص لغات و تصحیح خودکار و هوشمند خطاهای املائی در دنیای امروز در بسیاری از کاربردها نظیر نرم‌افزارهای تولید اسناد متنی و همچنین کیبوردهای مجازی گوشی‌های هوشمند متداول شده است.برای مثال حدود 10 تا 12 درصد پرس و جوهای وارد شده در موتورهای جستجو و بیش از 14% تمام پرس و جوهای ارسال شده برای بازیابی اطلاعات، شامل عبارت هایی با غلط املایی است.پس امروزه با فراگیر شدن پدیده اینترنت ، گسترش متون الکترونیکی و استفاده از واسط های مبتنی بر پرس و جو، وجود ابزارهایی کمکی جهت تسریع و تسهیل در غلط یابی و ارائه کلمه پیشنهادی مناسب، اجتناب ناپذیر گشته است.(1)
خطایاب های املایی در تصحیح و کمک به جستجوی سریعتر و دقیقتر در اینترنت، تصحیح خطاهای ناشی از تبدیل تصویر به متن،صرفه جویی در وقت و هزینه ، ابزارهای جانبی برای ویرایشگرهای متنی، ابزار پیش پردازنده در پردازش زبان های طبیعی ، واسط های بازیابی اطلاعات، تبدیل گفتار به متن و کامپیوترهای مبتنی بر قلم و … کاربرد های بسیاری دارند. همچنین امروزه حجم بسیار زیادی از اطلاعات و متون فارسـی توسـط رایانـه ها تولید میشوند. فرایند تولید و ورود اطلاعات، به ویژه متن، هیچ گاه عـاری از خطـا نبـوده و هزینه های بسیاری برای یافتن و برطرف ساختن این خطاها صرف میشود که این امر نیاز به خطایاب را بیشتر نمایان می کند.
ﺗﻔﺎوﺗﻲ ﺑﺎﻳﺪ ﺑﻴﻦ ﻛﺎر ﺗﺸﺨﻴﺺ ﺧﻄﺎی اﻣﻼﻳﻲ و ﺗﺼﺤﻴﺢ آن ﻗﺎﺋﻞ ﺷﺪ .روش ﻫﺎی ﻛﺎراﻳﻲ ﺑﺮای ﺗﺸﺨﻴﺺ رﺷﺘﻪ ﻫﺎﻳﻲ ﻛﻪ در ﻳﻚ ﻟﻐﺖ ﻧﺎﻣﻪ وﺟﻮد ﻧﺪارﻧﺪ اﻳﺠﺎد ﺷﺪه اﺳﺖ .وﻟﻲ ﺗﺼﺤﻴﺢ رﺷﺘﻪ ی ﺷﺎﻣﻞ ﻏﻠﻂ اﻣﻼﻳﻲ ﻣﺴﺌﻠﻪ ی ﺑﻪ ﻣﺮاﺗﺐ ﺳﺨﺖ ﺗﺮی اﺳﺖ.(1)
کارهای زیادی جهت مدل کردن الگوی خطا و مشخص نمودن پارامترهای آن صورت گرفته است. تقسیم بندی های متفاوتی از الگوی خطا، با توجه به منبع خطا وجود دارد. دسته بندیهای ارائه شده برای خطا ، به ساختار آوائی و نگارشی هر زبان بستگی دارد.مثلا یک دسته بندی می تواند مبتنی بر شباهت در تلفظ، خطای تایپوگرافی و خطای فتونیکی باشد. خطای تایپوگرافی شامل خطاهای ناشی از عادات کاربر و یا نزدیکی نوشتاری حروف است. خطاهای فتونیکی، از شباهت تلفظی حروف با نوشتار متفاوت، ناشی می شود. الگوهای خطای بدست آمده صرفنظر از دسته بندی های اعمال شده، به عنوان یک راهنما جهت تشخیص محل وقوع خطا و رفع آن عمل می نمایند. مشکل اساسی در این رابطه، وابستگی الگوی خطا به زبان و رسانه ای است که سیستم در آن کار می کند.
بخش کارهای مرتبط
به طور کلی خطایابی املایی شامل بررسی یک متن ، مشخص کردن کلمه یا کلمات اشتباه و تصحیح آن ها می شود. بعضی از خطایاب های امروزی به جای ارائه یک تصحیح، لیستی از پیشنهادات را برای کاربر نمایش می دهند. بعضی از خطایاب های قدیمی تر فقط کلمه ی شامل غلط املایی را مشخص می کنند و پیشنهادی برای املای صحیح ارائه نمی کنند چراکه عمل تصحیح، به مراتب پیچیده تر و نیازمند پردازش بیشتری است.
خطایاب ها برای پیدا کردن خطاها از الگو های مشخصی استفاده میکنند به طوریکه دسته بندی های مختلفی برای انواع خطاها وجود دارد و می توان توسط مدل سازی های مختلف زبان ها آنها را شناسایی کرد، که جلوتر به آنها می پردازیم.
خطاهای املایی را می توان به دسته های مختلفی تقسیم بندی کرد.
به طور کلی دو دسته ی :
۱) خطاهای غیر لغت ( Non-word Errors )
۲) خطاهای لغات واقعی ( Real-word Errors )
غیر لغات ها همانطور که از نام آنها پیداست کلماتی هستند که معنایی ندارند و در فرهنگ لغات وجود ندارند. معمولا عمل تصحیح آنها با اضافه یا کم کردن و یا با تغییر یک یا چند حرف انجام می شود. برای مثال اگر کاربر کلمه ی (فقث) را وارد کرده باشد می توان حدس زد که کلمه ی درست (فقط) می باشد.
خطاهای لغات واقعی خود شامل خطاهای چاپی(Typographical errors) ، خطاهای شناختی (Cognitive errors) و خطاهای آوایی (Phonetic) می شوند. در خطاهای لغات واقعی ممکن است کلمه ی نوشته شده از نظر املایی درست باشد و در فرهنگ لغات هم موجود باشد اما کاربرد آن در متن نوشته شده اشتباه باشد.
در خطاهای چاپی فرض بر این است که کاربر املای درست را می داند اما به دلایلی خطا انجام می دهد (برای مثال دیو به جای دیر و یا اسلام به جای سلام). خطاهای چاپی شامل خطاهای ناشی ازعادات کاربر و یا نزدیکی نوشتاری حروف است.
در خطاهای شناختی کاربر تسلط کافی به زبان را ندارد و معنای کلمه ی درست با کلمه ی وارد شده متفاوت است (برای مثال غصه به جای قصه و یا توجیح به جای توجیه ).
خطاهای آوایی همانند خطاهای شناختی هستند با این تفاوت که کلمه ی خطا از لحاظ آوایی مشابه کلمه ی صحیح مورد نظر است (برای مثال اصلاح به جای اسلاح )
ﺑﻴﺶ ﺗﺮ روش ﻫﺎی ﺧﻄﺎﻳﺎﺑﻲ اﻣﻼﻳﻲ ﻣﻮﺟﻮد ﺑﺮ روی ﻛﻠﻤﺎت ﻣﻨﺰوی ﺗﻤﺮﻛﺰ دارﻧﺪ و اﻃﻼﻋﺎﺗﻲ را ﻛﻪ از ﻣﺘﻨﻲ ﻛﻪ رﺷﺘﻪ در آن ﻇﺎﻫﺮ ﺷﺪه اﺳﺖ ﻣﻲ ﺗﻮاﻧﺪ ﺑﻪ دﺳﺖ آورد را در ﻧﻈﺮ ﻧﻤﻲ ﮔﻴﺮﻧﺪ .ﭼﻨﻴﻦ روش ﻫﺎﻳﻲ ﻗﺎدر ﺑﻪ ﺗﺸﺨﻴﺺ ﻗﺴﻤﺖ ﺑﺰرﮔﻲ از ﺧﻄﺎﻫﺎ از ﺟﻤﻠﻪ ﺧﻄﺎﻫﺎی ﭼﺎﭘﻲ، آواﻳﻲ و ﻧﺤﻮی ﻛﻪ ﻣﻨﺠﺮ ﺑﻪ ﺗﻮﻟﻴﺪ دﻳﮕﺮ ﻛﻠﻤﺎت ﻣﻮرد ﻗﺒﻮل ﻫﺴﺘﻨﺪ،نیستند.(1)
الگوی خطاهای اصلی :
در تحقیقاتی که در این زمینه انجام شده است مشخص شده که حدود ۸۰٪ از کل خطاهای املایی موجود در یک نوشتار شامل یکی از موارد زیر هستند :
۱)خطای درج اضافی حرف : اضافه شدن یک یا چند حرف به کلمه ی درست.
۲)خطای حذف حرف : پاک شدن یک یا چند حرف از کلمه ی درست.
۳)خطای جانشینی : استفاده از یک حرف به جای حرفی دیگر .
۴)خطای جابجایی : جابجایی دو حرف با هم.
۵)خطای فاصله : چسبیدن دو کلمه درست بدون فاصله به هم.
خطایاب ها با کمک این الگو های خطا و مدل سازی زبان ها ، می توانند به خطایابی بپردازند.
۱) تشخیص خطاهای غیر لغت :
دو روش اﺻﻠﻲ ﻛﻪ ﺑﺮای ﺗﺸﺨﻴﺺ ﺧﻄﺎی اﻣﻼﻳﻲ ﻏﻴﺮ ﻟﻐﺖ ﺑﻪ ﻛﺎر رﻓﺘﻪ اﻧﺪ، ﺗﺤﻠﻴﻞ ﭼﻨﺪ نگاشت و ﻣﺮاﺟﻌﻪ ﺑﻪ ﻟﻐت ﻧﺎﻣﻪ اﺳﺖ . ﭼﻨﺪﻧﮕﺎﺷﺖ ﻫﺎ زﻳﺮ دﻧﺒﺎﻟﻪ ﻫﺎی ﭼﻨﺪ ﺣﺮﻓﻲ از ﻛﻠﻤﺎت و رﺷﺘﻪ ﻫﺎ ﻫﺴﺘﻨﺪ ﻛﻪ ﭼﻨﺪ ﻣﻌﻤﻮﻻً ﻳﻚ، دو و ﻳﺎ ﺳﻪ اﺳﺖ .ﺑﻪ ﻃﻮر ﻛﻠﻲ روش ﻫﺎی ﺗﺸﺨﻴﺺ ﺧﻄﺎی ﻣﺒﺘﻨﻲ ﺑﺮ ﭼﻨﺪﻧﮕﺎﺷﺘﻲ ﺑﺎ اﻣﺘﺤﺎن در ﻣﺘﻦ ورودی و ﺑﻪ دﻧﺒﺎل آن در ﻳﻚ ﺟﺪول از ﭘﻴﺶ ﺗﻮﻟﻴﺪ ﻛﺮدن ﻫﺮ ﭼﻨﺪﻧﮕﺎﺷﺖ ﺷﺪه ﮔﺸﺘﻦ ﺑﺮای ﻣﺸﺨﺺ ﺷﺪن وﺟﻮد ﻳﺎ ﺗﻌﺪاد ﺗﻜﺮار آن، ﻛﺎر ﻣﻲ ﻛﻨﺪ .رﺷﺘﻪ ﻫﺎﻳﻲ ﻛﻪ دارای ﭼﻨﺪﻧﮕﺎﺷﺖ ﻫﺎی ﺑﺪون ﺗﻜﺮار ﻳﺎ ﺗﻜﺮار ﺑﺴﻴﺎر ﻛﻢ ﺑﺎﺷﻨﺪ )ﻣﺜﻞ ﺳﻪ ﻧﮕﺎﺷﺖ ﭘﺨﺰ ﻳﺎ ﻓﻘﺚ (ﺑﻪ ﻋﻨﻮان ﺧﻄﺎﻫﺎی اﺣﺘﻤﺎﻟﻲ در ﻧﻈﺮ ﮔﺮﻓﺘﻪ ﻣﻲ ﺷﻮﻧﺪ .اﻳﻦ روش ﻫﺎ ﻣﻌﻤﻮﻻً ﺑﻪ ﻳﻚ ﻟﻐﺖ ﻧﺎﻣﻪ ﻳﺎ ﻳﻚ ﻣﺠﻤﻮﻋﻪ ی ﺑﺰرگ از ﻧﻮﺷﺘﺠﺎت ﺑﺮای ﺗﻮﻟﻴﺪ از ﭘﻴﺶ ﺟﺪول ﭼﻨﺪﻧﮕﺎﺷﺖ ﻫﺎ ﻧﻴﺎز دارﻧﺪ .روش ﻫﺎی ﻣﺒﺘﻨﻲ ﺑﺮ ﻟﻐﺖ ﻧﺎﻣﻪ ﺑﻪ ﺳﺎدﮔﻲ ﻛﻠﻤﺎت ورودی را در ﻳﻚ ﻟﻐﺖ ﻧﺎﻣﻪ ﺟﺴﺘﺠﻮ ﻣﻲ ﻛﻨﻨﺪ .اﮔﺮ ﻛﻠﻤﻪ ی ورودی در ﻟﻐﺖ ﻧﺎﻣﻪ وﺟﻮد ﻧﺪاﺷﺖ ﺑﻪ ﻋﻨﻮان ﺧﻄﺎ ﻋﻼﻣﺖ ﮔﺬاری ﻣﻲ ﺷﻮد.
در ﻛﻞ ﺑﺎ اﻳﻨﻜﻪ ﺗﺤﻠﻴﻞ ﭼﻨد نگاشتی ممکن از برای خطاهای تولید شده ﺗﻮﺳﻂ ﻣﺎﺷﻴﻦ، ﺑﺮای ﻣﺜﺎل ﺗﺸﺨﻴﺺ ﻧﻮری ﺣﺮوف ﻣﻔﻴﺪ ﺑﺎﺷﺪ، وﻟﻲ ﺛﺎﺑﺖ ﺷﺪه اﺳﺖ ﺑﺮای ﺧﻄﺎﻫﺎی ﺗﻮﻟﻴﺪ ﺷﺪه ﺗﻮﺳﻂ اﻧﺴﺎن دﻗﺖ ﻛﻢ ﺗﺮی دارد .ﺑﻪ ﻫﻤﻴﻦ ﺧﺎﻃﺮ ﺑﻴﺶ ﺗﺮ روش ﻫﺎی ﺗﺼﺤﻴﺢ ﺧﻄﺎی اﻣﻼﻳﻲ ﺑﺮ اﺳﺎس ﻣﺮاﺟﻌﻪ ﺑﻪ ﻟﻐﺖ ﻧﺎﻣﻪ ﻫﺴﺘﻨﺪ .از آﻧﺠﺎﻳﻲ ﻛﻪ وﻗﺘﻲ ﻟﻐﺖ ﻧﺎﻣﻪ ﺑﺰرگ ﻣﻲ ﺷﻮد، ﺳﺮﻋﺖ ﭘﺎﺳﺦ ﮔﻮﻳﻲ ﻣﺴﺌﻠﻪ ی ﻣﻬﻤﻲ ﻣﻲ ﺷﻮد، روش ﻫﺎﻳﻲ ﻛﻪ از ﺟﺪول ﻫﺎی درﻫﻢ، درﺧﺖ ﻫﺎ و...اﺳﺘﻔﺎده ﻣﻲ ﻛﻨﻨﺪ ﺑﻪ وﺟﻮد آﻣﺪه اﻧﺪ.
استفاده از لغت نامه
ساده ترین و پراستفاده ترین روش برای تشخیص خطاهای غیر لغت ، استفاده از لغت نامه ها (Dictionaries) است. در این روش کلمات درست در یک لغت نامه ذخیره می شوند. سپس خطایاب تک تک کلمات وارد شده را در داخل لغت نامه جست و جو می کند و اگر همانند آن کلمه پیدا نشود ، خطایاب یک خطا را تشخیص داده است. بدین ترتیب هرچه لغت نامه بزرگتر باشد ، بهتر است. اما در این روش مسئله ی زمان پاسخگویی و همچنین فضای ذخیره شده نکات مهمی هستند. معمولا تعداد کلمات لغت نامه ها حدود ۲۵۰ هزار لغات یا بیشتر می باشد. با بزرگتر شدن لغت نامه زمان پاسخگویی سیستم بسیار بالا می رود. همچنین به فضای ذخیره سازی زیادی نیاز خواهیم داشت. برای حل این مشکل روش های مختلفی مثل مراجعه به لغت نامه های کارا، تقسیم لغت نامه ها و روش های مبتنی بر پردازش ریخت شناسی وجود دارند.
در ﻣﺮاﺟﻌﻪ ﺑﻪ ﻟﻐﺖ ﻧﺎﻣﻪ ﻣﺴﺌﻠﻪ زﻣﺎن ﭘﺎﺳﺦ ﮔﻮﻳﻲ اﺳﺖ .ﻣﻌﻤﻮﻻً اﻧﺪازه ی ﻟﻐﺖ نامه ها بین 25 هزار تا 250 هزار لغت است وبرای این اندازه لغت نامه ها زﻣﺎن ﭘﺎﺳﺦ ﮔﻮﻳﻲ ﺑﺴﻴﺎر ﺑﺎﻻ ﻣﻲ رود .اﻳﻦ ﻣﺸﻜﻞ از ﺳﻪ روش ﻣﺮاﺟﻌﻪ ﺑﻪ ﻟﻐﺖ ﻧﺎﻣﻪ ی ﻛﺎرا، ﺗﻘﺴﻴﻢ ﻟﻐﺖ ﻧﺎﻣﻪ و روش های ﻣﺒﺘﻨﻲ ﺑﺮ ﭘﺮدازش رﻳﺨﺖ ﺷﻨﺎﺳﻲ ﺳﻌﻲ ﺷﺪه اﺳﺖ ﻛﻪ ﺣﻞ ﺷﻮد.
ﭘﺮ اﺳﺘﻔﺎده ﺗﺮﻳﻦ روش ﺑﺮای دﺳﺘﺮﺳﻲ ﺳﺮﻳﻊ ﺑﻪ ﻟﻐﺖ ﻧﺎﻣﻪ ﻫﺎ اﺳﺘﻔﺎده از ﺟﺪول های درهم است.(4) برای امتحان کردن یک رشته ی ورودی، آدرس درﻫﻢ آن ﻣﺤﺎﺳﺒﻪ ﻣﻲ ﺷﻮد و ﺑﺎ ﻣﺮاﺟﻌﻪ ﺑﻪ ﺟﺪول درﻫﻢ از ﭘﻴﺶ ﺳﺎﺧﺘﻪ ﺷﺪه و درﻳﺎﻓﺖ ﻛﻠﻤﻪ ی ذﺧﻴﺮه ﺷﺪه در آن ﻣﻜﺎن اﮔﺮ ﻛﻠﻤﺎت ﻳﻜﻲ ﻧﺒﻮدﻧﺪ ﻳﺎ ﻛﻠﻤﻪ ای وﺟﻮد ﻧﺪاﺷﺖ، ﻏﻠﻂ اﻣﻼﻳﻲ ﺗﺸﺨﻴﺺ داده ﻣﻲ ﺷﻮد.
ﺣﺴﻦ اﺻﻠﻲ اﺳﺘﻔﺎده از ﺟﺪول ﻫﺎی درﻫﻢ ﻋﺪم ﻧﻴﺎز ﺑﻪ ﻣﻘﺎﻳﺴﻪ زﻳﺎد ﺑﻪ ﺧﺎﻃﺮ ﺧﺎﺻﻴﺖ دﺳﺘﺮﺳﻲ ﻣﺴﺘﻘﻴﻢ اﺳﺖ و ﻣﺸﻜﻞ ﺑﺰرگ آن ﭘﻴﺪا ﻛﺮدن ﺗﺎﺑﻊ درﻫﻤﻲ ﻣﻨﺎﺳﺐ ﺑﺮای ﺗﻮﻟﻴﺪ ﺟﺪول درﻫﻢ ﺑﻪ ﮔﻮﻧﻪ ای ﻛﻪ ﺗﻜﺮاری ﺗﻮﻟﻴﺪ ﻧﻜﻨﺪ و ﺳﺮﻳﻊ ﺑﺎﺷﺪ اﺳﺖ .اﻟﺒﺘﻪ روش ﻫﺎﻳﻲ ﺑﺮای ﺗﻮﻟﻴﺪ ﭼﻨﻴﻦ ﺗﻮاﺑﻌﻲ ﺗﻮﺿﻴﺢ داده ﺷﺪه اﺳﺖ.(5)
ﺑﺮﻧﺎﻣﻪ spellمربوط به سیستم عامل Unix از جمله برنامه هایی است ﻛﻪ از ﻳﻚ ﺟﺪول درﻫﻢ ﺑﺮای ﻣﺮاﺟﻌﻪ ی ﺳﺮﻳﻊ ﺑﻪ ﻟﻐﺖ ﻧﺎﻣﻪ اﺳﺘﻔﺎده ﻣﻲ کند.(6)
بهینه سازی روش لغت نامه
برای مثال یک روش این است که فقط ریشه ی کلمات را ذخیره کنیم (ریشه یابی). در این روش توسط الگوریتم ها و مجموعه قوانین خاص هر زبان پیشوند ها و پسوند های کلمات را حذف می کنیم. به هنگام جست و جوی خطا نیز همین کار را بر روی کلماتی که کاربر وارد کرده انجام می دهیم وریشه های ایجاد شده را با ریشه های ذخیره شده در لغت نامه مقایسه می کنیم. بدین ترتیب فضای اشغال شده توسط لغت نامه کمتر شده و زمان پاسخ گویی نیز بسیار سریعتر می شود. مشکل این روش این است که ممکن است بعضی خطاها نادیده گرفته شوند چراکه امکان دارد کلمه ی وارد شده توسط کاربر ریشه ی درستی داشته باشد ولی به همراه پسوند یا پیشوند وارد شده ، حاوی غلط املایی باشد.
روش دیگر استفاده از تابع درهم (Hash Function) در ذخیره سازی است. در این روش برای هر کلمه ی لغت نامه یک آدرس درهم در نظر می گیریم. این آدرس با اعمال تابع درهم بر روی هر یک از حروف الفبا به دست می آید. برای مثال به حرف الف عدد ۱، ب عدد ۲ پ عدد ۳ و به همین ترتیب به تمام حروف یک عدد را نسبت می دهیم. سپس با استفاده از تابع درهم یعنی اعمال محاسبات ریاضی بر روی اعداد حروف هر کلمه ، به یک عدد برای هر کلمه می رسیم. بدین ترتیب به جای ذخیره ی هر کلمه ، این عدد را در حافظه ذخیره می کنیم. هنگامی که کاربر یک رشته ی ورودی را وارد می کند، آدرس درهم آن محاسبه می شود و با مراجعه به جدول درهم از پیش ساخته شده و دریافت کلمه ی ذخیره شده در آن مکان اگر کلمات یکی نبودند یا کلمه ای وجود نداشت، غلط املایی تشخیص داده می شود. این روش در واقع نگاشت بیت به بیت (BitMap) می باشد.
بدین ترتیب سرعت دسترسی به اطلاعات و زمان پاسخگویی بسیار سریعتر می شود. به دلیل خاصیت دسترسی مستقیم نیازی به مقایسه های زیادی نیست. همچنین فضای ذخیره سازی نیز کاهش می یابد. مهمترین چالش در این روش داشتن تابع درهم مناسب است چراکه هر کلمه لازم است که آدرس منحصر به فردی داشته باشد. پیدا کردن تابع درهمی مناسب برای تولید این جدول درهم به گونه ای که کلمات تکراری تولید نکند و همچنین سریع بودن تابع مشکل اصلی این روش است. البته روش های مختلفی برای تولید چنین توابعی وجود دارد.
استفاده از تحلیل چند نگاشت (N-grams)
ﺧﻄﺎﻫﺎﻳﻲ ﻛﻪ ﺗﻮﺳﻂ دﺳتگاه ﻫﺎی ﺗﺸﺨﻴﺺ ﻧﻮری ﺣﺮوف معمولا انهایی هستند که ﺣﺮوف ﺷﺒﻴﻪ ﺑﻪ ﻫﻢ را ﺑﺎ ﻫﻢ اﺷﺘﺒﺎه ﻣﻲ ﻛﻨﻨﺪ، ﻣﺜﻞ اﻟﻒ و ﻻم ﻳﺎ 1والف.روش های مبتنی برﺗﺤﻠﻴﻞ ﭼﻨﺪﻧﮕﺎﺷﺖ ﺑﺮای ﺗﺸﺨﻴﺺ اﻳﻦ ﺧﻄﺎﻫﺎ ﺧﻮب ﻋﻤﻞ میﻛﻨﻨﺪ.
ﺟﺪول ﻫﺎی ﭼﻨﺪﻧﮕﺎﺷﺖ ﻣﻲ ﺗﻮاﻧﻨﺪ ﺑﻪ ﺷﻜﻞ ﻫﺎی ﻣﺘﻔﺎوﺗﻲ ﺗﻮﻟﻴﺪ ﺷﻮﻧﺪ .ﺳﺎده ﺗﺮﻳﻦ آن ﻫﺎ ﻳﻚ دوﻧﮕﺎﺷﺖ دودوﻳﻲ اﺳﺖ ﻛﻪ ﻳﻚ آراﻳﻪ ی دو بعدی 32 ×32است که تمام ترکیب های دوﺗﺎﻳﻲ ﺣﺮوف را در ﺑﺮ ﻣﻲ ﮔﻴﺮد.ﻫﺮ ﺧﺎﻧﻪ آن شامل 1 اﮔﺮ آن دوﻧﮕﺎﺷﺖ در ﻣﺘﻦ ﻣﺎ ﺣﺪاﻗﻞ یکبارتکرارشده باشد یا 0است.ﻳﻚ ﺳﻪ ﻧﮕﺎﺷﺖ دودوﻳﻲ ﺑﻪ ﻫﻤﻴﻦ ﺷﻜﻞ و ﻳﻚ آراﻳﻪ سه بعدی است.ﻫﺮ دو آراﻳﻪ ﻫﺎی ﺑﺎﻻ را ﭼﻨﺪﻧﮕﺎﺷﺖ ﻫﺎی دودوﻳﻲ ﻏﻴﺮ واﺑﺴﺘﻪ ﺑﻪ ﻣﻮﻗﻌﻴﺖ ﻣﻲﻧﺎﻣﻨﺪ .ﺑﺪﻳﻦ ﻣﻌﻨﺎ ﻛﻪ ﻣﺤﻞ ﭼﻨﺪﻧﮕﺎﺷﺖ را در ﻛﻠﻤﻪ ﻣﺸﺨﺺ ﻧﻤﻲ ﻛﻨﻨﺪ.
در اﺧﺘﺼﺎص ﻓﻀﺎی ﺑﻴﺶ ﺗﺮ ﺑﻪ ﺟﺪول ﭼﻨﺪ ﻧﮕﺎﺷﺖ ﻣﻲ ﺗﻮان ﻣﻮﻗﻌﻴﺖ ﭼﻨﺪ ﻧﮕﺎﺷﺖ را ﻫﻢ ذﺧﻴﺮه ﻛﺮد.در آزﻣﺎﻳﺸﺎت ﻣﺸﺨﺺ ﺷﺪه اﺳﺖ ﻛﻪ ﭼﻨﺪﻧﮕﺎﺷﺖ ﻫﺎی واﺑﺴﺘﻪ ﺑﻪ ﻣﻮﻗﻌﻴﺖ ﺑﻬﺘﺮ ﻋﻤﻞ ﻣﻲ کنند.(2)(3)
روش دیگر برای تشخیص خطاهای غیر لغت استفاده از تحلیل چند نگاشت است. چندنگاشت ها زیر دنباله های چند حرفی از رشته های کاراکتری هستند. برای مثال یک، دو، و یا سه حرفی. برای مثال، زیر نگاشت ۳ حرفی کلمه ی “آفتاب” شامل ‘آفت’ ، ‘فتا’ و ‘تاب’ ، می شود. دو روش کلی برای تحلیل چند نگاشت وجود دارد.
در یکی از این روش ها به طور غیر مستقیم از لغت نامه استفاده می کنیم بدین ترتیب که برای مثال ابتدا سه نگاشت های تمام کلمات لغت نامه را ذخیره می کنیم. حال هنگامی که کاربر رشته ای را وارد می کند چند نگاشت های آن نیز به همان روش قبلی ساخته می شوند و با چند نگاشت های لغت نامه مقایسه می شوند. عدم وجود آن ها در چند نگاشت های لغت نامه، مشخص کننده ی خطاهای احتمالی است.در این روش معمولاً به یک لغت نامه برای نگه داری از پیش جدول چندنگاشت ها نیازاست. در روش های مبتنی بر تحلیل چندنگاشت ممکن است تعداد قابل توجهی از خطاها تشخیص داده نشوند چراکه بسیاری از کلمات حاوی خطا، شامل چند نگاشت های غیرمعمول نمی شوند اما در تشخیص خطاهایی که توسط دستگاههای تشخیص نوری حروف (Optical Character Recognition) خطایابی می شوند ، خوب عمل می کنند.
در روش دیگر برای تحلیل چند نگاشت ها از لغت نامه استفاده نمی شود. همانند روش قبل ابتدا چند نگاشت های متن ورودی توسط کاربر مشخص می شوند اما این بار تعداد تکرار آن ها در متن اهمیت دارد. برای مثال سه نگاشت “پخز” که فقط یکبار در متن تکرار شده باشد،احتمال خطا بودن آن زیاد است. اما “هست” که بسیار بیشتر استفاده شده است احتمال خطا بودن آن ناچیز است. همانند روش قبل احتمال تشخیص ندادن خطا های عادی وجود دارد اما این روش در تشخیص خطاهای تایپی بسیار کارا عمل می کند.همچنین مزیت دیگر آن این است که برای هر زبانی می توان از این روش استفاده کرد.
جدول های چند نگاشت می توانند با روش های مختلفی ساخته شوند. ساده ترین روش استفاده از دونگاشت دودویی است که یک آرایه ی دو بعدی است که تمام ترکیبهای دوتایی حروف را در بر می گیرد. هر خانه ی آن شامل ۱ اگر آن دونگاشت در متن ما حداقل یکبار تکرار شده باشد یا ۰ است. یک سه نگاشت دودویی به همین شکل ولی یک آرایه ی سه بعدی است.
این آرایه ها را چند نگاشت های دودویی غیر وابسته به موقعیت می نامند. بدین معنا که محل چندنگاشت را در کلمه مشخص نمی کنند.
با اختصاص فضای بیشتر به جدول چند نگاشت می توان موقعیت چندنگاشت را هم ذخیره کرد. این کار باعث بهبود کارایی روش های چند نگاشت ها می شود چراکه می توان محل آن ها در کلمه را نیز مقایسه کرد.
به طور کلی تحلیل چند نگاشتی در بعضی زمینه ها مثل تشخیص نوری حروف و خطاهای تایپی مفید است، ولی برای خطاهای تولید شده توسط انسان دقت کمتری دارد. به همین خاطر بیشتر روش های تصحیح خطای املایی بر اساس مراجعه به لغتنامه می باشند.
خطای حرف اول
عموما خطا در حرف اول کلمات رخ نمی دهد. بدین ترتیب می توانیم لغتنامه ها را بر اساس حرف اول تقسیم بندی کنیم تا زمان مراجعه به لغت نامه و زمان پاسخ گویی کاهش یابند.مشکل این دسته بندی این است که در این صورت دسته ای از خطاها(خطاهای حرف اول) توسط سیستم ما تشخیص داده نمی شود.
طول کلمه
طبق تحقیقات انجام شده، در بسیاری از مواقع طول کلمه ی خطا در فاصله ی دوتایی از طول کلمه ی صحیح است. این موضوع باعث می شد محققان لغتنامه ها را بر اساس طول کلمات به چند دسته تقسیم کنند تا زمان جستجو کاهش یابد.
با توجه به قانون زیپف در یک نوشته کلمات کوتاه تر تعداد تکرارهای بیشتری دارند. همچنین کلمات با تکرار بیشتر همسایه های تک خطایی بیشتری دارند. ولی معمولاً کلمات کوتاه کمتر اشتباه نوشته می شوند. در ضمن هرچه کلمه کوتاه تر باشد متن درون کلمه ای کمتری در اختیار ما قرار می دهد و کار تصحیح سخت تر می شود.
۲) تشخیص خطای لغات واقعی :
از جمله ایرادات خطایاب ها می توان به تشخیص دادن کلمه ی درست به عنوان خطا و یا تشخیص ندادن بعضی خطاها اشاره کرد. دلیل ایراد نوع اول ، وجود کلمات مبهم و اسم های خاص در متن وارد شده می باشد. می توان با فراهم کردن لغت نامه ی بزرگتر برای خطایاب و یا استفاده از لغت نامه ی تخصصی برای انواع مختلف متن (برای مثال پزشکی) درصد این ایراد را کاهش داد. اما برای ایراد دوم راه حل خاصی وجود ندارد چراکه تعداد اسم های خاص بسیار زیاد است. بسیاری از خطایاب ها امکانی را فراهم می کنند که کاربر اسم خاص را برای خطایاب مشخص کند تا بعد از اولین باری که خطا در نظر گرفته می شود خطایاب دوباره آن را خطا اعلام نکند.
ایراد نوع دوم در مقابل ایراد اول یعنی تشخیص اشتباه بسیار مهم تر است چراکه کاربر همواره می تواند خطا را نادیده بگیرد ، اما تشخیص ندادن کلمه ی خطا نگران کننده است چراکه کاربر انتظار متنی بدون خطا را دارد.
این مشکل با افزایش سایز لغت نامه برای کاهش ریسک ایراد نوع اول ، بیشتر نیز می شود چراکه با افزایش لغات مبهم لغت نامه امکان تشخیص ندادن خطاهای لغات واقعی بیشتر می شود.
خطایاب های کمی هستند که می توانند خطای لغات واقعی را تشخیص دهند. ۳ پروژه در این زمینه قابل ذکر هستند.
اولی سیستمی با نام CRITIQUE است که توسط IBM ساخته شده است. در این برنامه متن از لحاظ نوشتاری ، دستور زبان و قالب نوشتاری ، بررسی می شود.سیستم توسط گرامری که برای آن طراحی شده است ، متن را بررسی می کند و نقش کلمات شامل اسم ، قید ، افعال اصلی و کمکی و غیره را مشخص می کند. اگر جمله ای با قواعد گرامر تعریف شده همخوانی نداشته باشد ، آن قاعده کنار گذاشته می شود و دوباره جمله بررسی می شود. این کار تا زمانی ادامه پیدا می کند که جمله مورد قبول واقع شود. حال سیستم با دانستن قواعد کنار گذاشته شده ، می تواند تشخیص دهد چه قسمتی از دستور زبان مشکل داشته است.
پروژه ی دوم نیز همانند سیستم اولی بر پایه قواعد نحوی است. در ابتدا این پروژه در دانشگاه لنکستر فقط برای مشخص کردن نقش کلمات در جمله بود اما بعدها به خطایاب املایی تبدیل شد. سیستم ابتدا با مراجعه به یک لغت نامه نقش کلمات را مشخص می کند. لغت نامه بر اساس نقش کلمات مرتب شده است (برای مثال لغت نامه ای برای افعال). همچنین سیستم حاوی جدولی است که جایگاه و ترتیب قرار گرفتن نقش های مختلف در جمله را مشخص می کند. وقتی کاربر متنی را وارد می کند سیستم ترتیب قرار گرفتن کلمات با نقش های دستوری مختلف را بررسی می کند و دنباله ای که احتمال درست بودن آن کم است را ، مشخص می کند. بدین ترتیب سیستم حدس هایی رو برای پیشنهاد کلمه ی درست ارایه می دهد.
پروژه ی بعدی مدل پیشرفته تر سیستم قبلی بود که باز هم توسط IMB انجام شد. در این سیستم احتمال قرار گرفتن ۲ کلمه در کنار هم (و یا احتمال های دنباله ی ۳ تایی کلمات) محاسبه می شوند. سپس عمل تشخیص و تصحیح با توجه به این احتمالات انجام می شوند.
تصحیح خطا
برای تصحیح ، خطایاب باید کلمه ی مورد نظر کاربر را حدس بزند و همچنین قادر به نوشتن املا صحیح آن باشد. تولید املا درست سخت نیست چراکه همانطور که توضیح داده شد روش ها ی مختلفی برای ذخیره ی املا ی درست (از جمله ذخیره به صورت لغت نامه) وجود دارد. اما قسمت سخت تر ارایه ی پیشنهاد مناسب است.
به طور کلی کامپیوتر در تصحیح کلمات کوتاه تر کار سخت تری دارد تا کلمات بلند چراکه انتخاب ها برای کلمات کوتاه تر بسیار بیشتر است.
به دلیل حجیم بودن لغت نامه ها خطایاب برای عمل تصحیح باید قادر باشد فقط بخشی از لغت نامه که احتمال وجود کلمه ی درست در آن بیشتر است را ، ابتدا بررسی کند. این کار با توجه به توضیحی که در قسمت خطای حرف اول دادیم و در نظر گرفتن اینکه اکثر خطاها یکی از انواع الگوی خطاهای اصلی هستند ، انجام می شود. یعنی بیشتر خطاها از نوع خطای درج اضافی حرف ، خطای حذف حرف ، خطای جانشینی و یا خطای جابجایی هستند که معمولا با تغییر فقط یک حرف ، می توانیم به کلمه ی درست برسیم . همچنین حرف اول عموما صحیح است و بدین ترتیب لغت نامه بر اساس آن می تواند محدوده ی جست و جوی خود را مشخص کند و کلماتی که به فاصله ی یک یا چند حرف از کلمه ی ورودی هستند را بررسی کند. طبق تحقیقات انجام شده ۸۰٪ از خطاها به فاصله ی یک حرف از کلمه ی درست هستند. فاصله در این مبحث به تعداد عملیات های تصحیح مورد نیاز گفته میشود.
برای تصحیح این خطاها می توان از الگوریتم ‘کمترین فاصله ی تصحیح’ استفاده کرد. در این الگوریتم برای رسیدن به کلمه ی درست می توان از درج یک حرف ، حذف حرف و جا به جایی استفاده کرد . هر کدام از این اعمال را می توان چند بار انجام داد تا کلمه ی درست تولید شود.
Soundex
در این سیستم با توجه به آوا و تلفظ ، کلمات در دسته های مختلفی دسته بندی می شوند. کلمات با تلفظ مشابه در گروهای یکسان قرار می گیرند. برای هر کلمه یک کد soundex ساخته می شود. این روش بر اساس مشابهت حروف صفحه کلید می باشد. حال با ساخته شدن کد برای هر کلمه و دسته بندی آنها ، خطایاب می تواند با مراجعه به گروه کلمه ی خطا ، کاندید های تصحیح را انتخاب کند.در کد soundex حروف صدادار حذف می شوند و حروف بی صدا دسته بندی می شوند.
ساخت کد soundex :
۱) حرف اول به صورت بزرگ نگه داشته می شود
۲) حروف a,e,i,o,u,y,h,w با خط فاصله جایگزین می شوند
۳) دسته بندی حروف دیگر:
b,f,p,v : 1
c,g,j,k,q,s,x,z :2
d,t : 3
l :4
m,n :5
r :6
۴) اعداد کنار هم مشابه حذف می شوند
۵) خط فاصله ها حذف می شوند
۶) حرف اول به صورت بزرگ به همراه ۳ عدد اول نگه داشته می شوند.( اگر کمتر از ۳ عدد ساخته شده بود ، ۰ اضافه می کنیم )
برای مثال : (car(C600) ، toy(T00) ، bicycle(B224
SPEEDCOP
سیستم speedcop برای خطایابی سریع و خصوصا خطاهای تایپوگرافی به صورت خودکار ساخته شد. یک کلید برای هر کلمه ی لغت نامه ساخته می شود. حرف اول نگه داشته می شود ، سپس حروف بی صدای کلمه به ترتیب بعد از آن قرار می گیرند. حروف یکسان فقط یکبار نوشته می شوند. سپس حروف صدادار به ترتیب بعد از آنها قرار می گیرند. برای مثال کلمه ی xenon به XNEO تبدیل می شود. وقتی سیستم خطایی را تشخیص می دهد ، کد آن را می سازد و درلغت نامه جست و جو می کند تا آن را پیدا کند. سپس برای عمل تصحیح کلمات مشابه با این کد را بررسی می کند.
روش های Soundex و SPEEDCOP برای مشخص کردن قسمت خاصی از لغت نامه و بررسی کاندید ها در آن قسمت ، به کار می روند چون همانطور که گفتیم جست و جوی کل لغت نامه هزینه ی بسیاری دارد. چالش پیش رو در این روش این است که اگر کلمه ی درست در محدوده ی مشخص شده ی لغت نامه نباشد ، خطایاب قادر به پیدا کردن آن نخواهد بود.
انتخاب کاندیدهای پیشنهادی
مرحله ی بعدی برای خطایاب انتخاب لیستی از کلمات درست ( لیست کاندید ها ) و سپس ارایه ی بهترین انتخاب است.
برای خطاهای تایپی این کار سخت نیست چراکه بسیاری از آن ها از نوع ۴ نوع اصلی هستند. خطایاب کلمات مشابه را بررسی می کند و اگر در یکی از این ۴ نوع با کلمه ی ورودی تفاوت داشته باشند به لیست کاندید ها اضافه می شوند.
روش دیگر محاسبه ی ارزش شباهت برای هر کلمه ی نزدیک به کلمه ی خطا است. سپس کلمات با ارزش بیشتر به لیست اضافه می شوند. به این عمل ‘تطبیق رشته (String-Matching)’ می گویند. روش های مختلفی برای این کار وجود دارد. برای مثال در نظر گرفتن تعداد حروف در زیردنباله های مشابه از حروف در دو کلمه. مثلا کلمهات medsin و medicine در زیردنباله های med و in ، ۵ حرف مشابه دارند یعنی ۶۳٪ تشابه .
همچنین می توانیم چند نگاشت های کلمات را مقایسه کنیم. هر دو کلمه ای که چند نگاشت های مشابه بیشتری داشته باشند ، بیشتر به هم شباهت دارند ( برای مثال می توان سه نگاشت ها را در نظر گرفت ).
در بعضی روش ها به بعضی حروف ارزش بیشتری داده می شود. برای مثال حروف نزدیک به ابتدا و یه حروف بی صدا ارزش بیشتری می گیرند.
روش آماری :
دیگر روش هایی که خطایاب ها برای امتیازدهی و تصحیح استفاده می کنند ، روش های آماری هستند که بر اساس احتمال کار می کنند. در این روش ها جدولی وجود دارد که احتمال خطا های مختلف را ذخیره می کند. سپس پس از تولید لیست کاندید ها توسط خطایاب برای امتیازدهی و رتبه بندی از فرمول زیر استفاده می کنیم:
P(X|Y)\quad =\quad \frac { P(Y|X)\quad *\quad P(X) }{ P(Y) }
در این فرمول X یکی از نامزدها و Y کلمه ی خطای مشاهده شده است. (P(X|Y احتمال مناسب بودن کاندید X است. (P(Y|X احتمال خطا بودن Y برای کلمه ی درست X است. (P(X احتمال وقوع X است.
برای تمام کلمات کاندید احتمال را محاسبه می کنیم و سپس بر اساس آن ها رتبه بندی را انجام می دهیم.
شباهت آوایی :
بعضی خطایاب ها بر اساس شباهت تلفظ ، کلمات مشابه را ارزشگذاری می کنند به این معنی که عمل مقایسه بر روی تلفظ انجام می شه نه املای کلمات. برای مثال کلمه ی خطای indissceat به صورت /IndIski:t/ تلفظ می شود. خطایاب این تلفظ را به صورت سه تایی جدا می کند. برای کلمات لغت نامه نیز همین کار انجام شده. بدین ترتیب با مقایسه ی این حروف سه تایی عمل ارزشگذاری انجام می شود. هرچه تعداد شباهت ها بیشتر باشد ، کلمه ارزش بیشتری پیدا می کند.
indissceat \#In Ind ndI dIs Isk ski: ki:t i:t#
indiscreet \#In Ind ndI dIs Isk skr kri: ri:t i:t#
در مثال بالا ۶ شباهت را مشاهده می کنیم که می تواند حدس بسیار مناسبی برای تصحیح باشد.
مراجع
1-K. Kukich, “Techniques for automatically correcting words in text,” ACM Computing Surveys, vol. 24, pp. 378-439, 1992.
2-Hanson, Riseman, and Fisher, “Context in word recognition,” Patt. Recog. 8 35-45
3-J. J. Hull, and S. N. Srihari, “Experiments in text recognition with binary n-gram and Viterbi algorithms,” IEEE Trans. Patt. Anal. Machine Intell. PAMI-4, 5 (Sept.), 1982 520-530.
4-D. E. Knuth, “The Art of Programming Vol. 3, Sorting and Searching,” Addison-Wesley, Reading 1973.
5-E. A. Fox, Q. F. Chen, and L. S. Heath, “A faster algorithm for constructing minimal perfect hash functions,” In Proceedings of the 15th annual International SIGIR Meeting. ACM, New York, 1992, 266-273.
6-K. Atkinson, “Gnu aspell,” In Available at http://aspell.net, 2009.
7-F. J. Damerau, “A technique for computer detection and correction of spelling errors,” Commun ACM 7, 3 (Mar.), 1964, pp. 171-176.
8-G. K. Zipf, “The Psycho-Biology of Language,” Houghton Mifflin, Boston, 1935.
9-J. J. Pollock, and A. Zamora, “Collecting and characterization of spelling errors in scientific and scholarty text,” J. Amer. Soc. Inf. Sci. 34, 1, 1983, pp. 51-58.
10-J. Grudin, “Error patterns inskilled and novice transcription typing. In Cognitive Aspects of Akilled Typewriting,” W. E. Copper, Ed. Springer-Verlag, New York, 1983.
11-B. Van Berkel, and K. DeSmedt, “Triphone analysis, A combined method for the correction of orthographical and typographical errors,” in Proceedings of the 2nd Applied Natural Language Processing Conference (Austin, Tex., Feb.) Association for Computational Linguistics (ACL), 1988.
12-A. V. Aho, “Algorithms for finding patterns in strings,” in Handbook of Theroretical Computer Science, J. Van Leeuwen, Ed. Elsevier Science Publishers, 1990.
13-M. K. Odell, and R. C. Russell, U.S Patent Number 1261167, 1918. 14-E. M. Riseman, and A. R. Hanson, “A contextual postprocessing system for error correction using binary n-grams,” IEEE Trans. Comput. C-23, (May), 480-493, 1974.
15-W. W. Bledsoe, and I. Browning, “Pattern recognition and reading by machine,” in Proceedings of the Eastern Joint Computer Conference, vol. 16, 225-232, 1959.