Предложен новый метод нумерации последовательностей, порожденных источником Маркова. Нумеруются равновероятные последовательности фиксированной длины. Предполагается, что известна память источника, но не известны переходные вероятности. Ранее известные методы имеют экспоненциальную сложность с ростом длины последовательности, числа состояний и памяти источника, что делает их неприменимыми на практике. Последний результат в этой области описывает нумерацию для источника Маркова над алфавитом {0, 1} и памяти, равной одному. Описанный в работе метод имеет сложность, эквивалентную сложности нумерации источника Бернулли, описанному в работе Рябко Б.Я., и может быть применен для сжатия информации. Метод также применим в идеальной стеганографической системе, описанной в работе Рябко Б.Я. и Рябко Д.Б.
Основная идея метода заключается в том, что нумеруется не всё множество равновероятных последовательностей, а его подмножества. С ростом длины последовательностей количество таких подмножеств остается постоянным, что делает метод асимптотически оптимальным.
Abstracts file: | Monarev.doc |
Full text file: | monarevVA.pdf |