Описание тега cyk

Вопросы с тегом
Алгоритм CYK - это эффективный алгоритм для определения того, находится ли строка на языке, созданном с помощью контекстно-свободной грамматики. Он использует динамическое программирование и является самым быстрым, когда входная грамматика имеет нормальную форму Хомского.
1 ответ

Шаги для генерации дерева разбора из алгоритма CYK (обработка естественного языка)

В настоящее время я работаю над проектом с участием НЛП. Я реализовал идентификатор CKY, указанный в Jurafsky and Martin (алгоритм на стр. 450). Созданная таблица фактически хранит нетерминалы в таблице (вместо обычных логических значений). Однако е…
14 ноя '15 в 06:48
1 ответ

Дополнительные ветви добавляются в дерево при генерации

Я реализовал алгоритм синтаксического анализа CYK, который использует подход "снизу вверх" для построения дерева разбора. При прохождении алгоритма путь к окончательному решению сохраняется в обратных указателях. Из обратных указателей мы строим дер…
07 июн '17 в 04:18
1 ответ

Не может понять псевдокод алгоритма CYK

Я читал об алгоритме CYK, и есть одна часть псевдокода, которую я не могу понять. Весь псевдокод: let the input be a string S consisting of n characters: a1 ... an. let the grammar contain r nonterminal symbols R1 ... Rr. This grammar contains the s…
15 апр '13 в 01:04
2 ответа

CYK алгоритм путаницы псевдокодов

Так что я читал об алгоритме CYK в википедии и во многих powerpoints/pdfs. В википедии есть часть, где я не на 100% говорю то, что пытаюсь сказать. Можете ли вы, ребята, сломать это для меня? let the input be a string S consisting of n characters: a…
05 фев '13 в 09:49
2 ответа

Как производить продукты на столе CYK в прологе?

Мы используем концепцию формирования таблицы CYK для получения этих результатов на Прологе. Вот некоторые примеры выходных данных для product_c(+Cell1, + ​​Cell2, -Product): ?- product_c(["A","B"],["C","D"],What). What = ["AC", "AD", "BC", "BD"]. ?-…
01 мар '18 в 13:18
1 ответ

Как ускорить алгоритм CYK в C++?

Я хотел бы реализовать алгоритм CYK в C/C++, но доступный на различных веб-сайтах псевдокод не дает ответа на вопрос, как эффективно его реализовать. Я написал версию, которая использует некоторые структуры stl, такие как map и sets, но она очень ме…
05 апр '13 в 18:15
1 ответ

Простой парсер CFG с эпсилон-переходом

Я наткнулся на множество различных алгоритмов (CYK и Earley), чтобы проверить, является ли строка частью CFL, чей CFG предоставляется. Я ищу что-то простое для понимания и реализации. То, что мне нужно знать, это если строка находится в CFG или нет.…
01 апр '13 в 03:07
3 ответа

Произведение из 2 списков в ocaml без императивных функций

ERS, Я пытаюсь научиться функциональному программированию с помощью таблиц ocaml и CYK, поэтому нет List.mem или каких-либо императивных функций в этом отношении. Моя цель - сформировать произведение из 2 клеток. Вот что у меня сейчас есть: let stri…
07 апр '18 в 22:59
1 ответ

Как реализовать эпсилон-переход?

В настоящее время я пытаюсь внедрить CYK с эпсилон-переходом. Как предоставленный алгоритм обрабатывает эпсилон-переходы? Если нет, то как вы собираетесь это осуществить? (Я использую Java)
16 апр '13 в 00:11
1 ответ

Реализация алгоритма CYK Java

Я пытаюсь реализовать алгоритм CYK на основе псевдокода Википедии. Когда я проверяю строку "a b" для ввода грамматики: S-> AB A-> а В-> б Это дает мне ложь, и я думаю, что это должно быть правдой. У меня есть arraylist под названием AllGrammar, кото…
06 апр '14 в 14:03
1 ответ

