راهنمایی در مورد برنامه غلط یابی

[arm672001]

من می خواهم یک برنامه بنویسم که یک متن که دارای تعدادی غلط املایی است را از ورودی خوانده سپس غلط ها را با توجه به یک فایل دیکشنری که در اختیار داریم شناسایی کرده و گزارش دهد می خواستم در مورد الگوریتم های مورده استفاده آن من را راهنمایی کنید

[khabarkhan]

ابتدا باید دیکشنری را در یک ساختار داده مناسب وارد کنیم به اصطلاح دیکشنری را load کنیم .برای پیاده سازی این دیکشنری از ساختار های داده ی متفاوتی(لیست ،لیست های پرش، hashtable ، درخت و... )می توان استفاده کرد اما آنچه که برای ما مهم است کل زمان لازم برای load کردن دیکشنری است.بهترین ساختار داده برای پیاده سازی دیکشنری درخت های جست و جوی دودویی می باشند از جمله درخت های (4و2) ،AVL،(a,b B-tree، قرمز-سیاه و... اما من درخت قرمز-سیاه را پیشنهاد می کنم ،شما می توانید کارایی یک درخت قرمز-سیاه را در کتاب های مختلف مطالعه کنید اما عملیات درج،حذف و جست وجو در این درخت در بدترین حالت به (O(logn می رسد.
بعد از پیاده سازی دیکشنری شما باید فایل حاوی متن غلط دار را به صورت توکن به توکن بخوانید و هر توکن را با متد جست و جوی درخت قرمز-سیاه در دیکشنری جست وجو کنید و این کار را تا انتهای فایل ادامه دهید تا تمام به اصطلاح Misspelled ها پیدا شوند ( به همین سادگی!!!..:لبخندساده: ).

[manager]

البته در تکمیل صحبت های این دوست عزیزمون باید بگم یک الگوریتم معروف و قوی برای شناسائی ریشه کلمات وجود داره که بهتره از اون استفاده کنید تا بتونید حجم دیتابیستون رو کاهش بدید. اگر در مورد این الگوریتم تحقیق کردید و موارد خوبی گیر آوردید برای مردم در این بخش قرار بدید تا این بحث مفید واقع بشه.
و اما اگر خواستید تحقیق کنید :
دسته ای از الگوریتم ها برای Stemming وجود دارند که به Stemmerها معروف هستند البته من اطلاعات دقیق در مورد این الگوریتم ها ندارم ولی می دونم که الکوریتم Porter می تونه شروع خوبی برات باشه.
اطلاعات بیشتر در مورد Stemming (http://en.wikipedia.org/wiki/Stemming)
What is Stemming? (http://www.comp.lancs.ac.uk/computing/research/stemming/general/)
الگوریتم Porter (http://tartarus.org/%7Emartin/PorterStemmer/)

سایر اطلاعات .... (http://www.google.com)