CYK algorithm
http://dbpedia.org/resource/CYK_algorithm an entity of type: WikicatParsingAlgorithms
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 , John Cocke, Tadao Kasami, Jacob Schwartz und unabhängig voneinander entwickelte Algorithmus nutzt das Prinzip der dynamischen Programmierung.
rdf:langString
CYK法（英: CYK algorithm）は、ある文字列が与えられた文脈自由文法で生成できるかを決め、生成できる場合の生成方法を求めるアルゴリズムである。CYK は Cocke-Younger-Kasami の略（それぞれ、RISCの先駆と言われる801などでも知られるジョン・コック、Daniel Younger、嵩忠雄である）。文脈自由文法の構文解析手法と捉えることもできる。このアルゴリズムは一種の動的計画法である。 標準的なCYK法は、チョムスキー標準形で書かれた文脈自由文法で定義される言語を認識する。任意の文脈自由文法をチョムスキー標準形に書き換えるのはそれほど困難ではないので、CYK法は任意の文脈自由文法の認識に使うことができる。CYK法を拡張してチョムスキー標準形で書かれていない文脈自由文法を扱うようにすることも可能である。これにより性能は向上するが、アルゴリズムを理解することは難しくなる。 CYK法の最悪時間計算量は Θ(n3) であり、n は解析対象の文字列の長さである。従って、CYK法は任意の文脈自由言語を認識できる最も効率的なアルゴリズムの1つである。ただし、文脈自由言語の特定のサブセットについて、より効率の良いアルゴリズムが他に存在する。
rdf:langString
CYK 알고리즘(Cocke-Younger-Kasami 알고리즘, CYK Algorithm) 또는 CKY 알고리즘은 특정한 문자열에 대해, 그 문자열이 특정한 문맥 자유 문법에 속하는지를 판단하고, 또한 어떠한 방식으로 생성되는지를 판단하는 파싱 알고리즘이다. 이 알고리즘은 동적 계획법을 사용하며, 구조를 가지고 있다. 기본적으로 CYK 알고리즘에서는 으로 표현된 문맥 자유 문법을 사용하지만, 모든 문맥 자유 문법은 촘스키 정규 형식으로 변환이 가능하기 때문에 CYK 알고리즘을 사용할 수 있다. 문자열의 길이가 일 때, CYK 알고리즘은 Θ(n3)의 시간 복잡도를 가진다. 이것은 현재 모든 문맥 자유 문법을 파싱할 수 있는 가장 효율적인 알고리즘이다. (CYK 알고리즘보다 효율적으로 동작하는 몇몇 알고리즘이 있지만, 그 알고리즘은 특정한 문법의 경우에만 사용이 가능하다.)
rdf:langString
Algorytm CYK (Cocke’a-Youngera-Kasamiego) – dynamiczny algorytm sprawdzający, czy słowo należy do języka bezkontekstowego. Język bezkontekstowy musi być przedstawiony w postaci normalnej Chomsky’ego. Algorytm działa w czasie gdzie jest długością słowa, a jest rozmiarem gramatyki.
rdf:langString
CYK算法（英語：Cocke–Younger–Kasami algorithm，縮寫為CYK algorithm）是由約翰·科克，Younger和共同研究出来大约发表于1965年的一个算法，它是一个用来判定任意给定的字符串 是否属于一个上下文无关文法的算法。普通的回溯法（backtracking）在最坏的情况下需要指数时间才能解决这样的问题，而CYK算法只需要多项式时间就够了（ ， n 为字符串 w 的长度）。CYK算法采用了动态规划的思想。 对于一个任意给定的上下文无关文法，都可以使用CYK算法来计算上述问题，但首先要将该文法转换成乔姆斯基范式。
rdf:langString
خوارزمية كوك-يونغير-كاسامي Cocke-Younger-Kasami (وتسمى أيضاً CKY) هي خوارزمية تحليل نحوي تنتمي للقواعد النحوية الخالية من السياق في علوم الحاسوب، وقد سميت باسم مخترعيها، جون كوك، دانيال يونغير وتاداو كسامي. وهي تستخدم في التحليل من الأسفل إلى الأعلى والبرمجة الديناميكية. يعمل الإصدار القياسي من الخوارزمية فقط على القواعد الخالية من السياق في نموذج تشومسكي الطبيعي (CNF). ومع ذلك، يمكن تحويل أي قواعد نحوية خالية من السياق إلى قواعد CNF معبرة عن نفس اللغة.
rdf:langString
Algoritmus CYK (Cocke-Younger-Kasami) je algoritmus, který určuje, zda slovo náleží do bezkontextového jazyka, a to v časové složitosti vzhledem k délce slova. Bezkontextový jazyk musí být zapsán gramatikou v Chomského normální formě. Algoritmus vypadá takto: Jiné algoritmy jsou Earlyho parser a .
rdf:langString
In computer science, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars published by Itiroo Sakai in 1961. The algorithm is named after some of its rediscoverers: John Cocke, Daniel Younger, Tadao Kasami, and Jacob T. Schwartz. 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 (after convention) to a CNF grammar expressing the same language.
rdf:langString
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.
rdf:langString
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, publié par Itiroo Sakai en 1961. 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 redécouvert 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.
rdf:langString
Het Cocke-Younger-Kasami (CYK)-algoritme (soms ook bekend als CKY) bepaalt of een string gegenereerd kan worden door een gegeven contextvrije grammatica en, als dit het geval is, levert het de manier waarop de string gegenereerd kan worden. Dit proces noemt men het parsen of ontleden van de string. Het algoritme is een voorbeeld van . Het algoritme is vernoemd naar John Cocke, en .
rdf:langString
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.
rdf:langString
Алгоритм Кока — Янгера — Касами (англ. Cocke — Younger — Kasami algorithm), алгоритм CYK либо CKY — алгоритм, позволяющий установить, можно ли в заданной контекстно-свободной грамматике вывести заданную строку, и если это так, то предоставить её вывод. Другими словами, это алгоритм синтаксического анализа строки. Алгоритм реализует синтаксический анализ снизу-вверх и основывается на методе динамического программирования. его открыватели: Джон Кок, Дэниел Янгер, Тадао Касами и Джейкоб Т. Шварц. Они использовали восходящий анализ и динамическое программирование.
rdf:langString
rdf:langString
خوارزمية CYK
rdf:langString
Algoritmus Cocke-Younger-Kasami
rdf:langString
Cocke-Younger-Kasami-Algorithmus
rdf:langString
Algoritmo CYK
rdf:langString
CYK algorithm
rdf:langString
Algorithme de Cocke-Younger-Kasami
rdf:langString
CYK法
rdf:langString
CYK 알고리즘
rdf:langString
CYK-algoritme
rdf:langString
Algorytm CYK
rdf:langString
Algoritmo CYK
rdf:langString
Алгоритм Кока — Янгера — Касами
rdf:langString
CYK算法
rdf:langString
Cocke–Younger–Kasami algorithm
xsd:integer
53929
xsd:integer
1113022326
rdf:langString
Parsing with context-free grammars
rdf:langString
, where:
* is length of the string
* is the size of the CNF grammar
rdf:langString
Algoritmus CYK (Cocke-Younger-Kasami) je algoritmus, který určuje, zda slovo náleží do bezkontextového jazyka, a to v časové složitosti vzhledem k délce slova. Bezkontextový jazyk musí být zapsán gramatikou v Chomského normální formě. Algoritmus vypadá takto: Vytvoříme pole , pro , kde jsou postupně všechny neterminály (nebo alternativně jejich čísla), a hodnoty všech jeho prvků nastavíme na 0Pro každý znak na pozici , a pro každé takové, že v gramatice existuje pravidlo , nastavíme v poli Pro každou délku podslova od 2 do :Pro každý začátek podslova od 1 do :Pro každou délku první poloviny podslova od 1 do :Jestliže v poli mají jedničkovou hodnotu i , a v gramatice existuje pravidlo , nastavíme v poli Slovo náleží do jazyka, jestliže , kde je vstupní neterminál gramatiky. Jiné algoritmy jsou Earlyho parser a .
rdf:langString
خوارزمية كوك-يونغير-كاسامي Cocke-Younger-Kasami (وتسمى أيضاً CKY) هي خوارزمية تحليل نحوي تنتمي للقواعد النحوية الخالية من السياق في علوم الحاسوب، وقد سميت باسم مخترعيها، جون كوك، دانيال يونغير وتاداو كسامي. وهي تستخدم في التحليل من الأسفل إلى الأعلى والبرمجة الديناميكية. يعمل الإصدار القياسي من الخوارزمية فقط على القواعد الخالية من السياق في نموذج تشومسكي الطبيعي (CNF). ومع ذلك، يمكن تحويل أي قواعد نحوية خالية من السياق إلى قواعد CNF معبرة عن نفس اللغة. تنبع أهمية خوارزمية (CYK) من كفاءتها العالية في مواقف معينة. إذا ما قيمنا كفاءة عملها بواسطة مقياس التعقيد الحسابي Big O، فإن اسوء حالة تشغيل يمكن الحصول عليها في خوارزمية CYK هي ، حيث تمثل n طول الجملة المراد تحليلها فيما تمثل G حجم القواعد ضمن نموذج تشومسكي الطبيعي الذي يتم العمل عليه. ويجعلها هذا إحدى أكثر خوارزميات التحليل النحوي فاعلية، من ناحية التعقيد الحسابي.
rdf:langString
In computer science, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars published by Itiroo Sakai in 1961. The algorithm is named after some of its rediscoverers: John Cocke, Daniel Younger, Tadao Kasami, and Jacob T. Schwartz. 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 (after convention) to a CNF grammar expressing the same language. 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.
rdf:langString
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 , John Cocke, Tadao Kasami, Jacob Schwartz und unabhängig voneinander entwickelte Algorithmus nutzt das Prinzip der dynamischen Programmierung.
rdf:langString
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.
rdf:langString
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, publié par Itiroo Sakai en 1961. 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 redécouvert 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.
rdf:langString
CYK法（英: CYK algorithm）は、ある文字列が与えられた文脈自由文法で生成できるかを決め、生成できる場合の生成方法を求めるアルゴリズムである。CYK は Cocke-Younger-Kasami の略（それぞれ、RISCの先駆と言われる801などでも知られるジョン・コック、Daniel Younger、嵩忠雄である）。文脈自由文法の構文解析手法と捉えることもできる。このアルゴリズムは一種の動的計画法である。 標準的なCYK法は、チョムスキー標準形で書かれた文脈自由文法で定義される言語を認識する。任意の文脈自由文法をチョムスキー標準形に書き換えるのはそれほど困難ではないので、CYK法は任意の文脈自由文法の認識に使うことができる。CYK法を拡張してチョムスキー標準形で書かれていない文脈自由文法を扱うようにすることも可能である。これにより性能は向上するが、アルゴリズムを理解することは難しくなる。 CYK法の最悪時間計算量は Θ(n3) であり、n は解析対象の文字列の長さである。従って、CYK法は任意の文脈自由言語を認識できる最も効率的なアルゴリズムの1つである。ただし、文脈自由言語の特定のサブセットについて、より効率の良いアルゴリズムが他に存在する。
rdf:langString
CYK 알고리즘(Cocke-Younger-Kasami 알고리즘, CYK Algorithm) 또는 CKY 알고리즘은 특정한 문자열에 대해, 그 문자열이 특정한 문맥 자유 문법에 속하는지를 판단하고, 또한 어떠한 방식으로 생성되는지를 판단하는 파싱 알고리즘이다. 이 알고리즘은 동적 계획법을 사용하며, 구조를 가지고 있다. 기본적으로 CYK 알고리즘에서는 으로 표현된 문맥 자유 문법을 사용하지만, 모든 문맥 자유 문법은 촘스키 정규 형식으로 변환이 가능하기 때문에 CYK 알고리즘을 사용할 수 있다. 문자열의 길이가 일 때, CYK 알고리즘은 Θ(n3)의 시간 복잡도를 가진다. 이것은 현재 모든 문맥 자유 문법을 파싱할 수 있는 가장 효율적인 알고리즘이다. (CYK 알고리즘보다 효율적으로 동작하는 몇몇 알고리즘이 있지만, 그 알고리즘은 특정한 문법의 경우에만 사용이 가능하다.)
rdf:langString
Het Cocke-Younger-Kasami (CYK)-algoritme (soms ook bekend als CKY) bepaalt of een string gegenereerd kan worden door een gegeven contextvrije grammatica en, als dit het geval is, levert het de manier waarop de string gegenereerd kan worden. Dit proces noemt men het parsen of ontleden van de string. Het algoritme is een voorbeeld van . De standaardversie van het CYK-algoritme herkent talen die gedefinieerd zijn door contextvrije grammatica's in Chomsky-normaalvorm. Aangezien elke contextvrije grammatica op eenvoudige wijze in deze normaalvorm om te zetten is, kan het CYK-algoritme 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. Zo'n uitbreiding maakt het algoritme meer performant, maar ook moeilijker om de werking te begrijpen. In het slechtste geval is de asymptotische tijdscomplexiteit van het CYK-algoritme Θ(n3), waar n de lengte van de geparseerde string is. Dit maakt het een 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, en .
rdf:langString
Algorytm CYK (Cocke’a-Youngera-Kasamiego) – dynamiczny algorytm sprawdzający, czy słowo należy do języka bezkontekstowego. Język bezkontekstowy musi być przedstawiony w postaci normalnej Chomsky’ego. Algorytm działa w czasie gdzie jest długością słowa, a jest rozmiarem gramatyki.
rdf:langString
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 . Isso o torna um dos algoritmos mais eficientes no reconhecimento geral de linguagens livres de contexto. Entretanto, algoritmos mais rápidos e especializados existem para certos subconjuntos de linguagens livres de contexto.
rdf:langString
Алгоритм Кока — Янгера — Касами (англ. Cocke — Younger — Kasami algorithm), алгоритм CYK либо CKY — алгоритм, позволяющий установить, можно ли в заданной контекстно-свободной грамматике вывести заданную строку, и если это так, то предоставить её вывод. Другими словами, это алгоритм синтаксического анализа строки. Алгоритм реализует синтаксический анализ снизу-вверх и основывается на методе динамического программирования. его открыватели: Джон Кок, Дэниел Янгер, Тадао Касами и Джейкоб Т. Шварц. Они использовали восходящий анализ и динамическое программирование. Стандартная версия CYK работает только с контекстно-свободными грамматиками, заданными в нормальной форме (CNF). Однако любая контекстно-свободная грамматика может быть преобразована (после конвертирования) в грамматику CNF, выражающую тот же язык (Sipser 1997). Является одним из самых эффективных алгоритмов синтаксического анализа с точки зрения асимптотической сложности в наихудшем случае, хотя существуют и другие алгоритмы с лучшим средним временем выполнения во многих практических сценариях.
rdf:langString
CYK算法（英語：Cocke–Younger–Kasami algorithm，縮寫為CYK algorithm）是由約翰·科克，Younger和共同研究出来大约发表于1965年的一个算法，它是一个用来判定任意给定的字符串 是否属于一个上下文无关文法的算法。普通的回溯法（backtracking）在最坏的情况下需要指数时间才能解决这样的问题，而CYK算法只需要多项式时间就够了（ ， n 为字符串 w 的长度）。CYK算法采用了动态规划的思想。 对于一个任意给定的上下文无关文法，都可以使用CYK算法来计算上述问题，但首先要将该文法转换成乔姆斯基范式。
xsd:nonNegativeInteger
17032
