Грамматика прямой линии

Прямолинейная грамматика ( иногда сокращенно SLG) — это формальная грамматика , которая генерирует ровно одну строку. ^[1] Следовательно, она не разветвляется (каждый нетерминал имеет только одно связанное с ним правило вывода) и не зацикливается (если нетерминал A появляется в выводе B , то B не появляется в выводе A ). ^[1]

Области применения

Прямолинейные грамматики широко используются при разработке алгоритмов, которые выполняются непосредственно на сжатых структурах (без предварительной декомпрессии). ^[2]^{: 212}

SLG представляют интерес в таких областях, как сложность Колмогорова , сжатие данных без потерь , обнаружение структур и сжатые структуры данных . ^{[ требуется разъяснение ]}

Задача поиска контекстно-свободной грамматики (эквивалентно: SLG) минимального размера, которая генерирует заданную строку, называется наименьшей грамматической задачей . ^{[ необходима цитата ]}

Прямые грамматики (точнее: прямые контекстно-свободные строковые грамматики) могут быть обобщены до прямых контекстно-свободных древовидных грамматик . Последние могут быть удобно использованы для сжатия деревьев . ^[2]^{: 212}

Формальное определение

Контекстно -свободная грамматика G является SLG, если:

1. для каждого нетерминала N существует не более одного правила продукций, в левой части которого находится N , и

2. ориентированный граф G =< V , E >, определяемый тем, что V — множество нетерминалов, а ( A , B ) ∈ E всякий раз, когда B появляется в правой части правила продукции для A , является ациклическим .

Математическое определение более общего формализма прямолинейных контекстно-свободных древовидных грамматик можно найти в работе Лори и др. ^[2]^{: 215}

SLG в нормальной форме Хомского эквивалентен прямолинейной программе . ^{[ требуется ссылка ]}

Список алгоритмов, использующих SLG

Алгоритм Sequitur строит прямолинейную грамматику для заданной строки.
Алгоритм Лемпеля-Зива-Уэлча создает контекстно-свободную грамматику настолько детерминированным образом, что необходимо хранить только начальное правило сгенерированной грамматики.
Кодирование пар байтов

Смотрите также

Грамматический код – алгоритм сжатия данных без потерь
Нерекурсивная грамматика — грамматика, которая не образует циклов, но может разветвляться; порождает конечный, а не одноэлементный язык.

Ссылки

^ ab Флориан Бенц и Тимо Кётцинг, «Эффективная эвристика для наименьшей грамматической проблемы», Труды пятнадцатой ежегодной конференции по генетическим и эволюционным вычислениям - GECCO '13, 2013. ISBN 978-1-4503-1963-8 doi :10.1145/2463372.2463441, стр. 488
^ abc Маркус Лорей; Себастьян Манет; Манфред Шмидт-Шаус (2009). «Сокращение параметров в сжатых грамматикой деревьях». Proc. FOSSACS (PDF) . LNCS. Том 5504. Springer. стр. 212–226.