CYK algoritması - CYK algorithm

İçinde bilgisayar Bilimi, Cocke-Younger-Kasami algoritması (alternatif olarak CYKveya CKY) bir ayrıştırma algoritma için bağlamdan bağımsız gramerler Ichirō Sakai tarafından icat edildi.^[1] Algoritma, yeniden keşfeden bazılarının adını almıştır: John Cocke, Daniel Younger ve Tadao Kasami. İş veriyor aşağıdan yukarıya ayrıştırma ve dinamik program.

CYK'nın standart versiyonu yalnızca şu şekilde verilen bağlamdan bağımsız gramerler üzerinde çalışır. Chomsky normal formu (CNF). Bununla birlikte, herhangi bir bağlamdan bağımsız dilbilgisi, (anlaşmadan sonra) aynı dili ifade eden bir CNF dilbilgisine dönüştürülebilir (Sipser 1997 ).

CYK algoritmasının önemi, belirli durumlarda yüksek verimliliğinden kaynaklanmaktadır. Kullanma Büyük O gösterimi, en kötü durum çalışma süresi CYK ${ displaystyle { mathcal {O}} sol (n ^ {3} cdot sol | G sağ | sağ)}$ , nerede ${ displaystyle n}$ ayrıştırılan dizenin uzunluğu ve ${ displaystyle sol | G sağ |}$ CNF gramerinin boyutu ${ displaystyle G}$ (Hopcroft ve Ullman 1979, s. 140). Bu, onu en kötü durum açısından en verimli ayrıştırma algoritmalarından biri yapar asimptotik karmaşıklık Diğer algoritmalar, birçok pratik senaryoda daha iyi ortalama çalışma süresine sahip olmakla birlikte.

Standart biçim

dinamik program algoritması bağlamdan bağımsız gramerin dönüştürülmesini gerektirir. Chomsky normal formu (CNF), çünkü mevcut diziyi iki küçük diziye bölme olasılıklarını test eder. Boş dizeyi oluşturmayan herhangi bir bağlamdan bağımsız dilbilgisi, CNF'de yalnızca üretim kuralları formların ${ displaystyle A rightarrow alpha}$ ve ${ displaystyle A rightarrow BC}$ .

Algoritma

Sözde kod olarak

Algoritma sözde kod Şöyleki:

İzin Vermek girdi bir dizge olabilir ben oluşan n karakterler: a₁ ... a_n.İzin Vermek gramer şunları içerir r terminal olmayan semboller R₁ ... R_r, başlangıç simgesiyle R₁.İzin Vermek P[n,n,r] bir boole dizisi olabilir. Tüm öğelerini başlatın P yanlış.her biri için s = 1 ila n    her biri için birim üretim R_v → a_s        Ayarlamak P[1,s,v] = doğruher biri için l = 2 ila n - Aralık uzunluğu    her biri için s = 1 ila n-l+1 - Aralık başlangıcı        her biri için p = 1 ila l-1 - Aralık bölümü            her biri için üretim R_a    → R_b R_c                Eğer P[p,s,b] ve P[l-p,s+p,c] sonra Ayarlamak P[l,s,a] = doğruEğer P[n,1,1] doğru sonra    ben dilin üyesidirBaşka    ben dilin üyesi değil

Olasılıksal CYK (en olası ayrıştırmayı bulmak için)

Tüm üretimlerin olasılıkları göz önüne alındığında en olası ayrıştırmayı kurtarmaya izin verir.

İzin Vermek girdi bir dizge olabilir ben oluşan n karakterler: a₁ ... a_n.İzin Vermek gramer şunları içerir r terminal olmayan semboller R₁ ... R_r, başlangıç simgesiyle R₁.İzin Vermek P[n,n,r] gerçek sayılar dizisi olabilir. Tüm öğelerini başlatın P sıfıra.İzin Vermek geri[n,n,r] backpointing üçlülerinden oluşan bir dizi.her biri için s = 1 ila n  her biri için birim üretim R_v →a_s    Ayarlamak P[1,s,v] = Pr (R_v →a_s)her biri için l = 2 ila n - Aralık uzunluğu  her biri için s = 1 ila n-l+1 - Aralık başlangıcı    her biri için p = 1 ila l-1 - Aralık bölümü             her biri için üretim R_a → R_b R_c        prob_splitting = Pr (R_a →R_b R_c) * P[p,s,b] * P[l-p,s+p,c]        Eğer P[p,s,b]> 0 ve P[l-p,s+p,c]> 0 ve P[l,s,a] sonra           Ayarlamak P[l,s,a] = prob_splitting Ayarlamak geri[l,s,a] =

