Rekursiv o'tish tarmog'i filtrlangan - Filtered-popping recursive transition network - Wikipedia

A rekursiv o'tish tarmog'i filtrlangan (FPRTN),^[1] yoki oddiygina filtrlangan tarmoq (FPN), a rekursiv o'tish tarmog'i (RTN )^[2] shtatlar xaritasi bilan a dan qaytib kelgan kalitlarga kengaytirilgan subroutine sakrash akseptor va qaytish holatlarini bir xil kalit bilan taqqoslashni talab qiladi. RTNlar bor cheklangan holatdagi mashinalar deb ko'rish mumkin cheklangan davlat avtomatlari bilan kengaytirilgan suyakka qaytish holatlari; shuningdek, o'tishlarni iste'mol qilish va ${ displaystyle varepsilon}$ - o'tish, RTNlar qo'ng'iroq o'tishlarini belgilashi mumkin. Ushbu o'tishlar a subroutine o'tish joyining maqsad holatini stakka surish va mashinani chaqirilgan holatga keltirish orqali sakrash. Har safar akseptor holatiga kelganda stakning yuqori qismidagi qaytish holati chiqadi, agar stak bo'sh bo'lmasa va mashina shu holatga keltirilgan bo'lsa.

Ushbu maqola davomida biz filtrlangan ochiladigan rekursiv o'tish tarmoqlariga murojaat qilamiz FPNlarbu qisqartma noaniq bo'lsa ham (masalan: loyqa Petri to'rlari ). Filtrlangan tarmoqlar va FPRTNlar aniq alternativalar.

Rasmiy ta'rif

FPN - bu struktura ${ displaystyle (Q, K, Sigma, delta, kappa, Q_ {I}, F)}$ qayerda

${ displaystyle Q}$ bu davlatlarning cheklangan to'plami,
${ displaystyle K}$ tugmachalar to'plami,
${ displaystyle Sigma}$ cheklangan kirish alifbosi,
${ displaystyle delta: Q marta ( Sigma cup { varepsilon } cup Q) to Q}$ qisman o'tish funktsiyasi, ${ displaystyle varepsilon}$ bo'sh belgi bo'lib,
${ displaystyle kappa: Q dan K gacha$ - bu kalitlarning holati xaritasi,
${ displaystyle Q_ {I} subseteq Q}$ boshlang'ich holatlar to'plami va
${ displaystyle F subseteq Q}$ qabul qilish holatlarining to'plamidir.

O'tish

O'tishlar FPN-ni manba holatidan olib kelish imkoniyatini anglatadi ${ displaystyle q_ {s}}$ maqsadli holatga ${ displaystyle q_ {t}}$ ehtimol qo'shimcha harakatni amalga oshirish orqali. Ushbu harakatga qarab biz quyidagi turlarini ajratamiz aniq- belgilangan o'tish:

${ displaystyle varepsilon}$ - o'tish shaklning o'tishlari ${ displaystyle delta (q_ {s}, varepsilon) dan q_ {t}} gacha$ va qo'shimcha harakatlar qilmaslik,
o'tishlarni iste'mol qilish shaklning o'tishlari ${ displaystyle delta (q_ {s}, sigma) dan q_ {t}} gacha$ va kirish belgisini iste'mol qiling ${ displaystyle sigma}$ va
o'tish qo'ng'iroqlari shaklning o'tishlari ${ displaystyle delta (q_ {s}, q_ {c}) dan q_ {t}} gacha$ va bajaring subroutine chaqirilgan holatga o'tish ${ displaystyle q_ {c}}$ yetmasdan oldin ${ displaystyle q_ {t}}$ .

Qo'ng'iroq o'tishining harakati ikki xil tomonidan boshqariladi bilvosita- belgilangan o'tish:

har bir qo'ng'iroq o'tish uchun ${ displaystyle delta (q_ {s}, q_ {c}) dan q_ {t}} gacha$ FPN to'g'ridan-to'g'ri a ni belgilaydi surish o'tish bu mashinani olib keladi ${ displaystyle q_ {s}}$ ga ${ displaystyle q_ {c}}$ surish orqali ${ displaystyle q_ {t}}$ ustiga suyakka va
har bir davlat uchun ${ displaystyle (q_ {f}, q_ {r}) in F marta Q}$ FPN to'g'ridan-to'g'ri a ni belgilaydi pop o'tish bu mashinani olib keladi ${ displaystyle q_ {f}}$ ga ${ displaystyle q_ {r}}$ poping orqali ${ displaystyle q_ {r}}$ uyumdan iff ${ displaystyle q_ {r}}$ stackning yuqori qismidagi holat va ${ displaystyle kappa (q_ {f}) = kappa (q_ {r})}$ .

Bosish o'tish jarayoni boshlanadi subroutine sakrashlar va pop-o'tishlarga teng qaytarish bayonotlari.

Maqsad

A (tabiiy til ) matnini metamahborot bilan a-ni qo'llash orqali boyitish mumkin Chiqish bilan RTN; masalan, RTN qo'shilishi XML teglar o'zgarishi uchun ishlatilishi mumkin Oddiy matn tuzilgan XML hujjatiga. A ni ko'rsatadigan RTN tabiiy til grammatika har bir matn jumlasining sintaktik tuzilishini chegaralaydi va qo'shadi (qarang tahlil qilish ). Chiqish bilan boshqa RTNlar tegishli ma'lumotlarni o'z ichiga olgan matn segmentlarini belgilashlari mumkin (qarang ma'lumot olish ). Chiqishi ifodalangan RTN ning qo'llanilishi noaniq grammatika natijalarni mumkin bo'lgan tarjima yoki talqinlarning to'plamiga olib keladi. Ushbu to'plamni hisoblash eksponentga ega eng yomon narx, hatto uchun Earley tahlilchisi chiqishi bo'lgan RTNlar uchun,^[3] tarjimalar soni keskin o'sib boradigan holatlar tufayli w.r.t. kirish uzunligi; masalan, a-ni talqin qilish soni tabiiy til jumla w.r.t. hal qilinmagan soni predlogli ibora qo'shimchalar:^[4]^[5]

gapda qiz teleskop bilan maymunni ko'rdi, qiz teleskopdan foydalanganmi yoki maymun uni ushlab turganmi noma'lum (2¹ sharhlar),
gapda qiz bog'da teleskop bilan maymunni ko'rdi, shuningdek, maymun bog'da bo'lganmi yoki aksiya bog'da bo'lganmi noma'lum (2² sharhlar),
gapda qiz teleskop bilan maymunni daraxt tagidagi bog'da ko'rdi, maymun daraxt ostida bo'lganmi yoki harakat daraxt ostida bo'lganmi, noma'lum (2³ sharhlar),
va boshqalar.

FPN-lar ushbu tarjimalar to'plamining ixcham vakili bo'lib xizmat qiladi va uni kubik vaqt ichida Earleyga o'xshash ajralish vositasi yordamida hisoblashga imkon beradi.^[1] FPN holatlari ijro etish holatlariga mos keladi (qarang. Qarang ko'rsatma bosqichlari ) uchun Earley-parser RTNlar holda chiqish va FPN o'tishlari kirish belgilarining mumkin bo'lgan tarjimalariga mos keladi. The ${ displaystyle kappa}$ Olingan FPN xaritasi ko'rsatilgan chiqish segmentlari va tan olingan kirish segmentlari o'rtasidagi yozishmalarni beradi: taniqli kirish ketma-ketligi berilgan ${ displaystyle sigma _ {1} ldots sigma _ {l}}$ va FPN yo'li ${ displaystyle p}$ davlatdan boshlab ${ displaystyle q}$ va bir holatda tugaydi ${ displaystyle q ^ { prime}}$ , ${ displaystyle p}$ kirish segmentining mumkin bo'lgan tarjimasini anglatadi ${ displaystyle sigma _ { kappa (q) +1} ldots sigma _ { kappa (q ^ { prime})}}$ . Filtrni o'chirish xususiyati tarjimalarni namoyish qilish uchun FPN yo'llaridan qochish uchun talab qilinadi uzilgan yoki ustma-ust kirish segmentlari: FPN chaqiruvi chaqirilgan holatdan akseptor holatiga bir nechta tarjima yo'llarini o'z ichiga olishi mumkin, bu erda ular kirish segmentlari bir xil boshlang'ich nuqtasini baham ko'rishlari kerak, lekin bir xil uzunlikka ega bo'lishlari shart emas. Qo'ng'iroqni tugatgan akseptor holatiga qaraganda bir xil kirish nuqtasiga mos keladigan faqat qaytish holatlari yaroqli qaytish davlatlari.

