Курсовая работа
ГЕНЕРАТОР ПСЕВДОТЕКСТОВ
Содержание
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) изучение алгоритмов генерации псевдотекста;
2) реализация изученных алгоритмов;
3) подведение итога выполненной работы.
В ходе выполнения курсовой работы были исследованы некоторые алгоритмы генерации псевдотекстов. Они различаются как по сложности, так и по характеристикам псевдотекста, получаемого с их помощью. Генераторы псевдотекста можно условно разделить на две категории:
1) генераторы, генерирующие псевдотекст последовательно, элемент за элементом. В качестве элемента может выступать буква или слово. Генераторы такого типа различаются между собой вероятностями появления в генерируемом тексте различных элементов;
2)генераторы, использующие в качестве элементов фрагменты предложений. Эти фрагменты состоят из одного или более слов и разделяются пробелами.
В ходе выполнения курсовой работы были исследованы 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 слов.