رده:ریشه یاب

از دانشنامه فناوری وب
پرش به: ناوبری، جستجو

ریشه‌یابی

زبان فارسي يک زبان هندي- اروپايي است که در کشورهاي ايران، افغانستان و تاجيکستان از اين زبان استفاده مي‌گردد. الفباي فارسي شامل 32 حرف است، و از راست به چپ نوشته مي‌شود. برخي زبان‌هاي ديگر مانند عربي، کردي و اردو از شکل رسم‌الخط فارسي استفاده مي‌کنند، اما ويژگي‌هاي خاص خود را دارا مي‌باشند. فارسي نيز مشخصه‌هاي ويژه خود را دارد، به عنوان مثال عدم تلفظ علائم تکيه (جز در موارد خاص) و چند شکلي نوشتاري است. اين زبان يکي از زبان‌هايي است که داراي پيچيدگي‌هاي زيادي در نحو و ساخت است و ساخت ابزار مربوط به پردازش زبان طبيعي براي اين زبان چالش‌هاي فراواني را ايجاد مي‌نمايد.
ريشه‌يابي عبارتست از بدست آوردن ريشه کلمات با حذف پسوندها و پيشوندها به طوري که کلمات با ريشه يکسان داراي شکل يکسان گردند. معمول‌ترين هدف ريشه يابي استانده کردن کلمات بوسيله کاهش يک کلمه تا رسيدن به پايه و اساس آن کلمه مي‌باشد. در سيستم بازيابي اطلاعات استفاده از کلمات ريشه‌يابي شده به جاي کلمات اصلي مي‌تواند تا 15 درصد کارايي سيستم را ارتقا دهد. ريشه‌يابي در مسائلي از جمله بازيابي اطلاعات، ترجمه ماشيني، خلاصه سازي و ساير زمينه هاي پردازش زبان طبيعي کاربرد دارد. ولي در روش‌هاي ريشه‌يابي فعلي بعد از حذف وندها ممکن است معناي کلمه تغيير يابد. نکته مهمي که براي ساخت اين ابزار در زبان فارسي بايستي توجه شود، وجود مجموعه‌اي از پيشوندها و پسوندهاي کلمات در زبان فارسي است. اين وندها با اتصال به کلمه معني آن را در جمله اصلاح مي‌نمايند. همچنين زبان فارسي از سمت راست به چپ نوشته مي‌شود و از اينرو پيشوندها به سمت راست و پسوندها به سمت چپ کلمات مي‌چسبند. در زبانهايي مثل زبان انگليسي به دليل ماهيت زبان و شباهت ريشه با کلمه اصلي، انجام عمل ريشه يابي کار آساني است. اما در برخي زبانهاي ديگر مانند زبان فارسي به دليل ماهيت تصريفي زبان، عمليات ريشه‌يابي، فرايند پيچيده‌اي دارد . برخلاف زبان انگليسي، مشکلات مختلفي هنگام ريشه‌يابي کلمات زبان فارسي وجود دارد از جمله اينکه ضماير مي‌توانند به دو صورت جدا و متصل در جمله ظاهر شوند. جدول زیر انواع ضمیرهای زبان فارسی را نشان می‌دهد.
Jadvale 1.2.jpg
البته در مورد افعال مسئله کمي پيچيده‌تر است، به طوري که علاوه بر وندهاي فعلي، شخص (فاعل) و زمان جمله نيز بر روي حالت فعل تاثير گذار هستند. برخي از افعال تصريف شده زبان فارسي در جدول زير نشان داده شده‌اند.
Jadvale 1.3.jpg
در زبان فارسي دو نوع بن گذشته و حال وجود دارد به طوري که براساس زمان جمله هر يک از آنها به شکل مناسبي در قالب فعل قرار مي‌گيرد.
مشکل ديگري که در مورد ريشه‌يابي افعال وجود دارد حالت منفي فعل است. در زبان فارسي پيشوند «ن» پرکاربردترين پيشوند منفي‌ساز است. اين پيشوند منفي‌ساز در جايگاه‌هاي مختلفي از فعل مي‌تواند ظاهر گردد که همين امر تشخصي افعال منفي را مشکل مي‌نمايد.
با توجه به مسائل مطرح شده يک فعل مي‌تواند به حالت‌هاي بسيار زيادي تبديل گردد که تمامي اين حالت‌ها داراي يک ريشه واحد هستند و يک ريشه‌ياب بايستي بتواند آنرا از تمامي حالت‌هاي صرف آن فعل استخراج نمايد.
Jadvale 1.4.jpg
جداسازي و حذف وندها (پسوندها و پيشوندها) کارکرد اصلي ريشه ياب به شمار مي‌رود. اين امر نخستين راه حل براي طراحي ريشه‌ياب است. در حال حاضر، برخي ريشه‌ياب‌هاي فارسي به اين روش عمل مي‌کنند. ليکن، مشکلات و استثنائاتي در ادبيات فارسي وجود دارد که ناديده گرفتن آن‌ها منجر به تقليل چشمگير عملکرد ريشه ياب هاي فارسي مي‌گردد. وندهايي وجود دارد که جداسازي آن‌ها از واژه ريشه‌اي را بدست مي‌دهد که معناي آن بسيار متفاوت از واژه مبداء است. به عنوان مثال، اگر پسوند «ستان» از واژه «پاکستان» جدا شود، بن «پاک» بدست مي‌آيد که بسيار متفاوت از واژه اصلي است. بنابراين، به منظور اجتناب از بروز چنين مشکلاتي، وندها بايد با دقت انتخاب شوند.
در فارسي، برخي واژه‌هاي حساس به وند وجود دارد که به برخي وندهاي معين حساس مي‌باشند. به عنوان مثال، افزودن پسوند جمع «ان» به واژه حساس به وند «دانا» واژه «دانايان» را بدست مي‌دهد که حرف جديد «ي» پيش از اين پسوند در آن ديده مي‌شود. افزودن، حذف يا حتي جايگزيني يک يا چند حرف در واژه مبداء در صورت بکارگيري چنين پسوندهايي با واژه‌هاي حساس به وند پديد مي‌آيد. اگر ريشه ياب صرفاً وندها را حذف کند و اين تغييرات را مورد توجه قرار ندهد، در تطبيق ريشه و تغييرات ريشه ناموفق خواهد بود. در مثال قبل، اگر پسوند جمع «ان» بدون فرآيند بررسي کنار گذاشته شود، واژه «داناي» باقي مي‌ماند که شباهتي با واژه مبداء «دانا» ندارد.
با گذشت زمان، برخي واژه‌ها از زبان‌هاي ديگري مانند عربي، انگليسي و فرانسه وارد زبان فارسي شده است. زبان عربي بيشترين تاثير را داشته است، بنابراين برخي قواعد گرامري عربي وارد زبان فارسي شده و براي واژه‌هاي عربي بکاررفته (عاريتي) در اين زبان مورد استفاده قرار مي‌گيرد. خوشبختانه، اين قواعد اغلب صرفاً براي واژه‌هاي عربي بکار مي‌رود (گاهي اين قواعد براي واژه‌هاي عاريتي غير عربي نيز بکار برده مي‌شود). از اينرو، علاوه بر دستور زبان فارسي، قواعد گرامري وارد شده از زبان عربي نيز مطالعه شده و اين قواعد در ريشه ياب مورد توجه قرار گرفت. عليرغم بررسي فرهنگ نامه، به منظور تعيين زبان اصلي، ريشه ياب سعي در تعيين چهار حرف تبعيضي «پ»، «ژ»، «گ» و «چ» در واژه دارد. هنگامي که ريشه ياب واژه‌اي را عربي مي‌يابد، برخي از کارکردهاي ريشه يابي زبان عربي را بکار مي‌گيرد.
در روش پيشنهاد شده در اين مقاله، هدف بدست آوردن ريشه معنايي کلمات با حذف وندهاي اضافي است به طوري که بزرگ‌ترين واحد معنادار کلمه استخراج گردد. مثلاً کلمه «دانشجويان» داراي سه ريشه «دانشجو» و «دانش» و «دان» است. در روش پيشنهاد شده، هدف رسيدن به ريشه «دانشجو» است. البته در روش پيشنهادي سطوح معنايي مختلف را نيز مشخص کرده و خروجي براساس آن مشخص شود. نکته ديگري که در اين روش توجه شده است، توجه به نقش کلمات است. يعني ابتدا با استفاده از يک الگوريتم افعال را تشخيص داده و سپس در ادامه براساس نوع عبارت (فعل يا غير فعل) ريشه آن استخراج مي‌گردد.

