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

Я хотел бы реализовать Алгоритм CYK в C / C ++, но доступный на различных сайтах псевдокод не дает ответа на вопрос, как эффективно его реализовать. Я написал версию, которая использует некоторые структуры stl, такие как map и sets, но она очень медленная. Я думал об улучшении моей реализации, используя только двоичные операции, но я не знаю, как хранить мою таблицу с наборами. Допустим, у нас есть только 8 символов для нетерминалов и 26 для терминалов. Я думал об использовании таблицы знаков без знака (2 ^ 8 -> 8 позиций для 0-1) для хранения информации о продукции, но я не знаю, как ее хранить.

Не могли бы вы дать мне помощь или подсказку?

3

Решение

Вы не предоставляете много деталей, простая реализация (даже псевдокод) может сильно помочь вам дать подсказки.

Из википедии:

пусть на входе будет строка S, состоящая из n символов: a1 … an. позволять

для этого вы можете использовать простую строку или вектор символов

грамматика содержит r нетерминальных символов R1 … Rr.

Я хотел бы хранить нетерминальные символы в массиве bools
std :: array nonterminal {};
тогда, поскольку у вас есть символы, вы можете инициализировать позицию, соответствующую символу, с помощью true.

нетерминальный [static_cast (‘C’)] = true;
вы делаете то же самое с терминалом, и у вас есть действительно быстрый механизм поиска.

Эта грамматика
содержит подмножество Rs, которое является набором начальных символов. пусть P [n, n, r] быть массивом логических значений. Инициализируйте все элементы P в false. за
каждый i = 1 до n для каждой единицы продукции Rj -> ai
установить P [i, 1, j] = true для каждого i = 2 до n — длина диапазона для каждого j = 1 до n-i + 1 — начало диапазона
для каждого k = 1 до i-1 — разделение диапазона
для каждого производства РА -> РБ РЦ
если P [j, k, B] и P [j + k, ik, C], тогда установить P [j, i, A] = true, если любой из P [1, n, x] равен true (x повторяется по множество s, где s все
индексы для Rs) тогда S является членом языка, иначе S не является членом
языка

Алгоритм кажется довольно простым после этого. Просто следите за тем, чтобы не инициализировать временные значения внутри замкнутых циклов, и все будет в порядке.

0

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector