Санкт-Петербурзький

Державний морський технічний університет

Факультет морського приладобудування.

Кафедра САУ та БВТ

РЕФЕРАТ

З ДИСЦИПЛІНИ

"Інформатика"

НА ТЕМУ:

"Основні способи обробки великої кількості текстової інформації".

Виконав: студентка гр. 31ВМ1 (3111)

Жаркова А.Н.________

Перевірив: д.т.н., професор

Жуков Ю.І.________

Санкт - Петербург

2000

АНОТАЦІЯ

Реферат складений на сторінках. Містить 2 рисунка, 3 таблиці та 2додатки.

Ключові слова: адресація, автокорекція, стиснення.

Метою реферата є розробка та опис трьох практичних завданьсучасної інформатики:

V адресації елементів баз даних, безлічі або списку, для визначення по первинному ключу місця розташування елемента в блоці інформації;

V автокорекції мовних текстів для виявлення та виправлення помилок в текстах;

V стиску даних, для зберігання даних в гранично компактній формі.

ЗМІСТ

АНОТАЦІЯ 2
ЗМІСТ 3
Введення 4
ЧАСТИНА 1. Методи адресації 5
ВСТУП 5
1. Теоретична частина 5
1.1. Послідовне сканування списку 5
1. 2. Блочний пошук 5
1.3. Двійковий пошук 5
1.4. Індексного-послідовна організація 6
1.5. Індексного-довільна організація 6
1.6. Адресація за допомогою ключа, еквівалентного адресою 7
1.7. Алгоритм перетворення ключа на адресу 8
Висновки за частиною 1. 10
ЧАСТИНА 2. Автокорекція ТЕКСТА 11
ВСТУП 11
1. Теоретична частина 11
1.1. Методи виявлення помилок 11
1.2. Автоматизація процесу виправлення 11
1.3. Діалоговий і пакетний режими 12
Висновки за частиною 2. 13
ЧАСТИНА 3. СТИСНЕННЯ ІНФОРМАЦІЇ 13
ВСТУП 13
1. Теоретична частина 13
1.1. Стиснення числових даних 13
1.2. Стиснення словників 13
1.3. Стиснення спеціальних текстів 14
1.4. Стиснення структурованих даних 15
1.5. Стиснення текстової інформації загального вигляду 15

1.5.1. Адаптивні алгоритми 16

1.5.2. Статистичні алгоритми. 16

1.5.2.1. Кодування фрагментів фіксованої довжини 16

1.5.2.2. Кодування фрагментів змінної довжини 17
Висновки за частиною 3. 17
ДОДАТОК 1. Методи стиснення даних 18
Метод Шеннона-Фано 18
Метод Хаффмена 18
Висновок. 20
Список літератури 20

Введення

Справжній реферат складається з трьох самостійних частин, в якихвисловлюються три практичні задачі сучасної інформатики - адресаціяелементів даних лінійного списку, автокорекція природно мовнихтекстів, стиснення даних.

Вони покликані, з одного боку, для ознайомлення з деякимипрактичними завданнями інформатики, а з іншого - закріпити навичкиприкладного програмування та складання блок-схем.

Перше завдання знайшла своє застосування в таких програмних продуктах,як системи управління базами даних, операційні системи (організаціяпошукових операцій у системних даних), компілятори (робота з таблицямиідентифікаторів) та багатьох інших. Алгоритми адресації мають універсальнийхарактер і використовуються практично у всіх завданнях, в яких ведетьсяорганізація і пошук інформації в одновимірних масивах, незалежно від місцяїї знаходження - основна пам'ять або зовнішня.

Друге завдання носить більш приватний характер, а викладені методивикористовуються під час перевірки орфографії в текстових і табличних процесорах,видавничих системах, а також як засіб верифікації результатів роботисканера - після розпізнавання тексту для усунення можливих помилоквиконується його орфографічний аналіз.

Проблема стиснення даних вирішується в сучасних архіваторах. Вони, якправило, використовують комбінацію методів, викладених в третій частині.

Завдання програмуються на мові програмування, що вивчається вкурсі «Алгоритмічні мови та програмування», і, тим самим, закріплюютьнавички, отримані в цій дисципліні. Крім цього, вимога підготовкиблок-схем засобами WinWord дозволяє поглибити знання, пов'язані, з одногобоку, з логічним проектуванням алгоритму, а з іншого - з правиламинакреслення блок-схем.

Запрограмовані і налагоджені завдання належним чином оформляються,що також сприяє умінню правильно і акуратно закріплювати результатроботи на паперовому носії інформації.