Nesir olarak

Gayri resmi terimlerle, bu algoritma giriş dizesinin olası her alt dizesini dikkate alır ve ${ displaystyle P [l, s, v]}$ uzunluk alt dizesi ise doğru ${ displaystyle l}$ den başlayarak ${ displaystyle s}$ terminal olmayan değişkenden üretilebilir ${ displaystyle R_ {v}}$ . 1 uzunluğundaki alt dizeleri dikkate aldıktan sonra, 2 uzunluğundaki alt dizelere gider ve bu böyle devam eder. Uzunluk 2 ve daha büyük olan alt dizeler için, alt dizenin her olası bölümünü iki parçaya ayırır ve bir miktar üretim olup olmadığını kontrol eder. ${ displaystyle P ile Q ; R}$ öyle ki ${ displaystyle Q}$ ilk bölümle eşleşir ve ${ displaystyle R}$ ikinci bölümle eşleşir. Eğer öyleyse, kaydeder ${ displaystyle P}$ tüm alt dizeyle eşleşecek şekilde. Bu işlem tamamlandıktan sonra, tüm giriş dizesini içeren alt dize, başlangıç sembolü ile eşleşirse, cümle dilbilgisi tarafından tanınır.

Misal

CYK algoritmasını kullanarak cümle ayrıştırma

Bu örnek bir gramerdir:

{ displaystyle { begin {align} { ce {S}} & { ce {-> NP VP}} { ce {VP}} & { ce {-> VP PP} } { ce {VP}} & { ce {-> V NP}} { ce {VP}} & { ce {-> yiyor}} { ce {PP }} & { ce {-> P NP}} { ce {NP}} & { ce {-> Det N}} { ce {NP}} & { ce {-> she}} { ce {V}} & { ce {-> yiyor}} { ce {P}} & { ce {-> with}} { ce {N}} & { ce {-> balık}} { ce {N}} & { ce {-> fork}} { ce {Det}} & { ce {-> a}} end {hizalı}}}

Şimdi cümle çatalla bir balık yer CYK algoritması kullanılarak analiz edilir. Aşağıdaki tabloda, ${ displaystyle P [i, j, k]}$ , $ben$ satırın numarasıdır (en alttan 1'den başlar) ve $j$ sütunun numarasıdır (soldan 1'den başlar).

CYK tablosu
S
	VP

S
	VP			PP
S		NP			NP
NP	V, VP	Det.	N	P	Det	N
o	yiyor	a	balık	ile	a	çatal

Okunabilirlik için, CYK tablosu P burada 2 boyutlu bir matris olarak temsil edilmektedir M bir dizi terminal olmayan sembol içerir, öyle ki $R k$ içinde ${ displaystyle M [i, j]}$ ancak ve ancak, ${ displaystyle P [i, j, k]}$ Yukarıdaki örnekte, bir başlangıç sembolü S içinde ${ displaystyle M [7,1]}$ , cümle dilbilgisi ile oluşturulabilir.

Uzantılar

Ayrıştırma ağacının oluşturulması