مروری بر کارهای انجام شده

تا کنون الگوريتم‌هاي زيادي براي ريشه‌يابي کلمات معرفي شده است. با اين حال در يک دسته‌بندي کلي مي‌توان دو ايدة اصلي در تمامي آن‌ها جستجو کرد:
• ريخت‌شناسي و برپايه قانون: در اين رويکرد، از قوانين ساخت کلمات استفاده مي‌شود. اين الگوريتم‌ها با بررسي روشهاي ساخت کلمات، ريشة کلمات را پيدا مي‌کنند. مثلاً مي‌توان گفت که رشته "ing" از انتهاي کلمه حذف شود. به عنوان مثال working به work تبديل مي‌شود. اين روش‌ها به علت مشخص بودن روش‌هاي ساخت کلمات امکان مکانيزه شدن خوبي را فراهم کرده‌اند، اما مشکل اصلي در آن‌ها هنگامي رخ مي‌دهد که دو کلمة جامد با دو تغيير مختلف يک کلمة مرکب يکسان مي‌سازند. به عنوان مثال کلمة"goes" مي‌تواند به معناي goe + s به معناي زنبورهاي عسل باشد و يا go + es به معني صورتي از فعل رفتن. همچنين برخي از قوانين استثنائاتي نيز دارند که بايستي در نظر گرفته شود. نمونه‌هايي از الگوريتم‌هاي ريخت‌شناسي الگوريتمهاي معروف پورتر و الگوريتم کراوتز در انگليسي و الگوريتم کاظم تقوا در فارسي هستند.
• استفاده از ديکشنري: در اين رويکرد از تعداي ديکشنري براي تشخيص ريشه و انجام مراحل کار بهره گرفته شده است. به طوري که با استفاده از يک ديکشنري‌هايي براي کلمات ريشه و افعال، مي‌توان ريشه کلمات را تشخيص و استخراج نمود. البته اين روش‌ها در مورد کلمات جديد دچار مشکل مي‌شوند و لغت نامه‌ها بايستي به طور مداوم بروزرساني گردند.
البته برخي روش‌ها نيز به طور ترکيبي از هر دو روش بهره گرفته‌اند که با استفاده از نقاط قوت يکديگر، اين روش نتايج مطلوب‌تري توليد مي‌نمايد. در اين پژوهش، با توجه به تفاوت‌هاي ذاتي که مسئله ريشه يابي در زبان‌هاي گوناگون دارد، کارهاي انجام شده در اين زمينه را در زبان فارسي دنبال می‌کنیم. همانند زبان انگليسي، زبان فارسي داراي ريخت‌شناسي لغوي از نوع اضافه‌اي (پسوندي، پيشوندي) مي‌باشد. به بيان ديگر، پسوندها و پيشوندها به کلمات متصل مي‌شوند تا معاني جديدي را ايجاد کنند. فارسي از راست به چپ خوانده مي‌شود بنابراين پيشوندها به سمت راست ريشه مي‌چسبند و پسوندها به سمت چپ. همچنين مشابه زبان انگليسي، کلمات در زبان فارسي به منظور رساندن مفاهيم مالکيت و فاعليت و جمع دگرگون مي‌شوند؛ ولي با اين حال افعال فارسي نسبت به افعال در انگليسي بيشتر دچار تغيير مي‌شوند. افعال فارسي با توجه به صرف فعل، شخص، حالت نفي و زمان تغيير مي‌يابندبراي زبان فارسي روش‌هاي ريشه‌يابي معدودي وجود دارد که همگي مبتني بر ساختار زبان هستند. در همين راستا اخيراً تلاش‌هايي براي رسمي کردن گرامر فارسي صورت گرفته است. با توجه به اين که فرمال کردن گرامر و قواعد زبان فارسي قدمت چنداني ندارد، در نتيجه توسعه سيستم‌هاي ريشه ياب در زبان فارسي نيز کاري نوپا است و از طرفي شايد غير مشخص بودن ساختارهاي فارسي و وجود استثناهاي فراوان کار ريشه يابي را سخت‌تر کرده است. نکته‌اي که درباره زبان فارسي مي‌تواند قابل توجه باشد آن است که زبان فارسي مانند زبان انگليسي، زباني است که در آن غالباً با پسوند و پيشوند مشتق ايجاد مي‌شود و برخلاف زبان‌هاي عربي ريشه اصلي کلمه از درون تغيير نمي‌کند. مهم‌ترين کارهايي که در مورد ريشه‌ياب‌هاي ساختاري براي زبان فارسي ارائه شده است. عبارتند از کارهاي کاظم تقوي و ارومچيان. همه اين سيستم‌ها به صورت ساختاري مسأله ريشه يابي را حل مي‌کنند و از ماشين حالات محدود بهره مي‌برند.

الگوريتم کراوتز براي زبان فارسي
همان طور که بيان شد براي زبان‌هايي که داراي اشتقاق‌هاي ريختي زيادتري هستند قابليت‌هاي الگوريتم کراوتز بهتر ديده مي‌شود. فارسي و عربي از اين دسته هستند. روشهاي مشابه تنها از ساختارهاي زباني استفاده کرده‌اند که در نتيجه نتايج آن‌ها قابل بهتر شدن مي‌باشد. در زبان فارسي تغييرات در بن ماضي و مضارع تنها به مواردي که بن ماضي يا مضارع با يک حرف صدادار آغاز يا خاتمه مي‌يابد در موارد خاصي انجام مي‌گيرد که اين موارد در الگوريتم کراوتز فارسي در نظر گرفته شده است. در قالب يک جدول، شبه کد الگوريتم کراوتز در ادامه آمده است. اساس الگوريتم براساس ساخت انواع افعال زبان فارسي بدست آمده است.