Adabiyotlar

^ ^a ^b Xaver M. Sastre, "Filtrlangan ochiladigan rekursiv o'tish tarmoqlari yordamida samarali tahlil qilish", Sun'iy intellektdagi ma'ruza yozuvlari, 5642:241-244, 2009
^ Uilyam A. Vuds, "Tabiiy tilni tahlil qilish uchun o'tish tarmog'i grammatikalari", ACM aloqalari, ACM tugmachasini bosing, 13:10:591-606, 1970
^ Xaver M. Sastre va Mikel L. Forkada, "Chiqish bilan rekursiv o'tish tarmoqlaridan foydalangan holda samarali tahlil qilish", Kompyuter fanidan ma'ruza matnlari, 5603:192-204, 2009
^ Advayt Ratnaparxi, "Nazorat qilinmaydigan prepozitsion iborani biriktirish uchun statistik modellar", ACL-36: Hisoblash lingvistikasi assotsiatsiyasining 36-yillik yig'ilishi va kompyuter lingvistikasi bo'yicha 17-xalqaro konferentsiya materiallari, 1079-1085-betlar, 1998
^ Miriam Butt, "Yig'ma / sayoz tahlil", ma'ruza matnlari, 2002 y

[sastre09jb-1] Xaver M. Sastre, "Filtrlangan ochiladigan rekursiv o'tish tarmoqlari yordamida samarali tahlil qilish", Sun'iy intellektdagi ma'ruza yozuvlari, 5642:241-244, 2009

[woods70jb-2] Uilyam A. Vuds, "Tabiiy tilni tahlil qilish uchun o'tish tarmog'i grammatikalari", ACM aloqalari, ACM tugmachasini bosing, 13:10:591-606, 1970

[sastre09ja-3] Xaver M. Sastre va Mikel L. Forkada, "Chiqish bilan rekursiv o'tish tarmoqlaridan foydalangan holda samarali tahlil qilish", Kompyuter fanidan ma'ruza matnlari, 5603:192-204, 2009

[ratnaparkhi98ip-4] Advayt Ratnaparxi, "Nazorat qilinmaydigan prepozitsion iborani biriktirish uchun statistik modellar", ACL-36: Hisoblash lingvistikasi assotsiatsiyasining 36-yillik yig'ilishi va kompyuter lingvistikasi bo'yicha 17-xalqaro konferentsiya materiallari, 1079-1085-betlar, 1998

[5] Miriam Butt, "Yig'ma / sayoz tahlil", ma'ruza matnlari, 2002 y

[1]

[2]

[3]

[4]

[5]