مقدمه
به دلیل به هم خوردگی متن فایل 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 = (dp + P[i]) mod q;
t = (dt + 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;
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 انتخاب می شود چون کمترین مقدار حاصل ضرب را دارد 41=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<BOXSIZEboxes;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,
[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,[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] برخی مسائل در طراحی موتور جستجوی قرآنی وب محمدی نصیر ، مجتبی