الگوريتم کراوتز بهبود يافته براي زبان فارسي
الگوريتم کراوتز هرچند داراي نتايج خوبي بوده است. اما مثال‌هايی وجود دارد که اين الگوريتم نمي‌تواند به جواب درست دست يابد.
Jadvale 1.5.jpg
از آنجا که کلمات «روم» و «مانند» در فرهنگ لغت وجود دارد اين اشتباهات رخ مي‌دهد. به همين منظور الگوريتم کراوتز بهبود يافته براي فارسي هم ارائه شده است. در آزموني که براي اين الگوريتم بهبود يافته با 1000 جمله فارسي انجام شد ديده شده است که تعداد اشتباهات در ريشه يابي از 13 مورد ريشه يابي غلط در الگوريتم کراوتز به چهار مورد ريشه يابي غلط در الگوريتم کراوتز بهبود يافته فارسي، کاهش يافته است.
Jadvale 1.6.jpg

الگوريتم ريشه‌ياب تقوا
الگوريتم ريشه‌ياب که در اينجا مورد بحث قرار مي‌گيرد، شباهت زيادي به الگوريتم پورتر در انگليسي دارد. هر دو الگوريتم بر مبناي ريخت‌شناسي هستند. همچنين هر دو ريشه‌ياب به دنبال پسوندهاي خاصي جستجو مي‌کنند و مراحل مختلفي را بر طبق ليست قوانين پسوندي پشته گذاري شده طي مي‌کنند. علاوه براين هر دو کران پائيني را براي اطلاعاتي که ريشه بايستي داشته باشد، در نظر مي‌گيرند. با اين حال تفاوت‌هاي مهمي بين اين دو الگوريتم وجود دارد. براي مثال الگوريتم ريشه‌ياب پورتر به منظور تخمين محتواي اطلاعات، الگوي حروف صدادار و بي صدا را تشخيص مي‌دهد؛ اما در فارسي بسياري از حروف صدادار نوشته نمي‌شوند، بنابراين ريشه‌ياب فارسي از طول رشته براي تعريف کران پائين محتواي ريشه استفاده مي‌کند. (در حال حاضر مينيمم طول ريشه 3 است). اين محدوديت در بعضي موارد باعث خطا مي‌گردد به خصوص زماني که يک زيررشته که قسمتي از يک کلمة کوتاه است، به اشتباه به عنوان يک پسوند در نظر گرفته شود. تفاوت ديگر اين دو الگوريتم آن است که اين الگوريتم بر خلاف الگوريتم پورتر، پيشوندها را هم شناسايي مي‌کند. کاظم تقوي، راسل به کلي و محمد ساده اين ريشه ياب را در سال 2005 طراحي کردند. در اين الگوريتم ساختواژه زبان فارسي و ماشين DFA با 40 گام براي حذف پسوند و پيشوند استفاده شده است.
اولين مرحلة ريشه‌ياب آن است که زيررشته اي از کلمة ورودي که در ليست انواع پسوندهاي متداول فارسي موجود است، يافته شود. اگر چندين پسوند با کلمه، مطابقتِ پسوندي داشته باشند، آنگاه همانند الگوريتم پورتر، طولاني‌ترين پسوندي که با حذف آن پسوند، ريشة باقيمانده حداقل سه حرف داشته باشد، انتخاب مي‌گردد. کلمة «دستشان» را در نظر بگيريد. هردو پسوند جمع «ان» و پسوند مالکيت «شان» با انتهاي کلمة مفروض مطابقت مي‌کنند؛ حذف «ان» 4 حرف و حذف «شان» 3 حرف را در کلمة مفروض باقي مي‌گذارد، از آنجا که با حذف هر يک از اين دو پسوند، ريشه باقيمانده، حداقل ِطول يعني 3 را دارا مي‌باشند، بنابراين از بين اين دو پسوند، پسوند «شان» که طولاني‌تر است براي حذف انتخاب شده و ريشه باقيمانده «دست» است.
پسوندها به صورت پسوندهاي فعلي، پسوندهاي اسم جمع، پسوندهاي اسم مالکيت و پسوندهاي اسم غير (مثل «نده») و ساير پسوندها (مثل «تر»)طبقه بندي مي‌شوند. اين گروه‌بندي باعث هدايت در حذف پيشوندها از افعال و حذف چندين پسوند از يک اسم مي‌گردد. اگر ريشه‌ياب در ابتدا پسوند «ند» را در کلمة «رفتند» به عنوان پسوند فعلي شناسايي کند، در ادامه مي‌تواند پسوند «ن» را شناسايي کرده و آنرا حذف کند تا سرانجام ريشة «رفت» حاصل گردد. پسوندهاي اسمي‌بر طبق الگوي زير از راست به چپ به ريشه افزوده مي‌شوند:
Kadre rishe va motealleghat1.jpg
براي مثال در کلمة «خواننده‌هايمان» در ابتدا ريشه‌ياب پسوند مالکيت «يمان» را مي‌يابد، سپس پسوند جمع «ها» را مي‌يابد و سرانجام پسوند اسمي غير «نده» (که به معناي عامليت کاري است) را مي‌يابد تا اينکه با حذف متوالي اين 3 پسوند ريشه که «خوان» است بدست آورد. به علاوه، چندين حالت غير معمول وجود دارد. معمولاً هنگامي‌که ريشه‌ياب پسوند «تان» را مي‌يابد آن را حذف مي‌کند. با اين حال وقتيکه «س» قبل از اين پسوند بيايد، اين پسوند يعني «ستان» را حذف نمي‌کند، چراکه پسوند «ستان» در فارسي اغلب براي اسامي مناطق و کشورها استفاده مي‌شود مثل «کردستان». ريشه‌ياب «ستان» را حذف نمي‌کند چون در صورت حذف آن نتيجة حاصل يعني «کرد» براي موتور جستجو مفيد نيست. استثناي ديگر آن است که ريشه‌ياب پسوندهاي فعلي «د» و «ت» را پيدا مي‌کند ولي آن‌ها را حذف نمي‌کند.
در بسياري از موارد، ريشه‌ياب به حرف ماقبل پسوند مفروض نگاه مي‌کند. اغلباً اين حرف ماقبلِ پسوند به منظور تشخيصِ پسوند بودنِ زيررشتة انطباق داده شده و اينکه آيا بايستي اين پسوند حذف شود يا خير، مورد استفاده قرار مي‌گيرد؛ در اين موارد در صورت حذف پسوند، حرف ماقبل پسوند حذف نمي‌شود.
به منظور پياده سازي الگوريتم، ريشه‌ياب فارسي از اتوماتاي نامتناهي معين (DFA) که 70 حالت دارد استفاده مي‌کند. رشتة ورودي DFA از معکوس کردن رشته ورودي ريشه‌ياب حاصل مي‌شود. شکل زير قسمتي از اين اتوماتا که پسوندهاي "تان"، "هايم" و "ان" را پيدا مي‌کند را نشان مي‌دهد.
Shekle 1.1.jpg
DFA به صورت يک آرايه دوبعدي کُد مي‌شود. رديف‌ها نمايانگر حالات و ستون‌ها نمايانگر حروف ورودي هستند. جدول زير چنين آراية دوبعدي معادل با ماشين شکل فوق را نشان مي‌دهد.
Jadvale 1.7.jpg
DFA از پايان ورودي ريشه‌ياب شروع مي‌کند و تا به سومين حرف از ورودي از ابتدا ادامه مي‌دهد. DFA هرگز دو حرف ابتداي کلمه (از سمت راست) را چک نمي‌کند. در هر دور چرخش DFA با مشاهدة داده در رديف s وستون l، حالت بعدي را مشخص مي‌کنند ( s حالت فعلي و l کاراکتر ورودي است). هنگامي که ماشين DFA به يک حالت نهايي مي‌رسد، کلمه و شماره حالت به پس پردازشگر براي حذف پسوند فرستاده مي‌شود. براي مثال اگر ما بخواهيم ريشة کلمة «زمان» را بيابيم، دو حرف ابتداي آن يعني «زم» را حذف کرده و باقي حروف را به DFA مي‌دهيم. مي‌توان متوجه شد که DFA در حالت 3 که يک حالت NIL است پايان مي‌پذيرد. در هر مورد هنگامي که حذف تنها پسوند ممکن در کلمه، موجب برجاماندن ريشه اي بسيار کوتاه مي‌گردد، حالت نهايي NIL خواهد بود. از سويي ديگر ريشه‌يابي کلمة «پسران» حالت 8 را برمي‌گرداند.
پس پردازشگر از حالت نهائي براي تعيين گروه پسوندي استفاده مي‌کند. SuffixGroup[] يک آراية يک بعدي است. اگر F حالت نهايي باشد، SuffixGroup[F] مشخصه‌اي براي گروه پسوندي مي‌دهد. اين مشخصه به منظور جداسازي پسوندها استفاده مي‌شود. براي مثال در مورد کلمة «زمان»، SuffixGroup[3]، NIL را بر مي‌گرداندکه به معناي آن است که هيچ پسوندي از اين کلمه جدا نمي‌شود (حروف باقيمانده ريشه درست، ولي بسيار کوتاه هستند). در مورد کلمة «پسران»، SuffixGroup[8]، PL2 را بر مي‌گرداند که مشخصة آن است که کلمة مورد نظر جمع است و دو حرف از آن بايستي حذف گردند. بنابراين ريشه‌ياب کلمة «پسر» را برمي‌گرداند. جدول زير آراية SuffixGroup را براي اتوماتاي شکل طراحي شده، نشان مي‌دهد.
Jadvale 1.8.jpg
اگر پسوند تشخيص داده شده، پسوند مالکيت يا پسوند جمع باشد، پس پردازشگر، کلمة جداسازي شده را به DFA مي‌دهد تا بقية پسوندها شناسايي شوند. اگرپسوندهاي پشت سرهم پيدا شوند، در صورتيکه اين پسوندها به کلاسهاي اسمي درستي متعلق باشند، پس پردازشگر آن‌ها را حذف مي‌کند. هنگامي که پس پردازشگر يک حالت پسوند فعلي را يافت (همانند حالت 10 در شکل DFA)، آنگاه کلمة جداسازي شده را به اتوماتاي پيشوندي مي‌فرستدکه اين اتوماتا شبيه اتوماتاي پسوندي است.

