Курсовая работа
ГЕНЕРАТОР ПСЕВДОТЕКСТОВ
Содержание
2. Алгоритмы генерации псевдотекстов
2.1. Генераторы, основанные на псевдослучайном выборе букв или слов
2.1.1. Генератор с равными вероятностями всех букв
2.1.2. Генератор с равными вероятностями всех слов
2.1.3. Генератор с различными вероятностями всех букв
2.1.4. Генератор с более сложным анализом вероятностей
2.2. Генератор, использующий SIMP-таблицы
3. Реализация алгоритмов генерации псевдотекстов
3.4. Генератор псевдотекста, анализирующий вероятность появления в тексте буквы после четырёх букв
3.5. Генератор псевдотекста с использованием SIMP-таблиц
1. Введение
В данной курсовой работе исследуются алгоритмы генерации псевдотекстов. Псевдотекст - это последовательность слов, пробелов и знаков препинания. Слова, из которых состоит псевдотекст, совсем необязательно существуют в реальном языке, так же как и сам псевдотекст может вовсе не иметь смысла. Псевдотексты играют огромную роль в жизни современного общества. Многие композиторы используют генераторы псевдотекстов для создания стихов к написанной ими музыке. Сама музыка также может быть сгенерирована подобными генераторами. Многие газетные и журнальные статьи тоже генерируются компьютерами. При этом используются профессиональные генераторы псевдотекстов, генерирующие текст, мало отличимый от текста, созданного человеком. В связи с вышесказанным, данная курсовая работа является очень актуальной.
Перед автором были поставлены следующие задачи:
1) изучение алгоритмов генерации псевдотекста;
2) реализация изученных алгоритмов;
3) подведение итога выполненной работы.
2. Алгоритмы генерации псевдотекстов
В ходе выполнения курсовой работы были исследованы некоторые алгоритмы генерации псевдотекстов. Они различаются как по сложности, так и по характеристикам псевдотекста, получаемого с их помощью. Генераторы псевдотекста можно условно разделить на две категории:
1) генераторы, генерирующие псевдотекст последовательно, элемент за элементом. В качестве элемента может выступать буква или слово. Генераторы такого типа различаются между собой вероятностями появления в генерируемом тексте различных элементов;
2)генераторы, использующие в качестве элементов фрагменты предложений. Эти фрагменты состоят из одного или более слов и разделяются пробелами.
2.1 Генераторы, основанные на псевдослучайном выборе букв или слов
В ходе выполнения курсовой работы были исследованы 4 алгоритма генерации псевдотекста, основанные на псевдослучайном выборе букв или слов.
2.1.1 Генератор с равными вероятностями всех букв
Можно создать генератор, генерирующий текст с равными вероятностями появления каждой буквы. Из заданного алфавита выбирается одна из букв и помещается в выходную строку. Затем выбирается следующая буква и тоже помещается в выходную строку. Процесс продолжается, пока не будет получен необходимый объём псевдотекста. Вероятности появления в сгенерированном тексте каждой буквы равны 1 / N, где N - размер алфавита. Пример текста (200 букв), сгенерированного генератором такого типа, приведён ниже. В качестве алфавита использовались строчные буквы русского алфавита и пробел.
гъ цчцёэпетйащадмп жжцъооойчшмккхойбфззбфмяджетёелшсфвры
сджйдгщпёмйщярыыуфщехфвщтаоёюхвбвншмьёжьгкманмсшюпхыжяяпдёчссвёншьшзоеюьмвцйвзюторйьэкзомбгежфмъхьгявмъыихёюькаыбаянсшоасуъжяыътъигзё во
2.1.2 Генератор с равными вероятностями всех слов
Аналогично можно построить генератор, который псевдослучайным образом, с одинаковой вероятностью, генерирует не буквы, а слова. Исходными данными для такого генератора является список используемых слов. Пример текста (20 слов), сгенерированного генератором такого типа, приведён ниже. В качестве словаря использовался словарь операционной системы Linux (/usr/dict/words, с русскими словами, объём словаря порядка 32000 слов).
Разберет раскололся раскрывшейся измеряя вкусами значительным отдернулась подано новом паслась двумя видевший доносил служила пивную сны вынул величавым невелики проснувшихся
2.1.3 Генератор с различными вероятностями всех букв
Для генерирования более качественного псевдотекста необходимо знать вероятности появления различных букв. Эти вероятности можно приближённо определить, взяв достаточно большой отрывок, написанный по-русски, и рассчитав для него относительные частоты отдельных букв. Строго говоря, эти частоты могут несколько зависеть от характера текста. Например, в учебнике по высшей математике частота обычно очень редкой буквы "ф" будет заметно выше средней из-за частого повторения слов "функция", "дифференциал", коэффициент" и некоторых других. Ещё больше отклонения от нормы в частоте употребления отдельных букв можно наблюдать в некоторых художественных произведениях, особенно в стихах. Поэтому для надёжного определения средней частоты появления буквы желательно иметь набор различных текстов, заимствованных из различных источников. Как правило, однако, подобные отклонения будут всё же сравнительно небольшими и в первом приближении ими можно пренебречь. Ориентировочные значения частот отдельных букв русского языка собраны в следующей таблице [4]:
пробел 0,175 | р 0,040 | я 0,018 | х 0,009
о 0,090 | в 0,038 | ы 0,016 | ж 0,007
е, ё 0,072 | л 0,035 | з 0,016 | ю 0,006
а 0,062 | к 0,028 | ь, ъ 0,014 | ш 0,006
и 0,062 | м 0,026 | б 0,014 | ц 0,004
т 0,053 | д 0,025 | г 0,013 | щ 0,003
н 0,053 | п 0,023 | ч 0,012 | э 0,003
с 0,045 | у 0,021 | й 0,010 | ф 0,002
Пример текста (200 букв), сгенерированного генератором, использующим данную таблицу, приведён ниже.
ырдаеноа бпевтбн нчиг нларв ибее лытоо м йиясаьнд вудьчч и онаонво морвмиуенунисмлепнп чы аа поырюпитлсиичо жиныгте г аачт чтврвнтдиу вьин иисатнхл нрсдмол лмноищатвпяоцоаав бф амдб иенждр жо леетй
Этот текст несколько более похож на русскую речь, чем текст, сгенерированный первым вариантом генератора. Здесь всё же наблюдается сравнительно правдоподобное распределение числа гласных и согласных и близкая к обычной средняя длина слова.
Собрав статистику использования различных слов в текстах на русском языке, можно было бы создать генератор, сочетающий в себе черты генераторов номер 2 и номер 3.
2.1.4 Генератор с более сложным анализом вероятностей
Несходство последнего приведённого текста с осмысленным текстом объясняется тем, что на самом деле последовательные буквы русского текста вовсе не независимы друг от друга. Так, например, если мы знаем, что очередной буквой явилась гласная, то значительно возрастает вероятность появления на следующем месте согласной буквы. Буква "ь" никак не может следовать ни за пробелом, ни за гласной буквой. За буквой "ч" никак не могут появиться буквы "ы", "я" или "ю", а скорее будет стоять одна из гласных "и" или "е" или согласная "т" (слово "что") и т.д. Для построения генератора псевдотекста, использующего приведённые выше факты, необходимо взять текст на русском языке и вычислить вероятности появления в нём всех двухбуквенных сочетаний. Каждое такое сочетание можно разделить на 2 части - первую букву и вторую букву. При фиксированной первой букве вероятности появления после неё второй буквы различны для различных букв алфавита. Этот факт и используется в алгоритме. Выбрав первую букву текста (можно произвольно, а можно и с учётом таблицы вероятностей), выбираем одно из двухбуквенных сочетаний, начинающихся с этой буквы. Это сочетание выбирается с учётом вероятности его появления в исходном тексте. Вторая его буква записывается в генерируемую строку и далее рассматриваются сочетания, начинающиеся с этой буквы. Данный процесс повторяется, пока сгенерированный текст не достигнет необходимого объёма. Генератор, использующий данный алгоритм, создаёт текст вроде этого:
стразределастванный ребно пребяза подру) получить дому непространия вату прого тщается чтольно вы усли ем, вышей Лицениванензие уведом, обязаннак одить илисполжными порсисходны вознает. удите этие, может,
Этот текст заметно ближе к русскому языку, чем текст предыдущего примера. Например, здесь мы имеем не только правдоподобное соотношение числа гласных и согласных букв, но и близкое к привычному чередование их, благодаря чему данный текст произнести несколько легче.
Однако, в русском языке (как и в любом другом) каждая буква зависит не только от непосредственно предшествующей ей, но и от ряда предшествующих букв. Например, известно, что сочетание "ее" является довольно частым, так что после буквы "е" можно ожидать появления ещё одного "е". Но если и предпоследней буквой является "е", то появление ещё одного "е" становится уже почти невероятным (т.к. сочетание "еее" встречается крайне редко). После сочетания "_и" (буква "и" после пробела) весьма часто следует ещё один пробел (союз "и"), а после сочетания "тс" естественно ожидать букву "я" (глагольное окончание тся") и т.д.
Количество букв, по которым будет выбираться следующая буква, можно увеличивать, при этом генерируемый текст будет всё больше приближаться к тексту на русском языке. Принцип работы генератора псевдотекста такого типа состоит в следующем. Достаточно большой отрывок текста на русском языке анализируется с целью подсчёта вероятностей появления каждой буквы после каждого n-буквенного сочетания. Далее случайным образом генерируются первые n букв. В соответствии с полученной статистикой выбирается следующая буква. По n последним буквам полученного текста генерируется следующая буква, и т.д. Генерация завершается, как только будет сгенерировано необходимое число букв. Как и в случае с предыдущими генераторами, вместо букв можно использовать слова, предварительно вычислив вероятности появления каждого слова после каждых n слов.
2.2 Генератор, использующий SIMP-таблицы
Фирмой "Хониуэлл Иннкорпорейтед" разработан генератор псевдотекста, использующий 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. Библиография
Гарднер, М. Путешествие во времени / М. Гарднер. – М.: Мир, 1990. – 341 с., ил.
Гасфилд, Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология / Пер. с англ. И. В. Романовского. – СПб.: Невский диалект; БХВ-Петербург, 2003. – 654 с.: ил.
Керниган, Б. Язык программирования С, 2-е издание / Б. Керниган, Д. Ритчи. – М.: Издательский дом “Вильямс”, 2006. – 304 с.: ил.
Яглом, А. Вероятность и информация / А.М. Яглом, И.М. Яглом. – М.: Наука, 1973. – 512с.: ил.