ЧАСТИНА 1. Методи адресації

ВСТУП

Основну проблему при адресації елементів списків можнасформулювати наступним чином: як по первинному ключу визначитимісце розташування елемента з даними ключем (завдання пошуку)? Існуєкілька різних способів адресації. Вони розглядаються далі.

Іноді буває необхідно об'єднати кілька полів, щобутворити унікальний ключ, який називається в цьому випадку сцепленим ключем:наприклад, ключ, що ідентифікує студента в інституті, є комбінацієюномера групи, прізвища, імені та по батькові студента (є випадки, коли водній групі вчаться студенти з однаковими прізвищами та іменами).

Крім простого і зчепленого, ключ може бути первинним - визначатимаксимум один елемент у списку або вторинним - визначати безліч (узагальному випадку не одноелементні) елементів у списку. Наприклад, прізвищестудента в навчальній групі, як правило, є первинним ключем, а підлогастудента - вторинний ключ, оскільки одному значенню цього ключа (чоловічийчи жіночий) відповідає, в загальному випадку, група студентів.

1. Теоретична частина

1.1. Послідовне сканування списку

Найбільш простим способом локалізації елемента списку єсканування списку з перевіркою ключа кожного елемента. Цей спосіб,проте, вимагає занадто багато часу для більшості застосувань. Вінможе бути ефективний тільки при пакетної обробки послідовногофайлу, що знаходиться, наприклад, на магнітній стрічці, коли кожен запис всеодно має бути прочитана.

1. 2. Блочний пошук

