Cтраница 4
Производящая функция, рассматриваемая как цельный объект, может обладать такими свойствами, которые трудно и противоестественно записать в терминах отдельных коэффициентов ряда и которые даже совсем не имеют места для отдельно взятого коэффициента. Этим объясняется кажущийся парадокс: ряд задач на подсчет удается решить только после вышеупомянутого усложнения их постановки. Общий подход к нахождению считающих рядов и их производящих функций был впервые предложен Пойя [180]; сам автор применил свою основную теорему для подсчета количества неизоморфных деревьев с заданным числом вершин и выделенной вершиной ( корнем), а также для определения количества изомеров у некоторых химических соединений. Подробное изложение теоремы Пойя и разнообразных ее применений имеется в книге Риордана [52], однако для первого ознакомления мы рекомендуем статью Харари [133], в которой без введения большого числа понятий даются формулировка этой теоремы и ее непосредственные приложения, такие как подсчет графов и диграфов ( направленных графов) с заданными количествами вершин и ребер, подсчет связных графов и некоторых взвешенных графов. Из работ этого направления, появившихся в период между выходом оригинала книги Риордана ( 1958 г.) и 1962 годом, отметим работу Рида [185, 186]; доказанная им теорема суперпозиции позволяет значительно расширить сферу применимости теоремы Пойя, например, дает возможность подсчитывать количество неизоморфных графов с заданными степенями вершин. [46]
Процесс кодирования текста подобен процедуре построения словаря. На каждом этапе головная часть входного текста проверяется на совпадение в возможно большем числе позиций с гнездами словаря. Совпавшая цепочка заменяется в тексте соответствующим кодирующим диграфом, и начало просмотра входного текста сдвигается на длину выделенной цепочки. Если же в словаре не найдено нужного гнезда, в выходной текст просто переносится первая литера из головной части входного текста и начало просмотра перемещается вправо на одну позицию. Декодирование осуществляется путем простой замены кодирующих диграфов их эквивалентами из словаря. [47]
Как только построение словаря завершилось, необходимо составить таблицы для кодирования и декодирования. Образуем все возможные диграфы, начинающиеся с литеры, которая нигде в тексте не используется. Поставим в соответствие гнездам словаря полученные выше кодирующие диграфы, начиная с гнезд, имеющих наибольшую частоту. Формирование таблицы кодировок завершается по исчерпании гнезд словаря или набора диграфов. [48]