पार्सिंग में चार्ट क्या होता है?

एक चार्ट एक तालिका है जो वाक्य के प्रत्येक विस्तार पर पाए गए प्रत्येक आंशिक घटक को संग्रहीत करती है, ताकि साझा उपसंरचनाओं की गणना एक बार की जा सके और उनका पुन: उपयोग किया जा सके, जिससे बहुपद-समय पार्सिंग मिलती है।

घटक और संदर्भ-मुक्त पार्सिंग

संदर्भ-मुक्त व्याकरण, CKY और अर्ली जैसे डायनामिक-प्रोग्रामिंग एल्गोरिदम, और अस्पष्टता को हल करने वाले संभाव्य व्याकरणों का उपयोग करके एक वाक्य के वाक्यांश-संरचना वृक्ष की गणना करना।

PaperMind से विषय खोजेंजल्द हीFind papers & topics

Tools & resources

स्लाइड डाउनलोड करें

Learn & explore

वीडियोजल्द ही

Definition

घटक पार्सिंग एक संदर्भ-मुक्त व्याकरण के अनुसार एक वाक्य को एक नेस्टेड वाक्यांश-संरचना वृक्ष प्रदान करती है, सामान्यतः एक संभाव्य व्याकरण के तहत सबसे संभावित वृक्ष का चयन करती है।

Scope

संदर्भ-मुक्त व्याकरणों के साथ पार्सिंग को शामिल करता है: CKY और अर्ली एल्गोरिदम, चॉम्स्की सामान्य रूप, संभाव्य संदर्भ-मुक्त व्याकरण और उनके शाब्दिक परिष्करण, और ट्रीबैंक-प्रशिक्षित सांख्यिकीय पार्सर। यह अस्पष्टता समाधान और पार्सर मूल्यांकन को संबोधित करता है। निर्भरता प्रतिनिधित्व और गैर-संदर्भ-मुक्त औपचारिकताएं संबंधित विषयों में वर्णित हैं।

Core questions

CKY एल्गोरिथम एक वाक्य को क्यूबिक समय में कैसे पार्स करता है?
व्याकरणों को अक्सर पहले चॉम्स्की सामान्य रूप में क्यों परिवर्तित किया जाना चाहिए?
संभाव्य और शाब्दिक व्याकरण अस्पष्टता को कैसे सुधारते हैं?
एक ट्रीबैंक के मुकाबले पार्सर की सटीकता को कैसे मापा जाता है?

Key concepts

संदर्भ-मुक्त व्याकरण
CKY एल्गोरिथम
अर्ली एल्गोरिथम
चॉम्स्की सामान्य रूप
संभाव्य संदर्भ-मुक्त व्याकरण
शाब्दिककरण
पार्स वृक्ष
ट्रीबैंक

Key theories

डायनामिक-प्रोग्रामिंग पार्सिंग: CKY और अर्ली एल्गोरिदम उप-घटकों के एक चार्ट को भरकर बहुपद समय में सभी पार्स की गणना करते हैं, जिससे भोली खोज के घातीय विस्तार से बचा जा सकता है।
शाब्दिक संभाव्य पार्सिंग: नियम संभावनाओं को हेड शब्दों पर आधारित करने से सादे PCFG से अनुपस्थित शाब्दिक वरीयताओं को पकड़कर पार्सिंग सटीकता में काफी सुधार होता है।

History

CKY एल्गोरिथम (1960 के दशक) और अर्ली के 1970 के एल्गोरिथम ने कुशल संदर्भ-मुक्त पहचान प्रदान की। पेन ट्रीबैंक के साथ, कोलिन्स और चारनियाक के संभाव्य और फिर शाब्दिक पार्सर ने 1990 के दशक के अंत में उच्च सटीकता प्राप्त की, जिसने तंत्रिका मॉडल से पहले सांख्यिकीय पार्सिंग युग को परिभाषित किया।

Debates

कितने शाब्दिककरण की आवश्यकता है?: शाब्दिक पार्सर सटीक लेकिन विरल होते हैं; बहस इस बात पर केंद्रित थी कि क्या सावधानीपूर्वक राज्य-विभाजन वाले गैर-शाब्दिक PCFG उनसे मेल खा सकते हैं, जिसे बाद के काम ने आंशिक रूप से संभव दिखाया।

Key figures

Jay Earley
Michael Collins
Eugene Charniak

Seminal works

earley1970
collins2003

Frequently asked questions

पार्सिंग में चार्ट क्या होता है?: एक चार्ट एक तालिका है जो वाक्य के प्रत्येक विस्तार पर पाए गए प्रत्येक आंशिक घटक को संग्रहीत करती है, ताकि साझा उपसंरचनाओं की गणना एक बार की जा सके और उनका पुन: उपयोग किया जा सके, जिससे बहुपद-समय पार्सिंग मिलती है।