Yukarıdaki algoritma bir tanıyıcı bu sadece bir cümlenin dilde olup olmadığını belirleyecektir. Bunu bir ayrıştırıcı aynı zamanda bir ayrıştırma ağacı, ayrıştırma ağacı düğümlerini boolean 1 yerine dizinin öğeleri olarak depolayarak. Düğüm, ağaç yapısını inşa etmek için onu üretmek için kullanılan dizi elemanlarına bağlıdır. Yalnızca bir ayrıştırma ağacı üretilecekse, her bir dizi elemanında böyle bir düğüm gereklidir. Bununla birlikte, belirsiz bir cümlenin tüm ayrıştırma ağaçlarının saklanması gerekiyorsa, çözümleme sürecinde karşılık gelen düğümün elde edilebileceği tüm yolların bir listesini dizi öğesinde saklamak gerekir. Bu bazen ikinci bir B [n, n, r] tablosu ile yapılır. arka işaretçilerNihai sonuç, ortak ağaç parçalarının çeşitli ayrıştırmalar arasında çarpanlara ayrıldığı, olası ayrıştırma ağaçlarının ortak ormanıdır. Bu paylaşılan orman rahatlıkla bir belirsiz gramer yalnızca ayrıştırılan cümleyi, ancak orijinal dilbilgisi ile aynı belirsizlikle ve aynı ayrıştırma ağaçlarını, terminal olmayanların çok basit bir yeniden adlandırmasına kadar, Lang (1994).

CNF olmayan bağlamdan bağımsız gramerleri ayrıştırma

İşaret ettiği gibi Lange ve Leiß (2009) Chomsky normal biçimine dönüştüğü bilinen tüm dönüşümlerin dezavantajı, gramer boyutunda istenmeyen bir şişkinliğe yol açabilmeleridir. Bir dilbilgisinin boyutu, üretim kurallarının boyutlarının toplamıdır; burada bir kuralın boyutu bir artı sağ tarafının uzunluğudur. Kullanma ${ displaystyle g}$ orijinal dilbilgisinin boyutunu belirtmek için, en kötü durumda boyut şişmesi, ${ displaystyle g ^ {2}}$ -e ${ displaystyle 2 ^ {2g}}$ , kullanılan dönüştürme algoritmasına bağlı olarak. Öğretimde kullanım için, Lange ve Leiß, "algoritmanın etkinliğinden, sunumunun netliğinden veya ispatların basitliğinden ödün vermeden" CYK algoritmasının hafif bir genellemesini önermektedir (Lange ve Leiß 2009 ).

Ağırlıklı bağlamdan bağımsız gramerleri ayrıştırma

CYK algoritmasını kullanarak dizeleri ayrıştırmak için genişletmek de mümkündür. ağırlıklı ve stokastik bağlamdan bağımsız gramerler. Ağırlıklar (olasılıklar) daha sonra boole'lar yerine P tablosunda saklanır, bu nedenle P [i, j, A], i'den j'ye kadar olan alt dizenin A'dan türetilebileceği minimum ağırlığı (maksimum olasılık) içerecektir. algoritması, bir dizenin tüm çözümlemelerinin en düşükten en yükseğe ağırlığa (en yüksekten en düşüğe) numaralandırılmasına izin verir.

Valiant algoritması

en kötü durum çalışma süresi CYK ${ displaystyle Teta (n ^ {3} cdot | G |)}$ , nerede n ayrıştırılmış dizenin uzunluğudur ve |G| CNF gramerinin boyutu G. Bu, pratikte genel bağlamdan bağımsız dilleri tanımak için en verimli algoritmalardan biri olmasını sağlar. Valiant (1975) CYK algoritmasının bir uzantısını verdi. Algoritması, CYK algoritmasıyla aynı ayrıştırma tablosunu hesaplar; yine de gösterdi verimli çarpma için algoritmalar nın-nin 0-1 girişli matrisler bu hesaplamayı yapmak için kullanılabilir.

Kullanmak Bakırcı-Winograd algoritması bu matrisleri çarpmak için bu, asimptotik bir en kötü durum çalışma süresi verir. ${ displaystyle O (n ^ {2.38} cdot | G |)}$ . Ancak, tarafından gizlenen sabit terim Büyük O Notasyonu Coppersmith-Winograd algoritmasının yalnızca günümüz bilgisayarlarında işlenemeyecek kadar büyük olan matrisler için değerli olduğu kadar büyüktür (Knuth 1997 ) ve bu yaklaşım çıkarma gerektirir ve bu nedenle yalnızca tanıma için uygundur. Etkili matris çarpımına bağımlılıktan tamamen kaçınılamaz: Lee (2002) zaman içinde çalışan bağlamdan bağımsız gramerler için herhangi bir ayrıştırıcının ${ displaystyle O (n ^ {3- varepsilon} cdot | G |)}$ ürününü hesaplayan bir algoritmaya etkili bir şekilde dönüştürülebilir ${ displaystyle (n kere n)}$ -zaman içinde 0-1 girişli matrisler ${ displaystyle O (n ^ {3- varepsilon / 3})}$ .

