Parsing (1)

Report
‫ارائه دهنده‪:‬‬
‫دانشکده مهندس ی‬
‫مجید یاقوتی‬
‫گروه مهندس ی کامپیوتر‬
‫استاد‪:‬‬
‫‪Parsing‬‬
‫)‪(1‬‬
‫دکتر کاهانی‬
‫درس‪:‬‬
‫سیستم‌های مبتنی بر دانش‬
‫فروردین ‪92‬‬
‫‪1‬‬
‫)‪Parsing (1‬‬
‫فهرست‬
‫‪ ‬مقدمه‬
‫‪ ‬استراتژی‌های جستجو‬
‫‪ ‬تجزیه‌ی باال به پایین‬
‫‪ ‬تجزیه‌ی پایین به باال‬
‫‪2‬‬
‫)‪Parsing (1‬‬
‫فهرست‬
‫‪ ‬برنامه‌نویس ی پویا‬
‫‪ ‬الگوریتم ‪CKY‬‬
‫‪ ‬الگوریتم ‪Earley‬‬
‫‪ ‬نرم‌افزارهای موجود‬
‫‪3‬‬
‫)‪Parsing (1‬‬
‫مقدمه‬
‫‪ Parsing ‬یا تجزیه‌ی یک جمله‬
‫‪ ‬ساختن یک درخت یا اشتقاق صحیح با داشتن گرامر‬
‫سازگار بودن درخت با ورودی ‌و گرامر‬
‫‌‬
‫‪« ‬صحیح»‪ :‬صرفا به معنی‬
‫امر داده شده‬
‫‪ ‬یک درخت با وجود صحیح بودن ممکن است درخت واقعی عبارت ورودی ‌و گر ‌‬
‫نباشد‪.‬‬
‫‪ ‬برگ‌های درخت‪ :‬اجزای جمله‌ی ورودی‬
‫‪4‬‬
‫)‪Parsing (1‬‬
‫مقدمه‬
‫‪ ‬پارسر‪ :‬الگوریتمی برای محاسبه‌ی یک ساختاری‌ برای رشته‌ی ورودی با توجه‬
‫به گرامر‬
‫‪ ‬دو ویژگی همه‌ی پارسرها‬
‫‪ ‬جهت‪ :‬روند یا مراحل تولید ساختار‬
‫‪ ‬باال به پایین یا پایین به باال‬
‫‪ ‬استراتژی جستجو‪ :‬روش پیمایش فضای جستجوی انواع مختلف تجزیه‌ها‬
‫‪ ‬اول سطح یا اول عمق‬
‫‪5‬‬
‫)‪Parsing (1‬‬
‫مقدمه‬
‫‪ ‬فرض‌های اولیه قبل از تجزیه‬
‫‪ ‬همه‌ی کلمات را در یک بافر در اختیار داریم‪.‬‬
‫‪ ‬همه‌ی کلمات شناخته شده هستند‪.‬‬
‫‪6‬‬
‫)‪Parsing (1‬‬
‫مقدمه‬
‫‪ ‬مثال‪ :‬یک گرامر و دیکشنری لغات‬
‫‪ ‬درخت متناظر با عبارت «‪»Book that flight‬‬
‫‪7‬‬
‫)‪Parsing (1‬‬
‫تجزیه‌ی باال به پایین‬
‫‪‌ ‬از ریشه‌ی درخت شروع به ساختن آن می‌کنیم‪.‬‬
‫امر ‌و‬
‫‪ ‬حرکت به سمت برگ‌های درخت (کلمات) با استفاده ‌از قوانین گر ‌‬
‫عمل اشتقاق‬
‫‪ ‬هدف نهایی‬
‫‪ ‬پیدا کردن درختی که ریشه اش ‪ S‬باشد ‌و رشته‌ی ورودی را تولید کند‪.‬‬
‫سایر روش‌ها‬
‫کمتر نسبت به ‌‬
‫‪ ‬دارای سرعت ‌‬
‫‪8‬‬
‫)‪Parsing (1‬‬
‫تجزیه‌ی باال به پایین‬
‫‪ ‬نمونه‌ای از یک تجزیه‌ی باال به پایین‬
‫‪9‬‬
‫)‪Parsing (1‬‬
‫تجزیه‌ی باال به پایین‬
‫‪ ‬نحوه‌ی اشتقاق و رسیدن از ریشه به برگ‌ها‬
‫‪ ‬روش اول عمق‪ :‬پیمایش یک شاخه از فضای جستجو در هر زمان‬
‫‪ ‬بازگشت به عقب در صورت بن بست‬
‫‪ ‬اول سطح‪ :‬پیمایش موازی تمام شاخه‌های ممکن‬
‫‪ ‬محدودیت حافظه‬
‫‪10‬‬
‫)‪Parsing (1‬‬
‫تجزیه‌ی باال به پایین‬
‫‪ ‬مشکالت روش باال به پایین‬
‫‪ ‬جستجو توسط ورودی هدایت نمی‌شود‪.‬‬
‫‪ ‬تولید درخت‌های صحیحی که رشته‌ی ورودی را تولید نمی‌کنند‪.‬‬
‫‪11‬‬
‫)‪Parsing (1‬‬
‫تجزیه‌ی باال به پایین‬
‫‪ ‬مشکالت روش باال به پایین‬
‫‪ ‬ابهام سراسری و محلی‬
‫ی‬
‫ی‪ :‬چندین تجزیه‌ی ساختاری به دلیل قوانین گرامری و یا لغو ‌‬
‫‪ ‬ابهام سراسر ‌‬
‫‪ ‬ابهام محلی‪ :‬حتی اگر کل جمله بدون ابهام باشد‪ ،‬ممکن است زیر رشته هایی وجود داشته‬
‫باشند که ابهام دارند‪.‬‬
‫‪‬‬
‫«‪ »book‬در جمله‌ی «‪ »Book that flight‬دو تفسیر متفاوت دارد (اسم و فعل)‪.‬‬
‫‪ ‬ابهام محلی در زبان‌های طبیعی بسیار معمول است‪.‬‬
‫‪12‬‬
‫)‪Parsing (1‬‬
‫تجزیه‌ی باال به پایین‬
‫‪ ‬مشکالت روش با ‌ال به پایین‬
‫در کلمات‬
‫ی ‌‬
‫امر ‌و ابهام لغو ‌‬
‫در گر ‌‬
‫ی ‌‬
‫اثر ابهام ساختار ‌‬
‫‪‌ ‬‬
‫مسیر اشتباه‬
‫در ‌‬
‫‪ ‬حرکت ‌‬
‫‪ ‬تولید چند باره‌ی یک ز ‌یر درخت خاص‬
‫‪‬‬
‫بازگشت به عقب شروع مجدد‬
‫در بدترین حالت ‌از مرتبه‌ی نمایی است‪.‬‬
‫‪ ‬پیچیدگی این بازگشت به عقب ‌‬
‫‪13‬‬
‫)‪Parsing (1‬‬
‫تجزیه‌ی پایین به باال‬
‫‪ ‬حرکت ‌از کلمات رشته‌ی ورودی به سمت باالی درخت‬
‫در لبه‌ی باالیی درخت با سمت راست یک‬
‫‪ ‬با تطبیق دادن یک یا چند گره ‌‬
‫قانو ‌ن ‌از گرامر‬
‫‪ ‬افزودن سمت چپ آن قانو ‌ن به درخت به عنوان والد آن گره یا گره‌ها‬
‫ی او ‌ل عمق ‌و او ‌ل سطح‬
‫ی جستجو ‌‬
‫کار گیر ‌‬
‫‪ ‬به ‌‬
‫‪14‬‬
‫)‪Parsing (1‬‬
‫تجزیه‌ی پایین به باال‬
‫‪ ‬نمونه‌ای ‌از تجزیه‌ی پایین به‬
‫با ‌ال با رویکرد اول‌ سطح‬
‫‪15‬‬
‫)‪Parsing (1‬‬
‫تجزیه‌ی پایین به باال‬
‫‪ ‬مزیت‬
‫هر درخت ختم شده به ‪ S‬با رشته‌ی ورودی‬
‫‪ ‬سازگاری‌ ‌‬
‫‪ ‬مشکالت روش پایین به باال‬
‫در نتیجه محاسبات تکراری‌‬
‫‪ ‬ابهام سراسری‌ و محلی ‌و ‌‬
‫ساختار کلی‪ ،‬بدو ‌ن معنا هستند‪.‬‬
‫‌‬
‫‪ ‬تولید درخت هایی که از لحاظ‬
‫در فضاهای نامتناهی به مشکل ‌بر خواهد خورد‪.‬‬
‫‪‌ ‬‬
‫‪16‬‬
‫)‪Parsing (1‬‬
‫برنامه‌نویس ی پویا‬
‫ی زیررشته‌ها اجتناب کند‪.‬‬
‫آنالیز تکرار ‌‬
‫سر باید بتواند ‌از ‌‬
‫‪ ‬پار ‌‬
‫هر زیررشته‪ ،‬به بقیه‌ی فرآیند تجزیه وابسته نیست‪.‬‬
‫آنالیز ‌‬
‫‪‌ ‬‬
‫‪ ‬کشف این عدم وابستگی‌ها با استفاده ‌از برنامه‌نویس ی پویا‬
‫‪ ‬برنامه‌نویس ی پویا اساس همه‌ی الگوریتم‌های تجزیه‌ی مبتنی ‌بر چارت‬
‫است‪.‬‬
‫‪17‬‬
‫)‪Parsing (1‬‬
‫برنامه‌نویس ی پویا‬
‫در برنامه‌نویس ی پویا‬
‫‪‌ ‬‬
‫ی راه حل بهینه‌ی زیرمسئله‌هاست‬
‫‪‌ ‬پر کردن یک جدو ‌ل که حاو ‌‬
‫در آینده مجبور‌ به محاسبه‌ی مجدد آنها نباشیم‪.‬‬
‫‪ ‬ذخیره‌ی جواب‌های بهینه تا ‌‬
‫‪ ‬رسیدن به جواب مسئله‌ی کلی با ترکیب جواب‌های زیرمسائل‬
‫‪18‬‬
‫)‪Parsing (1‬‬
‫برنامه‌نویس ی پویا‬
‫آنالیز زیررشته‌ها هستند‪.‬‬
‫در مسائل تجزیه‪ ،‬زیرمسئله‌ها ‌‬
‫‪‌ ‬‬
‫هر آنالیز‬
‫‪‌ ‬‬
‫‪ ‬مربوط به یک ساختار (زیردرخت) کامل است که توسط محل‌های شروع ‌و پایان‬
‫زیررشته مشخص شده است‪.‬‬
‫ساختار کامل که ممکن است پیدا شود‪.‬‬
‫‌‬
‫در مورد یک‬
‫‪ ‬و یا یک فرض ‌‬
‫‪19‬‬
‫)‪Parsing (1‬‬
‫برنامه‌نویس ی پویا‬
‫در این روش‬
‫‪‌ ‬‬
‫آنالیز دوباره‌ی آنها‬
‫ی زیردرخت‌ها به جای ‌‬
‫‪ ‬جستجو ‌‬
‫در مواجهه با ابهام‬
‫‪ ‬کمک ‌‬
‫در چارت‬
‫‪ ‬ذخیره‌ی تمام تجزیه‌های ممکن را ‌‬
‫‪ ‬بازنمایی بصورت ماتریس یا گراف‬
‫‪ ‬سطرها ‌و ستون‌های ماتریس‪ ،‬نشان دهنده‌ی محل‌های شروع ‌و پایان یک محدوده‬
‫‪20‬‬
‫)‪Parsing (1‬‬
‫برنامه‌نویس ی پویا‬
‫هر خانه ‌از ماتریس مربوط به زیررشته ای است که شروعش اندیس‬
‫‪‌ ‬‬
‫سطر ‌و پایانش اندیس ستون‌ آن خانه است‪.‬‬
‫‌‬
‫‪ ‬حاوی‌ اطالعاتی درباره‌ی‬
‫ساختار آن محدوده ‌از زیررشته‬
‫‌‬
‫‪ ‬نوع‬
‫‪ ‬اشاره گرهایی به زیرساختارهای آن‬
‫در ادامه‌ی زیررشته‬
‫در مورد ساختارهایی که ممکن است ‌‬
‫‪‌ ‬و یا پیش‌بینی هایی ‌‬
‫ظاهر شوند‪.‬‬
‫‌‬
‫‪21‬‬
‫)‪Parsing (1‬‬
‫برنامه‌نویس ی پویا‬
‫‪ ‬مثال‪ :‬تجزیه‌ی عبارت «‪ »See with a telescope in hand‬با روش‬
‫برنامه‌نویس ی پویا ‌و استفاده ‌از ماتریس‬
‫‪22‬‬
‫)‪Parsing (1‬‬
‫برنامه‌نویس ی پویا‬
‫در بازنمایی گرافی‬
‫‪‌ ‬‬
‫‪ ‬رئوس گراف‪ :‬نشان دهنده‌ی محل‌های شروع ‌و پایان‬
‫‪ ‬یال‌های گراف‪ :‬مشخص کننده‌ی شروع ‌و پایان یک محدوده ‌از یک زیررشته‬
‫در یال‌ها‬
‫ی اطالعات خانه‌های ماتریس ‌‬
‫‪ ‬قرارگیر ‌‬
‫‪23‬‬
‫)‪Parsing (1‬‬
‫برنامه‌نویس ی پویا‬
‫‪ ‬تجزیه‌ی زیررشته‌ی «‪ »with a telescope‬با روش برنامه‌نویس ی پویا ‌و‬
‫استفاده ‌از گراف‬
‫‪24‬‬
‫)‪Parsing (1‬‬
‫برنامه‌نویس ی پویا‬
‫‪ ‬الگوریتم‌هایی برای تجزیه‌ی مبتنی ‌بر چارت‪:‬‬
‫‪ ‬الگوریتم ‪ :CKY‬فقط ساختارها را ذخیره می‌کند‪.‬‬
‫‪ ‬الگوریتم ‪ :Earley‬هم ساختارها ‌و هم پیش شرط‌ها را ذخیره می‌کند‪.‬‬
‫‪25‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪CKY‬‬
‫در چارت طراحی شد‪.‬‬
‫‪ ‬برای تشخیص ساختارها ‌و ذخیره‌ی آنها ‌‬
‫‪ ‬طراحی اولیه برای فرم نرمال چامسکی (‪)ABC; Aa‬‬
‫ی ‌و هریسو ‌ن تعمیم داده شد‪.‬‬
‫‪ ‬توسط گر ‌‬
‫اگر یک قانو ‌ن وجود داشته باشد که‪:‬‬
‫در خانه‌ی ‪ i,j‬وارد می‌شود ‌‬
‫‪ ‬ساختار ‪ A‬را ‌‬
‫در خانه‌ی ‪ i,j‬وجود داشته باشد ‌و یا‬
‫‪ AB ‬و ‪‌ B‬‬
‫در خانه‌ی ‪ k,j‬وجود داشته باشد‪.‬‬
‫در خانه‌ی ‪ i,k‬و ‪‌ C‬‬
‫‪ ABC ‬و ‪‌ B‬‬
‫‪26‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪CKY‬‬
‫‪ ‬الگوریتم ‪ CKY‬برای تجزیه‌ی مبتنی ‌بر چارت‬
‫‪ ‬این الگوریتم کامل ‌و ‌از مرتبه‌ی )‪ O(n3‬است‪.‬‬
‫‪27‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪ - CKY‬مثال‬
‫‪ ‬گرامر‬
Parsing (1)
28
‫ مثال‬- CKY ‫الگوریتم‬
:»the frogs ate fish« ‫ مراحل پر شدن جدول برای عبارت‬
Unary branching rules: detthe
Parsing (1)
29
‫ مثال‬- CKY ‫الگوریتم‬
:»the frogs ate fish« ‫ مراحل پر شدن جدول برای عبارت‬
Unary branching rules: Nfrogs,
NomN, NPNom
Unary branching rules: tvate
Parsing (1)
30
‫ مثال‬- CKY ‫الگوریتم‬
:»the frogs ate fish« ‫ مراحل پر شدن جدول برای عبارت‬
Unary branching rules: Nfrogs,
NomN, NPNom, ivfish, vpiv
Binary branching rules: NPDet Nom
(0,1) & (1,2)  (0,2)
Parsing (1)
31
‫ مثال‬- CKY ‫الگوریتم‬
:»the frogs ate fish« ‫ مراحل پر شدن جدول برای عبارت‬
(1,2) & (2,3)  ×
Binary branching rule: VPTV NP
(2,3) & (3,4)  (2,4)
Parsing (1)
32
‫ مثال‬- CKY ‫الگوریتم‬
:»the frogs ate fish« ‫ مراحل پر شدن جدول برای عبارت‬
Binary branching rule: S NP VP
(1,2) & (2,4)  (1,4)
(1,3) & (3,4)  ×
Binary branching rule: S  NP VP
(0,1) & (1,4)  ×
(0,2) & (2,4)  (0,4)
(0,3) & (3,4)  ×
‫‪33‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪CKY‬‬
‫‪ ‬محدودیت‌های ‪CKY‬‬
‫هر خانه ‌از ماتریس یا گراف را نگه نمی‌دارد‪.‬‬
‫‪ ‬علت ذخیره‌ی اطالعات ‌‬
‫اگر د ‌و قانون‌ به صورت ‪ VP  V NP‬و ‪ VP  VP PP‬داشته باشیم ‌و رشته‌ی‬
‫‪‌ ‬‬
‫ورودی «‪ »The boy opened the box on the floor‬باشد‪ ،‬نمی‌دانیم یال ‪ VP‬چه‬
‫چیزی‌ را تولید می‌کند؛ ‪‌ VP  V NP‬و یا ‪VP  VP PP‬؟‬
‫‪34‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪CKY‬‬
‫نظر گرفتن قانون‌ ‪VP  V NP‬‬
‫در ‌‬
‫‪ ‬با ‌‬
‫‪35‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪CKY‬‬
‫نظر گرفتن قانون‌ ‪VP  VP PP‬‬
‫در ‌‬
‫‪ ‬با ‌‬
‫‪36‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪CKY‬‬
‫‪ ‬رفع این محدودیت‬
‫هر خانه ‌از جدو ‌ل‬
‫‪ ‬افزودن یک فیلد اضافه برای ذخیره‌ی نحوه‌ی تولید ‌‬
‫‪37‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪CKY‬‬
‫‪ ‬محدودیت‌های ‪CKY‬‬
‫‪ ‬استفاده ‌از روش پایین به باال‬
‫‪ ‬ختم نشدن بسیاری‌ ‌از زیردرخت‌های تولید شده‪ ،‬به ریشه‬
‫‪ ‬رفع مشکل‪:‬‬
‫‪ ‬استفاده ‌از روش‌های فیلترینگ خاص ی برای تشخیص این زیردرخت‌ها‬
‫‪ ‬استفاده ‌از استراتژی‌ با ‌ال به پایین‬
‫‪38‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪Earley‬‬
‫‪ ‬مجبو ‌ر نیستم فقط قوانین کامل شده را ذخیره کنیم‪.‬‬
‫‪‬‬
‫ذخیره‌ی قوانین کامل نشده‬
‫ظاهر خواهد شد‪.‬‬
‫در ادامه ‌‬
‫‪ ‬ساختارهای ناقص‪ :‬پیش‌بینی‌هایی ‌از آنچه که ‌‬
‫‪‬‬
‫بیان ساختارهای ناقص با استفاده ‌از قوانین نقطه‌دار‬
‫‪‬‬
‫مقدار ‌از سمت راست یک قانون‌ تاکنون‌ پیدا شده است ‌و‬
‫‌‬
‫نقطه‪ ،‬مشخص می‌کند که چه‬
‫ظاهر خواهد شد‪.‬‬
‫در ادامه ‌‬
‫مابقی آن‪ ،‬یک پیش‌بینی ‌از چیزی‌ است که ‌‬
‫‪39‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪ - Earley‬مثال‬
‫‪ ‬قانون ‪ VP  V NP‬می‌تواند قوانین نقطه‌دار زیر را تولید کند‪:‬‬
‫‪ VP  ● V NP‬یال ناقص‬
‫‪ VP  V ● NP‬یال ناقص‬
‫● ‪ VP  V NP‬یال کامل‬
‫‪40‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪Earley‬‬
‫‪ ‬ذخیره‌ی قوانین تولید برای ساختارهای کامل‬
‫‪‬‬
‫ظاهر شده است‬
‫‌از ابتدا تا انتهایش ‌‬
‫‪‬‬
‫‌دار برای ساختارهای ناقص‬
‫ذخیره‌ی قوانین نقطه ‌‬
‫دیگر آن (سمت راست نقطه)‬
‫ظاهر شده است ‌و بخش ‌‬
‫‌‬
‫‪ ‬بخش ی ‌از قانون‌ (سمت چپ نقطه)‬
‫ظاهر شود‪.‬‬
‫انتظار می‌رود که ‌‬
‫‌‬
‫‪41‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪Earley‬‬
‫‪ ‬مثال‪ :‬برای زیررشته‌ی «‪»…5 on 6 the 7 floor 8‬‬
‫در چارت ذخیره می‌شود‪.‬‬
‫عبارت ]‪‌ NP  Det ● N, [6,7‬‬
‫‪‬‬
‫در ادامه‬
‫مشخص می‌کند کلمه‌ی بین ‪ 6‬و ‪ 7‬یک ‪ Det‬است و پیش‌بینی می‌شود یک ‪‌ N‬‬
‫ظاهر شود‪.‬‬
‫‪‬‬
‫در موقعیت ‪ 6‬خواهیم داشت‪.‬‬
‫ظاهر شود‪ ،‬یک رشته‌ی ‪ NP‬را ‌‬
‫اگر ‌‬
‫‪42‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪Earley‬‬
‫‪ ‬یک چارت با قوانین نقطه‌دار‬
‫‪43‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪Earley‬‬
‫بار عبور‌ ‌از روی ورودی ‌پر می‌کند‪.‬‬
‫‪ ‬اگوریتم ‪ Earley‬چارت را با یک ‌‬
‫‪ ‬اندازه‌ی چارت ‪ N+1‬و ‪ N‬تعداد کلمات ورودی است‪.‬‬
‫در ورودی‪ ،‬لیستی ‌از حالت‌ها را نگه می‌دارد‪.‬‬
‫هر موقعیت کلمه ‌‬
‫‪ ‬چارت برای ‌‬
‫‪‬‬
‫درخت‌های تجزیه‌ی جزئی که تاکنون‌ تولید شده‌اند‪.‬‬
‫‪44‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪Earley‬‬
‫‪ ‬ورودی‌های چارت سه نوع مختلف دارند‪:‬‬
‫‪ ‬ساختارهای کامل شده‬
‫‪ ‬ساختارهای در حال پردازش‬
‫‪ ‬ساختارهای پیش‌بینی شده‬
‫‪45‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪Earley‬‬
‫‪ ‬مثال‬
‫در ابتدای جمله‪ VP ،‬پیش‌بینی شده است‪.‬‬
‫یک ‪ NP‬در حال پردازش است‪ Det .‬از ‪ 1‬تا ‪ 2‬پیدا شده است و‬
‫پیش‌بینی می‌شود در ادامه ‪ Nominal‬ظاهر شود‪.‬‬
‫‪ VP‬ظاهر شده است با شروع از صفر و پایان در ‪3‬‬
‫‪ ‬نمایش گرافی حالت‌ها‬
‫]‪S  ● VP [0,0‬‬
‫]‪NP  Det ● Nominal [1,2‬‬
‫]‪VP  V NP ● [0,3‬‬
‫‪46‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪Earley‬‬
‫‪ ‬روند تجزیه‪:‬‬
‫صفر تا ‪‌ N‬بر روی جدو ‌ل‬
‫‪ ‬حرکت ‌از حالت ‌‬
‫‪ ‬شروع از ‪‌ S‬و حرکت ‌از با ‌ال به پایین‬
‫در با ‌ال بیان شد‬
‫‪ ‬تولید ‪ 3‬نوع حالتی که ‌‬
‫‪‬‬
‫در جدول‌‬
‫تولید حالت‌های پیش‌بینی شده ‌بر اساس ورودی‌های موجود ‌‬
‫‪‬‬
‫در حال پردازش جدید با توسعه‌ی حالت‌های موجود‬
‫تولید حالت‌های ‌‬
‫‪‬‬
‫در حال پردازش به انتهای قانو ‌ن‬
‫در یک حالت ‌‬
‫تولید حالت‌های کامل شده‌ی جدید زمانی که نقطه ‌‬
‫می‌رسد‪.‬‬
‫‪47‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪Earley‬‬
‫‪ ‬بازگشت به عقبی وجود ندارد‪.‬‬
‫‪ ‬هیچ حالتی حذف نمی‌شود‪.‬‬
‫‪ ‬تجزیه‌ی موفقیت‌آمیز‬
‫در آخرین ورودی چارت‬
‫‪ ‬حالت ]‪‌ S  α ● [0,N‬‬
Parsing (1)
48
‫ – شبه کد‬Earley ‫الگوریتم‬
‫‪49‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪Earley‬‬
‫‪ ‬الگوریتم ‪ Earley‬سه تابع اصلی دارد‪:‬‬
‫‪ :Predictor ‬پیش‌بینی‌ها را به چارت اضافه می‌کند‪.‬‬
‫‪ :Completer ‬زمانی که ساختارهای جدید پیدا می‌شوند‪ ،‬نقطه را به سمت‬
‫راست حرکت می‌دهد‪.‬‬
‫‪ :Scanner ‬کلمات ورودی را خوانده ‌و حالت‌هایی که بیان‌کننده‌ی آن کلمات‬
‫هستند را وارد چارت می‌کند‪.‬‬
‫‪50‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪Earley‬‬
‫‪ ‬مشکالت این روش‬
‫‪‬‬
‫در چارت ذخیره می‌کند که‬
‫نسخه‌ی با ‌ال به پایین الگوریتم ‪ Earley‬چیزهایی را ‌‬
‫بالاستفاده هستند‪.‬‬
‫‪‬‬
‫مسئله‌ی ابهام را حل نمی‌کند‪.‬‬
‫‪‬‬
‫هر د ‌و روش ‪ CKY‬و ‪ Earley‬ممکن است برای ورودی ]‪ [0,N‬جدول‪ ،‬به چندین‬
‫‌‬
‫ساختار ‪ S‬ختم شوند‪.‬‬
‫‪51‬‬
‫)‪Parsing (1‬‬
‫الگوریتم ‪Earley‬‬
‫ی برای بهبود عملکرد این الگوریتم‪:‬‬
‫‪ ‬استراتژی‌های دیگر ‌‬
‫ی پایین به باال‬
‫‪ ‬استراتژ ‌‬
‫‪‬‬
‫ی ابتدا بهترین (*‪)A‬‬
‫استراتژ ‌‬
‫هر کدام ‌از ساختارها‬
‫‪ ‬گسترش حالت‌ها ‌بر اساس احتمال ‌‬
‫در زمان تجزیه محاسبه ‌و ذخیره می‌شود‪.‬‬
‫هر کدام ‌از ساختارها ‌‬
‫‪ ‬احتمال ‌‬
‫‪52‬‬
‫)‪Parsing (1‬‬
‫نرم افزارهای موجود‬
‫‪Stanford Parser ‬‬
‫ی ‌و به زبان جاوا‬
‫سر آمار ‌‬
‫‪ ‬پار ‌‬
‫‪ ‬پشتیبانی زبان‌های انگلیس ی‪ ،‬چینی‪ ،‬آملانی‪ ،‬عربی‪ ،‬ایتالیایی‪ ،‬فرانسوی‌ و‪...‬‬
‫‪Berkeley Parser ‬‬
‫‪‬‬
‫ی گرامرهای مستقل ‌از متن احتماالتی‬
‫مبتنی ‌بر یادگیر ‌‬
‫‪‬‬
‫پشتیبانی ‌از چندین زبان‬
Parsing (1)
53
‫منابع‬
1.
Philipp Koehn, "Advanced Natural Language Processing", school of
informatics, september 2012.
2.
Hesham Faili, "Introduction to NLP", chapter 13: Parsing with contex-free
grammars, University of Tehran.
3.
Zubair Buitms, "Natural Language Processing", available
http://zubairbuitms.hubpages.com/hub/Natural-Language-Processing.
4.
Laura Kassner, "Left-corner parsing", Lecture for course Computational
Linguistics II: Parsing, 2007.
at:
‫با تشکر‬
‫ارائه‌ی بعد‬
‫تجزیه‌ی آماری‌‬
‫تجزیه‌ی وابستگی‬
‫تجزیه در زبان فارس ی‬

similar documents