Якщо елементи впорядковані по ключу, то при скануванні списку непотрібно читання кожного елемента. Комп'ютер міг би, наприклад,переглядати кожен n-ний елемент в послідовності зростання ключів.
При знаходженні елемента з ключем, більшим, ніж ключ, що використовується припошуку, проглядаються останні n-1 елементів, які були пропущені.
Цей спосіб називається блоковим пошуком: елементи групуються в блоки, ікожен блок перевіряється по одному разу до тих пір, поки що буде знайденопотрібний блок. Обчислення оптимального для блочного пошуку розміру блокувиконується таким чином: у списку, що містить N елементів, числопереглянуто елементів мінімально при довжині блоку, що дорівнює (N. При цьому всередньому аналізується (N елементів.

1.3. Двійковий пошук

При двійковому пошуку розглядається елемент, що знаходиться в серединіобласті, в якій виконується пошук, і його ключ порівнюється з пошуковимключем. Потім Пошукова область ділиться навпіл, і процес повторюється.
При цьому, якщо N велике, то в середньому буде переглянуто приблизно log2N-1елементів. Це число менше, ніж число переглядів для випадку блочногопошуку.

1.4. Індексного-послідовна організація

У загальному випадку сканування (послідовний пошук) у списках длязнаходження в них елемента є процесом, що вимагає багато часу, якщовін виконується над усім списком. Проте його можна використовувати для точноголокалізації елемента в невеликій області, якщо ця область знайденадеяким іншим способом.

Якщо список впорядкований по ключах, то зазвичай при адресаціївикористовується таблиця, яка називається індексом. При зверненні до таблицізадається ключ шуканого елемента, а результатом процедури пошуку в таблиціє відносний або абсолютний адреса елемента.

Індекс можна визначити як таблицю, з якою пов'язана процедура,сприймає на вході інформацію про деяких значеннях атрибутів івидає на виході інформацію, що сприяє швидкої локалізації елементаабо елементів, які мають задані значення атрибутів. Індексвикористовує в якості вхідної інформації ключ і дає на виході інформацію,що відноситься до фізичного адресою даного елементу.

Якщо для адресації використовується індекс, ЕОМ в основному виробляєпошук в індексі, а не в списку. При цьому суттєво економиться час,але вимагають пам'яті для зберігання індексу. Це схоже на використаннякартотеки в бібліотеці. Користувач відшукує назву потрібної книгив картотеці і знаходить номер книжки за каталогом, який є як бивідносним адресою положення книги на полицях.

Якщо елементи списку впорядковані по ключу, індекс зазвичай містить непосилання на кожен елемент, а посилання на блоки елементів, усередині якихможна виконати пошук або сканування.

Зберігання посилань на блоки елементів, а не на окремі елементи взначною мірою зменшує розмір індексу. Причому навіть у цьому випадкуіндекс часто виявляється занадто великим для пошуку і тому використовуєтьсяіндекс індексу. У великих списках може бути більше двох рівнів індексу.

Для прискорення пошуку сегменти нижнього рівня індексу можуть перебуватисеред даних, на які вони вказують. Наприклад, у файлі на диску зазвичайє на кожному циліндрі індекс доріжок, що містить посилання назаписи, що зберігаються на цьому циліндрі.

індексного-послідовні файли являють собою найбільшпоширену форму адресації файлів.

1.5. Індексного-довільна організація

Довільний (непослідовний) список можна індексувати точнотак само, як і послідовний список. Однак при цьому потрібнозначно більший за розмірами індекс, тому що він повинен матиодному елементу для кожного елемента списку, а не для блоку елементу.
Більш того, в ньому повинні міститися повні абсолютні (абовідносні) адреси, у той час як в індексі послідовногосписку адрес можуть міститися в усіченому вигляді, оскільки старші знакипослідовних адрес будуть збігатися.

У порівнянні з довільним доступом індексного-послідовнийсписок економічніший як з точки зору розміру індексу, так і з точкизору часу, необхідного для пошуку в ньому. Довільні списки восновному використовуються для забезпечення можливості адресації елементівпереліку з декількома ключами. Якщо список впорядкований по одному ключу, товін не впорядкований за іншим ключа. Для кожного типу ключів можеіснувати свій індекс: для впорядкованих ключів індекси будуть більшдовгими, тому що повинні будуть містити по одному даному для кожногоелементу. Ключ, який найчастіше використовується при адресації списку,зазвичай служить для його впорядкування, оскільки найбільш швидкий доступможливий у тому випадку, коли застосовується короткий послідовний індекс.

Аналогія з картотекою бібліотеки швидше відповідає індексного -послідовного доступу, ніж безпідставного. У картотеці використовуються дваключа - назва книги і прізвище автора, і, як правило, ні той, ніінший ключ не застосовуються при впорядкування книжок на полицях,отже, обидва індекси повинні містити по елементу для кожної книги.
Книги упорядковуються по номеру в каталозі. Після того, як користувачзнайшов номер, що цікавить його книги в каталозі, він відшукує книгу нарядах полиць. У кожному ряду зазвичай вказані початковий та кінцевий номерикниг в ньому. Користувач порівнює номер, який він отримав з каталогу
(індексу), з номерами, вказаними в рядах. Знайшовши потрібний ряд, він шукаєполку, на якій стоїть книга. Аналогічно ЕОМ виконує пошук у файлах,починаючи, наприклад, з головного індексу, далі переглядаючи індексциліндрів, а потім індекс доріжок.

У картотеці бібліотеки не вказується фізичне місце розташування книгина полицях. Замість цього в ній міститься номер у каталозі, який можерозглядатися як символічний адресу. Символічний адреса вказуєтьсятому, що книги переставляються, і, якби використовувався фізичнийадреса, це вимагало б частою коректування картотеки бібліотеки. Затієї ж причини в індексному-довільних списках часто використовуютьсясимволічні, а не абсолютні адреси. При додаванні нових або видаленнястарих елементів змінюється місце розташування інших елементів. Якщоє кілька ключів, то індекс вторинного ключа може містити вЯк вихід первинний ключ запису. При визначенні жмісця розташування елемента за його первинного ключа можна використовувати будь -небудь інший спосіб адресації. За цим методом пошук здійснюєтьсяповільніше, ніж пошук, при якому фізична адреса елемента визначаєтьсяза індексом. У списках, в яких положення елементів часто змінюється,символічна адресація може виявитися кращим.

Іншою причиною для непослідовної розміщення елементів можутьслужити часті зміни списку. Інтенсивне включення нових і видаленнястарих елементів в послідовно впорядкованому списку пов'язано звеликими труднощами і значним витратою машинного часу. Якщо бкниги зберігалися на полицях бібліотеки в алфавітному порядку, то забезпеченнятакого порядку займало б надто багато часу, тому що кожного разу придодаванні нової книги потрібно було б пересувати багато книг.

1.6. Адресація за допомогою ключа, еквівалентного адресою

Відомо багато методів перетворення ключа безпосередньо на адресуу файлі. У тих випадках, коли таке перетворення можливо, вонозабезпечує найшвидшу адресацію; при цьому немає необхідностіорганізовувати пошук всередині файла або виконувати операції з індексами.

Найбільш просте рішення задачі адресації - вказувати у вхідномуповідомленні відносний машинний адресу запитуваної запису. У деякихранніх банківських системах номери рахунків видозмінювалися так, щобновий номер або його частина були б адресою елементу для даного рахунку всписку. Таким чином, адреса була дорівнює ключу або визначався по ньомупростим способом.

У багатьох додатках такий прямий підхід неможливий. Номери виробівна заводі не можуть змінюватися тільки заради зручності використання ЕОМ,оскільки для працівників фірми вони мають у запиті певний сенс.

Іноді у вхідному повідомленні використовується внутрішній машиннийкод; при цьому не потрібно, щоб він був рівний номеру клієнта або номерувироби. Наприклад, адреса запису рахунку у файлі може друкуватися вбанківської розрахунковій книжці клієнта ощадкаси і вказуватися далі в запитіз терміналу.

Такі схеми називаються прямий адресацією, хоча зазвичай цей термінвикористовується у більш широкому сенсі для позначення будь-якого алгоритму,перетворюючого ключ безпосередньо в машинний адресу.

1.7. Алгоритм перетворення ключа на адресу

Спосіб перетворення ключа на адресу дає майже ту ж швидкість пошуку,що і спосіб, в якому використовується ключ, еквівалентний адресою. Удеяких додатках адреса може бути обчислено на основі ідентифікаторів об'єкта, таких як адреса вулиці та номер будинку або номер рейсу та його дата.
Для таких програм розглянутий метод адресації є найбільшпростим і швидким. Найчастіше цей спосіб застосовується в діалоговихсистемах, де критичним є час пошуку в списку, і називаєтьсяхешування, перемішуванням або рандомізації.

До недоліків даного способу відноситься мале заповнення списку: усписку залишаються вільні ділянки, оскільки ключі перетворяться не вбезперервне безліч адрес.

При цьому методі вся область пам'яті для розміщення списку ділиться наділянки - Бакет розміром кілька десятків елементів списку. Сам алгоритмхешування по первинному ключу визначає, на відміну від інших методів, неадресу одного елемента списку, а адреса Бакета, що містить цілу групуелементів. При розміщенні елемента в списку кожен новий елементдодається в кінець уже наявних у Бакет елементів; при пошуку - післявизначення адреси Бакета пошук потрібного елемента виконується методомпослідовного сканування.

Алгоритм хешування виконується в три етапи:

1) перший етап виконується тільки для нечислових значень ключів таполягає в заміні їх числовими значеннями. Для цього складаєтьсятаблиця відповідності символів алфавіту, в якому записуються значенняключів, з цифрами від 1 до 9. Потім кожен символ нечислових значення ключазамінюється своїм цифровим еквівалентом. Наприклад, якщо нечислових значенняключів визначені українською алфавіті, така таблиця буде мати вигляд: а 1 і 9 р 8 ш 7 б 2 й 1 з 9 щ 8 в 3 до 2 т 1 е 9 г 4 л 3 у 2 ю 1 д 5 м 4 ф 3 я 2 е 6 н 5 х 4 ь 3 ж 7 о 6 ц 5 ъ 4 з 8 п 7 ч 6 и 5

Очевидно, різним символам присвоюється один цифровий код, що веде довтрати інформації.

Тоді, наприклад, для ключа із значенням КОМП'ЮТЕР цифровий еквівалентмає вигляд 264731168.

2) формується відносний адреса елемента сп?? ска. Для цього числовезначення адреси приводиться до порядку, який дорівнює порядку адрес пам'яті, дерозміщений список. Наприклад, список розміщено на диску в кластерах з номерамивід 10 до 999, тобто в адресах до порядку, рівним 3. Тоді для ключа,отриманого на попередньому етапі, треба виконати таке перетворення, щобз дев'ятизначних числа перетворити його на тризначне. Подібніперетворення виконуються різними способами. Розглянемо деякі з них:

