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

Question

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

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

Answer 1

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

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

пусть на входе будет строка 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 - Разделение диапазона для каждого производства RA -> RB RC, если P[j,k,B] и P[j+k,ik,C], затем установить P[j,i,A] = true, если любое из P[1,n,x] истинно (x итерируется по множеству s, где s все индексы для Rs), тогда S является членом языка, иначе S не является членом языка

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