Кіріспе
Контекстсіз грамматикаларды талдау алгоритмі
Компьютерлік ғылымда Кокке–Янгер–Касами алгоритмі (басқаша CYK немесе CKY деп аталады) – 1961 жылы Итиро Сакай жариялаған контекстсіз грамматикаларды талдау алгоритмі. Алгоритм оны қайта ашқандардың кейбірінің есімімен аталады: Джон Кокке, Дэниел Янгер, Тадао Касами және Джейкоб Т. Шварц. Ол төменнен жоғары талдау және динамикалық бағдарламалауды қолданады. CYK алгоритмінің стандартты нұсқасы тек Чомскидің қалыпты түрінде (CNF) берілген контекстсіз грамматикалармен жұмыс істейді. Дегенмен, кез келген контекстсіз грамматиканы алгоритмдік түрде сол тілді білдіретін CNF грамматикасына түрлендіруге болады. CYK алгоритмінің маңыздылығы оның белгілі бір жағдайлардағы жоғары тиімділігінен туындайды. Үлкен O нотациясын қолданғанда, CYK-нің ең нашар жағдайдағы орындалу уақыты , мұндағы – талданатын тізбектің ұзындығы, ал – CNF грамматикасының мөлшері. Бұл оны ең нашар жағдайда асимптотикалық күрделілік тұрғысынан ең тиімді талдау алгоритмдерінің біріне айналдырады, бірақ көптеген практикалық жағдайларда орташа орындалу уақыты жақсырақ болатын басқа алгоритмдер де бар.
The importance of the CYK algorithm stems from its high efficiency in certain situations. Using big O notation, the worst case running time of CYK is , where is the length of the parsed string and is the size of the CNF grammar This makes it one of the most efficient parsing algorithms in terms of worst case asymptotic complexity, although other algorithms exist with better average running time in many practical scenarios.
Стандартты нысан
Динамикалық бағдарламалау алгоритмі контекстсіз грамматиканы Чомскидің қалыпты түріне (CNF) келтіруді талап етеді, себебі ол ағымдағы тізбекті екі кішірек тізбекке бөлу мүмкіндіктерін тексереді. Бос тізбекті жаратпайтын кез келген контекстсіз грамматика CNF түрінде тек , , және түрлеріндегі өндіріс ережелерін пайдалана отырып бейнеленуі мүмкін, мұнда – бастапқы символ.
Прозалық
Бейресми түрде, бұл алгоритм кіріс жолдың барлық мүмкін кіші жолдарын қарастырады және егер ұзындығы *k* болатын, *i*-ден басталатын кіші жол берілген түйіндік ережеден туындатылса, оны рас деп белгілейді. Ол ұзындығы 1-ге тең кіші жолдарды қарастырғаннан кейін, ұзындығы 2-ге тең кіші жолдарға және т.б. көшеді. Ұзындығы 2 және одан үлкен кіші жолдар үшін, ол кіші жолды екі бөлікке бөлудің барлық мүмкін жағдайларын қарастырады және содан кейін, бірінші бөлікке сәйкес келетін және екінші бөлікке сәйкес келетін өндіріс ережесі бар-жоғын тексереді. Егер бар болса, ол кіші жолдың толығымен сәйкес келетінін тіркеп алады. Бұл процесс аяқталғаннан кейін, кіріс жол грамматика бойынша туындатылса, кіріс жолдың толығымен қамтылған кіші жолы бастапқы символға сәйкес келеді.
Талдау ағашын құру
Жоғарыда келтірілген алгоритм – сөйлемнің тілде болуын анықтайтын танушы. Оны массивтің элементтері ретінде талдау ағашының түйіндерін сақтау арқылы, 1-дің орнына, талдау ағашын құратын талдаушыға кеңейту оңай. Ағаш құрылымын құру үшін түйін, оны жасауға қолданылған массив элементтерімен байланыстырылады. Егер тек бір талдау ағашы жасалса, әрбір массив элементінде тек бір түйін жеткілікті. Дегенмен, егер екі мәнді сөйлемнің барлық талдау ағаштарын сақтау қажет болса, массив элементінде талдау процесінде осы түйінге жетудің барлық мүмкіндіктерінің тізімін сақтау керек. Мұндай жағдайда, көбінесе B[n,n,r] деп аталатын «кері сілтемелер» деп аталатын екінші кесте қолданылады. Нәтижесінде, әртүрлі талдаулар арасында ортақ бөліктері бөлінген, мүмкін талдау ағаштарының ортақ орман пайда болады. Бұл ортақ орманды тек қана талданған сөйлемді ғана құратын екі мәнді грамматика ретінде қарастыруға болады, бірақ бастапқы грамматикадағы сияқты екі мәнділік сақталады және терминал емес элементтердің өте қарапайым атауы ауыстырылғанда бірдей талдау ағаштары алынады, бұл көрсетілгендей.
CNF-ке жатпайтын контекстсіз грамматикаларды талдау
А. Чомскидің нормальды түріне барлық белгілі түрлендірулердің кемшілігі – грамматика көлемінің қажетсіздей үлғаюына әкелуі мүмкін. Грамматика көлемі – оның өндіріс ережелерінің көлемінің қосындысы, мұнда ереженің көлемі оның оң жақ бөлігінің ұзындығына бір қосылған сан. Түпкі грамматиканың көлемін білдіру үшін қолдансақ, ең жаман жағдайда көлемнің өсуі қолданылған түрлендіру алгоритміне байланысты , аралығында болуы мүмкін. Оқыту мақсатында Ланге мен Лейс CYK алгоритмін "алгоритмнің тиімділігіне, оның түсініктілігіне немесе дәлелдеудің қарапайымдылығына зиян келтірмей" сәл кеңейтуді ұсынады.
Контекстен тыс салмақталған грамматиканы талдау
Сондай-ақ, CYK алгоритмін салмақты және стохастикалық контекстсіз грамматикаларды қолдана отырып, тізбектерді талдау үшін кеңейту мүмкін. Салмақтар (ықтималдықтар) бұлеан мәндерінің орнына P кестесінде сақталады, сондықтан P[i,j,A] i-ден j-ға дейінгі кішкентай тізбекті A арқылы тудыруға болатын ең төмен салмақты (ең жоғары ықтималдықты) көрсетеді. Алгоритмнің одан әрі кеңейтілген нұсқалары тізбенің барлық талдауларын ең төмен салмақтан ең жоғары салмаққа дейін (ең жоғары ықтималдықтан ең төмен ықтималдыққа дейін) тізімдеуге мүмкіндік береді.
Сандық тұрақтылық
Ұзын тізбекке ықтималдық CYK алгоритмі қолданылғанда, көптеген ықтималдықтарды көбейтуден бөлу ықтималдығы тым кішкентай болып қалуы мүмкін. Мұны ықтималдықтарды көбейтудің орнына логарифм бойынша ықтималдықтарды қосу арқылы шешуге болады.
Валианттың алгоритмі
CYK-нің ең нашар жағдайдағы орындалу уақыты , мұндағы n – талданатын жолдың ұзындығы, ал |G| – CNF грамматикасы G-нің мөлшері. Бұл оны практикада жалпы контекстсіз тілдерді тану үшін ең тиімді алгоритмдердің біріне айналдырады. автор CYK алгоритмінің кеңейтілген нұсқасын ұсынды. Оның алгоритмі CYK алгоритмімен бірдей талдау кестесін есептейді; алайда, ол 0 және 1 жазбалары бар матрицаларды тиімді көбейту алгоритмдерін пайдалану арқылы осы есептеуді жүзеге асыруға болатынын көрсетті. Бұл матрицаларды көбейту үшін Coppersmith–Winograd алгоритмін қолданса, асимптотикалық ең нашар жағдайдағы орындалу уақыты болады. Дегенмен, Big O белгілемесінде жасырылған тұрақты шама соншалықты үлкен, Coppersmith–Winograd алгоритмі қазіргі компьютерлерде өңдеуге тым үлкен матрицалар үшін ғана тиімді, ал бұл тәсіл азайту операцияларын қажет етеді, сондықтан тек тану үшін қолданылады. Тиімді матрица көбейтуге тәуелділікті толығымен жою мүмкін емес: автор дәлелдегендей, кез келген контекстсіз грамматика үшін белгілі бір уақыт ішінде жұмыс істейтін кез келген талдағышты 0 және 1 жазбалары бар матрицалардың көбейтіндісін сол уақыт ішінде есептейтін алгоритмге тиімді түрлендіруге болады, ал Аббоуд және авторлар бұл тұрақты мөлшерлі грамматикаға да қатысты екенін көрсетті.
as the CYK algorithm; yet he showed that algorithms for efficient multiplication of matrices with 0 1 entries can be utilized for performing this computation. Using the Coppersmith–Winograd algorithm for multiplying these matrices, this gives an asymptotic worst case running time of However, the constant term hidden by the Big O Notation is so large that the Coppersmith–Winograd algorithm is only worthwhile for matrices that are too large to handle on present day computers , and this approach requires subtraction and so is only suitable for recognition. The dependence on efficient matrix multiplication cannot be avoided altogether: has proved that any parser for context free grammars working in time can be effectively converted into an algorithm computing the product of matrices with 0 1 entries in time , and this was extended by Abboud et al. to apply to a constant size grammar.