Ayrıca bakınız

Referanslar

^ Grune, Dick (2008). Ayrıştırma teknikleri: pratik bir rehber (2. baskı). New York: Springer. ISBN 978-0-387-20248-8.

Kaynaklar

Cocke, John; Schwartz, Jacob T. (Nisan 1970). Programlama dilleri ve derleyicileri: Ön notlar (PDF) (Teknik rapor) (2. revize edilmiş baskı). CIMS, NYU.
Hopcroft, John E.; Ullman, Jeffrey D. (1979). Otomata Teorisi, Dilleri ve Hesaplamaya Giriş. Okuma / MA: Addison-Wesley. ISBN 0-201-02988-X.CS1 bakimi: ref = harv (bağlantı)
Kasami, T. (1965). Bağlamdan bağımsız diller için verimli bir tanıma ve sözdizimi analizi algoritması (Teknik rapor). AFCRL. 65-758.
Knuth, Donald E. (14 Kasım 1997). The Art of Computer Programming Volume 2: Seminumerical Algorithms (3. baskı). Addison-Wesley Profesyonel. s. 501. ISBN 0-201-89684-2.CS1 bakimi: ref = harv (bağlantı)
Lang Bernard (1994). "Tanıma, ayrıştırmaktan daha zor olabilir". Bilgisayar. Zeka. 10 (4): 486–494. CiteSeerX 10.1.1.50.6982. doi:10.1111 / j.1467-8640.1994.tb00011.x.CS1 bakimi: ref = harv (bağlantı)
Lange, Martin; Leiß, Hans (2009). "CNF'ye mi yoksa CNF'ye mi? CYK Algoritmasının Etkili Ancak Takdir Edilebilir Bir Versiyonu". Informatica Didactica. 8.CS1 bakimi: ref = harv (bağlantı)
Lee, Lillian (2002). "Hızlı bağlamdan bağımsız dilbilgisi ayrıştırma, hızlı Boolean matris çarpımı gerektirir". J. ACM. 49 (1): 1–15. arXiv:cs / 0112018. doi:10.1145/505241.505242.CS1 bakimi: ref = harv (bağlantı)
Sipser, Michael (1997). Hesaplama Teorisine Giriş (1. baskı). IPS. s.99. ISBN 0-534-94728-X.CS1 bakimi: ref = harv (bağlantı)
Valiant, Leslie G. (1975). "Kübik süreden daha kısa sürede genel bağlamdan bağımsız tanıma". J. Comput. Syst. Sci. 10 (2): 308–314. doi:10.1016 / s0022-0000 (75) 80046-8.CS1 bakimi: ref = harv (bağlantı)
Daha genç Daniel H. (Şubat 1967). "Bağlamdan bağımsız dillerin zaman içinde tanınması ve ayrıştırılması n³". Bilgi vermek. Kontrol. 10 (2): 189–208. doi:10.1016 / s0019-9958 (67) 80007-x.

Dış bağlantılar

[1] Grune, Dick (2008). Ayrıştırma teknikleri: pratik bir rehber (2. baskı). New York: Springer. ISBN 978-0-387-20248-8.

[1]

Algoritmaları ayrıştırma
Yukarıdan aşağıya	LL Yinelemeli iniş Özyinelemeli kuyruk Pratt ayrıştırıcı
Altüst	Öncelik Basit Şebeke Manevra sahası Sınırlı bağlam LR Basit İleriye bak Kanonik Genelleştirilmiş CYK Yinelemeli yükselme Shift-azalt
Karışık, diğer	Birleştirici Grafik Earley
İlgili konular	PEG Kesin cümle dilbilgisi Deterministik ayrıştırma Dinamik program Memoization Ayrıştırıcı oluşturucu LALR Ayrıştırma ağacı AST Tarayıcısız ayrıştırma Derleyici yapısının tarihi Ayrıştırıcı oluşturucuların karşılaştırılması