22
Курсовая работа
ГЕНЕРАТОР ПСЕВДОТЕКСТОВ
Содержание
В данной курсовой работе исследуются алгоритмы генерации псевдотекстов. Псевдотекст - это последовательность слов, пробелов и знаков препинания. Слова, из которых состоит псевдотекст, совсем необязательно существуют в реальном языке, так же как и сам псевдотекст может вовсе не иметь смысла. Псевдотексты играют огромную роль в жизни современного общества. Многие композиторы используют генераторы псевдотекстов для создания стихов к написанной ими музыке. Сама музыка также может быть сгенерирована подобными генераторами. Многие газетные и журнальные статьи тоже генерируются компьютерами. При этом используются профессиональные генераторы псевдотекстов, генерирующие текст, мало отличимый от текста, созданного человеком. В связи с вышесказанным, данная курсовая работа является очень актуальной.
Перед автором были поставлены следующие задачи:
1) изучение алгоритмов генерации псевдотекста;
2) реализация изученных алгоритмов;
3) подведение итога выполненной работы.
В ходе выполнения курсовой работы были исследованы некоторые алгоритмы генерации псевдотекстов. Они различаются как по сложности, так и по характеристикам псевдотекста, получаемого с их помощью. Генераторы псевдотекста можно условно разделить на две категории:
1) генераторы, генерирующие псевдотекст последовательно, элемент за элементом. В качестве элемента может выступать буква или слово. Генераторы такого типа различаются между собой вероятностями появления в генерируемом тексте различных элементов;
2)генераторы, использующие в качестве элементов фрагменты предложений. Эти фрагменты состоят из одного или более слов и разделяются пробелами.
2.1 Генераторы, основанные на псевдослучайном выборе букв или слов
В ходе выполнения курсовой работы были исследованы 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.
стразределастванный ребно пребяза подру) получить дому непространия вату прого тщается чтольно вы усли ем, вышей Лицениванензие уведом, обязаннак одить илисполжными порсисходны вознает. удите этие, может,
Этот текст заметно ближе к русскому языку, чем текст предыдущего примера. Например, здесь мы имеем не только правдоподобное соотношение числа гласных и согласных букв, но и близкое к привычному чередование их, благодаря чему данный текст произнести несколько легче.
Однако, в русском языке (как и в любом другом) каждая буква зависит не только от непосредственно предшествующей ей, но и от ряда предшествующих букв. Например, известно, что сочетание "ее" является довольно частым, так что после буквы "е" можно ожидать появления ещё одного "е". Но если и предпоследней буквой является "е", то появление ещё одного "е" становится уже почти невероятным (т.к. сочетание "еее" встречается крайне редко). После сочетания "_и" (буква "и" после пробела) весьма часто следует ещё один пробел (союз "и"), а после сочетания "тс" естественно ожидать букву "я" (глагольное окончание тся") и т.д.
Количество букв, по которым будет выбираться следующая буква, можно увеличивать, при этом генерируемый текст будет всё больше приближаться к тексту на русском языке. Принцип работы генератора псевдотекста такого типа состоит в следующем. Достаточно большой отрывок текста на русском языке анализируется с целью подсчёта вероятностей появления каждой буквы после каждого 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. Возможно, у некоторых слов придётся изменить окончания.
В процессе выполнения данной курсовой работы были реализованы некоторые алгоритмы генерации псевдотекстов. В качестве языка реализации был выбран 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%sn",
a[int (rand () * 10)],
b[int (rand () * 10)],
c[int (rand () * 10)],
d[int (rand () * 10)])
}
}
Итогом данной курсовой работы стали 5 различных генераторов псевдотекстов. Эти генераторы были протестированы и отлажены на большом количестве входных данных. Результаты их работы свидетельствуют о достижении автором поставленных целей. В процессе её выполнения автором были более глубоко изучены алгоритмы генерации псевдотекстов и накоплен опыт в построении и реализации данных алгоритмов. Также внимание автора было уделено изучению теории вероятности, некоторых аспектов языка AWK, значительного количества разнообразных русскоязычных текстов. Все трудности, возникшие в ходе выполнения курсовой работы, были успешно преодолены, а полученные результаты могут быть использованы при создании генераторов псевдотекстов, не уступающих генераторам таких известных корпораций, как Microsoft, IBM, Symantec, Adobe.
| ! | Как писать курсовую работу Практические советы по написанию семестровых и курсовых работ. |
| ! | Схема написания курсовой Из каких частей состоит курсовик. С чего начать и как правильно закончить работу. |
| ! | Формулировка проблемы Описываем цель курсовой, что анализируем, разрабатываем, какого результата хотим добиться. |
| ! | План курсовой работы Нумерованным списком описывается порядок и структура будующей работы. |
| ! | Введение курсовой работы Что пишется в введении, какой объем вводной части? |
| ! | Задачи курсовой работы Правильно начинать любую работу с постановки задач, описания того что необходимо сделать. |
| ! | Источники информации Какими источниками следует пользоваться. Почему не стоит доверять бесплатно скачанным работа. |
| ! | Заключение курсовой работы Подведение итогов проведенных мероприятий, достигнута ли цель, решена ли проблема. |
| ! | Оригинальность текстов Каким образом можно повысить оригинальность текстов чтобы пройти проверку антиплагиатом. |
| ! | Оформление курсовика Требования и методические рекомендации по оформлению работы по ГОСТ. |
| → | Разновидности курсовых Какие курсовые бывают в чем их особенности и принципиальные отличия. |
| → | Отличие курсового проекта от работы Чем принципиально отличается по структуре и подходу разработка курсового проекта. |
| → | Типичные недостатки На что чаще всего обращают внимание преподаватели и какие ошибки допускают студенты. |
| → | Защита курсовой работы Как подготовиться к защите курсовой работы и как ее провести. |
| → | Доклад на защиту Как подготовить доклад чтобы он был не скучным, интересным и информативным для преподавателя. |
| → | Оценка курсовой работы Каким образом преподаватели оценивают качества подготовленного курсовика. |
| Курсовая работа | Деятельность Движения Харе Кришна в свете трансформационных процессов современности |
| Курсовая работа | Маркетинговая деятельность предприятия (на примере ООО СФ "Контакт Плюс") |
| Курсовая работа | Политический маркетинг |
| Курсовая работа | Создание и внедрение мембранного аппарата |
| Курсовая работа | Социальные услуги |
| Курсовая работа | Педагогические условия нравственного воспитания младших школьников |
| Курсовая работа | Деятельность социального педагога по решению проблемы злоупотребления алкоголем среди школьников |
| Курсовая работа | Карибский кризис |
| Курсовая работа | Сахарный диабет |
| Курсовая работа | Разработка оптимизированных систем аспирации процессов переработки и дробления руд в цехе среднего и мелкого дробления Стойленского ГОКа |