بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
غلط ياب املائي با استفاده از تکنيک هاي يادگيري ماشين
چکيده : در اينجا يک سيستم غلط ياب املائي مستقل از زبـان ، بـدون نياز به الگوي خطاي از پيش تعين شـده و مبتنـي بـر سـاختار درخـت جستجوي سه تايي وزن دهـي شـده ، پيـشنهاد شـده اسـت سيـستم پيشنهادي ، شکل صحيح کلمه با غلط املائي را بـا اسـتفاده از پيمـايش غير قطعي درخت پيشنهاد مي دهد. به عب رت ديگر مساله غلط يـابي بـه مساله پيمايش درخت با لبـه هـاي وزن دار متغييـر تبـديل شـده اسـت سيستم پيشنهادي با گذشت زمان الگوي خطاي کاربر يا رسـانه را يـاد گرفته و از اين طريق سعي مي نمايد کيفيت پيشنهادات خـود را بهبـود بخشد. در اينجا به جاي استفاده از دانش فرد خبره بـراي مـدل کـردن الگوي خطـا، از تعامـل کـاربر و سيـستم بـراي يـادگيري الگـوي خطـا استفاده مي شود.
واژه هاي کليدي : يادگيري ماشين ، غلط يـاب ، الگـوي خطـا، درخـت جستجوي سه تايي .
١- مقدمه
امروزه با فراگير شدن پديـده اينترنـت ،گـسترش متـون الکترونيکـي و استفاده از واسط هاي مبتني بر پـرس و جـو، وجـود ابزارهـايي کمکـي جهت تسريع و تسهيل در غلط يابي و ارائـه کلمـه پيـشنهادي مناسـب ، اجتنـاب ناپـذير گـشته اسـت . بـراي مثـال حـدود ۱۰ تـا ۱۲ درصـد پرس وجوهاي وارد شده در موتـورهـاي جـستجو و بـيش از ۱۴% تمـام پغرلط س اومجلائهي ي اسارس.ا[ل ۱]شدغله ط براي بازيابي اطلاعات ، شامل عبـارت هـايي بـا ياب ها در حوزه وسيعي از کاربردهـا هماننـد تصحيح و کمک به جستجوي سـريعتر ور دبـه يقمتـتن در اي۴ن]ر[نـ۵]ت [۳] [۲]، تصحيح خطاهاي ناشي از تبـديل تـصوي ، ابزارهـاي جانبي بـراي ويرايـشگرهاي متنـي ، ابـزار پـيش پردازنـده در پـردازش زبان هاي طبيعي ، واسط هاي بازيابي اطلاعات ، تبـديل گفتـار بـه مـتن و کامپيوترهاي مبتني بر قلم بکار مي آيند[۱۰] [۷].
ارائه دانش مربوط به کلمات زبان ( کامپيوتري کردن ديکشنري ) عـلاوه بر ارائه دانش کلمات مربوط به زبان ، سياستها و جهت گيري هـاي کلـي دصرـــطورراتحيـکي ه وصـمـعـرميـاحري تعرسييـ ـسف م شرـاـمدـه شباخشـص ــدـ بي ــکـنه ـدشـاــکن ل دواانژـگش ـــادن [۶][۹][۱۰][۱۱][۱۲][۱۳][۱۴] و در صــورت اســتفاده از روشــها ي تلويحي به شکل مدلهاي آماري [۵] نمود پيدا مـي کنـد. در روش هـاي تلويحي موجوديت کاملا مشخصي به نـام واژگـان وجـود نـدارد و تنهـا احتمال همنشيني کارکترهاي زبان در مجاورت يکديگر نگهـداري م ي - شود. در گروهي از سيستم ها، مسئله واژگان و ارائه آن به تفصيل بررسي شده است . [۱۱] [۱۴]در برخي از کارهـاي انجـام شـده ، واژگـان تنهـا حاوي ريشه کلمات زبان است و از قوانين صـرف زبـان و تحليـل لغـوي براي تشخيص مابقي کلمات زبان اسـتفاده شـده اسـت . [۴] [۹] [۱۰]
[۱۲] در مقابل در گروهي ديگر از کارها، کليه کلمـات زبـان در واژگـان ارائــه شــده اســت و از تحليــل هــاي لغــوي اســتفاده نمــي شــود. [۶][۱۱][۱۴][۱۵] طراحي و پياده سازي واژگان در دسـته اول نـسبت به دسته دوم پيچيده تر است ولي از ميزان فشردگي مناسبي براي ارائـه دانش واژگاني برخوردار مي باشد. يکي از مسائل مهم ديگـر در طراحـي واژگان ، نحوه جـستجو و دسترسـي بـه کلمـه اسـت . متـداولترين روش استفاده از ديکشنري هايي به شکل جدول هاي درهم سازي شـده اسـت .
[۳][۱۳] مشکلات ين روش شـامل چگـونگي تعريـف صـريح و دقيـق کليد، عدم فشرده سازي و انعطاف پذيري پايين است . روش ديگري کـه غالبا در مسائل تبديل تصوير به متن کاربرد دارد، روش گراف چند تايي است . ايجاد يک گراف مناسب از اطلاعات متني که هيچ پردازشـي روي آن انجام نشده است مهمترين مسئله در ايـن روش مـي باشـد. کلمـات پيشنهادي در اين روش الزاما کلمات درستي نخواهند بود. اين روش هـا به عنوان يک پس پردازش براي تبديل تـصوير بـه مـتن بـسيار مـورد استفاده قرار گرفته اند.[۵] يکي ديگـر از روشـهاي متـداول بـراي ارائـه واژگان استفاده از ساختارهاي مبتني بر درخت اسـت . نمونـه اي از ايـن روش در [۲] پيشنهاد شده است که از ساختمان داده درخت جستجوي سه تايي براي بازنمايي واژگان اسـتفاده کـرده اسـت . مزيـت اسـتفاده از ساختارهاي درختي جهت ارائه دانش واژگاني شامل جـستجوي سـريع ، فراهم آوردن امکانات پيشرفته همانند تطبيق جزئي با پيچيدگي زماني و پردازشي مناسب به همراه فشرده سازي قابل توجه در فـضاي ذخيـره سازي است . بطور کلي کامپيوتري کردن ديکشنري شـامل پارامترهـاي انـدازه ديکـشنري [۱۱], مـسله انعطـاف پـذيري و امکـان توليـد کليـه ترکيبات ممکن [۱۴]، ساختار فايل ديکشنري ، بخش بندي ديکـشنري و تکنيک هاي دسترسي به کلمه است . [۱۱]
کارهاي زيـادي جهـت مـدل کـردن الگـوي خطـا و مـشخص نمـودن پارامترهاي آن صورت گرفته است .[۱۸] تقسيم بنـدي هـاي متفـاوتي از الگوي خطا، با توجه به منبع خطا وجود دارد. دسته بنديهاي ارائه شـده براي خط ، به ساختار آوائي و نگارشي هر زبان بـستگي دارد. مـثلا يـک دسته بندي مي تواند مبتني بر شباهت در تلفظ ، خطاي تايپوگرافي [۱۶]
[۱۲] و خطاي فنوتيکي [۱۳] باشد. خطاي تايپوگرافي شامل خطاهـاي ناشي از عادات کاربر و يـا نزديکـي نوشـتاري حـروف اسـت . خطاهـاي فونتيکي ، از شباهت تلفظي حروف با نوشتار متفـاوت ، ناشـي مـي شـود.
الگوهاي خطاي بدست آمده صرف نظر از دسته بندي هاي اعمال شـده ، به عنوان يک راهنما جهت تشخيص محل وقـوع خطـا و رفـع آن عمـل مي نمايند. مشکل اساسي در ين رابطه ، وابستگي الگوي خطا به زبـان و رسانه اي است که سيستم در آن کار مي کند. تشخيص الگوي خطـا بـا توجه به وابستگي آن به زبان و رسانه کـاربرد، کـاري دشـوار ، زمـانبر و عموما نيازمند استفاده از خبرگان زبان اسـت ، هـر چنـد کـه در بيـشتر موارد چنين مدل هايي از دقت و کارائي مقبولي بر خوردار هستند. دقت الگـوي خطـاي بدسـت آمـده شـديدا بـر روي کـارائي سيـستم تـاثير مي گذارد. عموما خطاهاي موجود در نوشتار به دليل يکي از مـوارد زيـر
است . [۲][۷] (شکل شماره ۱):
۱- خطاي جانشيني : استفاده يک حرف به جاي حرف ديگر.
۲- خطاي حذف : حذف ناخواسته يک يا چند حرف .
۳- خطاي درج : درج ناخواسته يک يا چند حرف در کل کلمه .
۴- خطاي جابجايي : جابجايي دو حرف مجاور.
۵- خطاي چسبيدن : چسبيدن دو کلمه درست بدون فاصله .
هر پيشنهاد سيستم براي يک کلمه غلط ، با اعمال يک يا چنـد تغييـراز تغييرات ذکر شده ، بر روي رشته ورودي ، بدست مي آيد. هر چند که در سيستم هاي فعلي همگي اي ن خطاهـا بـا هـم پوشـش داده نمـي شـود.
سيستم غلط ياب براي ارائه يک پيشنهاد صـحيح بـا فـضاي جـستجوي بزرگي روبرو مي شود که در ميان اين پيشنهادات مي بايـستي تنهـا يـک کلمه به عنوان کلمه صحيح انتخاب شود. در يک سيستم غلط ياب هدف اين است که با کمک مدل هاي خطا، فضاي جستجو محدودتر شود تا با کمترين هزينه محاسباتي نزديکترين و بهترين کلمـه صـحيح پيـشنهاد شود.[۱۶]
٢- کارهاي مرتبط
تصحيح خطاي املائي از تاريخچه طولاني در علوم کـامپيوتر برخـوردار مي باشد[١٧] و امروزه تقريبا براي بيشتر زبان هـاي دنيـا سيـستم هـاي غلط ياب املائي وجود دارد .[١٤] اکثر اين سيستم ها در يک محـيط در ارتباط با کـاربر ، اسـتفاده مـي شـوند[۱۳] [۱۵] [۱۶] و سيـستم يـک ليست از کلمات پيشنهادي را توليد مي کند و در نهايت اين کاربر اسـت که کلمه صحيح را انتخاب مي کنـد. در گروهـي ديگـر بـه عنـوان پـس پردازنده براي يک سيستم OCR و يا تبديل گفتار به مـتن ، غلـط يـاب تنها يک پيشنهاد ارائه مي دهد و تقابلي با کاربر ندارد[۴][۵][۶].
متدهاي پيشنهاد شده شامل محدوده وسيعي همانند فاصـله ويرايـشي [٢][١٣][١٦] ، تکنيک هاي مبتنـي بـر قـانون ، تکنيـک هـاي احتمـال [٨][١٥] و مدل هاي گراف چندتايي [٤] [٥]، سيستم هاي خبـره [١٤]، متــدهــاي کليــد شــباهت [١٣] و يــا متــدهــاي ترکيبــي مــي - باشند[٦][٧][١٠]. در اکثر اين روش ها، گام اول تهيه واژگـان مربـوط به زبان و سپس شناسائي الگوهاي خطا در آن زبان خاص است . در گـام بعدي سعي مي شود، الگوهاي خطا مدل شوند و به کمـک ايـن مـدلها محل خطا تشخيص داده شود و راهکار مناسب براي رفع خطـا معرفـي گردد. [٧][١٠][١٥][١٦]
الگوريتم هاي مبتني بر کمترين فاصله ويرايشي معمولا فاصله ويرايـشي را با يک تابع ثابت تعريف مي کنند. کلمـه اي کـه کمتـرين فاصـله را بـا کلمه داده شـده ورودي داشـته باشـد بـه عنـوان کلمـه برنـده انتخـاب مي گردد .به عنوان مثال يک تابع فاصله ويرايشي بسيار ساده مي تواند به کمک اختصاص دادن وزن به هر يک از تبديلاتي که بايد انجام گيرد تـا کلمه به شکل صحيح خود بازگردد مانند درج و يا حذف يـک کـارکتر و اعمال اپراتورهاي رياضي ساده بر روي آنهـا تعريـف شـود.[٧] [١٣] در اين روش نحوه تعريف فاصله ، اعم از تعداد اعمال در نظـر گرفتـه شـده ، ترتيب و وزن آنها بر دقت الگوريتم تاثير مي گذارد. در اين روش ها دقـت و سرعت الگوريتم به چگونگي تعريـف فاصـله ويرايـشي بـستگي دارد و بسته به تعريف ، مي تواند انعطاف پذير باشد.
در متد کليد شباهت ، يک تابع براي تبديل کلمه به يک کليد شـباهت ، که نمايش دهنده مشخصات کلمه است ، ارائـه شـود. از مقايـسه کليـد شباهت کلمه مورد تست و کليد شباهت مربوط به کلمـات واژگـان ، بـه منظور پيشنهاد ليست کلمـات درسـت اسـتفاده مـي شـود.[١٠] مثـال متداول براي اين روش سيستم هاي SoundEX و الگوريتم هاي متافون براي توليد کليد کلمـات مـي باشـد[١٣]. در ينجـا از پارامترهـاي تـابع تبديل براي مدل کردن الگوهاي خطا استفاده مي شود. در ين متد غالبا از ساختار جدول هاي درهـم سـازي شـده ، بـراي ارائـه دانـش واژگـاني استفاده مي شـود و تـابع تبـديل نقـش تـابع آدرس دهـي را بـر عهـده دارد.[١٣] اين روش بسيار وابسته به الگوي خطـا بـوده و دقـت آن بـه چگونگي تعريف کليد شباهت بست ي دارد و از انعطـاف پـذيري نـسباتا پاييني بر خوردار است . سادگي الگوريتم به لحـاظ سـاختاري ، سـرعت مناسب و دقت بالا براي زماني که مدل خطا به درسـتي شـناخته شـده باشد، از مزاياي اين روش است .
در روشهاي مبتني بـر مـدل گـراف چنـدتايي ، احتمـال وقـوع رشـته کاراکترهاي يک کلمه محاسبه مي شود. اين متد ، جزء معدود متـدهايي است که دانش واژگاني در آن به شکل تلويحي ارائه شده است .[٤] [٥] در[١٢] يک معماري تطبيق پذير براي سيستم غلط ياب املائي معرفـي شده است . تطبيق پذيري در اينجا به معني يادگيري فرکانس يـک نـوع خطاي خاص همانند درج ، حذف و ... است . يادگيري فرکانس انواع خطا سبب بهبود پيشنهادات اين سيستم شده است . ولي الگوي خطا ثابـت و از پيش تعريف شده مي باشد.
٣- غلط ياب املائي ديجيتال کلون
غلط ياب املائي پيشنهادي يک غلط ياب تطبيق پذير، مستقل از زبـان و مبتني بر ساختار درخت جستجوي سه تايي است که در آن پيمايش بر روي يال هاي رخت با هزينه متغيـر انجـام مـي شـود. روش پيـشنهادي ، امکان يادگيري مدل خطا را چنان فراهم مي آورد که پاسـخ سيـستم بـا گذشت زمان بـراي شـرايط مـشابه ، تغييـر و بهبـود يابـد. در سيـستم پيشنهادي ، به کمک تقابل ميان سيـستم و کـاربر معمـولي ، اسـتخراج مي شود. الگوي خطا با اختصاص وزن به يالهاي درخت ترنـري و تغييـر آن با توجه به بازخو هاي کاربر،توسط سيستم ياد گرفته ميشود.
شکل ٢ شماي کلي سيستم را نمايش مي دهـد. غلـط يـاب از ٣ بخـش اصلي شامل تصحيح کننده املايي ، پيمانه يادگيري و تطبيق ، واژگان و ماتريس هزينه ها تشکيل شـده اسـت . تـصحيح کننـده املائـي وظيفـه تشخيص خطا و ارائـه پيـشنهادهاي مناسـب را بـر عهـده دارد. وظيفـه پيمانه يادگيري و تطبيق محاسبه تغييرات هزينه انتقال و وزن يال هـاي درخت است . واژگان ، دانش واژگاني زبان را نگهداري مي نمايـد. الگـوي خطا بصورت ضمني به کمک وزن لبه ها در ماتريس هزينه ها مدل شـده است ، علاوه بر اين از دو حد آستانه براي کنترل انداره فـضاي جـستجو در ارائه کلمات صحيح ، استفاده حـد آسـتانه عمـومي تعـداد
مـي شـود.
کلمات تشکيل دهنده يک پيشنهاد را کنترل مي کند. علاوه بر اين حـد آستانه محلي يک محدوديت براي انجام هر يک از تبديلات بر روي اجزا شکيل دهنده پيشنهاد، فراهم مي آورد.
شکل ٢- پيمانه ها و ارتباط آنها با يکديگر.
رشته ورودي توسط پيمانه تصحيح کننده املايـي گرفتـه مـي شـود. در صورتيکه کلمه متعلق بـه واژگـان زبـان نباشـد، بـا اسـتفاده از وزنهـاي اختصاص داده شده به لبه هـا، مـسير مشخـصي از درخـت جـستجوي ترنري واژگان پيمايش مي شود. ليست کلمات استخراج شده بـه همـراه اطلاعات مربوط به نحوه توليد و هزينه ساخت آنهـا، در ليـست کلمـات پيشنهادي ذخيره مي شود. ليست کلمات پيشنهادي بـر اسـاس هزينـه مرتب و براي کاربر فرستاده مي شوند. بسته به انتخاب کـاربر مبنـي بـر ذخيره اين کلمه و يا انتخـاب يـک پيـشنهاد، رشـته ورودي در واژگـان ذخيره مي گردد و يـا هزينـه انتقـال ، در مـاتريس هزينـه هـا و وزنهـاي اختصاص داده شده به لبه ها تغيير مي يابد.در ادامـه هـر يـک از اجـزاي سيستم به تفصيل تشريح شده اند.
٣-١ واژگان
دانش واژگاني در اين سيستم به کمک يک درخت جستجوي ترنري که يال هاي آن وزن دهي شده اند، بازنمـائي شـده اسـت . درخـت ترنـري اولين بار در [١٩] معرفي شده است . ساختمان داده در درخت ترنري به گونه اي است که رشت هاي اوليه مشترک ميان داده هاي ذخيره شـونده ، تنها يک بار ذخيره مي شوند. در اين روش در هـر گـره از درخـت ، يـک حرف ذخيره مي شود. هر گره به سه گـره چـپ ، وسـط و راسـت اشـاره مي کند. اشاره گر سمت چپ به حرف با کد کوچکتر و اشاره گـر سـمت راست به حرف با کد بزرگتر اشاره مي کند . (شکل ٣) اشاره گر وسط به کاراکتر بعدي در رشته ورودي اشاره مي کند. پيمـايش درخـت توسـط گره هاي سمت چپ و راست ، سبب پيمايش در رشته ورودي نمي شود.
۳-۲ ماتريس هزينه ها
يال هاي درخت با توجه به گره هاي مبدا و مقصد سـازنده آنهـا دسـته بندي شده اند. هر دسته از اين يالها يک وزن اختصاص داده شده است .
وزن مربوط به لبه ها در ماتريسي به نام ماتريس هزينه ها ذخيـره شـده است . هزينه مربوط ه يک يال با مراجعه به خانه اي از ماتريس هزينه ها که انديس سطر و ستون هاي آن به ترتيـب برابربـا مقـدار گـره مبـدا و مقصد (کارکتر مبدا و مقصد) است ، استخراج مي شود. عـلاوه بـر ايـن براي افزودن قابليت يادگيري اعمال درج و حذف ، يک سطر و ستون بـا برچسب NULL براي ذخيـره هزينـه هـاي درج و حـذف بـه مـاتريس هزينه ها افزوده شده است . شکل شـماره ٣ قـسمتي از ايـن مـاتريس را نمايش مي دهد. (شکل ٣)
۳-۳ پيمانه تصحيح کننده خطا
با توجه به معماري در نظر گرفته شده ، فرايند غلط يابي به پيمايش غير قطعي يک درخت با لبه هاي وزن دار تبديل شده است . پيمانه تـصحيح کننده خطا به کمک پيمايش درخت ، ليست کلمات پيشنهادي صـحيح را براي کاربر فـراهم مـي نمايـد. فراينـد جـستجو جهـت ارائـه ليـست
پيشنهادات به شکل زير است :
١. اگر کاراکتر ذخيره شده در گره جـاري بـا کـاراکتر جـاري از رشـته ورودي يکسان باشد بر روي رشته و درخت پيمايش مي شـود در غيـر اينصورت ، کاراکتر جاري در رشته ورودي با توجـه بـه هزينـه در نظـر گرفته شده در ماتريس هزينه ها به کارکتر ذخيره شـده در گـره جـاري درخت تبديل مي شـود و ايـن تبـديل و هزينـه مربـوط بـه آن ذخيـره مي شود. در صورتيکه گره جاري انتهاي کلمه باشد، کلمه پيشنهاد شده ذخيره مي شود و با مراجعه به ريشه درخت سعي در پيمـايش مـابقي رشته مي نمايد به شرط آنکه مجموع هزينـه هـاي انجـام شـده از حـد آستانه محلي و حد آستانه عمومي بيشتر نشود. در صورتيکه گره جاري انتهاي کلمه نباشد؛ بـه پيمـايش مـابقي رشـته از اشـاره گـر وسـطي پرداخته مي شود.
٢. اگر کاراکتر ذخيره شده در گره جـاري بـا کـاراکتر جـاري از رشـته ورودي يکسان نباشد، و همچنين هـيچ جابجـائي تـا بـه حـال صـورت نگرفته باشد، در صـورتيکه جابجـايي کـارکتر جـاري رشـته ورودي بـا کارکتر بعد از آن امکان پذير باشد ، جابجائي انجـام مـي شـود و مـابقي درخت پيمايش مي شود.
٣. اگر کاراکتر ذخيره شده در گره جاري بـا کـاراکتر جـاري از رشـته ورودي يکسان نباشد آنگاه اگر امکان تبـديل کـارکتر جـاري در رشـته ورودي به کاراکتر پوچ با توجه به هزينه هاي استخراج شده از ماتريس و مقايسه آن با حدهاي آسـتانه محلـي و عمـومي ؛ وجـود داشـته باشـد، کارکتر جاري حذف مي شود و ادامه پيمايش درخـت از گـره جـاري بـا توجه به کارکتر بعدي در رشته ورودي صورت مي گيرد.
٤. اگرکاراکتر ذخيره شده در گـره جـاري بـا کـاراکتر جـاري از رشـته ورودي يکسان نباشد، آنگاه اگر امکان تبـديل کـاراکتر پـوچ در رشـته ورودي به کاراکتر گره جاري با توجه به هزينه هـاي اسـتخراج شـده از ماتريس هزينه ها و مقايسه آن با حد آسـتانه محلـي و عمـومي ؛ وجـود داشته باشد، کاراکتر گره جاري درج مي شود و ادامه پيمايش درخت از گره وسطي باتوجه به کاراکتر جاري در رشته ورودي صورت مي گيرد.
٥. پيمايش بالا براي گره هاي سمت چپ و راست نيز آزمايش مي شـود.
عمليات فوق تا رسيدن به انتهاي رشته ورودي يا رسيدن به گـره پـوچ ادامه مي يابد.
٣-۴ يادگيري و تطبيق
وظيفه پيمانه يادگيري و تطبيق ، يادگيري الگـوي خطـاي کـاربر و درج کلمات جديد در واژگان است . در صورتيکه کاربر کلمـه اي را وارد نمايـد که در واژگان وجود نداشته باشد، سيستم کلمه مورد نظر را بـه عنـوان يک کلمه غلط شناسائي خواهد نمود. در صورتيکه کاربر تمايـل داشـته باشد، مي تواند کلمه خود را به واژگان بيفزايد. فرايند اضافه نمودن کلمه جديد به واژگان دقيقا مشابه درج يـک کلمـه در سـاختار داده درخـت جستجوي سـه تـايي اسـت . در صـورتيکه کـاربر يکـي از گزينـه هـاي پيشنهادي سيستم را به عنوان کلمه صحيح مورد نظـر انتخـاب نمايـد، اين انتخاب سبب تغيير مقـادير هزينـه هـاي ذخيـره شـده در مـاتريس هزينه ها و وزن يالهاي درخت خواهد شد. تغييرات هزينه ها با توجـه بـه
رابطه (۱) صورت مي گيرد.
که در آن α نرخ يادگيري ، index انديس کلمه در ليست پيشنهادي و selected انـديس کلمـه صـحيح و COT مقـدار هزينـه انتقـال يـک کاراکتر به کاراکتر ديگر در ماتريس هزينه ها باشد
۳-۵ حدود آستانه
حد آستانه محلي بر مبناي طول هر کلمه پيشنهادي تعريف مي شـود و حد آستانه عمومي نيز بر مبنـاي طـول رشـته ورودي و تعـداد کلمـات سازنده هر پيشنهاد در ليست نهايي تعريف مي گردد. اگر طـول کلمـات پيشنهادي با استفاده از Lsuggest و طول رشته ورودي با Linput نمـايش داده شود و Nwords ، تعداد کلمات ليست پيشنهادي باشد. يک تعريـف ساده براي حد آستانه محلي و عمومي مي تواند بصورت (۲) و (۳) مي -
باشد.
بطوريکه λ، ماکزيمم نرخ عدم شباهت براي کنتـرل عمـق جـستجو در درخت باشد و γ نرخ محدود کننده براي تعداد کلمات پيشنهادي است .
۴- ارزيابي سيستم پيشنهادي
براي آزمايش الگوريتم ، بانک اطلاعاتي از کلمات نادرست بدسـت آمـده ار دفترهاي ديکته بعضي از دانش آموزان مقطع چهارم و پنجم ابتـدايي در مناطق ١٣ و ١٤ تهران از تاريخ ٨٣.١٠.٢٥ تـا ٨٤.١.٢٢. و کلمـات نادرست هنگام تايپ که از مراکز تايپ ميدان انقـلاب تهـران و قبـل از چک پرينت از تاريخ ٨٣.٨.١٤ تا ٨٣.١٠.٢٤ جمع آوري شده است .
در مجموع ٥٥٩٥ کلمه نادرسـت بـه همـراه شـکل درسـت شـان تهيـه گرديد. بانک اطلاعاتي به دو بخش تقسيم شده است : يکي براي آموزش سيستم و ديگري براي ارزيابي سيستم . مجموعه آموزشي شـامل ٣٨٢٧ کلمه و مجموعه آزمايشي شـامل ١٧٦٨ کلمـه مـي باشـد. در جـدول ١ تعداد و نوع خطاها آورده شده است . در جدول ٢ براي هر يک از انـواع خطا مثالي آورده شده است . براي انجام تـست ، از يـک واژگـان شـامل ٤٠٠٠٠ لغت معمول فارسي استفاده شد.
دقت سيستم مطابق فرمول (۴) محاسبه شده است . فرمول ارائـه شـده بـراي Precision، بـه لحـاظ اهميـت رتبـه کلمـه در ليـست کلمـات پيشنهادي با نمونه هاي کلاسيک آن متفاوت است .
کلمـــه iام و
کـــه در ايـــن فرمـــول N تعـــداد کـــل کلمـــات ، SuggestNowi شماره ايندکس کلمه مورد نظر در ليـست پيـشنهادي براي کلمه iام در مجموعه تست و يا آموزش است
