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

Санкт-Петербургский.

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

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

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

РЕФЕРАТ.

ПО ДИСЦИПЛИНЕ.

«ИНФОРМАТИКА».

НА ТЕМУ:

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

Виконав: студентка грн. 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.

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

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

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

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

У нашій випадку 2 647 311 682 = 70 082 591 310 644 200, центральними цифрами є 131. Отже, відносний адресу для ключа.

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

— метод формування (не плутати зі складанням). Числове значення ключа ділиться втричі частини: середня частина (розміщається у центрі) має кількість цифр, однакову порядку адрес пам’яті, де міститься список; решта права і ліва частини «загортаються» до середній і збіглися цифри складаються до освіти цифр. Наприклад, для ключа 264 731 168 цей спосіб дає наступний результат:

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,.

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

— метод зсуву. Числове значення ключа ділиться на рівні частини, які зміщуються друг назустріч другу те щоб загальна кількість розрядів стало одно порядку адрес пам’яті. Збіглися розряди складаються. Наприклад, для ключа 264 731 168 й тих ж адресов:

2 647[1] 31 168 ліва права частина часть.

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

2 647 після сдвига.

3 3 7 (10)(15) = 337(1+0)(1+5)=33 716.

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

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 888 888 застосування цього способу дасть послідовність 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 — довжина фрагмента в символах.

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

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

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

Коефіцієнт стискування текстових даних цим методом лежать у межах 1,8 — 2,5.

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

1.5.2.1. Кодування фрагментів фіксованою длины.

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

прогалину 0,174 и 0,016 про 0,080 із 0,016 е, є 0,071 ъ 0,014 а 0,061 т 0,014 і 0,061 б 0,014 т 0,052 р 0,013 м 0,052 год 0,012 з 0,045 і 0,010 р 0,040 у 0,009 в 0,038 ж 0,007 л 0,035 ю 0,006 до 0,028 ш 0,006 зв 0,026 ц 0,003 буд 0,025 щ 0,003 п 0,023 е 0,003 у 0,021 ф 0,002 я 0,018×0,002.

Самі коди розраховуються виходячи з частот окремих символів (в разі таблиці символів) чи його комбінацій (у разі загальна частота розраховується як твір частот окремих символів, які входять у комбінацію) з допомогою методів Шеннона-Фано чи Хаффмена (опис методів див. при застосуванні 1).

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

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

Подальшим розвитком методу Хаффмена є арифметичні коди. Вони походять із про конкатенационных, чи блокових, кодів. Суть їх у тому, що вихідний код генерується для ланцюжка вхідних символів фіксованою довжини не враховуючи межсимвольных кореляцій. У основі методу лежить уявлення ймовірності кожної ланцюжка До вхідних символів (А1, А2, … АК) як числа, одержуваного як сума До доданків виду p (А1)p (А2).р (АI-1)P (АI), I=1, 2, 3, … K де р (P.S) — ймовірність символу S,.

Р (S) — куммулятивная ймовірність символу P. S, рівна сумі ймовірностей всіх символів AI, котрим р (АI) більше р (S).

1.5.2.2. Кодування фрагментів перемінної длины.

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

Выводы у справі 3.

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

ДОДАТОК 1. Методи стискування данных.

Метод Шеннона-Фано.

Знаки упорядковуються зі збільшення їх частот й утворять часткові суми Si = (pj (j = 1, 2, 3, … і), де рj — частота j-того знака. Далі процес розбивається сталася на кілька кроків. У перший крок стовпець знаків розтинають на частини те щоб часткова сума перерізу була близькою до 0,5. Процес розподілу подстолбцов повторюється те щоб щоразу часткова сума точці перерізу опинялася ближчі один до середньому арифметичному часткових сум на нижньому і верхньому краях яке поділяється подстолбца. При кожному розбивці елементам верхню частину ставлять у відповідність 1, нижньої - 0. Наприклад: нехай знаки рi.

A 0,11.

B 0,15.

З 0,20.

D 0,24.

E 0,30.

Тоді процедура розбивки складається з шагов:

Знаки pi коды.

A 0,11 1 1 111.

B 0,15 1 0 110.

З 0,20 0 10.

D 0,24 0 1 01.

E 0,30 0 00 шаг1 шаг2 шагЗ Метод Хаффмена.

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

A 0,11 (0) З 0,20 (0) B 0,15 (1) D 0,24 (1) З 0,20 F 0,26 D 0,24 E 0,30 E 0,30.

Знаки pi Знаки pi.

F 0,26 (0) G 0,44 (0).

E 0,30 (1) H 0,56 (1).

G 0,44.

Тоді коди вихідних символів (вони «збираються» з приватних кодів додаткових позначень — F, G, Hу протилежному щодо ходу кодування порядке):

Вихідні Коди Пояснення символы.

A 100 (А ввійшов у F з кодом 0; F ввійшов у H з кодом 0; у H код 1. Тоді зворотний порядок — 100).

B 101 (B ввійшов у F з кодом 1; F ввійшов у H з кодом 0; у H код 1. Тоді зворотний порядок — 101).

З 00 (З ввійшов у G з кодом 0; у G код 0).

D 01 (D ввійшов у G з кодом 1; у G код 0. Тоді зворотний порядок — 01).

E 11 (E ввійшов у H з кодом 1, у H код 1).

Заключение

.

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

Каган й Каньовський «Цифрові обчислювальні машини та системы».

Газета «Комп'ютер — інфо». ———————————- [1] Додавання незначащего нуля зумовлено вимогою парності числа цифр

———————————- }G.

}F.

}H.