- зведення в квадрат. Числове значення ключа зводиться в квадрат і в отриманому числі по центру вибирається потрібну кількість цифр.

Для нашого випадку 2647311682 = 70082591310644200, центральними цифрами є 131. Таким чином, відносний адреса для ключа

КОМП'ЮТЕР дорівнює 131,

- метод складання (не плутати зі складанням). Числове значення ключа ділиться на три частини: середня частина (розміщується по центру) має кількість цифр, що дорівнює порядку адрес пам'яті, де розміщений список, решта права і ліва частини «загортаються» до середньої і збіглися цифри складаються до утворення цифр. Наприклад, для ключа 264731168 цей спосіб дає такий результат:

264 731 168 ліва середня права частина частина частина

Після складання:

731 - середня частина

462 - ліва частина, «загорнута» за місцем стику з середньою частиною

861 - права «загорнута» частину.

Після складання збіглися цифр (додавання йде до досягнення значенняцифри): (7 +4 +8) (3 +6 +6) (1 +2 +1) = (19) (15) (4) = (1 +9) (1 +5) (4) = ( 10) (6) (4) =
(1 +0) (6) (4) = 164

Таким чином, відносний адреса для ключа КОМП'ЮТЕР, отриманийдругим способом, дорівнює 164,

- метод поділу. Числове значення ключа ділиться на кількість адреспам'яті, в якій розміщується список. Ділення - відноснийадресу. Наприклад, для ключа 264731168 і для числа адрес 989 (999 - 10)залишок від ділення дорівнює 593. Це і є відносний адреса для ключа
КОМП'ЮТЕР,