بهبود الگوريتم کاظم تقوي
کلماتي وجود دارند که از لحاظ ساختاري به کلمات ديگر شبيه هستند، اين کلمات نبايد با استفاده از ريشه ياب پيشوند و ريشه ياب پسوند مورد استفاده قرار بگيرند. به عنوان مثال اولين حرف از کلمه غيرفعلي «برنامه»، «ب» است که شبيه به پيشوند افعال امري در فارسي هستند. اما حرف «ب» نبايد حذف شود. يا کلمه «نيمکت» با «ن» شروع مي‌شود که شبيه به افعال منفي مي‌باشد و همچنين به «ت» ختم مي‌شود که شبيه ضماير ملکي است. اما اين حروف نبايد به عنوان پسوند يا پيشوند حذف شوند. همچنين اسامي جمعي در زبان فارسي وجود دارد که مکسر ناميده مي‌شوند و قواعد خاصي براي ساخت آن‌ها وجود ندارد. قواعد فعلي براي پيدا کردن ريشه اين چنين کلمات نمي‌تواند مورد استفاده قرار بگيرد. همچنين اين الگوريتم محدوديت ديگري که دارد اين است که نتايج ريشه بايد سه حرف يا بيشتر داشته باشد. اما کلماتي وجود دارد که طول ريشه آن‌ها کمتر از سه حرف است. براي مثال فعل «مي‌کنيم»، الگوريتم واژه «مي» را به عنوان پيشوند حذف مي‌کند. سپس «يم» را به عنوان بزرگ‌ترين پسوند شناسايي مي‌کند اما اگر الگوريتم «يم» را حذف کند قسمت باقي مانده تنها شامل دو حرف مي‌شود. بنابراين الگوريتم تنها «م» را حذف مي‌کند و «کني» را به عنوان ريشه برمي گرداند در حالي که ريشه درست «کن» است، بنابراين پايگاه داده اي جهت ذخيره سازي ريشه اين کلمات استفاده شد و الگوريتم با در نظر گرفتن اين استثناها بهبود يافت.
يک پايگاه داده براي بهبود در ريشه يابي مورد استفاده قرار گرفت. در اين پايگاه داده کلمات غيرفعلي که با واژه اي شروع مي‌شود که شبيه به پيشوند فعل ساز است و يا کلماتي که به واژه اي ختم مي‌شوند که شبيه به پسوند هستند، ذخيره مي‌شود. اما اگر بعد از حذف اين واژگان قسمت باقي مانده از کلمه کمتر از سه حرف داشت، اين کلمات نبايد در پايگاه داده ذخيره بشوند. براي مثال کلمه «ميوه» با «مي» شروع مي‌شود که شبيه به پيشوند فعل ساز «مي» در فارسي مي‌باشد، اما اين پيشوند نيست. اگر قسمت «مي» حذف شود قسمت باقي مانده «وه» تنها دو حرف دارد. بنابراين اين کلمه نبايد داخل پايگاه داده ذخيره شود. يا کلمه «نيما» که با «ن» شروع مي‌شود که شبيه به ساختار فعل منفي است. اگر حرف «ن» حذف شود قسمت باقي مانده سه حرف خواهد داشت. بنابراين کلمه «نيما» بايد در پايگاه داده ذخيره شود. همچنين بعضي از کلمات جمع به نام مکسر و مفرد آن‌ها داخل پايگاه داده ذخيره مي‌شوند. در شروع الگوريتم کلمه بايد در پايگاه داده جستجو شود در صورت پيدا شدن ريشه آن برگردانده مي‌شود، در غير اين صورت حذف پسوندها و پيشوندها به وسيله توابع الگوريتم‌ها انجام مي‌گيرد.
به علاوه بعضي از کلماتي که ريشه آن‌ها کمتر از سه حرف دارد در پايگاه داده ذخيره مي‌شوند. اگر بعد از حذف اين پسوندها و پيشوندها ريشه‌ياب با ريشه‌اي کمتر از سه حرف روبرو شد، ابتدا در پايگاه داده جستجو انجام مي‌دهد. اگر ريشه در پايگاه داده پيدا شد، برگردانده مي‌شود. اما اگر پيدا نشد ريشه‌ياب نمي‌تواند پسوند يا پيشوندي را حذف کند.
الگوريتم Perstem
الگوريتم Perstem يک ريشه ياب لغت و تحليل‌گر ساخت واژه آسان براي زبان فارسي است که به وسيله Jon Dehdari نوشته شده است. اين ريشه ياب با استفاده از زبان پرل نوشته شده است و از يک مجموعه اصطلاحات با قاعده که جايگزين‌هايي براي تک واژهاي صرفي جدا از ريشه است، استفاده مي‌کند. ورودي ممکن است در قالب کدهاي UTF-8، Windows-1256، ISIRI 3342، موجوديت کاراکتر HTML، يا متن‌هايي که در آن از حروف عادي استفاده شده است، نوشته شده باشد. ورودي سپس به طور هم ريختي به يک ساختار دروني براي اجرا و ثبات داخلي ترسيم شده است.
کلمات ابتدا در يک جدول درهم مورد جستجو قرار مي‌گيرند، و اگر کلمه با يک کليد تطبيق پيدا کند، ارزش وابسته، خروجي و محصول است و هيچ جايگزيني اصطلاح با قاعده‌اي اتفاق نمي‌افتد. اين گام ابتدايي استفاده از يک جدول درهم که هدف‌هاي چندگانه را ارائه مي‌کند، مي‌باشد. هدف عمده، اين است که در رفتار بيشتر کلماتي که به طور عادي اتفاق مي‌افتند، تسريع شود. پذيرفتن يک نسخه پنهان شده از تحليل ساخت واژه براي اينکه خروجي باشد به جاي اينکه يک کلمه تکرارشونده به تعداد زيادي از جايگزيني‌ها و تطابق‌هاي اصطلاح باقاعده غلبه کند. يک مثال از اين نمونه ورودي در جدول درهم، در خط اول جدول زیر تشخيص داده مي‌شود.
Jadvale 1.9.jpg
هدف ديگري که جدول انتخابي درهم به کار مي‌گيرد، کمک کردن به ترکيب‌هاي صيغه جمع شکسته ريشه کلمات معمولي مي‌باشد. صيغه جمع شکسته در فارسي، ترکيب‌هاي غير عادي اسامي جمع هستند که به عربي شکسته مي‌شوند. روش‌هاي باقاعده براي تحليل يا ريشه يابي اين کلمات وجود ندارد، چنان که يک جدول انتخابي براي اين ترکيب‌ها ايده‌آل است. خط دوم از جدول فوق صيغه جمع شکسته از «ک ت ب» کتب "books " را نشان مي‌دهد، که به شکل ساده کتاب تفکيک مي‌شود.
هدف سوم حذف کلمات صامت است. اين‌ها رشته‌اي خالي دارند که ارزش وابسته‌شان در جدول درهم در خط سوم از جدول فوق نشان داده شده است. هدف نهايي جدول درهم، تصحيح معدود کلمات با تکرار زياد است که در غير اين صورت به طور نادرست به وسيله اصطلاحات باقاعده ريشه لغت گرفته مي‌شود. خط چهارم از جدول فوق، عبارت سازمان organization"" را نشان مي‌دهد، که به وسيله جانشيني عبارت باقاعده به عنوان يک ريشه، «سازم»، با يک پسوند جمع، «آن»، تحليل شده است.
اکثريت بيشتر کلمات ورودي با هيچ کليدي در جدول درهم تطبيق پيدا نمي‌کنند، و به جاي آن به وسيله جايگزيني اصطلاح باقاعده تحليل مي‌شوند. اين جايگزيني‌ها پيشوندهاي صرف فعل و مکان يک +- بين ريشه و پيشوند را مشخص مي‌کنند، و بعلاوه پسوندهاي صرف فعل و مکان يک + بين ريشه و پسوند را مشخص مي‌کنند. براي مثال، يک کلمه مانند نمي – خوردند، ابتدا به صورت (ن + مي + خور + د + ند) تحليل مي‌شود. پس ريشه يابي به سادگي يک موضوع حذف همه پيشوندها و همه پسوندها است. چنانچه مثال قبلي از «خور» ريشه گرفته شده است.
الگوريتم Perstem معمولاً در حدود پنجاه قانون، جايگزيني باقاعده دارد. اين سطوح عالي دقت و سرعت در تجارب قبلي، به طور صحيح تحليل 97% از کلمات در يک دستگاه آزمايش، را نشان مي‌دهد. بيشتر خطاها شامل کلماتي که به حرف «يي» خاتمه پيدا مي‌کنند، مي‌شود که مي‌تواند يک پسوند مستقيم اشتقاقي، يک پسوند نکره مشخص صرفي، يا ممکن است به آساني قسمتي از ريشه باشد. ريشه يابي يک نشانوند خط فرمان دارد که تعدادي از اصطلاحات باقاعده اضافي را براي تحليل‌هاي با ابهام بالا توانا مي‌سازد، مانند کلماتي که به «يي» خاتمه پيدا مي‌کنند. توانايي اين نشانوند معمولاً حافظه را به هزينه دقت افزايش مي‌دهد. ريشه يابي لغت مي‌تواند پانزده هزار کلمه در ثانيه را در يک کامپيوتر روميزي پردازش کند.
رهيافت پايين به بالا براي ريشه‌يابي کلمات فارسي
الگوريتم طراحي شده توسط شريفي‌لو مبتني بر قانون و به صورت پايين به بالا است. در قدم اول، اين الگوريتم سعي مي‌کند تا زير رشته‌هايي از کلمه را بيابد که شامل ريشه‌ها هستند يا تکواژهايي که از هر ريشه مشتق شده باشند، که آن‌ها را هسته ناميده‌اند. بعد از آن، الگوريتم هر کدام از هسته‌ها را به عناصر ديگر کلمه براي توليد آن کلمه توسط قواعد موجود، متصل مي‌کند. در نهايت، هر هسته با حداقل يک توليد صحيح، هسته درست و صحيح مي‌باشد و ريشه آن ريشه درست کلمه مي‌باشد. الگوريتم شامل سه فاز مي‌باشد: 1- برچسب گذاري زير رشته . 2- تطبيق قاعده . 3- تطبيق ضد قاعده(شکل زیر).
در فاز برچسب گذاري زير رشته، ما اطلاعات ساخت‌واژي براي تمام زير رشته هاي ممکن از کلمه را استخراج مي‌کنيم. در انتهاي اين فاز ما مي‌فهميم که کداميک از زير رشته هاي کلمه، تکواژ هستند و کداميک تکواژ نيستند. همچنين ما خوشه‌هايي را شناختيم که هر تکواژ عضو آن‌ها بود. اين روش، از خوشه‌ها براي فاز تطبيق قاعده استفاده مي‌کند، از اين رو، هسته‌ها در کلمه قبل از شروع فاز دوم شناسايي مي‌شوند. جزئيات تگ گذاري زير رشته در بخش بعد توصيف مي‌کنيم.
Shekle 1.2.jpg
در فاز تطبيق قاعده، براي هر هسته که در فاز قبلي شناخته شده است، قاعده مربوطه را استخراج مي‌کنيم. براي مثال «خوان» يک هسته از کلمه «مي‌خوانم» است و «بن مضارع»، خوشه اي است که «خوان» عضو آن مي‌باشد. همچنين «م» عضو خوشه «شناسه مضارع» مي‌باشد و «مي» عضو خوشه «مي» مي‌باشد. ما قاعده اي در مخزن قواعد داريم به صورت: مي + بن مضارع + شناسه مضارع
که با کلمه «مي‌خوانم» تطبيق داده مي‌شود. بنابراين يک قاعده تطبيقي براي «خوان» پيدا مي‌شود. در انتهاي فاز دوم هر هسته اي که هر قاعده ممکني را براي کلمه استخراج کند، در ليست هسته‌ها باقي مي‌ماند و هسته هاي ديگر از ليست حذف خواهند شد.
در فاز تطبيق ضد قاعده، ضد قواعدي را از مخزن ضد قواعد براي هر هسته در ليست استخراج مي‌شود. هر هسته اي که هر ضد قاعده تطبيق شده را با تکواژهاي کلمه داشته باشد، از ليست هسته‌ها حذف خواهد شد. در انتهاي فاز سوم هر ريشه از هر هسته در ليست هسته‌ها، ريشه صحيحي براي کلمه مي‌باشد.
1- برچسب گذاري زير رشته
هر کلمه با طول N به تعداد N(N+1) /2 زير رشته دارد. بنابراين احتياج به N(N+1) /2 تطبيق رشته براي پيدا کردن آن‌ها در مخزن تکواژها داريم. از يک درخت Trie براي ذخيره سازي تکواژها و براي نمايش الگوريتمي، براي بازيابي اطلاعات ساختواژي از آن درخت که تعداد انطباق رشته را کاهش مي‌دهد، استفاده مي‌شود. اين الگوريتم در کل احتياج به N(N+1) /2 انطباق کاراکتر (به جاي انطباق رشته) دارد. يک قسمت ساده شده از درخت در شکل زير نشان داده شده است.
Shekle 1.3.jpg
در الگوريتم پيشنهاد شده، با N (طول کلمه است) تا اشاره گر که هر کدام به ريشه درخت اشاره مي‌کنند شروع مي‌کند. همچنين از يک شمارنده C که ايندکسي در کلمه است استفاده مي‌شود. در ابتدا مقدار C برابر با يک است، بدين معناست که حرف مربوطه آن اولين حرف کلمه است. در پايان هر گام، به مقدار C يک واحد اضافه مي‌شود. بنابراين در هر گام C به حرفي از کلمه اشاره مي‌کند که اين حرف را L ناميده مي‌شود. در گام اول اولين اشاره‌گر P1 يک لبه بين لبه هاي ريشه که حرف آن برابر با L مي‌باشد را مي‌يابد. اشاره‌گر P1 بر روي درخت توسط آن لبه پايين مي‌رود. در اين جا، P1 اطلاعات ساختواژي از محل جديدش (يک گره از درخت) را استخراج مي‌کند و اطلاعات ساختواژي را براي زير رشته، (1,2) پر مي‌کند. در گام دوم L دومين حرف از کلمه است، دومين اشاره گر P2 يک لبه را بين لبه هاي ريشه پيدا مي‌کند که حرف آن مساوي با L است. اشاره‌گر P2 بر روي درخت توسط آن لبه پايين مي‌رود، اطلاعات ساختواژي از مکان جديدش (يک گره از درخت) را استخراج مي‌کند و اطلاعات ساختواژي را براي زير رشته، (2,3) پر مي‌کند. همچنين P1 بر روي درخت توسط لبه اي که شامل L هست از مکانش که يکي از بچه هاي ريشه است، پايين مي‌رود و اطلاعات ساختواژي را براي زير رشته، (1,3) پر مي‌کند. در گام سوم، L سومين حرف از کلمه است سومين اشاره گر P3 از ريشه شروع مي‌کند و بر روي درخت توسط لبه اي که حرف آن مساوي با L است پايين مي‌آيد و اطلاعات ساختواژي را براي زير رشته، (3,4) پر مي‌کند. اشاره‌گرهای P1 و P2 اين کار را از مکانشان تکرار مي‌کنند و اطلاعات ساختواژي را براي زير رشته به ترتيب (1,4) و (2,4) پر مي‌کنند.
گام‌هاي بعدي مشابه با اين گام‌ها انجام مي‌شوند. در نهايت اطلاعات ساخت‌واژي براي تمام زير رشته‌هاي کلمه به دست مي‌يابد. همچنين اگر اشاره‌گري نتواند هيچ لبه اي با مقدار L بيابد تا انتهاي الگوريتم مسدود مي‌شود. شکل زير شبه کد الگوريتم را نشان مي‌دهد.
Shekle 1.4.jpg
2- انطباق قاعده
در اين روش، از قواعد زيادي براي توليد کلمات صحيح بوسيله تکواژها در زبان فارسي استفاده مي‌شود. اين قواعد در مخزن قواعد ذخيره مي‌شوند. بعضي از قواعد جمع شده در جدول زير نمايش داده شده است.
Jadvale 1.10.jpg
هر قاعده دنباله اي از خوشه‌ها است. يک خوشه نشان دهنده مجموعه اي از تکواژها مي‌باشد که نقش آن‌ها در کلمه را تحت تأثير قرار مي‌دهند. به عبارت ديگر هر تکواژ مي‌تواند به عنوان يک نقش يا نقش‌هاي بيشتر براي توليد کلمات به کار برده شود. بنابراين هر نقش مي‌تواند يک عضويت خوشه باشد. به عنوان مثال در زبان انگليسي "book" هم اسم مي‌باشد و هم فعل. اما اين کلمه به عنوان يک اسم شکل جمع دارد (books) و به عنوان يک فعل شکل گذشته دارد (booked).
به طور مشابه در زبان فارسي کلمه «مُرد» ريشه فعل است و «مردند» نيز فعل مي‌باشد. «مَرد» اسم مي‌باشد و «مَردها» يکي از شکل‌هاي جمع آن مي‌باشد. در نتيجه کلمه «مرد» را در هر دو خوشه «اسم» و «بن ماضي» قرار مي‌دهيم. زماني که يک قاعده احتياج به يک خوشه داشت، يک خوشه جديد ايجاد مي‌کنيم و آن خوشه در مخزن خوشه‌ها نمي‌باشد. همان طور که در مورد آن بحث شد در زبان فارسي، چندين پسوند براي شکل جمع داريم که هر کدام از آن‌ها براي مجموعه اي از اسم‌ها استفاده مي‌شود. پسوند «ها» براي هر اسمي استفاده مي‌شود و پسوند «ان» مخصوص هر چيز زنده مي‌باشد. ديگر پسوندها براي تعدادي از کلمات قرض گرفته شده از عربي و تعدادي از کلمات فارسي به کار برده مي‌شوند. اسمي مانند «پسر» چندين صورت جمع دارد (پسرها، پسران). بنابراين خوشه‌ها براي سازماندهي اين موقعيت‌ها به کار برده مي‌شوند. براي مثال تکواژ «پسر» را در خوشه «اسم» و «جاندار» قرار مي‌دهيم. بنابراين دو قاعده در مخزن قواعد داريم : اسم + ها مانند جاندار + ان تکواژ «پسر» عضوي از هر دو خوشه «اسم» و «جاندار» مي‌باشد. بنابراين کلمات «پسران» و «پسرها» شکل‌هاي صحيحي هستند و ريشه آن‌ها «پسر» است. اما در مورد تکواژ «کتاب»، اسم مي‌باشد و عضوي از خوشه «اسم» مي‌باشد، اما عضو خوشه «جاندار» نمي‌باشد. بنابراين «کتاب‌ها» شکل صحيحي است و ريشه آن «کتاب» است در مقابل «کتابان» شکل غلطي است و ريشه آن «کتاب» نمي‌باشد. همچنين پسوندها را در خوشه‌ي همسان مثل خوشه «شناسه مضارع»، «حرف نفي فعل» سازماندهي شده‌اند. جدول زير تعدادي از خوشه‌ها را نشان مي‌دهد.
Jadvale 1.11.jpg
در انتهاي اين فاز هر هسته بايد قاعده اي داشته باشد که مي‌تواند کلمه را توليد کند. وگرنه از ليست هسته‌ها حذف مي‌شود.
3- انطباق ضد قاعده
اين فاز مشابه فاز قبلي مي‌باشد اما اندکي با آن تفاوت دارد. در اين روش مخزني از قواعد وجود دارد، اما همه اين قواعد لزوماً در زبان فارسي به کار برده نمي‌شوند. در حقيقت اين قواعد استثنائاتي از قواعد مرحله قبل مي‌باشد. براي مثال يک قاعده در مخزن قواعد داريم: اسم جاندار + ان. از طرف ديگر استثنائي براي اين قاعده وجود دارد. هر اسمي با حرف پاياني «ه» مي‌تواند از اين قاعده استفاده نکند. براي مثال «پرنده» يک نوع حيوان با حرف پاياني «ه» مي‌باشد و کلمه «پرنده ان» کلمه اشتباهي در زبان فارسي است. اين قواعد استثنا "ضد قاعده " ناميده شده‌اند. جزئيات اين فاز: هر هسته از ليست هسته‌ها ضد قواعدي را بازيابي مي‌کند که درگير آن هستند، بعد از آن هر ضد قاعده بازيابي شده با تکواژهايي که در کلمه وجود دارند براي احتمال توليد کلمه، بررسي مي‌شوند. تا الآن تمام موارد شبيه به فاز قبلي بود اما تفاوت اينجاست. اگر هر ضد قاعده اي مربوط به قاعده هر هسته وجود داشته باشد، آن قاعده از ليست قاعده کانديد آن هسته حذف مي‌شود. در انتهاي اين فاز، هر هسته بايد حداقل يک قاعده که مي‌تواند توليد کلمه بکند، داشته باشد و گرنه از ليست هسته‌ها حذف خواهد شد. سرانجام هسته هاي باقي مانده در ليست هسته‌ها ريشه هاي صحيحي از کلمه دارند. در اين روش، مجموعه اي از ضد قواعد در مخزن جمع آوري شده است که هر ضد قاعده مربوط به قاعده‌اي در مخزن قاعده مي‌باشد. تعدادي از اين ضد قواعد در جدول زير نشان داده مي‌شوند.
Jadvale 1.12.jpg

