Фирмой "Хониуэлл Иннкорпорейтед" разработан генератор псевдотекста, использующий SIMP-таблицы (Simplified Integrated Modular Prose - упрощённая интегрированная модульная проза). Данный генератор позволяет генерировать общеупотребительные псевдонаучные фразы. Его работа основана на генерации случайного четырёхзначного числа и выборке из четырёх SIMP-таблиц [1] соответствующих частей предложения. Например, если сгенерировано число 3672, а таблицы имеют следующий вид

Таблица A

1. В частности

2. С другой стороны,

3. Однако

4. Аналогично,

5. Таким образом

6. Нетрудно видеть, что

7. Как показывают приведённые выше соображения,

8. Например,

9. Итак,

0. Что касается нашей конкретной задачи, то

Таблица B

1. гиперповерхность в пространстве состояний

2. постоянный поток эффективной информации

3. отличительная особенность выбранных критериев

4. инициация развития критической подсистемы

5. комплексная программа испытаний

6. траектория в конфигурационном пространстве

7. нагруженный несущий элемент

8. включение дополнительных внутренних связей

9. независимый принцип функционирования

0. первичное отношение между подсистемой и технологией подсистемы

Таблица C

1. находит широкое применение и требует

2. сводит до минимума затраты при условии

3. указывает на пределы применимости

4. свидетельствует о необходимости более тщательного анализа

5. чрезвычайно усложняется, если не принять во внимание условие

6. подразумевает более основательное использование теории

7. открывает весьма интересные перспективы

8. признаёт значимость других систем и необходимость

9. позволяет эффективно использовать

0. требует применения

Таблица D

1. более тонкой аппаратурной реализации.

2. оборудования четвёртого поколения.

3. тестирования четвёртого поколения.

4. проектирования на основе системного подхода.

5. предварительного отбора данных по определённым критериям.

6. гибкого, изменяющегося в зависимости от условий, описания.

7. интеграции и специализации.

8. более строгой стандартизации основных модулей.

9. функционирования в режиме дискретного времени.

0. разветвления сети сопровождения и поддержки.

Результатом работы данного генератора станет предложение "Однако траектория в конфигурационном пространстве открывает весьма интересные перспективы функционирования в режиме дискретного времени". Добавив ещё несколько четырёхзначных чисел, можно получить целый абзац на языке SIMP. Генератор можно немного модифицировать, расположив таблицы в другом порядке, например DACB, BACD или ADCB. Возможно, у некоторых слов придётся изменить окончания.

3. Реализация алгоритмов генерации псевдотекстов

В процессе выполнения данной курсовой работы были реализованы некоторые алгоритмы генерации псевдотекстов. В качестве языка реализации был выбран AWK. Причинами такого выбора явились:

1) приспособленность AWKа к обработке текстовой информации;

2) сложность реализации некоторых алгоритмов на C, Pascal или другом общем языке программирования;

3) наличие у автора курсовой работы качественной реализации интерпретатора данного языка.

AWK представляет собой язык, предназначенный для обработки текстовой информации. Программа на AWKе состоит из пар шаблон-действие. Действие заключается в фигурные скобки. Каждая строка входного файла сопоставляется с каждым шаблоном; если обнаружено соответствие, то выполняется соответствующее действие. Если шаблон не указан, то действие выполняется для каждой входной строки. Если не указано действие, то строка выводится на стандартный вывод. Шаблон BEGIN распознаётся перед началом чтения файла, шаблон END - после его окончания. Текущая входная строка находится в переменной $0. Все массивы в AWKе - ассоциативные, размерности 1. Индексироваться массивы могут как одним значением (напр. x[2], q["abc"]), так и несколькими, что используется для эмуляции многомерных массивов (напр. y[1,2,3], f["2",6]). Большинство операций заимствовано из Си. Кроме того, есть операция конкатенации строк - a = b c. Строки b и c конкатенируются, и результат помещается в a. AWK имеет операторы for и if, аналогичные соответствующим операторам языка Си [3]. У оператора for также имеется форма for (i in array) operator, при этом operator выполняется для i, принимающего последовательно значения всех индексов массива array. Порядок перебора элементов не определён. В приведённых ниже программах использованы следующие встроенные функции AWKа:

1) srand() - инициализирует генератор псевдослучайных чисел текущим временем;

2) int(expr) - возвращает целую часть выражения expr;

3) rand() - возвращает случайное число в диапазоне от 0 до 1;

4) length(str) - возвращает длину строки str;

5) printf(...) - аналогична одноимённой функции ANSI C;

6) substr(str, i, n) - возвращает подстроку строки str, начиная с i-го символа, длиной не больше n символов;

7) exit - завершает выполнение программы.

Комментарии начинаются со знака "#" и продолжаются до конца строки.

3.1 Генератор псевдотекста со случайным выбором букв без учёта вероятностей их появления в текстах на русском языке

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