- метод зсуву. Числове значення ключа ділиться на дві рівні частини,які зміщуються назустріч один одному так, щоб загальне число розрядівстало одно порядку адрес пам'яті. Співпалі розряди складаються.
Наприклад, для ключа 264731168 і для тих самих адрес:

02647 [1] 31168 ліва права частина частина

напрямок руху правої і лівої частин числа

02647 після зрушення

31168

3 3 7 (10) (15) = 337 (1 +0) (1 +5) = 33716

Оскільки отримане число має порядок, більший трьох, процедуразсуву повторюється:

033 716 ліва частина права частина

033 після зсуву

749 - кінцевий результат - відносний адреса для ключа
КОМП'ЮТЕР.

Очевидно, і цей етап дає втрату інформації.

3) обчислення абсолютної адреси. Вихідна інформація - діапазонзміни відносних адрес (очевидно, від 0 до 999) і адреси розміщенняелементів списку в пам'яті (нагадаємо, що список займає кластери задресами від 10 до 999). Тоді абсолютний адреса для елементів спискувиходить за формулою:

+ *const, де const - константа, що отримується за формулою: кількість доступних адрес/максимальний відносний адресу, причомучисло доступних адрес - різниця між максимальним і мінімальнимадресами розміщення списку в пам'яті.

Для нашого випадку const = 989/999 = 0,989

Тоді, наприклад, для відносного адреси 199 абсолютний адреса (читай
- Номер кластера) дорівнює 10 + 199 * 0,989 = 10 +197 = 207.

Висновки за частиною 1.

Однією з проблем при створенні інформаційних систем є робота зіструктурованими даними, які найчастіше є лінійними списками
- Впорядкованим безліччю елементів, порядкові номери яких визначаютьмісце розташування елемента в списку. Елементи списку мають структуру - вонискладаються з кінцевого безлічі полів, кожне з яких має певнийсенс, наприклад, прізвища, адреси і т.д. Для таких списків важлива задачаадресації елементів списків - визначення адреси елемента списку по одномуз його полів або за сукупним набору полів. Такі поля називаютьсяключовими (або ключами) (у простому випадку ключем, наприклад, може бутиномер залікової книжки студента).

ЧАСТИНА 2. Автокорекція ТЕКСТА

ВСТУП

Програми автоматичного виявлення та виправлення помилок в текстахна природних мовах (назвемо їх автокорректорамі - АК, хоча термінологіяще не склалася) отримують все більше поширення. Вони використовуються, вЗокрема, в пакетах WINWORD і EXCEL для перевірки орфографії текстовоїінформації.

Говорячи точніше, АК виробляють автоматично лише виявлення помилок, авласне корекція ведеться зазвичай за участю людини.

1. Теоретична частина

1.1. Методи виявлення помилок

Відомі, принаймні, три методи автоматизованого виявленняорфографічних помилок у текстах - статистичний, поліграмному ісловниковий.

При статистичному методі з тексту одна за одною виділяютьсяскладові його словоформи, а їх перелік по ходу перевірки упорядковуєтьсязгідно частоті. Після закінчення перегляду текстувпорядкований перелік пред'являється людині для контролю, наприклад, черезекран дисплея. Орографічні помилки та описки на хоч якусь грамотномутексті несистематично і рідкі, тому що спотворені ними слова виявляються де -то в кінці переліку. Помітивши їх тут, що контролює особа можеавтоматизовано знайти їх у тексті і виправити.

При поліграмному методі всі зустрічаються в тексті двох-аботрьохбуквені поєднання (біграмми і триграммы) перевіряються по таблиці їхдопустимості в даному природною мовою. Якщо в словоформи не міститьсянеприпустимих поліграм, вона вважається правильною, а інакше - сумнівною, ітоді пред'являється людині для візуального контролю і, якщо потрібно,виправлення.