ساخت ابزار ریشه‌یابی زبان فارسی در آزمایشگاه فناوری وب

در الگوريتم پياده‌سازي شده، از هر دو رويکرد استفاده از فرهنگ لغت و قوانين نحوي استفاده شده است. براي اجراي مراحل الگوريتم از چهار فرهنگ لغت استفاده شده است.
• فرهنگ لغت براي نگه داشتن تمامي ريشه هاي مربوط به کلمات غير فعلي (شامل اسامي، صفت‌ها، قيدها و ...).
• فرهنگ لغت براي نگهداري کلمات جمع مکسر و حالتهاي جمع بدون قاعده به همراه حالت مفرد اين کلمات
• فرهنگ لغت شامل بن‌هاي گذشته و حال افعال زبان فارسي
• فرهنگ لغت شامل تمامي وند (پيشوند و پسوند) هاي زبان فارسي
• فرهنگ لغت براي کلمات استثناء
براي ايجاد فرهنگ لغت مربوط به بن‌هاي گذشته و حال حدود 6000 فعل زبان فارسي از مجموعه دادگان زبان فارسي مورد بررسي قرار گرفت و در نهايت حدود 400 بن گذشته و حال افعال استخراج گرديد. به عنوان مثال دو فعل «خواب ديدن» و «ديدن» يک فعل در نظر گرفته شده است. سپس بن‌هاي گذشته و حال آن به شکل «ديد» و «بين» در فرهنگ لغت ذخيره مي‌گردد. دليل اين عمل اين است که تنها بن فعل در جمله تغيير حالت مي‌دهد و ساير قسمت‌هاي فعل به ازاي زمان و شخص‌هاي مختلف، تغيير شکل نمي‌دهند.
در الگوريتم ريشه‌يابي، ابتدا بايستي نوع عبارت (فعل يا غيرفعل)، تشخيص داده شود. براي انجام اين عمل از دو روش استفاده شده است. در روش اول شناسايي صحيح انواع فعل پيشوندي، ساده و مرکب در زمان‌هاي مختلف در متن با بهره‌گيري از قواعد نحوي گرامر زبان فارسي، موقعيت لغات و تحليل ريخت‌شناسي لغات (مطالعه ساختار لغات) صورت پذيرفته است. براي شناسايي افعال موجود در متن، احتمال ظهور فعل در موقعيت‌هايي خاص نظير لغات قبل از جداکننده‌هاي جملات مثل علامت‌هاي «.»، «»، «!»، «؟»، «?»، «:» و غيره، جداکننده‌هاي لغات مثل علامت‌هاي «»، «,»، «-» و غيره. همچنين يک سري حروف خاص آغاز کننده جملات مثل «که»، «اساسا»، «البته»، «تا»، «اما»، «اگر»، «ولي»، «زيرا»، «سپس»، «همچنين»، «و»، «يا» و غيره از طريق چک کردن تطبيق با ساختار يکي از زمان‌هاي افعال فارسي، مورد بررسي قرار مي‌گيرد. احتمال فعل بودن لغات در موقعيت‌هاي ذکر شده با بررسي مطابقت با انواع ساختار افعال فارسي توسط عبارات منظم بررسي مي‌گردد. در صورتي که لغات مورد ارزيابي با هر کدام از ساختارهاي فعل توسط عبارات منظم، تطبيق پيدا کنند، گروه فعلي را تشکيل خواهند داد. ساير عباراتي که در اين قالب نمي‌گنجند نيز به صورت غيرفعل شناسايي مي‌گردند.
در روش دوم ابتدا از روي افعال استخراج شده از مجموعه دادگان تمامي تصريف‌هاي مختلف افعال درون يک فرهنگ لغت ايجاد مي‌شوند و سپس با جستجوي کلمه در اين مجموعه نوع عبارت تشخيص داده مي‌شود. سپس در مرحله بعد براي هر کدام از عبارات فعل و غير فعل به صورت جداگانه و براساس قوانين جداگانه عمل مي‌شود.
ريشه يابي عبارات فعلي
در اين روش ابتدا فعل را به دو صورت منفي يا مثبت تفکيک مي‌نماييم. سپس در صورتي که منفي باشد پسوند منفي‌ساز فعل از آن حذف مي‌گردد. در مرحله بعد ساختار فعل با يکي از ساختارهاي انواع فعل در زبان فارسي تطبيق داده مي‌شود. پس از تطبيق و يافتن زمان مناسب فعل، براساس نوع فعل به ترتيب پسوندها و پيشوندهاي موجود در فعل حذف مي‌شوند. نکته‌اي که بايستي به آن دقت شود اين است که در صورتي که فعل مانند «خواب ديده بود» به صورت مرکب و چند قسمتي باشد فقط قسمت تصريف شده آن (در اين مثال «ديده بود») ريشه‌يابي مي‌گردد و ساير قسمت‌هاي قبلي به صورت مستقيم به همراه ريشه به عنوان ريشه معرفي مي‌گردد.
در انتها پس از بدست آوردن ريشه فعل، دو زمان حال و آينده در قالب بن‌هاي ماضي و مضارع ارائه مي‌گردند. براي اين منظور در فرهنگ لغتي شامل حدود 400 فعل حال به همراه معادل گذشته‌شان ذخيره شده است. پس از يافتن و استخراج قسمت اصلي فعل آنرا داخل اين فرهنگ لغت جستجو نموده و بن‌هاي متناسب استخراج مي‌گردند. همچنين اطلاعات اضافي‌اي در مورد زمان و شخص فعل نيز در ادامه فعل درج مي‌گردد. نکته مهمي ه در اين پروژه به آن دقت شده است اين است که برخي کلمات که داراي بن فعلي هستن براساس شرايطي جايگاه فعل خود را از دست مي‌دهند و ريشه‌يابي براي آن‌ها بايستي به صورت ديگري انجام گيرد. براي اين منظور ليستي از حروف اضافه استخراج شده است که زماني که قبل از کلمه مورد نظر که شامل بن فعلي است قرار گيرند حالت کلمه را از حالت فعل به اسم تغيير مي‌دهند. به عنوان مثال عبارت «به گفته» باعث مي‌شود که کلمه «گفته» به اسم تبديل شود و ريشه آن به صورت «گفت+ه» مشخص مي‌گردد. جدول زير نمونه حروف اضافه مورد استفاده در اين موارد را نشان مي‌دهد.
Jadvale 1.13.jpg
مراحل کار روش پيشنهادي در شکل زير نشان داده شده است.
Shekle 1.5.jpg
ريشه‌يابي عبارات غيرفعل
در اين مرحله ابتدا کل کلمه درون فرهنگ لغت شامل ريشه کلمات جستجو مي‌گردد. اگر کلمه وجود داشته باشد، خود کلمه به عنوان ريشه معرفي مي‌گردد. در غير اينصورت کلمه درون فرهنگ لغت مربوط به کلمات جمع مکسر و بدون قاعده جستجو مي‌گردد. اگر کلمه در اين فرهنگ لغت يافت شود، معادل مفرد آن به همراه يک نشانگر مبني بر جمع مکسر بودن آن، برگردانده مي‌شود. اما در غير اينصورت ابتدا با استفاده از قوانين مربوطه تمامي وندهاي ممکن موجود در کلمه يافت مي‌شود. فهرستي از وندهاي مورد استفاده در الگوريتم در ادامه نشان داده شده است. سپس از کوچک‌ترين پسوند شروع کرده و پسوندها حذف مي‌شوند. در هر مرحله و پس از حذف پسوند مجدداً کلمه درون فرهنگ لغت مربوط به کلمات ريشه جستجو مي‌شود. درصورتي که کلمه يافت شود مي‌تواند به عنوان ريشه معرفي گردد اما ممکن است اين استدلال غلط باشد. مثلاً در کلمه «ماشين» پسوند «ين» شناخته شده و ريشه «ماش» نيز در فرهنگ لغت موجود مي‌باشد اما اين ريشه براي کلمه «ماشين» صحيح نمي‌باشد. از آنجايي که استخراج قانون براي چنين شرايطي سخت و در بعضي مواقع غير ممکن است، از اينرو از يک فرهنگ لغت که شامل استثنائات مربوطه به حذف وندها است، بهره گرفته شده است. پس از اينکه پسوند تشخيص داده شده حذف و ريشه محتمل استخراج گرديد، آن ريشه درون فرهنگ لغت استثنائات جستجو شده و در صورتي که اين ترکيب جزو استثنائات نباشد؛ کلمه مربوطه به عنوان ريشه برگردانده مي‌شود. در غير اينصورت مجدداً کلمه درون فرهنگ لغت مربوط به جمع‌هاي مکسر جستجو مي‌شود و در صورت يافت شدن حالت مفرد کلمه به عنوان ريشه برگردانده مي‌شود. اين جستجو براي شرايطي صورت مي‌گيرد که کلمه مورد نظر براي ريشه‌يابي شامل يک کلمه جمع مکسر به همراه پسوند متصل به آن است. به عوان مثال مي‌توان کلمه «اساتيدان» را نام برد. در صورتي که باز هم کلمه در فرهنگ لغات کلمات جمع مکسر يافت نشود مجدداً عمليات حذف پسوند، با حذف پسوند بعدي ادامه مي‌يابد. همين مراحل براي پيشوندها نيز صورت مي‌گيرد و پيشوندها نيز از کلمه مربوطه حذف مي‌گردند تا ريشه به دست آيد. همچنين ممکن است دو کلمه در متن به هم متصل شده باشند و برنامه نتواند طبق روال فوق آن‌ها را ريشه‌يابي نمايد. به منظور رفع اين مشکل، براي جداسازي کلمات به هم چسبيده در متن، هر کلمه که در فرهنگ ريشه کلمات يافت نشود به دو بخش بزرگ‌تر از سه حرف شکسته شده و درصورتي که هر دو بخش در فرهنگ ريشه کلمات وجود داشته باشد، عمل جداسازي انجام مي‌شود. مي‌توان کلمه «آبمعدني» را به عنوان مثالي براي اين شرايط بيان نمود که به دو کلمه «آب» و «معدني» شکسته مي‌شود. اين عمليات به صورت تکراري ادامه مي‌يابد تا در نهايت ريشه نهايي استخراج گردد. مراحل کار در شکل‌هاي زير نشان داده شده است. با تکرار اين عمليات، تمامي سطوح مختلف براي ريشه‌يابي اعمال شده و ابزار اين قابليت را دارد که بتوان سطوح معنايي مختلف را از آن استخراج نمود. به عنوان مثال براي کلمه «خلاصه‌سازي» سه ريشه «خلاصه‌سازي»، «خلاصه‌ساز» و «خلاصه» به عنوان خروجي بازگردانده مي‌شود که بسته به نوع استفاده مي‌توان از هر کدام از آن‌ها استفاده نمود. به عنوان مثال ديگر براي کلمه «دانشجويان» نيز سه ريشه «دانشجو»، «دانش» و «دان» استخراج مي‌گردد.
Shekle 1.6.jpg
Shekle 1.7.jpg

این رده در حال حاضر حاوی هیچ صفحه یا پرونده‌ای نیست.