#----------------------------------------------------------------

# Программа 1. Генератор псевдотекста со случайным выбором букв

# без учёта вероятностей их появления в текстах на русском языке.

#---------------------------------------------------------------

BEGIN {

srand ()

str = "абвгдеёжзийклмнопрстуфхцчшщъыьэюя "

for (i = 0; i < 200; ++i) {

ind = int (rand () * length (str)) + 1

printf ("%c", substr (str, ind, 1))

}

}

3.2 Генератор псевдотекста со случайным выбором слов без учёта вероятностей их появления в текстах на русском языке

Данный генератор содержит массив words, в который добавляется каждое слово, прочитанное из словаря. Словарь представляет собой текстовый файл, каждая строка которого содержит одно слово. Слова не повторяются. После того, как весь файл будет прочитан, переменная n содержит количество слов, содержащихся в массиве words. Далее в цикле выводятся случайно выбранные слова, разделённые пробелами.

#----------------------------------------------------------------

# Программа 2. Генератор псевдотекста со случайным выбором слов

# без учёта вероятностей их появления в текстах на русском языке.

# Запуск: gawk -f prog3.awk words.txt

#----------------------------------------------------------------

{

words[++n] = $0

}

END {

srand ()

for (i = 0; i < 20; ++i)

printf ("%s ", words[int (rand () * n + 1)])

}

3.3 Генератор псевдотекста со случайным выбором букв с учётом вероятностей их появления в текстах на русском языке

Данная программа отличается от Программы 2 тем, что строка str не задана явно, а генерируется в процессе выполнения на основе статистических данных. Массив freq для каждой буквы содержит её относительную частоту появления в тексте, умноженную на 1000. Строка str изначально пуста, но затем в цикле к ней добавляются буквы. Каждая буква записывается в str столько раз, какого значение соответствующего элемента массива freq. В переменной n накапливается длина строки. Затем, как и в Программе 2, из str случайно выбираются и выводятся 200 букв.

#---------------------------------------------------------------

# Программа 3. Генератор псевдотекста со случайным выбором букв

# с учётом вероятностей их появления в текстах на русском языке.

#---------------------------------------------------------------

BEGIN {

srand ()

freq[" "] = 175; freq["я"] = 18;

freq["о"] = 90; freq["ы"] = 16;

freq["е"] = 72; freq["з"] = 16;

freq["а"] = 62; freq["ь"] = 14;

freq["и"] = 62; freq["б"] = 14;

freq["т"] = 53; freq["г"] = 13;

freq["н"] = 53; freq["ч"] = 12;

freq["с"] = 45; freq["й"] = 10;

freq["р"] = 40; freq["х"] = 9;

freq["в"] = 38; freq["ж"] = 7;

freq["л"] = 35; freq["ю"] = 6;

freq["к"] = 28; freq["ш"] = 6;

freq["м"] = 26; freq["ц"] = 4;

freq["д"] = 25; freq["щ"] = 3;

freq["п"] = 23; freq["э"] = 3;

freq["у"] = 21; freq["ф"] = 2;

for (c in freq) {

for (i = 0; i < freq[c]; ++i) {

str = str c

++n

}

}

for (i = 0; i < 200; ++i) {

ind = int (rand () * n) + 1

printf ("%c", substr (str, ind, 1))

}

}

3.4 Генератор псевдотекста, анализирующий вероятность появления в тексте буквы после четырёх букв

В данной программе для хранения четырёх текущих букв используются переменные c0, c1, c2, c3. Каждый элемент массива nsuffix является количеством суффиксов (букв, следующих за четырьмя данными буквами), соответствующих данным четырём буквам, которые являются индексами этого массива. Сами суффиксы хранятся в массиве ststetab - первый суффикс, соответствующий данным четырём буквам c0, c1, c2, c3, хранится в statetab[c0,c1,c2,c3,1], второй - в statetab[c0,c1,c2,c3,2], и т.д. В основной секции программы каждая строка входного файла разбивается на буквы, которые записываются в соответствующие элементы массива statetab. Собственно генерация происходит после того, как весь файл будет прочитан, в секции END.

Начальные значения текущих четырёх букв одинаковы и равны EOL. В цикле при каждой итерации выбирается случайная буква, соответствующая текущим, и если она не является концом строки, она выводится на стандартный вывод, в противном случае программа завершается. Далее происходит сдвиг текущих букв, и только что выведенная буква становится последней буквой этой цепочки. Эти действия повторяются, пока не будет выведено необходимое число букв.

#----------------------------------------------------------------

# Программа 4. Генератор псевдотекста, анализирующий вероятность

# появления в тексте буквы после четырёх букв.

# Запуск: gawk -f prog4.awk textfile.txt

#----------------------------------------------------------------

BEGIN {

MAXGEN = 200

EOL = "\n"

c0 = c1 = c2 = c3 = EOL

}