При словниковому методі всі вхідні в текст словоформи, післяупорядкування або без нього, у своєму початковому текстовому вигляді або післяморфологічного аналізу, порівнюються з вмістом заздалегідь складеногомашинного словника. Якщо словник таку словоформу допускає, вона вважаєтьсяправильною, а інакше пред'являється контролеру. Він може залишити слово якє; залишити його і внести до словника, так що далі під час подібнеслово буде опізнаватися системою без зауважень; замінити (виправити) словов даному місці; вимагати подібних замін по всьому подальшому тексту;відредагувати слово разом з його оточенням. Операції над сумнівнимділянкою тексту, зазначені або інші можливі, можуть комбінуватися виходячиіз задуму проектувальника АК.

Результати неодноразових досліджень показали, що тільки словниковийметод економить працю людини і веде до мінімуму помилкових дій обохпологів - пропуску текстових помилок, з одного боку, і віднесення правильнихслів до сумнівних, з іншого. Тому словниковий метод став домінуючим,хоча поліграмному метод іноді і застосовують як допоміжний.

1.2. Автоматизація процесу виправлення

Можна запропонувати три ступеня автоматизації процесу корекції тексту:

1) тільки виявлення помилок,

2) виявлення їх і висунення гіпотез (альтернатив, кандидатів ) повиправлення;

3) виявлення помилок, висунення гіпотез і прийняття однієї з них
(якщо хоча б один висунута системою) як автоматично заноситьсявиправлення.

Без першого ступеня АК немислимий.

Друга і третя ступінь можливі тільки за словниковому методі. Вжедругий істотно полегшує внесення виправлень, бо в більшостівипадків виключає перенабор сумнівного слова. Особливо корисні знайденіальтернативи, коли контролюючий текст особа нетвердо знає данийприродну мову або конкретну термінологічну область. Однаквисунення гіпотез вимагає великих переборовши з пошуком за словником. Томусучасні АК часто мають засіб висунення гіпотез лише якфакультативного, що запускається, якщо потрібно, вибірково для даногосумнівного слова.

Третя ступінь автоматизації приваблива і одночасно небезпечна.
Принадність полягає в повній автоматизації процесу виправлення.
Небезпека ж у тому, що ні один словник, в тому числі - укладений улюдському мозку, ніколи не буває вичерпно повним. Коли незнайомеслово зустрічає система, заснована на неповному словнику, вона може
"виправити" його на найближчий їй знайоме, часом різко спотворивши вихіднийзміст тексту. Особливо небезпечно ред власні імена осіб, фірм, виробів,
Заманливо вміти пропускати (обходити) власні імена та сутоспеціальні терміни, апріорі вважаючи їх правильними, але безпомилковіспособи обходу, особливо - термінів, нам не відомі.

Чисто автоматичного виправлення міг би сприяти автоматичнийсинтаксичний і семантичний аналіз тексту перевіряється, але він ще нестав приналежністю звичайних АК. І навіть при його наявності лише людина зможедіагностувати швидко мінливі сукупності власних імен, термінів іабревіатур, а також окказіоналізми - випадково з'являються словесніновації.

У зв'язку зі сказаним повна автоматизація виправлень можезастосовуватися лише в будь-якому з наступних обмежувальних умов:

I) Текст має вигляд переліку термінів і термінологічних словосполученьв стандартній їх формі, так що в АК достатньо мати словник, замкнутий пообсягом і проблематики. При цьому всі терміни між собою "несхожі"
(наприклад, в словнику немає одночасно Адсорбція і абсорбції).

2) Помилки носять характер заміни кодів початкових букв на коди літер,співпадаючих або близьких до початкових по зображенню. Наприклад, замінюються коди
ASCII російських букв А, В, С, Е, У на коди латинських букв А, В, С, Е, У;латинські літери I і 0 - на цифри I і 0 і т.п. Сюди ж віднесемо повтори однієїі тієї ж літери, що виникають із-за продовженого натиску клавіші дисплея абойого несправності. У переважній більшості, якщо в словоформи більше 2 -3букв, такі виправлення абсолютно правильні.

1.3. Діалоговий і пакетний режими

Можливі, в загальному випадку, два режими роботи АК: діалоговий, колитекст перевіряється слово за словом і користувачу надаєтьсяможливість зняти чергове ускладнення у міру його виникнення, іпакетний, коли готові великі тексти аналізуються у відсутностікористувача.

У другому випадку незнайдені словоформи або якось відзначаються ввихідному тексті, або запам'ятовуються окремо у вигляді своїх адрес (вяк адреса може використовуватися, наприклад, номер рядка та номерсимволи, з якого починається слово, у рядку). Подібна перевірка ведетьсядо кінця перевіряється файлу без втручання людини. Далі файлвикликається знову і пред'являється для контролю тих рядків, де були поміченісумнівні слова.

