 #مقدمهتشخیص آیات قرآنی در متون که عنوان پروژه می باشد بیشتر در مورد متن های تفسیری صادق است به این مفهوم که آیات قرآن در متون تفسیری فارسی بیشتر به چشم می خورد. حال هدف تفسیر آیات قرآن به شرح ذیل است : ابتدا آیه مورد نظر مطرح می شود سپس آیه به طور یکجا و یا قطعه قطعه به استناد آیات قرآنی دیگر و یا احادیثی از ائمه اطهار(علیهم السلام) و روایات دیگر تفسیر می شود. نکته قابل توجه این است که متن عربی حدیث نیز در کنار توضیح فارسی آن به چشم می خورد (هدفی از طرح بیان این مطلب است که بعدأ ذکر خواهد شد.) بنابراین متون تفسیری فارسی در داخل متون فارسی که بخش عمده تفسیر را تشکیل می دهند در کنار آیات قرآن کریم ، حاوی متون حدیثی و روایتی است که آن ها نیز مانند قرآن کریم به زبان عربی اند. بنابراین این پژوهش به دو زیر مسئله تبدیل می شود : 1. تشخیص بخش های عربی در متون فارسی تفسیری 2. تشخیص آیات قرآن کریم از سایر متون عربی مسئله اول به عنوان یک مسئله تشخیص زبان و مسئله دوم به عنوان یک مسئله تشخیص منبع از دیدگاه فنون رده بندی متن (Text Classification) که از زیر شاخه های متن کاوی (Text Mining) است قابل بررسی اند. از آن جا که مسئله اول در حال حاضر در حیطه این پژوهش نمی باشد با فرض موفقیت سامانه در تفکیک بخش های عربی از فارسی پژوهش حاضر در مسئله دوم متمرکز شده و در آن تلاش بر تفکیک آیات قرآن کریم از سایر متون عربی خواهد بود. در حقیقت مسئله بر تشخیص آیات قرآن در متون فارسی تأکید دارد. حال شاخه علمی که برای حل این مسئله از آن مدد جسته شده است یعنی رده بندی متون توضیح داده می شود. در این راستا به الگوریتم Benedetteo, Caglioti & Loreto اشاره می شود که می تواند با تکیه بر شیوه استفاده الگوریتم های فشرده سازی از مفهوم آنتروپی در نظریه اطلاعات رشته مورد نظر را حتی در طول بسیار کوچک رده بندی نماید. در پایان شیوه ای خاص که توسط دکتر شکراللهی فر و همکارانش برای تشخیص آیات قرآنی مورد استفاده قرار می گیرد را توضیح می دهیم. #کارهای مرتبط محققان مشکل تشخیص آیات قرآن کریم در متون را از چند نظر بررسی می کنند : *تذکر*: به دلیل زیاد بودن متن تفسیری از آوردن آن در این جا معذورم. 1. برای نمونه متنی از ترجمه تفسیر مجمع البیان را در اختیار داریم ، این متن به این صورت است که بسیاری از پیکره متن فارسی و دارای بخش هایی عربی (آیات قرآن دارای اعراب) می باشد ، در این صورت چون متن قرآنی دارای حرکت است به راحتی از متن اصلی تمییز داده می شود ولی این همیشه صادق نیست. 2. متن دیگری را در نظر بگیرید که آیات دارای حرکت نیستند و به همین دلیل با احادیثی از ائمه اطهار(علیهم السلام) که در همان متن تفسیری می باشد اشتباه گرفته شده و همین امر مسئله تفکیک و تشخیص آیات را دچار مشکل می کند. 3. در همین راستا ممکن است برخی از اشعار عربی نیز در متون تفسیری یافت شوند و چون که آیات قرآنی دارای حرکت و اعراب نمی باشند هیچ مشخصه ظاهری ندارند که از سایر متون عربی تمییز داده شوند. 4. از لحاظ طول آیات قرآنی نیز در نمونه ای از تفسیر نور نکات قابل توجهی نهفته است: در این نمونه آیه مورد نظر هم به طور کامل به کار رفته است و هم در حد عبارت و یا حتی کلمه تنها شکسته شده است. بنابراین در متون فارسی تفسیری : 1. نه تنها تمامی بخش های فارسی بلکه بسیاری از آیات قرآنی مخلوط شده نیز فاقد حرکت می باشند. 2. این آیات در کنار بخش های عربی دیگر نظیر احادیث و اشعار قرار گرفته اند. 3. این آیات در طول های مختلف از جمله طولانی گرفته تا یک کلمه تنها در داخل متون فارسی مخلوط شده اند. #رده بندی و تشخیص منبع متن: مسئله تشخیص منبع یک متن در کنار دیگر متونی که از منابعی دیگرند ولی هم متن مورد نظر و هم دیگر متون به زبانی یکسان نگاشته شده اند حوزه ای است که از منظر رده بندی متن نگریسته می شود. از جمله کاربردهای مبحث رده بندی (طبقه بندی ، دسته-بندی یا کلاس بندی) متن است که در آن سه مرحله پیش-پردازش ، آموزش رده بند و رده بندی وجود دارد. در مرحله پیش-پردازش, دانش موجود در هر متن باید بازنمایی شود تا قابل استفاده نرم افزارهای رده بندی گردد. این بازنمایی به شکل مدل برداری از ویژگی های متن که برگرفته از عناصر موجود در آن است انجام می گیرد. رایج ترین این ویژگی ها کلمه است که برخی مواقع بوسیله نرم افزارهای پردازش زبان طبیعی با برچسب هایی همراه می شوند که حاوی اطلاعات صرفی- نحوی آنها است. در برخی موارد این ویژگی ها به صورت های پیچیده تری نیز تبدیل می شوند که رایج ترین شیوه استفاده از مدل سازی چند-گرمی است. برای بازنمایی متون با استفاده از ویژگی های مناسب استخراج یا ساخته شده از همان متون هر یک از این ویژگی ها به ارزشی عددی نگاشت داده می شود که به عنوان وزن آن ویژگی در متن مورد نظر محاسبه می شود. برای این منظور ماتریس m×n ایجاد می شود که در آن m کل متن های موجود در رده ها، n کل ویژگی های ایجاد شده، و Aij تعداد تکرار ویژگی i یا به عبارتی وزن آن در متن j است. در این هنگام بطور معمول مشکل گستره و پراکندگی زیاد وزن این ویژگی ها پیش می آید که برای حل آن به شیوه های گزینش ویژگی ها رجوع می شود تا مقادیری از ویژگی ها که بیش از دیگران قابلیت تمییز دهندگی متون را دارند گلچین شوند. در مرحله آموزش رده بند، برای ایجاد سامانه های رده بندی از سامانه های یادگیری ماشین با ناظر بهره گیری می شود. این سامانه ها بوسیله ویژگی- وزنهای به دست آمده در مرحله پیش-پردازش ازمتونی که تحت عنوان متون آموزشی از قبل رده بندی شده اند آموزش داده شده و به یک رده بند متون تبدیل می شوند. در مرحله رده بندی، متون مورد نظر برای رده بندی، پس از گذر از مرحله پیش-پردازش و تبدیل به بردارهای مقدار- وزن در قالب ویژگی های انتخاب شده در مرحله آموزش، به رده بند داده می شوند تا،مطابق با رده های از قبل آموزش داده شده به رده بند، در یکی از رده های آن رده بندی شوند. میزان موفقیت رده بند در این رده بندی معادل ارزیابی انجام شده بر روی آن در مرحله آموزش فرض می شود.در اجرای مراحل فوق برای ایجاد یک رده بند، آنچه رده بندهای مختلف را از یکدیگر متمایز می کند بیشتر نوع و چگونگی استفاده از ویژگی ها در مرحله پیش-پردازش است به علاوه نوع سامانه یادگیری ماشینی که انتخاب شده و برای منظور خاص تنظیم می شود. حال به دو نمونه از فنون موفق که برای استفاده از ویژگی های متون به منظور تأیید منبع بکار رفته اند اشاره می شود: # 1. الگوریتم Benedetteo, Caglioti & Loreto یکی از شیوه های غالب کنونی در ایجاد، استخراج و گزینش ویژگی های متن روش مورد استفاده توسط Darrio Benedetteo, Emanuele Caglioti and Vittorio Loreto است که در آن برای تشخیص منبع رشته فرضی از ویژگی توالی کلمات استفاده شده و برای وزن دهی مقادیر ویژگی ها ازفنون نظریه اطلاعات بهره گیری شده است. به نظر گروه فوق، بسیاری از پدیده های طبیعی، همچون زبان و توالی DNA و پروتئین،اغلب به صورت رشته هایی از کاراکترها بازنمایی می شوند که با تجزیه آنها می توان اطلاعاتشان را استخراج کرد. به طور مثال در مورد توالی DNA و پروتئین می توان زیر-توالی هایی که نشانگر ژنها و کارکردشان است تشخیص داد. و در متون مکتوب می توان زبان، نگارنده و موضوع آنرا مشخص ساخت. #ارزیابی الگوریتم :Benedetteo, Caglioti & Loreto ارزیابی گزارش شده توسط طراحان این الگوریتم در بکارگیری آن برای رده بندی متونی در زبانهای رایج اروپایی حاکی از صحت 93.3 % آن است. هرچند بکارگیری این الگوریتم برای رده بندی متون فارسی وعربی توسط طراحان آن گزارش نشده است، در آزمایش های اولیه در تشخیص آیات قرآن کریم واحادیث از یکدیگر بر اساس الگوریتم فوق توسط شکرالهی و همکارانش در دانشگاه نبی اکرم (ص)،تبریز،صحت مشابه حاصل شده است. # 2. بهره گیری از سامانه خبره مبین شیوه دیگری که توسط شکرالهی و همکارانش برای ایجاد و گزینش ویژگی های متنی در تشخیص آیات قرآن کریم و احادیث از یکدیگر استفاده شده است بکارگیری سامانه خبره مبین است که به منظوربرچسب گزاری دستوری واژه ها در متون عربی کلاسیک، همانند قرآن کریم و احادیث، توسط شکرالهی وهمکارانش طراحی و پیاده سازی شده است. #مرحله پیش-پردازش: برخلاف الگوریتم قبلی که در آن سنگ بنای ویژگی های ایجاد شده کلمه است، در این الگوریتم بجای کلمه از برچسب های دستوری کلمه ها بهره گیری می شود. به عنوان مثال رشته ذیل ترجمه یکی از آیه های قرآن کریم به تنها یک دسته از برچسب های دستوری کلمه های آن است. PN PN PN PN @ PN PN V PN @ PN PN PN @ N N PN @ N V P N در ایجاد ویژگی های متنی، از این رشته های ساده با استفاده از مدلسازی چند-گرمی رشته های ترکیبی ساخته می شود، که تا کنون آزمایشات بیشتر روی جفت-گرمی ها انجام یافته اند. گزینش بهینه در میان ویژگی ها بر اساس تابع خی-دو انجام می گیرد. بر اساس گزارشات پژوهشی متعدد در رده بندی متن، این تابع که در زیرارائه شده است بهتر از توابع مرسوم دیگر در داده کاوی نتیجه بخش بوده است. N*(TP*TN-FP*FN)^2]/(TP+FN)*(FP+TN)*(TP+FP)*(FN+TN)]=X^2 در این تابع که میزان وابستگی یک ویژگی مورد نظر و یک رده در مقایسه با سایر رده ها را با یک عددبیان کرده و در صورت صفر بودن نشان دهنده عدم وابستگی معنی دار است، آرگومان های استفاده شده به شرح ذیل میباشند. TP:تعداد تکرار ویژگی مورد نظر در رده مثبت FP:تعداد تکرار ویژگی مورد نظر در سایر رده ها FN:تعداد متون فاقد ویژگی مورد نظر در رده مثبت TN:تعداد متون فاقد ویژگی مورد نظر در سایر رده ها N:کل تعداد متن ها در تمامی رده ها بر اساس حاصل این تابع به ازای هر ویژگی- رده، برای هر رده ویژگی هایی که دارای بالاترین مقدارندگزینش می شوند، که تعداد آنها بطور معمول بین 1% تا 10 % تعداد کل ویژگی هاست. آنگاه نوبت وزن-دهی به این ویژگی هاست که تابع رایج آن بر اساس تابع TF.IDF به ترتیب زیر محاسبه میشود: TF.IDF=TF. logN/DF در این تابع TF به تعداد تکرار ویژگی مورد نظر یا به اصطلاح وزن آن در متن مورد نظر، DF به تعداد متن های شامل آن ویژگی،IDF به معکوس DF و N به تعداد کل متن ها اشاره دارند. بدین ترتیب ماتریس بزرگ قبلی با سلولهایی که حاوی تعداد تکرار تمامی ویژگی های ایجاد شده درتمامی متن ها بود به ماتریسی بسیار کوچک تبدیل می شود که سلولهای آن حاوی وزنهای ویژگی های گزینش شده برای همان متن هاست. #مرحله آموزش رده بند: ماتریس نهایی ایجاد شده در مرحله پیش- پردازش به عنوان مجموعه داده آموزشی برای سامانه های یادگیری ماشین با ناظر استفاده می شود. تا کنون سامانه های یادگیری ماشین با ناظر SVM و نیز درختهای تصمیم گیری با ویژگی های فوق برای تشخیص دسته آیات قرآنی از یکدیگر آموزش داده شده اند، ولی در زمینه تشخیص آیات قرآنی از احادیث و متون مشابه آزمایشات هنوز ادامه دارند. #مرحله رده بندی و ارزیابی: سامانه های فوق موفقیت چشمگیری در تشخیص دسته آیات قرآنی از یکدیگر، مانند آیات مکی مدنی و نیز آیات جزءهای ابتدایی قرآن از جزءهای دیگر آن داشته اند. در هر دو مورد F-score از آیات حدود %95 مشاهده شده است. #نتیجه گیری: بر اساس توضیحات عرضه شده در تشخیص هوشمند آیات قرآن در متون فارسی تفسیری، به جهت مخلوط بودن بخشهای دیگر عربی مانند احادیث و اشعار عربی در این متون و شباهت آنها با آیات قرآنی، ابتدا باید سامانه ای دیگر کلیه بخشهای عربی را از داخل متون فارسی تفسیری جدا نماید و سپس در این بخشهای عربی آیات قرآن تمییز داده شوند. از طرفی دیگر، این بخش های عربی در قالب رشته-هایی با طول های زیاد به اندازه یک آیه کامل یا چند سطر تا طولهای بسیار کوتاه در حد یک کلمه ظاهر شده اند. با نگریستن به سامانه هوشمند تشخیص آیات قرآن در متون فارسی تفسیری به عنوان سامانه ای برای تأیید منبع متن الگوریتم Benedetteo, Caglioti & Loreto در کنار موفقیت قابل توجه در،تشخیص منبع رشته های طولانی، توفیق شایانی در خصوص رشته های بسیار کوتاه نداشته است. سامانه-ای که برای حل این معضل با تلاش شکرالهی و همکارانش در حال ایجاد شدن است، با وجود نتیجه بخش بودن در تفکیک آیات قرآنی از یکدیگر، در تفکیک آنها از متون عربی دیگر از جمله احادیث هنوزبه سرانجام نرسیده است. به نظر می رسد پژوهش بیشتری باید در راستای شناسایی وجه ممیزه زبان قرآن با سایر متون مشابه انجام پذیرد. # اطلاعات مربوط به فاز 4 خرداد ! در این مرحله می خواهیم داده‌های مورد آزمایش و نحوه ارزیابی کمی مربوط به مساله را در این بخش توضیح دهیم. # روش پیشنهادی الگوریتم سیستم تشخیص هوشمند آیات قرآنی دارای 5 مرحله می باشد : 1- ساخت بانک قرآنی 2- پردازش اولیه بر روی متن ورودی 3- شناسایی کلمات قرآنی 4- جستجوی توالی الگوها و تشخیص آیه 5- آدرس دهی و برجسته سازی آیات قرآنی درون متن اصلی این الگوریتم الگوریتمی نوین مبتنی بر اندیس گذاری متن و الگوها است که ایده اصلی آن نگاشت الگوها و متن مورد پردازش به یک سری آرایه های عددی و پردازش بر روی این اعداد به جای پردازش متن است. در دو مرحله آیات قرآنی را می یابد I. با یک الگوریتم تطبیق دقیق چند الگویی اندیسی کلمات قرآنی تشخیص داده شده و به آرایه های عددی بدل می شوند II. فیلتری طراحی شده که با استفاده از جستجو بر روی اندیس ها توالی اندیسی بین کلمات را تشخیص می دهد و مشخص می کند که این کلمات یک آیه است یا بخشی از آیه یا چند آیه در جاهای مختلفی از قرآن # نتایج در این مرحله آزمایش های متفاوتی صورت گرفته است در ابتدا داده های مورد آزمایش را توصیف کرده و سپس نتایج به دست آمده را ارائه و تحلیل می کنیم نتیجه کلی از میانگین نتایج آزمایش ها به دست آمده است. #مجموعه داده ها برای انجام بررسی نتایج از دو منبع استفاده شده است: منابعی که آیات قرآنی در آن بسیار به چشم می خورد منابعی که آیات قرآنی کمتری دارد اما کلمات قرآنی در آن زیاد است این بخش ها طوری مورد آزمایش قرار می گیرند که آیا منابع مشابه با آن ها به اشتباه به عنوان منابع قرآنی در نظر گرفته می شوند یا نه # معیار های ارزیابی این سیستم جزو سیستم های بازیابی تشخیص اطلاعات است نه بازیابی داده معین ، چرا که ما با مسائلی من جمله اختلاف رسم الخط ها ، اختلاف قرائات و ... روبرو هستیم پس باید پردازش بیشتری و پیچیده تری روی سیستم انجام گیرد زیرا بازیابی اطلاعات برخلاف بازیابی داده ها با ابهاماتی رو به رو است بنابراین باید هر چه بیشتر اطلاعات را مدل کنیم تا ابهام در درک اطلاعات توسط سیستم کم شود در این سیستم همانند سیستم بازیابی اطلاعات معیار صحت ، دقت و معیار F معیار های اصلی ارزیابی اند معیار صحت تشخیص یک آیه تعداد کلماتی که به درستی به عنوان قرآن تشخیص داده شده اند نسبت به تعداد کل کلمات قرآنی موجود در متن معیار دقت تشخیص یک آیه تعداد کلماتی که به درستی به عنوان قرآن تشخیص داده شده اند نسبت به تعداد کل کلماتی که آیه تشخیص داده شده اند معیار F میانگین هارمونیک صحت و دقت و دارای تأثیرات هم زمان هر دو معیار # نتایج آزمایش ها متنی که توسط این سیستم هوشمند بررسی می شود برای هر کلمه در آن دو حالت پیش می آید که دو معیار ارزیابی در مورد آن است : بر اساس کلماتی که قرآن اعلام شده اند بر اساس کلماتی که قرآن اعلام نشده اند متنی با 2418 کلمه و فراوانی آیات بالا نوع کلمات الف ) کلماتی که قرآن تشخیص داده شده اند صحت : 1 دقت : 0.866788 معیار F :دارای 0.928641 ب ) کلماتی که قرآن تشخیص داده نشده اند صحت : 1 دقت : 0.96242 معیار F :دارای 0.98085 ج ) میانگین هندسی کل صحت : 1 دقت : 0.92864 معیار F :دارای 0.95403 متنی با 3802 کلمه و فراوانی آیات کم نوع کلمات الف ) کلماتی که قرآن تشخیص داده شده اند صحت : 0.95833 دقت : 0.81367 معیار F :دارای 0.8801 ب ) کلماتی که قرآن تشخیص داده نشده اند صحت : 0.97704 دقت : 0.99555 معیار F :دارای 0.98621 ج ) میانگین هندسی کل صحت : 0.9676 دقت : 0.89547 معیار F :دارای 0.93014 #مراجع 6. جستجوی هوشمند عبارات قرآنی در متون دیجیتال ، محمد حبیب زاده بیژنی 7. رده بندی متون فارسی با استفاده از روش های آماری ، محمد حسین الهی منش – دکتر بهروز مینایی 8. برچسب گذاری ادات سخن متون فارسی به کمک مدل مخفی مارکوف ، محمد حسین الهی منش – دکتر بهروز مینایی 9. امکان سنجی تولید سامانه هوشمند تشخیص آیات قرآن در متون فارسی تفسیری 11. برخی مسائل در طراحی موتور جستجوی قرآنی وب محمدی نصیر ، مجتبی 10. Dario Benedetteo, Emanuele Caglioti & Vittorio Loreto. Language Treesand Zipping. PHYSICAL REVIEW LETTERS. Volume 88, number 4, 2002. 5. George Forman. Feature Selection for Text Classification. Computational Methods of feature Selection. CRC Press/Taylor and Francis Group, 2007. 6. Mahmoud Shokrollahi-Far, Behrouz Minaei, Issa Barzegar, Hadi Hossein-Zadeh, Mojhdeh Ghasdi, Salman Hoseini. Bootstrapping Tagged Islamic Corpora. In Proceedings of 2nd International Conference on Arabic Language Resources and Tools, Cairo, Egypt. 2009. 7. Mahmoud Shokrollahi-Far. Mobin Exper System: Grammatical Tagger for Classical Arabic. Submitted to 10th International Conference on the Statistical Analysis of Text Data, Italy. 2010. 8. Mahmoud Shokrollahi-Far. Source Verification of Quranic Texts. Submitted to 10th International Conference on the Statistical Analysis of Text Data, Italy. 2010 . (ارجاع مربوط به شکراللهی و همکران) # پیوندهای مفید * [دریافت متن قرآن کریم](http://tanzil.net/) * [متن عربی و فارسی المیزان که برای تست مفید است](http://zolal.sobhe.ir/#almizan_ar/2_1) * [سورس کد](http://uplod.ir/5ob9rnkiaskz/code.txtبه دلیل به هم خوردگی متن فایل pdf آن در پایین ضمیمه شده است. با توجه به پیشرفت تکنولوژی و ابزارهای لازم در جهت برآورد نیازهای بشر من قبیل کامپیوتر، اینترنت و ... مشکل اساسی در این مقطع زمانی با توجه به محدودیت های استفاده از این ابزارها افزونگی داده ها می باشد که مشکلات عدیده ای را به همراه دارد. برای نمونه امکان دسترسی اطلاعات به این پایگاه عظیم داده ای گاهی دشوار و گاهی غیر ممکن به نظر می رسد. محققان و دست اندرکاران حوزه ی فناوری اطلاعات و علوم کامپیوتر در سراسر این کره خاکی دست به کار شده و امکانات زیادی را در جهت دسترسی آسان و به طور خاص مطمئن در این زمینه فراهم کردند. امکاناتی نظیر طبقه بندی اطلاعات بر اساس محوریت موضوعی ، محتوایی و ... در جهت جستجو و دسترسی آسان و بی دغدغه به دور از صرف هزینه گزاف و اتلاف وقت از جمله این کارها در جهت این اهداف محقق شده است. حال چگونگی دسترسی به این اطلاعات مطرح می شود که در این مقدمه سعی شده تا مفهومی نزدیک به ذهن مخاطب ارائه گشته و روند کار به طور واضح مشخص شود. در حوزه علوم اسلامی در سال های اخیر در جهت تسهیل کار طلاب علوم اسلامی و پیشبرد سریع تر اهداف حوزه های علوم اسلامی کتاب های ایشان که محتوای درسی و پژوهشی داشته و علی الخصوص کتب معتبر شیعه از منظر روایات ، تفاسیر و ... به نرم افزارهایی در حوزه ی دیجیتالی مبدل گردیده است. از این رو کار با این نرم افزارها باعث تسهیل در روند پژوهشی – آموزشی شده و ارتقای سطح کمی و کیفی مطالعات را به دنبال داشته است. حال در جهت این مهم سعی شده است تا امکانات اصلی و قطعی در امر مطالعات برای این نرم افزارها در نظر گرفته شود ؛ یکی از این امکانات جستجوی پیشرفته در متون می باشد. این امکان را در سطوح معمولی و بسیار ساده بسیاری از نرم افزار ها پشتیبانی می کنند ، به این صورت که کاربر کلمه ای را جستجو کرده و در متن مورد نظر تمامی عباراتی که آن کلمه را دارا می باشند گشته و آن کلمه را پیدا می کند اما گاهی اوقات کاربران نیاز به دسترسی پیشرفته تری در موضوعات مختلف دارند ، به عنوان مثال کاربر می خواهد آیات قرانی موجود در متن را بررسی کند. به این منظور نیاز به سیستم هوشمندی است که بتواند بر اساس نیاز کاربر به این مهم پاسخ دهد. #پیشینه کار و کارهای مشابه از آنجایی که عملیات پردازشی سیستم تشخیص آیات قرآنی در حیطه الگوریتم های تطبیق الگو (تطبیق رشته) قرار دارد در این بخش سیستم های تطبیق الگو را معرفی کرده و انواع الگوریتم ها و کاربرد های آن ها را شرح می دهیم. تطبیق الگو تطبیق الگو به دنبال پیدا کردن تمامی رخدادهای یک الگوی خاص در یک متن ورودی است،به طور کلی هر الگو توصیفی از یک مجموعه رشته است و هر رشته نیز از یک دنباله از نمادها تشکیل شده است.از این رو برای یک الگو علاوه بر محل وقوع الگوها تعداد وقوع الگوها نیز جستجو می شود. الگوریتم های تطبیق الگو دو هدف عمده دارند: 1- کاهش تعداد کاراکترهایی که نیاز است مورد مقایسه قرار گیرند (در بدترین حالت و حالت متوسط) 2- کاهش زمان مورد نیاز در بدترین حالت و حالت متوسط تطبیق رشته یکی از مهم ترین و پرکاربردترین زمینه های تطبیق الگو است که در آن الگوها رشته هایی از کاراکترها هستند که باید در یک متن ورودی که شامل دنباله ای از رشته هاست یافت شوند. الگوریتم های تطبیق الگو دو مرحله مختلف دارند: 1- مرحله پیش پردازش یا مطالعه الگو 2- مرحله پردازش یا جستجوی الگو در مرحله پیش پردازش اطلاعات کاملی درباره الگو جمع آوری شده و از این اطلاعات برای بهینه کردن تعداد مقایسه ها استفاده می شود ،حال آنکه مرحله جستجو الگو را به وسیله اطلاعاتی که در مرحله قبلی جمع آوری شده است پیدا می کند. دسته بندی الگوریتم های تطبیق رشته در حال حاضر الگوریتم های تطابق رشته زیادی وجود دارد که هر یک برای کاربردی مفید است،محققین از جنبه های گوناگون این الگوریتم ها را مورد مطالعه قرار داده و به همین جهت دسته بندی های متنوعی برای الگوریتم های تطبیق رشته ارایه شده است. الف) بر اساس نیاز یک متن یا الگو به مرحله پیش پردازش 1- الگوریتم های تطبیق رشته برخط 2- الگوریتم های تطبیق رشته اندیسی ب) بر اساس طول الگو 1- تطبیق پیشوندی 2- تطبیق پسوندی ج) بر اساس نوع پیدا کردن 1- تطبیق رشته دقیق 2- تطبیق رشته نسبی د) بر اساس تعداد الگو های مورد جستجو در متن 1- تطبیق تک الگویی 2- تطبیق چند الگویی اشاره (!) تطبیق رشته دقیق الگو را به طور دقیق در متن پیدا کرده و تطبیق رشته نسبی تمام الگوهای مشابه را در متن پیدا می کند. اگر یک الگوی خاص در متن مورد جستجو قرار گیرد تطبیق تک الگویی و اگر نیاز به جستجوی بیشتر از یک الگو در متن باشد تطبیق چند الگویی (چند گانه) خواهد بود،تطبیق چند الگویی می تواند هم زمان چند الگو را در متن بیابد. مهم ترین الگوریتم های تطبیق رشته Aho-Corasick ، KMP ، Boyer-Moore (BM) ، Horspool ، Boyer Moore Horspool (BMH) ، Zhu Takaoka ، Quick Search ، Berry and Ravindran(BR) ، SBOM (Set Backward Oracle Matching) ، Wu – Manber ، Fast Searching ، ZTMBH ، BRBMH SOG and … تطبیق رشته دقیق الگوریتم های تطبیق رشته دقیق سعی در پیدا کردن تمام مکان های وجود (تکرار) یک الگو در یک متن ورودی دارند. مسئله تطبیق الگوی دقیق را می توان این طور تعریف کرد: الگوی p با طول m و رشته T با طول n (m<=n) را در نظر می گیریم. کار اصلی پیدا کردن تمام رخداد های p در رشته T است به طوری که تطابق ها باید دقیق باشند یعنی باید دقیقا همان الگو در متن پیدا شود. نحوه کار الگوریتم های تطبیق دقیق رشته بدین صورت است که از سمت راست الگو و متن شروع به جستجو می کند در مواردی که یک عدم تطابق یا تطابق کامل یافت شود با استفاده از برخی ملاحظات الگو را به سمت راست انتقال داده و همین مراحل تکرار می شود تا زمانی که الگو به پایان سمت راست متن برسد. تطبیق رشته نسبی تطبیق الگوی غیر دقیق گاهی تطبیق رشته نسبی یا تطبیق با K عدم تطابق هم نامیده می شود. در این روش متنی که به صورت تقریبی با الگو تطابق داشته باشد پیدا می شود. تطبیق رشته نسبی به این صورت تعریف می شود: الگوی p با طول m و رشته T با طول n (m<=n) را در نظر می گیریم. کار اصلی پیدا کردن تمام رخداد های زیر رشته X درT است که به P شبیه هستند البته برای شباهت معیاری وجود دارد مثلا گفته می شود که تفاوت زیر رشته با P ، K کاراکتر باشد. این گونه الگوریتم ها معمولا از دو قسمت تشکیل می شوند : پیدا کردن تقریب مناسب برای این که بتوان بر آن تکیه کرد و بعد پیدا کردن تطبیق تقریبی الگو با قسمتی از متن. الگوریتم های تطبیق الگوی نسبی به 4 گروه تقسیم می شوند که عبارتند از: 1- روش برنامه نویسی پویا 2- روش اتوماتا 3- روش تقارن بیتی 4- روش فیلترکردن و خودکارسازی تطبیق تک الگویی مسئله تطبیق تک الگویی رشته را می توان به صورت زیر تعریف کرد: فرض کنید T رشته بزرگی است که از n کاراکتر تشکیل شده است و P یک الگو با اندازه ی m باشد. : الگو P = P[1]P[2]………P[m] : متنT = T[1]T[2]………T[n] کاراکتر های هر دو مجموعه P و T به یک مجموعه متناهی از عناصر مجموعه S تعلق دارد که m<<n است. فرایند جستجوی تک الگویی تمام رخدادهای موجود از الگوی P را در متن T نمایان می کند. تطبیق چند الگویی مسئله تطبیق چند الگویی (چندگانه) به شکل زیر تعریف می شود: با فرض مجموعه ای از الگوهای P = {p1,p2,…,pn}که در آن هر pi یک الگوی عبارت منظم از مجموعه الفبای ∑ است مسئله تطبیق چندالگویی عبارت است از پیدا کردن تمام رخداد های این الگوها در مجموعه داده D با الفبای یکسان. الگوریتم های تطبیق چند الگویی الگوریتم های متعددی برای تطبیق چند الگویی به کار رفته است که می توان آنها را به دو گروه کلی تقسیم کرد: 1- الگوریتم های مبتنی بر درخت 2- الگوریتم های مبتنی بر فیلترکردن الگوریتم های مبتنی بر درخت راه حل اصلی این الگوریتم ها ساخت درختی از الگو ها و جستجوی متن با کمک این درخت است. مشکل اصلی این الگوریتم ها این است که به همان سرعت که مجموعه الگوها بزرگ می شود درخت نیز به سرعت رشد می کند و نیاز به فضای بیشتری دارد. به همین دلیل برای مجموعه الگوهای بزرگ استفاده از این روش چندان مؤثر نیست. الگوریتم های مبتنی بر فیلترکردن ایده اصلی این الگوریتم ها این است که یک موقعیت در متن در نظر گرفته می شود و توسط یک فیلتر مشخص می شود که آیا در این مکان یک تطبیق با الگو وجود دارد یا نه. تطبیق دقیق چند الگویی الگوریتم های تطبیق دقیق چند الگویی به طور کلی به دو دسته تقسیم می شوند: 1- الگوریتم های مبتنی بر جدول انتقال 2- الگوریتم های مبتنی بر ماشین خودکار الگوریتم های مبتنی بر جدول انتقال از چند جدول از قبل محاسبه شده استفاده می کنند تا موقعیت مناسب بعدی را که الگو ممکن است در آن جا اتفاق بیفتد مشخص می کنند. روش های مبتنی بر ماشین خودکار از یک نمایش مبتنی بر DFA یا NFA برای نشان دادن عبارات منظم استفاده می کنند. از آن جایی که نمایش NFA تحت تاثیر مباحث ذخیره سازی است معمولا کندتر از DFA است. الگوریتم های تطبیق رشته در این مجال برخی از الگوریتم های تطبیق رشته را که پایه و اساس دیگر الگوریتم ها به شمار می روند شرح می دهیم: 1- الگوریتم جستجوی رشته نیو (Naive) آسان ترین و ناکارآمدترین راه برای آن که یک رشته و مکان آن را در یک متن پیدا کنیم امتحان کردن یک به یک همه مکان هایی است که آن رشته می تواند قرار بگیرد. در صورتی که متنی به طول n به صورت T[1…n] و رشته به طول m به صورت P[1…m] داشته باشیم که m<=n الگوریتم نیو همه حالت های ممکن را به این صورت بررسی می کند : در هر مرحله رشته P[1…m] با زیر رشته ای از متن T مقایسه می گردد. زیر رشته مورد نظر در مرحله اول از متن T[1…m] ، در مرحله دوم m حرف دوم از متن T[2…m+1] و به همین ترتیب در مرحله s ام m حرف s ام از متن T[s+1…s+m] می باشد. در این مقایسه ها هر بار که دو رشته مقایسه شده یکسان باشند نشانگر یک بار رخ دادن رشته P در متن T است. شبه کد جستجوی رشته نیو procedure NaiveStringMatcher (T,P) begin n=lenght(T); m=lenght(P); for s=0 to n-m do if P[1...m]=T[s+1...s+m] then print «Pattern occurs with shift» s; end 2- الگوریتم KMP معروف ترین الگوریتم تطبیق رشته و دارای زمانی خطی است، که سه تن از محققان (Donald Knuth, Vaughan Pratt, James H. Morris) این الگوریتم را به طور مجزا ایجاد نمودند. این الگوریتم در میان رشته S وجود کلمه W را بررسی می کند که برای این کار محل عدم تطابق کلمه را زیر نظر می گیرد تا با استفاده از آن بتواند اطلاعاتی را درباره مکان تطابق احتمالی بعدی به دست آورد. به طوری که وقتی یک عدم تطابق اتفاق می افتد خود کلمه اطلاعات کافی را در بر دارد تا محلی را که مطابقت بعدی ممکن است از آن جا شروع شود با آزمایش دوباره حروف تطبیق داده شده قبلی تعیین کند. الگوریتم جستجوی KMP While m+i is less than the length of S, do: If W[i] = S[m + i], If i equals the (length of W)-1, Return m Let i ←i + 1 otherwise, let m ←m + i - T[i], if T[i] is greater than -1, let i ←T[i] else let i ←0 اگر به این نقطه رسیدیم نتوانسته ایم تمام طول S را با موقعیت جستجو کنیم Return the length of S جدول تطابق جزئی (عمل شکست) هدف از ساختن این جدول آن است که الگوریتم هیچ کاراکتری از S را بیش از یک بار مطابقت ندهد. مثالی از جدول تطابق جزئی الگوریتم KMP (http://www.uploadax.com/images/72518545826998356990.bmp) الگوریتم kmp_table Let T[0] ←-1, T[1] ←0 While pos is less than the length of W, do: (first case: the substring continues) If W[pos - 1] = W[cnd], Let cnd ←cnd + 1, T[pos] ←cnd, pos ←pos + 1 (second case: it doesn't, but we can fall back) otherwise, if cnd > 0, let cnd ←T[cnd] (third case: we have run out of candidates. Note cnd = 0) otherwise, let T[pos] ←0, pos ←pos + 1 3- الگوریتم Boyer-Moore این الگوریتم مبتنی بر تطبیق دقیق تک الگویی است. این الگوریتم الگو و متن را از راست به چپ مقایسه می کند. در مواردی که یک عدم تطابق یا تطابق کامل اتفاق بیفتد الگوریتم از دو تابع انتقال استفاده می کند تا مکان شروع مقایسه بعدی را محاسبه کند. توابع انتقال الگوریتم بویر - مور که برای کم کردن تعداد مقایسه ها به کار می روند عبارتند از: • Bad Character • Good Suffix Bad Characteri (I در این حالت تابع occ را داریم که برای هر کاراکتر موجود در الفبا اندیس سمت راست ترین موقعیت رخداد آن کاراکتر را در الگو محاسبه می کند و اگر آن کاراکتر در الگو نباشد مقدار 1- را برای آن کاراکتر تخصیص می دهد. تابع bmInitocc تابع رخداد را برای الگوی P محاسبه می کند. void bmInitocc() { char a; int j; for (a=0; a<alphabetsize; a++) occ[a]=-1; for (j=0; j<m; j++) { a=p[j]; occ[a]=j; } } Good Suffix (II در این روش از یک آرایه به نام s استفاده می شود که مقدار هر درایه آن (s[i]) مقدار انتقال الگو است. اگر یک عدم تطابق در موقعیت i-1رخ دهد. برای مشخص کردن مقدار انتقال دو حالت به وجود می آید: حالت 1 : قسمت تطابق یافته از الگو در جای دیگری از الگو رخ داده باشد. حالت 2 : فقط قسمتی از قسمت تطابق یافته در جای دیگری از الگو رخ داده باشد. (http://www.uploadax.com/images/63554025687579014093.bmp) مرحله جستجو در مرحله جستجو الگو ها از چپ به راست با متن مقایسه می شوند. بعد از یک تطابق کامل الگو میزان انتقال برابر با بیشترین مقادیری است که از توابع good-suffix و bad-character به دست آمده است. Boyer-Moore searching algorithm void bmSearch() { int i=0, j; while (i<=n-m) { j=m-1; while (j>=0 && p[j]==t[i+j]) j--; if (j<0) { report(i); i+=s[0]; } else i+=Math.max(s[j+1], j-occ[t[i+j]]); } } 4- الگوریتم Boyer Moore Horspool این الگوریتم نسخه ساده شده الگوریتم بویر- مور است. این الگوریتم مقایسه ها را از سمت راست ترین کاراکتر شروع کرده و الگو را به راست حرکت می دهد. در مواردی که عدم تطابق یا تطابق کامل وجود داشته باشد این الگوریتم فقط از تابع انتقال Horspool bad استفاده می کند. 5- الگوریتم Aho-Corasick بسیاری از الگوریتم های تطابق رشته همانند الگوریتم KMP یا Boyer Moore برای جست و جوی یک رشته الگو در میان یک متن استفاده می شوند و مکان تکرار آن را در آن متن مشخص می کنند. ولی در برخی کاربردها نیاز به پیدا کردن بیش از یک رشته الگو در داخل یک متن داریم. الگوریتم آهوکوراسیک (AC) یک الگوریتم تطابق رشته ای چندگانه (تطابق چند الگویی) است که توسط آلفرد وی آهو و مارگارت جی کوراسیک ارایه شده است. 6- الگوریتم جستجوی Rabin – Karp این الگوریتم برای پیدا کردن مجموعه ای از رشته ها (الگوها) در یک متن از درهم سازی استفاده می کند. این کار در دو مرحله پیش پردازش و تطابق انجام می گیرد. این الگوریتم می تواند با سرعت بالا جمله ای را در بین مقالات مختلف بدون در نظر گرفتن بزرگی و کوچکی و اعراب جستجو کند. ایده اصلی در الگوریتم رابین – کارپ این است که این الگوریتم سعی دارد با به کارگیری تابع درهم سازی سرعت مقایسه رشته الگو و زیر رشته های متن را افزایش داده و از این طریق زمان اجرا را بهبود بخشد. تابع درهم سازی یک تابع درهم سازی تابعی است که مجموعه بزرگی از داده ها را به مجموعه کوچکتری از داده ها نگاشت می کند. در این جا تابع درهم سازی هر رشته را به یک مقدار عددی که به آن مقدار درهم سازی می گویند تبدیل می کند. برای مثال اگر تابع را برابر طول رشته تعریف کنیم hash("hello")=5 و hash("cat ")=3 خواهد بود. الگوریتم رابین – کارپ به جای مقایسه حرف به حرف دو رشته مقادیر درهم سازی آنان را مقایسه می کند. شبه کد الگوریتم Rabin – Karp procedure Rabin-Karp-Matcher (T,P,d,q) begin n = lenght(T); m = lenght(P); h = d^(m-1) mod q; p = 0; t = 0; for i = 1 to m do // Preprocessing p = (d*p + P[i]) mod q; t = (d*t + T[i]) mod q; for s = 0 to n-m do // Matching if p = t then if P[1...m] = T[s+1...s+m] then print «Pattern occurs with shift» s; if s < n-m then t = ( d * (t - T[s+1]*h ) + T[s+m+1] ) mod q; end روش های اندیسی الگوریتم های مبتنی بر اندیس یک نوع از الگوریتم های سریع تطبیق رشته مبتنی بر پیش پردازش متن هستند ، اساس این روش ها بر اندیس گذاری متن و الگو است. 7- الگوریتم SKIP SEARCH در این الگوریتم دو جدول اندیس یکی برای الگو و دیگری برای رشته ورودی تعریف شده و جستجو از طریق مقایسه اندیس های این جداول انجام می شود. شبه کد الگوریتم SKIP SEARCH ورودی: رشته S شامل n کاراکتر و یک الگوی P شامل m کاراکتر خروجی: تعداد رخدادهای و مکان های الگوی P در رشته S Algorithm: N=length of the string, M=length of the pattern. S= String ,P=Pattern Struct bucket { int *a; //for storing the index of letters. int count; //store total no occurrences of the} Str_buck[4], Ptr_buck[4] //for storing the indexes of the letters A,C,T and G Index //index of the letter chosen with minimum count. 1) Pre-Processing Phase //Store the index of the pattern 1.Loop for i=1 to i=N Str_buck[A,C,T,G].a[i]=i ; Str_buck[A…T].cout+=1; //Store the index of the pattern 2.Loop for i=1 to i=M Ptr_buck[A,C,T,G].a[i]=i ; Ptr_buck[A…T].cout+=1; 3. Find Index for which ((Str_buck[A..T].count)*(Str_buck[A…T].count) is minimum; Assign , mini_scount=Str_buck[Index].count mini_pcount=Ptr_buck[Index].count 2) Searching Phase LOOP1 i=1 to i=mini_scount q=S[Index].a[i] LOOP2 j=1 to j=mini_pcount IF (q>=Previous Pattern Index + Position of jth Char in Pattern) t=Str_buck[index].a[index]-Ptr_buck[index].a[index]; //t store the starting position from where it starts comparison in the string. LOOP3 k=1 to k=M Compare (S[t++],P[k]) until a mismatch occurs or Match Occurs. PRINT “Starting Index of the string for the Matched Pattern”. END LOOP3 END LOOP3 END LOOP1 جدول اندیس های حروف موجود در الگو (http://www.uploadax.com/images/02286088333229486734.bmp) مانند الگو اندیس های تمامی مکان های رخداد کاراکترها در رشته ورودی نیز در جدول اندیس ذخیره می شود. بعد از تشکیل این دو جدول یک کاراکتر انتخاب شده و مرحله جستجو آغاز می شود. جدول اندیس های حروف موجود در رشته ورودی (http://www.uploadax.com/images/16733399178656057302.bmp) با توجه به جداول بالا حرف G انتخاب می شود چون کمترین مقدار حاصل ضرب را دارد 4*1=4 این کاراکتر به عنوان کاراکتر انتخاب شده به مرحله بعدی (جستجو) فرستاده می شود. اگر دو کاراکتر مقدار حاصل ضرب یکسانی داشته باشند کاراکتری انتخاب می شود که مقدار کمتری در جدول اندیس رشته ورودی داشته باشد. 8- الگوریتم K-PARTITIONS ایده اصلی این الگوریتم تقسیم کردن الگو و رشته ورودی به بخش هایی با اندازه K و مقایسه ترتیبی کاراکتر های هر بخش به جای تمامی کاراکتر هاست تا بتوان از این طریق تعداد مقایسه ها را کاهش داد. شبه کد الگوریتم K-PARTITIONS ورودی: رشته S شامل n کاراکتر و یک الگوی P شامل m کاراکتر خروجی: تعداد رخدادهای و مکان های الگوی P در رشته S IKPMPM Algorithm Step 1: Integer arrays indexTab[4][n], charIndex[4] Integer found:=1, n_occ:=0, n_cmp:=1, boxes; Step 2: FOR i:=0;i<n;i:=i+1 indexTab[(S[i]-64)%5][charIndex[(S[i]-64)%5]++]:=i; End FOR Step 3:FOR i:=0;i<chatIndex[(P[0]-64)%5]; i:=i+1 found:=1; IF i+m-1 > n-1 found:=0 End IF boxes:=⎡m/BOXSIZE⎤ FOR k:=0;k<BOXSIZE;k:=k+1 Step 4:FOR j:=0;j<BOXSIZE*boxes;j:=j+BOXSIZE IF k+j < m n_cmp:=n_cmp+1 IF P[k+j]=S[i+j+k] DO NOTHING End IF ELSE found:=0 End ELSE End IF End FOR End FOR Step 5: IF found:=1 n_occ:=n_occ+1 PRINT “Pattern Found At Location i,Occurrence no is: n_occ” End IF End FOR تذکر(!) با بررسی دو الگوریتم ارایه شده مبتنی بر اندیس در می یابیم که این گونه روش های اندیسی برای مسایل تطبیق الگو که که در آن ها تعداد الفبا کوچک است (مانند تطبیق رشته در دنباله DNA بدن انسان که الفبای آن تنها دارای 4 کاراکتر {A,C,G,T} است) کارامد است. 9- الگوریتم Commentz-Walter این الگوریتم توابع فیلتر کردن الگوریتم های تطبیق تک الگویی مثل الگوریتم Boyer- Moore را با یک اتوماتای پسوندی ترکیب می کند تا محل های رخداد الگوهای چندگانه را در متن ورودی جستجو کند. 10- الگوریتم Wu-Manber این الگوریتم از عمومیت بخشیدن الگوریتم Horspool به دست آمده است و یک نوع ساده از الگوریتم Boyer- Moore است که فقط از تابع انتقال bad- character برای تطابق چند الگویی استفاده می کند. 11- الگوریتم Fast Searching این الگوریتم نوعی از الگوریتم Boyer- Moore است که کاراکتر های الگو و متن را از راست به چپ ب هم مقایسه می کند. در مواردی که عدم تطابق فقط در کاراکتر آخر وجود داشته باشد و یا به تطابق کامل برسیم از تابع bad- character استفاده می کند در غیر این صورت از تابع good suffix استفاده می کند. این الگوریتم برای الگوهای خیلی کوتاه بازده خوبی دارد. 12- الگوریتم Quick Search در این الگوریتم جستجو و مقایسه از انتهای رشته شروع شده و تا ابتدا ادامه می یابد. وقتی که یک عدم تطابق یافت شود الگوریتم محل بعدی را که جستجو باید از آن جا آغاز شود مشخص می کند. این الگوریتم برای الگوهای کوتاه با تعداد الفبای بالا بسیار مناسب است. 13- الگوریتم Bitap الگوریتم بایتپ الگوریتمی برای تشخیص تطابق تقریبی دو رشته است. این الگوریتم مشخص می کند که در متن ورودی زیر رشته ای وجود دارد که تقریبا با الگوی مورد نظر داده شده برابر باشد. در ادامه یک پیاده سازی کلی از الگوریتم بایتپ برای جستجوی دقیق الگو در متن به زبان سی ارایه شده است: #include <stdlib.h> #include <string.h> typedef char BIT; /* needs only to hold the values 0 and 1 */ const char *bitap_search(const char *text, const char *pattern) { const char *result = NULL; int m = strlen(pattern); BIT *R; int i, k; if (pattern[0] == '\0') return text; /* Initialize the bit array R */ R = malloc((m+1) * sizeof *R); R[0] = 1; for (k=1; k <= m; ++k) R[k] = 0; for (i=0; text[i] != '\0'; ++i) { /* Update the bit array. */ for (k=m; k >= 1; --k) R[k] = R[k-1] && (text[i] == pattern[k-1]); if (R[m]) { result = (text+i - m) + 1; break; } } free(R); return result; } توجه کنید در پیاده سازی کلی برای تبدیل شرط (text[i] == pattern[k-1]) به یک عملگر دودویی ، نیاز به یک ماسک دودویی CHAR_MAX داریم: #include <string.h> #include <limits.h> const char *bitap_bitwise_search(const char *text, const char *pattern) { int m = strlen(pattern); unsigned long R; unsigned long pattern_mask[CHAR_MAX+1]; int i; if (pattern[0] == '\0') return text; if (m > 31) return "The pattern is too long!"; /* Initialize the bit array R */ R = ~1; /* Initialize the pattern bitmasks */ for (i=0; i <= CHAR_MAX; ++i) pattern_mask[i] = ~0; for (i=0; i < m; ++i) pattern_mask[pattern[i]] &= ~(1UL << i); for (i=0; text[i] != '\0'; ++i) { /* Update the bit array */ R |= pattern_mask[text[i]]; R <<= 1; if (0 == (R & (1UL << m))) return (text + i - m) + 1; } return NULL; } در ادامه پیاده سازی الگوریتم تطبیق نسبی بایتپ ارایه شده است. این الگوریتم اولین زیر رشته ای که حداکثر k خطا در بر دارد برخواهد گرداند: #include <stdlib.h> #include <string.h> #include <limits.h> const char *bitap_fuzzy_bitwise_search(const char *text, const char *pattern, intk) { const char *result = NULL; int m = strlen(pattern); unsigned long *R; unsigned long pattern_mask[CHAR_MAX+1]; int i, d; if (pattern[0] == '\0') return text; if (m > 31) return "The pattern is too long!"; /* Initialize the bit array R */ R = malloc((k+1) * sizeof *R); for (i=0; i <= k; ++i) R[i] = ~1; /* Initialize the pattern bitmasks */ for (i=0; i <= CHAR_MAX; ++i) pattern_mask[i] = ~0; for (i=0; i < m; ++i) pattern_mask[pattern[i]] &= ~(1UL << i); for (i=0; text[i] != '\0'; ++i) { /* Update the bit arrays */ unsigned long old_Rd1 = R[0]; R[0] |= pattern_mask[text[i]]; R[0] <<= 1; for (d=1; d <= k; ++d) { unsigned long tmp = R[d]; /* Substitution is all we care about */ R[d] = (old_Rd1 & (R[d] | pattern_mask[text[i]])) << 1; old_Rd1 = tmp; } if (0== (R[k] & (1UL << m))) { result = (text+i - m) + 1; break; } } free(R); return result; } 14- الگوریتم Needleman Wunsch از این الگوریتم در بیوانفورماتیک استفاده می شود، در حقیقت این الگوریتم نمونه ای از برنامه نویسی پویا است. 15- الگوریتم Smith Waterman یک الگوریتم معروف برای اجرای هم تراز کردن دنباله های محلی است و به جای جستجو در کل دنباله ها قطعه هایی از همه طول های ممکن را مقایسه می کند و اندازه گیری شباهت را بهینه می کند. جدول مقایسه الگوریتم های تطبیق رشته (http://www.uploadax.com/images/23023200135545536724.bmp) کاربردهای مختلف الگوریتم ها • ویرایشگر متن کتابخانه دیجیتال و موتورهای جستجو • کاربردهای چند رسانه ای و زیست شناسی محاسباتی • آزمایش های پزشکی • تشخیص نفوذ در شبکه پژوهش های مشابه قرآنی 1- موتور های جستجو در زمینه تشخیص وجود یک آیه در متن 2- روشی برای طبقه بندی قرآن براساس ترتیب زمانی سوره 3- روشی برای طبقه بندی قرآن براساس مراحل مختلف زندگانی پیامبر مکرم اسلام (ص) 4- یک طبقه بندی آماری برای آیه های قرآن 5- یک چارچوب کارآمد به نام DataQuest برای مدل کردن و بازیابی دانش از منابع دانش توزیع شده مربوط به قرآن 6- حاشیه نویسی قرآن کریم برای متن کاوی 7- سیستم تشخیص خودکار گفتار مستقل از گوینده برای قرآن #چارچوب پیشنهادی سیستم هوشمند تشخیص خودکار آیات قرآنی الگوریتم سیستم هوشمند تشخیص خودکار آیات قرآنی در حیطه الگوریتم های تطبیق رشته دقیق قرار دارد چرا که می بایست عباراتی که تطبیق کامل با آیات قرآنی دارند جستجو شوند از طرفی چون بیش از یک الگو (تمامی کلمات قرآن) را در متن جستجو می کنیم باید یک الگوریتم تطبیق چند الگویی پیاده سازی کنیم. پیشنهاد ما یک الگوریتم تطبیق رشته دقیق مبتنی بر اندیس گذاری می باشد. تطبیق چند الگویی در مورد آیات قرآن کریم این سیستم از جهات زیر با سیستم های تطابق دقیق چند الگویی متمایز است: 1- جستجوی الگوهای متوالی 2- شکل های متفاوت برای یک الگو 3- حجم بسیار بزرگ مجموعه داده الگو در مقایسه با دیگر الگوریتم ها 4- پیاده سازی سیستم تطابق دقیق چند الگویی مشخصا برای قرآن جستجوی الگوهای متوالی یکی از مسائل منحصر به فرد در این سیستم که الگوریتم آن را پیچیده تر از سایر روش های جستجوی تطابق چند الگویی می سازد این است که علاوه بر یافتن الگوها توالی الگوها نیز یکی از شروط جستجوی الگوست. یعنی اگر کلمه ای از متن با الگویی تطابق داشت کلمه بعدی در متن باید با الگوی بعدی در بانک الگو تطابق داشته باشد تا بتوان قطعاتی از آیات را در متن تشخیص داد. بنابراین مسئله از جستجوی الگو به جستجوی الگوهای متوالی تغییر می یابد. شکل های متفاوت برای یک الگو یک کلمه در قرآن ممکن است رسم الخط های مختلفی داشته باشد (زیرا املاهای مختلفی برای نوشتن برخی از کلمات قرآنی وجود دارد) این بدین معنی است که ممکن است یک الگو به شکل های مختلفی ظاهر شود اما تمامی این رسم الخط های متفاوت یک کلمه باید به عنوان یک الگو تشخیص داده شوند. حجم بسیار بزرگ مجموعه داده الگو در مقایسه با دیگر الگوریتم ها قرآن کریم دارای بیش از 84000 کلمه است که هر کدام خود یک الگو را تشکیل می دهند علاوه بر آن در این موتور جستجو از تمامی رسم الخط های قرآنی موجود پشتیبانی می شود و این مسئله حجم مجموعه الگو ها را چهار برابر افزایش می دهد. الگوریتم سیستم تشخیص هوشمند آیات قرآنی دارای 5 مرحله می باشد : 1- ساخت بانک قرآنی 2- پردازش اولیه بر روی متن ورودی 3- شناسایی کلمات قرآنی 4- جستجوی توالی الگوها و تشخیص آیه 5- آدرس دهی و برجسته سازی آیات قرآنی درون متن اصلی ساخت بانک های قرآنی این مرحله ابتدایی ترین مرحله کار است که بانک های مورد نیاز سیستم را ایجاد می کنیم. برخی از بانک های مورد نیاز عبارت است از: بانک قرآن بانک رسم الخط های متفاوت بانک عبارات تک کلمه ای و دو کلمه ای بانک عبارات سه کلمه ای بانک قرآنی برای ساختن بانک قرآنی که اصلی ترین بانک اطلاعاتی سیستم است متن کامل قرآن را به صورت کلمه به کلمه و پشت سر هم در جدولی ذخیره می کنیم تا به هر کلمه از قرآن به صورت منحصر به فرد اندیسی تعلق یابد. هدف از این اندیس گذاری یکتا با علم به تکراری بودن بسیاری از کلمات قرآن در ادامه الگوریتم مشخص می شود. بانک رسم الخط های متفاوت از جمله رسم الخط های موجود در بین مسلمانان : ایرانی (طاهر خوشنویس) ترکی (حامد الآمدی) هندی مصری (عثمان طه) در جدول زیر مثالی از تفاوت کتابت این رسم الخط ها ارایه شده است. (http://www.uploadax.com/images/62509715524574747508.bmp) بانک عبارات تک کلمه ای و دو کلمه ای برای سنجش ارزش این عبارات دو معیار تعریف می کنیم : فراوانی عبارت موجود در متن تعداد قرآن بودن عبارت مورد نظر در متن در زیر تصویری از بانک های تک کلمه ای و دو کلمه ای ارایه شده است: (http://www.uploadax.com/images/99176875254590887885.bmp) (http://www.uploadax.com/images/40554429025353245636.bmp) بانک عبارات سه کلمه ای برخلاف آن چه در مورد عبارات تک کلمه ای و دو کلمه ای ذکر شد برخی عبارات قرآنی مانند {و ان کان ، و فی ذلک} و ... وجود دارند که علی رغم آن که سه کلمه پیاپی آن مشابه با برخی از بخش های قرآن است ولی استفاده آن در متون غیر قرآنی به حدی است که قرآن بودن آن را توجیه نمی کند. در زیر تصویری از بانک سه کلمه ای آورده شده است: (http://www.uploadax.com/images/28114545271640106456.bmp) پردازش اولیه بر روی متن ورودی در این مرحله ابتدا کاراکترهای اضافه از قبیل علایم ویرایشی اعراب و ... از متن حذف می شوند و برای هریک از کلمات باقی مانده ی متن ورودی اندیسی در نظر گرفته می شود تا جایگاهشان در متن مشخص باشد. شناسایی کلمات قرآنی در این مرحله تک تک کلمات متن به ترتیب چینش در متن با الگوهای موجود در بانک الگو مقایسه می شود. و اندیس الگوهایی که با کلمه مورد نظر تطابق دارند در آرایه ای ذخیره می شود. پس هر کلمه از متن به یک آرایه از اعداد نگاشته می شود. (http://www.uploadax.com/images/46623554196368432043.bmp) جستجوی توالی و تشخیص آیه با استفاده از جستجو بر روی اندیس ها به دنبال یک توالی اندیسی در بین کلمات قرآنی می گردیم چرا که در مرحله اول بانک قرآنی را به گونه ای تشکیل دادیم که تمامی کلمات یک آیه دارای اندیس های پشت سرهم هستند پس هر توالی اندیسی تشخیص یک آیه را می دهد. در این مرحله بلندترین رشته تطبیق یافته شده به عنوان آیه تشخیص داده شده برگردانده می شود. (http://www.uploadax.com/images/13302185484186640613.bmp) کمی تأمل(!) چون آرایه های مربوط به کلمات از ابتدا مرتب می شوند پس برای پیدا کردن بلندترین دنباله اعداد پشت سر هم از جستجوی دودویی استفاده می کنیم که سریع ترین جستجو در بین الگوریتم های جستجو است. حال اگر طول الگوی پیدا شده کمتر از 4 کلمه باشد باید از بانک های یک کلمه دو کلمه و سه کلمه ای استفاده کرد ،در این مرحله اگر طول الگوی پیدا شده سه کلمه باشد عبارت پیدا شده در بانک سه کلمه جستجو می شود اگر نتیجه جستجو مثبت باشد الگو به عنوان قرآن اعلام نمی شود ولی اگر نتیجه جستجو منفی باشد الگو به عنوان قرآن اعلام می شود. اگر طول الگوی پیدا شده 1 یا 2 کلمه باشد عبارت مورد نظر در بانک های یک یا دو کلمه ای جستجو می شود. اگر نتیجه جستجو مثبت باشد الگو به عنوان قرآن اعلام می شود ولی اگر نتیجه جستجو منفی باشد الگو به عنوان قرآن اعلام نمی شود. آدرس دهی و برجسته سازی آیات قرآنی در این مرحله با استفاده از اندیس الگو ها آیات قرآنی بازیابی شده و با استفاده از اندیس کلمات در رشته ورودی مکان حضور آیات قرآنی در متن نیز مشخص شده و به گونه ای برجسته می شود. #مجموعه داده ها برای انجام بررسی نتایج از دو منبع استفاده شده است: منابعی که آیات قرآنی در آن بسیار به چشم می خورد منابعی که آیات قرآنی کمتری دارد اما کلمات قرآنی در آن زیاد است # معیار های ارزیابی این سیستم جزو سیستم های بازیابی تشخیص اطلاعات است نه بازیابی داده معین ، چرا که ما با مسائلی من جمله اختلاف رسم الخط ها ، اختلاف قرائات و ... روبرو هستیم پس باید پردازش بیشتری و پیچیده تری روی سیستم انجام گیرد زیرا بازیابی اطلاعات برخلاف بازیابی داده ها با ابهاماتی رو به رو است بنابراین باید هر چه بیشتر اطلاعات را مدل کنیم تا ابهام در درک اطلاعات توسط سیستم کم شود در این سیستم همانند سیستم بازیابی اطلاعات معیار صحت ، دقت و معیار F معیار های اصلی ارزیابی اند معیار صحت تشخیص یک آیه تعداد کلماتی که به درستی به عنوان قرآن تشخیص داده شده اند نسبت به تعداد کل کلمات قرآنی موجود در متن معیار دقت تشخیص یک آیه تعداد کلماتی که به درستی به عنوان قرآن تشخیص داده شده اند نسبت به تعداد کل کلماتی که آیه تشخیص داده شده اند معیار F میانگین هارمونیک صحت و دقت و دارای تأثیرات هم زمان هر دو معیار # نتایج آزمایش ها متنی که توسط این سیستم هوشمند بررسی می شود برای هر کلمه در آن دو حالت پیش می آید که دو معیار ارزیابی در مورد آن است : بر اساس کلماتی که قرآن اعلام شده اند بر اساس کلماتی که قرآن اعلام نشده اند جداول زیر نتایج آزمایش ها را نشان می دهد: (http://www.uploadax.com/images/67855949070959668706.bmp) (http://www.uploadax.com/images/84723399126212734033.bmp) #کارهای آینده • ایجاد سیستم های هوشمند مکمل جستجو با استفاده از متون جستجوی تکمیلی کمکی نظیر: {قال تعالی، قوله عز و جل} و... که در اطراف متون قرآنی مشاهده می شوند • تشخیص هوشمند اختلاف قرائات و رسم الخط ها • اعراب گذاری هوشمند آیات قرآنی • انتخاب و یا هشدار هوشمند آدرس صحیح از میان آدرس های مشترک • ایجاد ارتباط میان متون خاص و عباراتی که تشابه معنایی با آن ها دارند در پایان باید خاطر نشان کنم به دلیل به هم خوردگی متن فایل pdf آن در پایین ضمیمه شده است. #مراجع [1] Tai, X., Ren, F. Kita, K., “An Information Retrieval Model based on Vector Space Method by Supervised Learning”, Information Processing & Management, 2001. [2] Alaa H. AL-Hamami, Mohammad A. AL-Hamami, Soukaena H. Hashem, “A strategy to compromise handwritten documents processing and retrieving using association rules mining”, Ubiquitous Computing and Communication (UbiCC) Journal, Volume6: Issue 3, pp. 901-906, 2011. [3] A. Christy, P. Thambidurai, “Extracting the information the information contained in electronic documents: a pattern matching algorithm for text mining”, journal of computer applications, Vol- 1, No.2, pp 18-21, Apirl-June 2008. [4] Witten, I. H., Don, K. J., Dewsnip, M. and Tablan, V. () “Text mining in a digital library.” International Journal on Digital Libraries 4(1), pp. 56-59, 2004. [5] Sharma, N., “Discovering knowledge with text mining”, M.S. Thesis, Texas A&M University, 2005. [6] Usama Fayyad, Gregory Piatetsky-Shapiro, and Padhraic Smyth, “From Data Mining to Knowledge Discovery in Databases”, American Association for Artificial Intelligence. All rights reserved. 0738-4602,1996. [7] Liddy, E. D., “Text mining”,Bulletin of the American Society for Information Science, 27 (1) :pp. 13-14, 2000. [8] J.Froelich, S.Ananyan, and D.L Olson, "Business Inteligence Through Text Mini.", Business Intelligence Journal, Vol.10, No. 1, pp. 43-50, April 2006. [9] Raymond J. Mooney and Un Yong Nahm, ”Text Mining with Information Extraction”, Multilingualism and Electronic Language Management: Proceedings of the 4th International MIDP Colloquium, Bloemfontein, South Africa, Daelemans, W., du Plessis, T., Snyman, C. and Teck, L. (Eds.) pp.141-160, Van Schaik Pub., South Africa, 2005. [10] Robert R. Korfhage,"Information Storage and Retrieval", ISBN: 978-0-471-14338-3, Hardcover 368 pages, June 1997. [11] Bi Kun, Gu Nai-jie, Tu Kun, Liu Xiao-hu, and Liu Gang , “A Practical Distributed String Matching Algorithm Architecture and Implementation”, World Academy of Science, Engineering and Technology 10, 2005. [12] Kuo-Kun Tseng, Ying-Dar Lin,Tsern-Huei Lee and Yuan-Cheng Lai, “A Parallel Automaton String Matching with Pre-Hashing and Root-Indexing Techniques for Content Filtering Coprocessor”, Proceedings of the16th International Conference on Application-Specific Systems, Architecture and Processors (ASAP’05),1063-6862/05, IEEE 2005. [13] Raju Bhukya, DVLN Somayajulu ; “Index based multiple pattern matching algorithm using DNA sequence and pattern count”, International Journal of Information Technology and Knowledge Management, Volume 4, No. 2, pp. 431-441, July-December 2011. [14] Raju Bhukya, DVLN Somayajulu, “Exact Multiple Pattern Matching Algorithm using DNASequence and Pattern Pair”. International Journal of Computer Applications (0975 – 8887). Volume 17– No.8, March 2011. [15] Raju Bhukya, DVLN Somayajulu, "An Index based Forward Backward Multiple Pattern Matching Algorithm ", World Academy of Science, Engineering and Technology 66, pp. 1527-1537, 2010. [16] Ramakrishnan Kandhan, Nikhil Teletia, Jignesh M. Patel, “SigMatch: Fast and Scalable Multi-Pattern Matching”, Vol. 3, No. 1, Proceedings of the 36th International Conference on Very Large Data Bases, Singapore, September 2010. [17] Changsheng Miao Sch. of Inf. Sci. & Eng., Northeastern Univ., Shenyang, China, "Filtering Based Multiple String Matching Algorithm Combining q-Grams and BNDM ", Fourth International Conference on Genetic and Evolutionary Computing (ICGEC), pp. 582 - 585, Shenzhen , 15 Dec. 2010. [18] S. Fide and S. Jenks, “ A Survey of String Matching Approaches in Hardware”, Department of Electrical Engineering and Computer Science University of California, Irvine, USA. 2008. [19] Awsan Abdulrahman Hasan, Nur’Aini Abdul Rashid, "Hybrid Exact String Matching Algorithm for Intrusion Detection System ", PP. 181-185, ICCIT, 2012. [20] Raju Bhukya, DVLN Somayajulu, "Index Based Sequential Multiple Pattern Matching Algorithm Using Pair Indexing ",International Conference on Life Science and Technology IPCBEE vol.3, pp. 1100-104, IACSIT Press, Singapore, 2011. [21] Raju Bhukya, DVLN Somayajulu,"An even odd multiple pattern matching algorithm ", International Journal of Engineering Science and Technology (IJEST), ISSN : 0975-5462 Vol. 3 No. 3, pp. 2118,2126, March 2011. [22] TAN Jianlong, LIU Xia, LIU Yanbing, LIU Ping, “Speeding up Pattern Matching by Optimal Partial String Extraction”, the First International Workshop on Security in Computers, Networking and Communications, 978-1-4244-9920-5/11, IEEE 2011. [23] Raju Bhukya, DVLN Somayajulu, "An Index Based Sequential Multiple Pattern Matching Algorithm",International Conference on Bioscience, Biochemistry and Bioinformatics IPCBEE vol.5, pp. 322-326, IACSIT Press, Singapore, 2011. [24] Raju Bhukya, Balram Parmer, Anand Kulkarni, "An Index Based Skip Search Multiple Pattern Matching Algorithm ", International Journal on Computer Science and Engineering (IJCSE), ISSN : 0975-3397 Vol. 3 No. 4, pp. 1510-1517, Apr 2011. [25] Vidya SaiKrishna, Akhtar Rasool, and Nilay Khare, "String Matching and its Applications in Diversified Fields", IJCSI International Journal of Computer Science Issues, Vol. 9, Issue 1, No 1, pp. 219-226, ISSN (Online): 1694-0814 , January 2012. [26] Prasad J.C and K.S.M.Panicker, “String Searching Algorithm Implementation-Performance Study with Two Cluster Configuration”, International Journal of Computer Science & Communication, Vol. 1, No. 2, pp. 271-275, July-December 2010. [27] Nimisha Singla, Deepak Garg, "String Matching Algorithms and their Applicability in various Applications", International Journal of Soft Computing and Engineering (IJSCE) ISSN: 2231-2307, Volume-I, Issue-6, January 2012. [28] A Fadel Klaib, Z Zainol, N Hashimah Ahamed, R Ahmad, and W Hussin, “Application of Exact String Matching Algorithms towards SMILES Representation of Chemical Structure”, World Academy of Science, Engineering and Technology 34, 2007. [29] Panagiotis D. Michailidis, Konstantinos G. Margaritis, "Flexible Approximate String Matching Application on a Heterogeneous Distributed Environment", Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA '03, Las Vegas, Nevada, USA, Volume 1; , June 23 - 26, 2003. [30] Charalampos S. Kouzinopoulos, Panagiotis D. Michailidis and Konstantinos G. Margaritis, “Parallel Processing of Multiple Pattern Matching Algorithms for Biological Sequences: Methods and Performance Results”, In: Bioinformatics - Computational Biology and Modeling, pp. 161-182, ISBN 979-953-307-280-6, 2011. [31] Leena Salmela, “Multi-Pattern String Matching with Very Large Pattern Sets”. ACM Journal of Experimental Algorithmic, Volume 11, November 1st 2007. [32] Iulian Moraru, David G. Andersen, “Exact Pattern Matching with Feed-Forward Bloom Filters”. by SIAM, 2011. [33] Scarpazza, D.P.; Villa, O.; Petrini, F., “High-speed string searching against large dictionaries on the Cell/B.E. Processor”. Parallel and Distributed Processing, IPDPS 2008. IEEE International Symposium on. ISSN: 1530-2075, pp. 1 – 12., Miami,FL, 14-18 April 2008. [34] Donald Knuth; James H. Morris, Jr, Vaughan Pratt, "Fast pattern matching in strings". SIAM Journal on Computing 6 (2): PP. 323–350, 1977. [35] Awsan Abdulrahman Hasan and Nur Aini Abdul Rashid, “Hash - Boyer-Moore - Horspool String Matching Algorithm for Intrusion Detection System”, International Conference on Computer Networks and Communication Systems (CNCS 2012) IPCSIT vol.35(2012) IACSIT Press, Singapore, 2012. [36] http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/bmen.htm. [37] Cheng-Hung Lin, Sheng-Yu Tsai, Chen-Hsiung Liu, Shih-Chieh Chang, Jyuo-Min Shyu, “Accelerating String Matching Using Multi-threaded Algorithm on GPU”, 978-1-4244-5637-6/10/$26.00, IEEE, 2010. [38] Pekka Kilpel ¨ainen, “Biosequence Algorithms, Lecture 4: Set Matching and Aho-Corasick Algorithm”, University of Kuopio Department of Computer Science spring 2005. [39] Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein, "The Rabin–Karp algorithm". Introduction to Algorithms (2nd edition ed.). Cambridge, Massachusetts: MIT Press. pp. 911–916. ISBN 978-0262032933, 2001. [40] Raju Bhukya, DVLN Somayajulu, “An Index Based K-Partitions Multiple Pattern Matching Algorithm”, Proc. of Int. Conf. on Advances in Computer Science 2010 ACEEE, DOI: 02.ACS.2010.01.194, PP. 83-87, 2010. [41] R. Baeza-Yates and G. Navarro, "A faster algorithm for approximate string matching", In Dan Hirchsberg and Gene Myers, editors ,Combinatorial Pattern Matching (CPM'96), LNCS 1075, pages 1– 23, Irvine, CA, June 1996. [42] G. Myers. "A fast bit-vector algorithm for approximate string matching based on dynamic programming", Journal of the ACM 46(3), pp. 395-415, May 1999. [43] Bálint Dömölki, "A universal compiler system based on production rules", BIT Numerical Mathematics, 8(4), pp 262–275, 1968. [44] Raja Jamilah Raja Yusof, Roziati Zainuddin, Mohd. Sapiyan Baba and Zulkifli Mohd. Yusoff, “Quranic words stemming”, The Arabian Journal for Science and Engineering, Volume 35, Number 2C, December 2010. [45] Mohamadou Nassourou, “A Knowledge-based Hybrid Statistical Classifier for Reconstructing the Chronology of the Quran”, Department of Computer Philology & Modern German Literature University of Würzburg Am Hubland D - 97074 Würzburg. [46] Mohamadou Nassourou, “Using Machine Learning Algorithms for Categorizing Quranic Chapters by Major Phases of Prophet Mohammad’s Messengership” , Department of Computer Philology & Modern German Literature University of Würzburg Am Hubland D - 97074 Würzburg. [47] Mohammed Naji Al-Kabi, Ghassan Kanaan, Riyad Al-Shalabi, “Statistical Classifier of the Holy Quran Verses (Fatiha and Yaseen Chapters)”, Journal of Applied Sciences 5 (3): 580-583, ISSN1812-5654, 2005. [48] Qurat ul Ain, Amna Basharat, “Ontology driven Information Extraction from the Holy Qur’an related Documents”, 26th IEEEP Students’ Seminar 2011 Pakistan Navy Engineering College National University of Sciences & Technology, 2011. [49] Abdul-Baquee M. Sharaf, “The Qur'an Annotation for Text Mining”, Supervisor: Dr. Eric Atwell, first year transfer report, December 2009. [50] Zaidi Razak, Noor Jamaliah Ibrahim, Mohd Yamani Idna Idris, Emran Mohd Tamil, Mohd Yakub, Zulkifli Mohd Yusoff and Noor Naemah Abdul Rahman, “Quranic Verse Recitation Recognition Module for Support in j-QAF Learning: A Review”, IJCSNS International Journal of Computer Science and Network Security, VOL.8 No.8, August 2008. [51] Ehab Mourtaga, Ahmad Sharieh, and Mousa Abdallah, “Speaker Independent Quranic Recognizer Based on Maximum Likelihood Linear Regression”, World Academy of Science, Engineering and Technology 36, pp. 61-67, 2007. [52] Hammo, B., Sleit, A; El-Haj, M., "Effectiveness of Query Expansion in searching the Holy Quran". In Proceeding of the Second International Conference on Arabic Language Processing CITALA'07, pages 1-10, Rabat, Morocco, CITALA, 2007. [53] جستجوی هوشمند عبارات قرآنی در متون دیجیتال ، محمد حبیب زاده بیژنی [54] رده بندی متون فارسی با استفاده از روش های آماری ، محمد حسین الهی منش – دکتر بهروز مینایی [55] برچسب گذاری ادات سخن متون فارسی به کمک مدل مخفی مارکوف ، محمد حسین الهی منش – دکتر بهروز مینایی [56] امکان سنجی تولید سامانه هوشمند تشخیص آیات قرآن در متون فارسی تفسیری [57] برخی مسائل در طراحی موتور جستجوی قرآنی وب محمدی نصیر ، مجتبی # پیوندهای مفید * [دریافت متن قرآن کریم](http://tanzil.net/) * [متن عربی و فارسی المیزان که برای تست مفید است](http://zolal.sobhe.ir/#almizan_ar/2_1) * [سورس کد](http://uplod.ir/q0g2wji1gpd7/quran.rar.htm) * [فایل متن](http://uplod.ir/o08mxusajn6q/New_Microsoft_Word_Do_ent.pdf.htm)