{

for (i = 1; i <= length($0); i++) {

c = substr ($0, i, 1)

statetab[c0,c1,c2,c3,++nsuffix[c0,c1,c2,c3]] = c

c0 = c1

c1 = c2

c2 = c3

c3 = c

}

}

END {

srand ()

statetab[c0,c1,c2,c3,++nsuffix[c0,c1,c2,c3]] = EOL

c0 = c1 = c2 = c3 = EOL

for (i = 0; i < MAXGEN; i++) {

r = int (rand () * nsuffix[c0,c1,c2,c3]) + 1

p = statetab[c0,c1,c2,c3,r]

if (p == EOL) {

exit

}

printf ("%c", p)

c0 = c1

c1 = c2

c2 = c3

c3 = p

}

}

3.5 Генератор псевдотекста с использованием SIMP-таблиц

В данной программе массив a содержит строки таблицы A, массив b - строки таблицы B, и т.д. После инициализации массивов инициализируется генератор псевдослучайных чисел. В цикле генерируются 4 случайных числа - индексы массивов, и соответствующие строки выводятся на стандартный вывод.

#---------------------------------------------------------------

# Программа 5. Генератор псевдотекста с использованием

# SIMP-таблиц.

#---------------------------------------------------------------

BEGIN {

a[1] = "В частности "

a[2] = "С другой стороны, "

a[3] = "Однако "

a[4] = "Аналогично, "

a[5] = "Таким образом "

a[6] = "Нетрудно видеть, что "

a[7] = "Как показывают приведённые выше соображения, "

a[8] = "Например, "

a[9] = "Итак, "

a[0] = "Что касается нашей конкретной задачи, то "

b[1] = "гиперповерхность в пространстве состояний "

b[2] = "постоянный поток эффективной информации "

b[3] = "отличительная особенность выбранных критериев "

b[4] = "инициация развития критической подсистемы "

b[5] = "комплексная программа испытаний "

b[6] = "траектория в конфигурационном пространстве "

b[7] = "нагруженный несущий элемент "

b[8] = "включение дополнительных внутренних связей "

b[9] = "независимый принцип функционирования "

b[0] = "первичное отношение между подсистемой и технологией подсистемы "

c[1] = "находит широкое применение и требует "

c[2] = "сводит до минимума затраты при условии "

c[3] = "указывает на пределы применимости "

c[4] = "свидетельствует о необходимости более тщательного анализа "

c[5] = "чрезвычайно усложняется, если не принять во внимание условие"

c[6] = "подразумевает более основательное использование теории "

c[7] = "открывает весьма интересные перспективы "

c[8] = "признаёт значимость других систем и необходимость "

c[9] = "позволяет эффективно использовать "

c[0] = "требует применения "

d[1] = "более тонкой аппаратурной реализации."

d[2] = "оборудования четвёртого поколения."

d[3] = "тестирования четвёртого поколения."

d[4] = "проектирования на основе системного подхода."

d[5] = "предварительного отбора данных по определённым критериям."

d[6] = "гибкого, изменяющегося в зависимости от условий, описания."

d[7] = "интеграции и специализации."

d[8] = "более строгой стандартизации основных модулей."

d[9] = "функционирования в режиме дискретного времени."

d[0] = "разветвления сети сопровождения и поддержки."

srand ()

for (i = 0; i < 10; ++i) {

printf ("%s%s%s%s\n",

a[int (rand () * 10)],

b[int (rand () * 10)],

c[int (rand () * 10)],

d[int (rand () * 10)])

}

}

4. Заключение

Итогом данной курсовой работы стали 5 различных генераторов псевдотекстов. Эти генераторы были протестированы и отлажены на большом количестве входных данных. Результаты их работы свидетельствуют о достижении автором поставленных целей. В процессе её выполнения автором были более глубоко изучены алгоритмы генерации псевдотекстов и накоплен опыт в построении и реализации данных алгоритмов. Также внимание автора было уделено изучению теории вероятности, некоторых аспектов языка AWK, значительного количества разнообразных русскоязычных текстов. Все трудности, возникшие в ходе выполнения курсовой работы, были успешно преодолены, а полученные результаты могут быть использованы при создании генераторов псевдотекстов, не уступающих генераторам таких известных корпораций, как Microsoft, IBM, Symantec, Adobe.

5. Библиография

1. Гарднер, М. Путешествие во времени / М. Гарднер. - М.: Мир, 1990. - 341 с., ил.

2. Гасфилд, Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология / Пер. с англ. И. В. Романовского. - СПб.: Невский диалект; БХВ-Петербург, 2003. - 654 с.: ил.

3. Керниган, Б. Язык программирования С, 2-е издание / Б. Керниган, Д. Ритчи. - М.: Издательский дом “Вильямс”, 2006. - 304 с.: ил.

4. Яглом, А. Вероятность и информация / А.М. Яглом, И.М. Яглом. - М.: Наука, 1973. - 512с.: ил.