Курсовая работа
ГЕНЕРАТОР ПСЕВДОТЕКСТОВ
Содержание
1. Введение
2. Алгоритмы генерации псевдотекстов
2.1. Генераторы, основанные на псевдослучайном выборе букв или слов
2.1.1. Генератор с равными вероятностями всех букв
2.1.2. Генератор с равными вероятностями всех слов
2.1.3. Генератор с различными вероятностями всех букв
2.1.4. Генератор с более сложным анализом вероятностей
2.2. Генератор, использующий SIMP-таблицы
3. Реализация алгоритмов генерации псевдотекстов
3.1. Генератор псевдотекста со случайным выбором букв безучёта вероятностей их появления в текстах на русском языке
3.2. Генератор псевдотекста со случайным выбором слов безучёта вероятностей их появления втекстах на русскомязыке
3.3. Генератор псевдотекста со случайным выбором букв сучётом вероятностей их появления в текстах на русском языке
3.4. Генератор псевдотекста,анализирующий вероятность появления в тексте буквы после четырёх букв
3.5. Генератор псевдотекста с использованием SIMP-таблиц
4. Заключение
5. Библиография
/>/>/>/>/>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
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
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
str = str c
++n
}
}
for (i = 0; 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
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
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
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с.:ил.