About: CYK algorithm   Goto Sponge  NotDistinct  Permalink

An Entity of Type : yago:WikicatParsingAlgorithms, within Data Space : dbpedia.org associated with source document(s)

In computer science, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars, named after its inventors, John Cocke, Daniel Younger and Tadao Kasami. It employs bottom-up parsing and dynamic programming. The standard version of CYK operates only on context-free grammars given in Chomsky normal form (CNF). However any context-free grammar may be transformed to a CNF grammar expressing the same language ().

AttributesValues
rdf:type
rdfs:label
  • CYK algorithm
  • Cocke-Younger-Kasami-Algorithmus
  • Algoritmo CYK
  • Algorithme de Cocke-Younger-Kasami
  • CYK法
  • CYK-algoritme
  • Algorytm CYK
  • Algoritmo CYK
  • Алгоритм Кока — Янгера — Касами
  • CYK算法
rdfs:comment
  • Der Cocke-Younger-Kasami-Algorithmus (CYK-Algorithmus) ist ein Algorithmus aus dem Gebiet der Theoretischen Informatik. Mit ihm lässt sich feststellen, ob ein Wort zu einer bestimmten kontextfreien Sprache gehört. In der Fachsprache bezeichnet man dies als Lösen des Wortproblems für kontextfreie Sprachen. Mit Hilfe von Backtracking kann der Parse-Tree bzw. die Parse-Trees eines gegebenen Wortes der Sprache konstruiert werden. Um den Algorithmus anzuwenden, muss zu der vorgegebenen Sprache eine Grammatik in Chomsky-Normalform vorliegen. Der in den 1960er Jahren von Itiroo Sakai, John Cocke, Tadao Kasami, Jacob Schwartz und Daniel Younger unabhängig voneinander entwickelte Algorithmus nutzt das Prinzip der dynamischen Programmierung.
  • CYK法(英: CYK algorithm)は、ある文字列が与えられた文脈自由文法で生成できるかを決め、生成できる場合の生成方法を求めるアルゴリズムである。CYK は Cocke-Younger-Kasami の略。文字列の構文解析手法として知られている。このアルゴリズムは一種の動的計画法である。 標準的なCYK法は、チョムスキー標準形で書かれた文脈自由文法で定義される言語を認識する。任意の文脈自由文法をチョムスキー標準形に書き換えるのはそれほど困難ではないので、CYK法は任意の文脈自由文法の認識に使うことができる。CYK法を拡張してチョムスキー標準形で書かれていない文脈自由文法を扱うようにすることも可能である。これにより性能は向上するが、アルゴリズムを理解することは難しくなる。 CYK法の最悪時間計算量は Θ(n3) であり、n は解析対象の文字列の長さである。従って、CYK法は任意の文脈自由言語を認識できる最も効率的なアルゴリズムの1つである。ただし、文脈自由言語の特定のサブセットについて、より効率の良いアルゴリズムが他に存在する。
  • Algorytm CYK (Cocke'a-Youngera-Kasamiego) – dynamiczny algorytm sprawdzający, czy słowo należy do języka bezkontekstowego. Algorytm działa w czasie względem długości słowa. Język bezkontekstowy musi być przedstawiony w postaci normalnej Chomsky'ego.
  • CYK算法(英语:Cocke–Younger–Kasami algorithm,縮寫為CYK algorithm)是由約翰·科克,Younger和嵩忠雄共同研究出来大约发表于1965年的一个算法,它是一个用来判定任意给定的字符串 是否属于一个上下文无关文法的算法。普通的回溯法(backtracking)在最坏的情况下需要指数时间才能解决这样的问题,而CYK算法只需要多项式时间就够了( , n 为字符串 w 的长度)。CYK算法采用了动态规划的思想。 对于一个任意给定的上下文无关文法,都可以使用CYK算法来计算上述问题,但首先要将该文法转换成乔姆斯基范式。
  • Алгоритм Кока — Янгера — Касами (англ. Cocke — Younger — Kasami algorithm), алгоритм CYK либо CKY — алгоритм, позволяющий установить, можно ли в заданной контекстно-свободной грамматике вывести заданную строку, и если это так, то предоставить её вывод. Другими словами, это алгоритм синтаксического анализа строки. Алгоритм реализует синтаксический анализ снизу-вверх и основывается на методе динамического программирования.
  • In computer science, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars, named after its inventors, John Cocke, Daniel Younger and Tadao Kasami. It employs bottom-up parsing and dynamic programming. The standard version of CYK operates only on context-free grammars given in Chomsky normal form (CNF). However any context-free grammar may be transformed to a CNF grammar expressing the same language ().
  • El algoritmo de Cocke-Younger-Kasami (CYK) determina si una cadena puede ser generada por una gramática libre de contexto y, si es posible, cómo puede ser generada. Este proceso es conocido como análisis sintáctico de la cadena. El algoritmo es un ejemplo de programación dinámica.
  • En informatique théorique et en théorie des langages, l'algorithme de Cocke-Younger-Kasami (CYK) est un algorithme d'analyse syntaxique pour les grammaires non contextuelles. Il permet de déterminer si un mot est engendré par une grammaire, et si oui, d'en donner un arbre syntaxique. L'algorithme est nommé d'après les trois personnes qui l'ont trouvé indépendamment, J. Cocke, dont l'article n'a jamais été publié, D. H. Younger et T. Kasami qui a publié un rapport interne aux US-AirForce. , où est la longueur du mot à analyser et est la taille de la grammaire.
  • Het Cocke-Younger-Kasami (CYK)-algoritme (soms ook bekend als CKY) bepaalt of een string gegenereerd kan worden door een gegeven context-vrije grammatica en, als dit het geval is levert het de manier waarop de string kan gegenereerd worden. Dit proces noemt men het parsen of ontleden van de string. Het algoritme is een voorbeeld van dynamisch programmeren. Het algoritme is vernoemd naar John Cocke, Daniel H. Younger en Tadao Kasami.
  • O algoritmo Cocke-Younger-Kasami (CYK) determina se uma cadeia de caracteres pode ser gerada por uma determinada gramática livre de contexto e, se ela puder, como ela pode ser gerada. Esse processo é conhecido como a análise sintática da cadeia, no caso, ascendente. A versão padrão do algoritmo opera em gramáticas livres de contexto expressas através da Forma Normal de Chomsky (CNF). No pior caso, o algoritmo possui complexidade , em que é o comprimento da cadeia de caracteres e o tamanho da gramática CNF
sameAs
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Link from a Wikipage to an external page
foaf:isPrimaryTopicOf
prov:wasDerivedFrom
has abstract
  • In computer science, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars, named after its inventors, John Cocke, Daniel Younger and Tadao Kasami. It employs bottom-up parsing and dynamic programming. The standard version of CYK operates only on context-free grammars given in Chomsky normal form (CNF). However any context-free grammar may be transformed to a CNF grammar expressing the same language (). The importance of the CYK algorithm stems from its high efficiency in certain situations. Using Landau symbols, the worst case running time of CYK is , where n is the length of the parsed string and |G| is the size of the CNF grammar G (, p. 140). 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.
  • Der Cocke-Younger-Kasami-Algorithmus (CYK-Algorithmus) ist ein Algorithmus aus dem Gebiet der Theoretischen Informatik. Mit ihm lässt sich feststellen, ob ein Wort zu einer bestimmten kontextfreien Sprache gehört. In der Fachsprache bezeichnet man dies als Lösen des Wortproblems für kontextfreie Sprachen. Mit Hilfe von Backtracking kann der Parse-Tree bzw. die Parse-Trees eines gegebenen Wortes der Sprache konstruiert werden. Um den Algorithmus anzuwenden, muss zu der vorgegebenen Sprache eine Grammatik in Chomsky-Normalform vorliegen. Der in den 1960er Jahren von Itiroo Sakai, John Cocke, Tadao Kasami, Jacob Schwartz und Daniel Younger unabhängig voneinander entwickelte Algorithmus nutzt das Prinzip der dynamischen Programmierung.
  • El algoritmo de Cocke-Younger-Kasami (CYK) determina si una cadena puede ser generada por una gramática libre de contexto y, si es posible, cómo puede ser generada. Este proceso es conocido como análisis sintáctico de la cadena. El algoritmo es un ejemplo de programación dinámica. La versión estándar de CYK reconoce lenguajes definidos por una gramática libre de contexto escrita en la forma normal de Chomsky (CNF). Cualquier gramática libre de contexto puede ser convertida a CNF sin mucha dificultad, CYK puede usarse para reconocer cualquier lenguaje libre de contexto. Es posible extender el algoritmo CYK para que trabaje sobre algunas gramáticas libre de contexto no escritas como CNF. Esto puede hacerse para mejorar la ejecución, aunque hace el algoritmo más difícil de entender. En el peor caso asintótico la complejidad temporal de CYK es de Θ(n3), donde n es la longitud de la cadena analizada. Esto hace a este algoritmo uno de los más eficientes (en estos términos) en el reconocimiento de los lenguajes libres de contexto. Sin embargo, existen otros algoritmos con un mejor funcionamiento para ciertos subconjuntos de los lenguajes libres de contexto.
  • En informatique théorique et en théorie des langages, l'algorithme de Cocke-Younger-Kasami (CYK) est un algorithme d'analyse syntaxique pour les grammaires non contextuelles. Il permet de déterminer si un mot est engendré par une grammaire, et si oui, d'en donner un arbre syntaxique. L'algorithme est nommé d'après les trois personnes qui l'ont trouvé indépendamment, J. Cocke, dont l'article n'a jamais été publié, D. H. Younger et T. Kasami qui a publié un rapport interne aux US-AirForce. L'algorithme opère par analyse ascendante et emploie la programmation dynamique. L'algorithme suppose que la grammaire est en forme normale de Chomsky. Cette restriction n'est pas gênante dans la mesure où toute grammaire non contextuelle admet une grammaire en forme normale de Chomsky équivalente. Le temps de calcul de cet algorithme est en , où est la longueur du mot à analyser et est la taille de la grammaire.
  • CYK法(英: CYK algorithm)は、ある文字列が与えられた文脈自由文法で生成できるかを決め、生成できる場合の生成方法を求めるアルゴリズムである。CYK は Cocke-Younger-Kasami の略。文字列の構文解析手法として知られている。このアルゴリズムは一種の動的計画法である。 標準的なCYK法は、チョムスキー標準形で書かれた文脈自由文法で定義される言語を認識する。任意の文脈自由文法をチョムスキー標準形に書き換えるのはそれほど困難ではないので、CYK法は任意の文脈自由文法の認識に使うことができる。CYK法を拡張してチョムスキー標準形で書かれていない文脈自由文法を扱うようにすることも可能である。これにより性能は向上するが、アルゴリズムを理解することは難しくなる。 CYK法の最悪時間計算量は Θ(n3) であり、n は解析対象の文字列の長さである。従って、CYK法は任意の文脈自由言語を認識できる最も効率的なアルゴリズムの1つである。ただし、文脈自由言語の特定のサブセットについて、より効率の良いアルゴリズムが他に存在する。
  • Algorytm CYK (Cocke'a-Youngera-Kasamiego) – dynamiczny algorytm sprawdzający, czy słowo należy do języka bezkontekstowego. Algorytm działa w czasie względem długości słowa. Język bezkontekstowy musi być przedstawiony w postaci normalnej Chomsky'ego.
  • Het Cocke-Younger-Kasami (CYK)-algoritme (soms ook bekend als CKY) bepaalt of een string gegenereerd kan worden door een gegeven context-vrije grammatica en, als dit het geval is levert het de manier waarop de string kan gegenereerd worden. Dit proces noemt men het parsen of ontleden van de string. Het algoritme is een voorbeeld van dynamisch programmeren. De standaard versie van CYK herkent talen gedefinieerd door contextvrije grammatica's die in Chomsky-normaalvorm zijn. Aangezien elke contextvrije grammatica op eenvoudige wijze in deze normaalvorm om te zetten is, kan CYK gebruikt worden om alle contextvrije talen te herkennen. Het is eveneens mogelijk het CYK-algoritme uit te breiden zodat de gegeven contextvrije grammatica niet noodzakelijk in Chomsky-normaalvorm moet staan. Zulke uitbreiding maakt het algoritme meer performant, maar ook moeilijker om de werking te begrijpen. In het slechtste geval is de asymptotische tijdscomplexiteit van CYK Θ(n3), waar n de lengte van de geparseerde string is. Dit maakt het één van de meest efficiënte algoritmes voor het herkennen van contextvrije talen qua tijdscomplexiteit. Er zijn echter wel andere algoritmes die nog beter presteren om bepaalde deelgroepen van de contextvrije talen te herkennen. Het algoritme is vernoemd naar John Cocke, Daniel H. Younger en Tadao Kasami.
Faceted Search & Find service v1.17_git21 as of Mar 09 2019


Alternative Linked Data Documents: PivotViewer | iSPARQL | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 07.20.3230 as of Dec 18 2018, on Linux (x86_64-generic-linux-glibc25), Single-Server Edition (61 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2019 OpenLink Software