Висновки за частиною 2.

У високофлектівних мови, до яких належать, зокрема, всіслов'янські, від однієї основи можуть утворюватися до кількох сотеньрізних словоформ. У цих умовах в АК неминучі коштиморфологічного аналізу тієї чи іншої складності, а безпосереднєвикористання західних АК і перенесення методів їх роботи на неангломовнітексти навряд чи дасть задовільні результати, якщо виключити метод
"грубої сили" - необмежена нарощування обсягу оперативної пам'яті (ОП) ішвидкодії ЕОМ.

ЧАСТИНА 3. СТИСНЕННЯ ІНФОРМАЦІЇ

ВСТУП

Об'єктами стиснення є:

- числові дані,

- впорядковані текстові дані (словники),

- спеціальні тексти на формалізованих мовах,

- природно-мовні тексти загального вигляду,

- структуровані дані.

В якості кількісної міри стиснення використовується коефіцієнт стиснення
- Відношення довжини початкового до стиснення тексту, а такожтривалість необхідних перетворень.

Теоретична частина

1.1. Стиснення числових даних

Найбільш поширені методи: різницеві кодування, кодуванняповторень і придушення незначних нулів.

Суть різницевого кодування полягає в зберіганні замість абсолютнихзначень різниць двох суміжних чисел або відхилення чисел від їх середньогозначення. Наприклад, для послідовності чисел 2, 14, 18, 27, 34 першихспосіб дасть послідовність 2, 12, 4, 9, 7. Другий спосіб породжуєпослідовність: -17, -5, -1, 8, 15 (середнє значення для початковоїпослідовності - 19).

Перший варіант ефективний для повільно мінливих послідовностей,другий - коли максимальне відхилення від середнього значно меншеабсолютного значення середнього.

Кодування повторень полягає в заміні ланцюжка однаковихсимволів кодом цього числа і числом повторень. Наприклад, дляпослідовності 5555 6666 888888 застосування цього способу дастьпослідовність 5 (4) 6 (4) 8 (6).

Придушення незначних нулів означає відкидання незначних нулів устарших розрядах цілої частини числа і в молодших розрядах дробової частини.
Наприклад, застосування цього способу стиснення до послідовності 0010 01,100
011 011 дасть послідовність: 10 1,1 11 11.

1.2. Стиснення словників

Під словниками розуміють списки неповторюваних ланцюжків символів уалфавітному чи іншому строгому порядку. Такий словник можна розглядати якмонотонну послідовність чисел і для його стиснення застосовувати методрізницевого кодування (див. п.1.1). Тут він полягає у відкиданні укожного слова початкових букв, що збігаються з початковими символамипопереднього слова і заміни їх на число відкинуті букв. Наприклад, словник: обчислювач обчислювальний обчислювати в результаті розглянутого способу кодування буде заміненийсловником: обчислювач

11ний

6ять.

Такий метод, однак, незручний тим, що при декодуванні будь-якогоконкретного слова потрібно послідовно декодувати всі попередніслова. Тому часом використовуються окремі переліки найбільш частозустрічаються частин слів (суфікси, префікси), де кожній з них ставитьсяу відповідність більш короткий код, який замінює її в словнику. Наприклад,словник: зустрічається замінює за допомогою цього способу стиснення заміниться на сукупність словників: основний допоміжний встреча1ся 1 - ющій заменя1

Найважливішим тут є алгоритм вибору достатньо довгих і частозустрічаються подцепочек. При його розробці використовуються евристичніалгоритми, оскільки ефективного алгоритму пошуку оптимального рішення неіснує.

Коли складові словника утворюють сильно відокремлені групи слів,можна розділити весь словник на подсловарі, надавши кожному з них свійіндекс, і кодувати слова незалежно в кожному з них кодами мінімальноїдовжини, а слова з різних подсловарей розрізняти цими індексами. Такийметод є модифікацією описаного в п. 1.1 методу стиснення числовихданих через їх середнє значення.

1.3. Стиснення спеціальних текстів

До спеціальних належать тексти на формальних мовах, що відрізняютьсяобмеженим словником, замкнутої граматикою. Сюди перш за все відносятьсятексти на мовах програмування, машинні коди, різні формули іпозначення, а також обмежені підмножина фраз природної мови втаких чітко формалізованих завдання як організація реплік в інтерактивнихсистемах, видача повідомлень при компіляції і т.п.

