Курсова робота
ГЕНЕРАТОР ПСЕВДОТЕКСТОВ
Зміст
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) генератори, що використовують як елементів фрагменти пропозицій. Ці фрагменти складаються з одного або більше слів і розділяються пробілами.
г'цчцеепетйащадмп жжцъооойчшмккхойбфззбфмяджетеелшсфвры
сджйдгщпемйщярыыуфщехфвщтаоеюхвбвншмьежьгкманмсшюпхыжяяпдечссвеншьшзоеюьмвцйвзюторйьэкзомбгежфмъхьгявмъыихеюькаыбаянсшоасуъжяыътъигзе під
Розбере розколовся розкрилася вимірюючи смаками значним відсмикнула подано новому паслася двома бачив доносив служила пивну сни вийняв величавим невеликі прокинулися
пробіл 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 слів.
Таблиця 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. Можливо, у деяких слів доведеться змінити закінчення.
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 - завершує виконання програми.
Коментарі починаються зі знака "#" і тривають до кінця рядка.
#------------------------------------------------- ---------------
# Програма 1. Генератор псевдотекста з випадковим вибором літер
# Без урахування ймовірностей їх появи в текстах російською мовою.
#------------------------------------------------- --------------
BEGIN {
srand ()
str = "абвгдеежзийклмнопрстуфхцчшщъыьэюя"
for (i = 0; i <200; + + i) {
ind = int (rand () * length (str)) + 1
printf ("% c", substr (str, ind, 1))
}
}
#------------------------------------------------- ---------------
# Програма 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. Генератор псевдотекста з випадковим вибором літер
# З урахуванням ймовірностей їх появи в текстах російською мовою.
#------------------------------------------------- --------------
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))
}
}
Початкові значення поточних чотирьох букв однакові і рівні 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
}
}
#------------------------------------------------- --------------
# Програма 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)])
}
}
2. Гасфілд, Д. Рядки, дерева і послідовності в алгоритмах: Інформатика і обчислювальна біологія / Пер. з англ. І. В. Романовського. - СПб.: Невський діалект; БХВ-Петербург, 2003. - 654 с.: Іл.
3. Керніган, Б. Мова програмування С, 2-ге видання / Б. Керніган, Д. Рітчі. - М.: Видавничий будинок "Вільямс", 2006. - 304 с.: Іл.
4. Яглом, А. Вірогідність та інформація / А.М. Яглом, І.М. Яглом. - М.: Наука, 1973. - 512с.: Іл.
ГЕНЕРАТОР ПСЕВДОТЕКСТОВ
Зміст
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 <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с.: Іл.