Правила грамматики CYK (Cocke-Younger-Kasami)

Я заинтересован в синтаксическом анализе естественного языка и написал Brill Part of Speech Tagger, и хотел бы улучшить его, объединив его с POS-тегом, основанным на грамматических правилах. Кто-нибудь знает где-нибудь файлы с открытым исходным кодо…
06 май '12 в 13:23
0 ответов

Python - Как реализовать детерминированный алгоритм CYK без NLTK

ПРИМЕЧАНИЕ. Для этого вопроса я не могу использовать импорт, кроме io и sys. Для задания НЛП я должен создать программу, которая принимает файл грамматики и файл высказываний в качестве системных аргументов, что я и сделал. Проблема в том, что я так…
03 ноя '16 в 18:24
0 ответов

CYK алгоритм сверху вниз с памяткой

Я запускаю алгоритм CYK, однако, я пытаюсь сделать это как нисходящий дизайн (памятка), любая помощь? bool canDerive(nonterminal S, string w) { return canDeriveRec(S, w, 0, w.size()); } /* Can you derive the substring [start, end) of w from S? */ bo…
19 сен '17 в 08:55
0 ответов

Узкое место в моем рекурсивном коде Python

Я написал код ниже, используя рекурсию для выполнения алгоритма CYK, чтобы грамматика G может генерировать любые слова, имеющие одинаковое количество aсопровождается любым количеством bНо почему-то это очень медленно, не знаете почему? Когда я испол…
21 окт '17 в 15:35
0 ответов

Показать / нарисовать дерево CYK без библиотеки

Я реализовал алгоритм CYK. Пример: вход: она ест рыбу вилкой Вывод: S[NP.She VP[VP[V.eats NP[Дет.а N.fish]] PP[P.with NP[Дет.а N.fork]]]] Как я могу отобразить этот вывод в виде двоичного дерева? Спасибо! Могу ли я использовать дерево выражений?
07 ноя '18 в 08:56
0 ответов

CYK построить дерево разбора из таблицы

Как построить дерево синтаксического анализа после получения таблицы CYK? Я не понял, что пытается сказать Википедия.Пример: A - C A - B B,D C,F E B,D Как мне вернуть список правил, применяемых для перехода от A к BCED (или любой другой комбинации б…
25 ноя '16 в 18:23
0 ответов

CYK не дает ожидаемого ответа

Я реализовал алгоритм CYK для проверки входной строки с заданной грамматикой.И если у меня есть следующая грамматика S->AB|BC A->BA|a B->CC|b C->AB|a и если я проверю строку ab алгоритм говорит, что это в грамматике. Но если у меня есть …
21 апр '14 в 14:21
0 ответов

Как применить CYK или любой другой алгоритм разбора без изменения моей грамматики?

Таким образом, у меня есть грамматика внутри одномерного массива, заданного формой struct array { char left; char right[3]; char number; } Пример: array.left = 'A'; array.right = "BC"; array.number = insert_some_conventional_null_character_here Это …
23 ноя '16 в 11:15
2 ответа

Является ли этот результат синтаксического анализатора CYK правильным?

Я пытаюсь изучить алгоритм разбора CYK. Для этого набора правил грамматики правильны ли получающиеся таблицы для двух данных предложений? S -> NP VP VP -> VB NP NP -> DT NN PP -> IN NP NP -> NP PP NP -> NN VP -> VP PP IN -> w…
22 май '12 в 10:32
1 ответ

Извлечение вероятностей и наиболее вероятного разбора дерева из Cyk

Чтобы понять алгоритм cyk, я проработал пример на: https://www.youtube.com/watch?v=VTH1k-xiswM&feature;=youtu.be. Результатом чего является: Как извлечь вероятности, связанные с каждым разбором, и извлечь наиболее вероятное дерево разбора?
11 май '18 в 18:16