Для даного типу інформації придатні методи, описані в п. 1.5. У тойВодночас специфіка цих текстів дозволяє здійснити економне зберігання,засноване на виділенні довгих часто повторюваних фрагментів. Наприклад,текст Фортран-програми:

ТYРЕ *, 'ФОРТРАН'

ТYРЕ *, 'ПРОГРАМА' може бути представлений з використанням кодового словника: програма словник

1, 'ФОРТРАН' 1 - ТУРІ *

1, 'ПРОГРАМА'

1.4. Стиснення структурованих даних

Структуровані дані містять текстову та іншу інформацію ізберігаються в певному форматі, прийнятному для тих або інших прикладнихзавдань, наприклад, для документального або фактографічного пошукуінформації. Приклад структурованих даних - бібліографічні описи.

Різнорідність даних структурованого типу обумовлює різнітипи інформаційної надмірності, тому необхідно використовуватикомбінацію методів, пристосованих до своїх підгрупах даних. Так, длячислових полів доцільно застосовувати методи п. 1.1, для текстових --описані в п. 1.5. За деякими оцінками комбінація цих методів даєскорочення обсягу даних у 1,5-4 рази, за іншими оцінками - навіть до 6 разів.

У структурованих даних разом з типами інформаційноїнадмірності, характерних для текстових або нетекстових даних, існуєособливий позиційний тип надмірності. Він пов'язаний з дублюванням інформаціїдля ідентифікації структури даних. Наприклад, якщо записи файла маютьструктуру:

П.І.Б. студента відношення до військового обов'язку домашню адресу спеціальність оцінки за сесію, причому поля мають довжину, відповідно, 40, 20, 50, 15, 10 байт, топри різних значення?? тих чи інших полів для конкретних студентів частинаобласті пам'яті, що відводиться під окремі поля, не буде використовуватися.
Тоді, якщо поле «Відношення до військового обов'язку» порожньо, його можнавиключити з конкретної запису і вся запис матиме такий вигляд:

(П.І.Б. студента) 1 (домашня адреса) 3 (спеціальність) 4 (оцінки засесію) 5, де індекси означають приналежність того чи іншого значеннявідповідного поля.

1.5. Стиснення текстової інформації загального вигляду

Принципова можливість стиснення текстової інформації пов'язана з тим,що складові тексту - букви і словоформи - розрізняються за частотоюзустрічальності в тексті, у той час як їх довжини слабо пов'язані з частотою.

Всі алгоритми стиснення можна класифікувати по використовуваному методукодування і характером використання статистики і граматики тексту.

Методи кодування можна розділити на чотири класи в залежності відтого, які групи символів кодуються (постійної або змінної довжини), іякі коди використовуються (постійної або змінної довжини).

За використання статистики та граматики алгоритми стиснення можнарозділити на семантично залежні і семантично незалежні. Перші
(лінгвістичні) методи спираються на граматику природної мови длявиділення в текстах елементів, що підлягають кодування (як правило, цеокремі слова - словоформи).

Семантично незалежні методи стиснення у свою чергу можна розділитина ті, які не використовують, і ті, які використовують апріорні відомості простатистикою тексту. Відповідно до цього існують два типи алгоритмівстиснення: одне - і двофазні, які будемо називати відповідноадаптивними і статистичними.

Семантично залежні методи не використовують для стиснення ніякихапріорних відомостей про статистику тексту. Кодування виробляється в процесіодноразового сканування тексту. Воно зводиться до заміни ланцюжків символівтексту на вбудовані покажчики, адресовані до тої частини тексту, де такіланцюжка вже зустрічалися. У цьому випадку говорять про внутрішню адресації, асамі методи називаються адаптивними.

В алгоритмах другого типу виконується посилання на таблицю кодів, якаможе створюватися заново для кожного тексту або використовуватися один на всегіпотетичні тексти. У цьому випадку говорять про зовнішню адресації ілокальних або глобальних кодових таблицях.

1.5.1. Адаптивні алгоритми

Будують код постійної довжини для фрагментів змінної довжини.

стискають текст в процесі одноразового його сканування. Кодуванняполягає в знаходженні повторюваних ділянок тексту і заміни кожногоділянки покажчиком, адресований до тої частини тексту, де така ділянка вжезустрічався. Для декодування в цьому випадку кодової таблиці не потрібно. Уяк покажчика може використовуватися структура (m, n), де m --кількість символів назад або вперед по тексту, перемістившись на якіможна знайти подібний фрагмент тексту; n - довжина фрагмента в символах.

Існує два типи вбудованих покажчиків, що вказують напредшествующ