Cтраница 2
Какие из следующих бесконечных префиксных кодов являются тупиковыми. [16]
Следствие 3.3. Если префиксный код Се Л неразложим, то 91 ( С) не имеет собственных конгруэнции. [17]
Ясно, что префиксный код является разделимым. Заметим, что если каждое слово префиксного кода заменить наименьшим его началом, которое не является началом других кодовых слов, то полученный код также будет префиксным. [18]
Прямой метод построения префиксного кода W, в котором длина кодового слова, соответствующего а, не более чем на единицу превышает ( 7), состоит в следующем. Нумеруются ( начиная с 0) частотные классы и слова, принадлежащие одному и тому же частотному классу. [19]
Ниже показано, что префиксный код, сохраняющий порядок, имеет ненамного большую избыточность, чем код Шеннона. [20]
Следствие 3.7. Пусть С - неполный префиксный код и С Cv - Сц - его максимальное разложение. Группа G ( C) подобна группе G ( C) полного кода О, а группа 0 ( СЦ) тривиальна. [21]
Преобразования 1 и 2 позволяют любой префиксный код из рассматриваемого класса, в том числе и код с минимальной избыточностью, привести к коду, дерево которого является насыщенным, не увеличивая при этом избыточность. [22]
Найти общее правило для построения префиксных кодов с минимальной средней длиной при указанном ограничении и объяснить, почему оно работает. [23]
Это вытекает из одного свойства рациональных префиксных кодов с конечной задержкой синхронизации ( следствие 2.14), достаточно замечательного, чтобы быть доказанным независимо. [24]
Слова fw ( a) образуют префиксный код. [25]
Для любой конечной полугруппы S существует конечный префиксный код С, эффективно вычислимый по S, такой, что ( 1) 5 делит синтаксическую полугруппу S ( C) полугруппы С; ( 2) S и S ( C) имеют одну и ту же групповую сложность. [26]
Если С s / 4 - конечный префиксный код, то все подгруппы синтаксического моноида М ( С) тривиальны в силу теоремы 1.5 из гл. Однако моноид М ( С) имеет, вообще говоря, нетривиальные подгруппы. Так как минимальный автомат, распознающий С, легко получается из С ( гл. Далее, как показывает теорема 2.12 из гл. Важно сразу отметить, что конечность кода С - это ключевое ограничение. [27]
При этом, очевидно, для любых префиксных кодов, в том числе и для бесконечных, из первого условия следует второе, а из второго - третье. [28]
Предложение 2.11. Если Р s X - префиксный код с конечной задержкой синхронизации, и а: Х - & ( А) - замещение, то а ( Р) - также префиксный код с конечной задержкой синхронизации. [29]
Тогда можно показать, что Р - префиксный код и что его пополнение Р, ( т.е. наименьший полный префиксный код, содержащий Р) таково, что 91 ( Р) моделирует Я. Более совершенная конструкция позволяет в некоторых случаях выполнить моделирование, используя конечные префиксные коды, синтаксические моноиды которых лежат в том же псевдомиогообразии, что и моноид переходов исходного автомата Я. [30]