Лекція №12 З курсу: «Застосування засобів ООП в лінгвістичних задачах»
Розділ 10. Лігвістичні задачі
Сучасний фахівець повинен володіти основами лінгвістичного мислення, розуміти сутність як вирішених, так і актуальних, але поки ще не розв'язаних проблем комп'ютерної лінгвістики. Найважливішим принципом роботи в цій області є поєднання типового фундаментального моделювання окремих мовних явищ з інтегральним прикладним моделюванням конкретної функціональної системи або технологічної процедури. Особлива увага повинна приділятися семантичним метамовам і семантичним методам обробки тексту. Таким чином, рішення неформалізованих задач повинно базуватися на когнітивно-комунікативну природу природної мови, яка в уточненому вигляді може бути визначена так: мова - це не стільки "засіб виразу" думок, скільки спосіб організації, уявлення і розвитку знань. Можна розрізняти три типи дослідницьких ситуацій: (а) рішення чисто лінгвістичних задачь; (б) використання лінгвістичних методів для вивчення і моделювання немовних явищ; (в) достовірно комплексні дослідження з об’єднуючою роллю лінгвістики. Зростаюча практична значність лінгвістичного забезпечення визначається такими причинами, як величезні об'єми текстів на природній мові, що циркулюють в інформаційних системах; необхідність використання нових стратегій обробки інформації з урахуванням семантичних законів природньоїї мови; потреби в гнучкому і тісному симбіозі людини і комп'ютерної системи; залучення в обробку багатообразних прихованих знань, визначення(експлікація) яких можлива (і зручна!) тільки на природній мові. Перераховані завдання і методи їх рішення складають основу інтенсивних досліджень. Наприклад активні експерименти з суфіксними деревами привели до різкого знижень пам'яті яка необхідна, так що вони стають де-факто стандартом в застосуваннях, пов'язаних з (нестрогим)
пошуком в словниках великих об'ємів. Список прикладів можна продовжити. Розглянемо задачі аналізу рядків, виникаючі при розробці систем обробки текстової інформації. Ми не ставимо за мету дати точні рішення всіх можливих задач, а швидше пропонуємо огляд існуючих алгоритмів, відповідних для подібних системи. Термін аналіз рядків використовується тут в досить загальному сенсі і визначає цілий клас завдань – таких, як локалізація заданих підрядків, виділення довгих співпадаючих підрядків двох рядків, обчислення відстані між двома рядками і т.д. Перш за все зовсім у загальних рисах описується проблема, потім приводяться точні формулювання. Обговорюються алгоритми аналізу рядків, порівнюються їх можливості і ефективність. Після цього йде опис основних алгоритмів. Нарешті, розглядається застосування цих алгоритмів в пропонованій системі.
10. Стрічки.1 Стрічки змінної довжини2. 1 Н. Вірт Алгоритми + Структури Даних = Програми 2 И.В. Романовский Дискретный анализ. СПб.: Невский диалект; 2003. – 30 с. Ил. Стр. 87 10.1. Стрічки, списки, послідовності
В багатьох розділах математики (неожиданно во многих) в якості об’єкта дослідження розглядається кінцева послідовність однотипових елементів. На відміну від багатомірніх векторів (или, в программистском понимании, массивов) в таких випадках довжина послідовності може варьювати, і в операціях з последовним доступом до елементу за номером рахується або неможливим, або затруднительным. В якості прикладів таких послідовностей можно назвати набір коефіціентів багаточлена в математичному аналізі, послідовність вершин багагранника або контура в геометрії, список ненульових елементів разреженного вектора або матриці в лінійній алгебрі, ланцюговий список в програмуванні, слово, стрічку тексту, сам текст або послідовність текстів в багатьох розділах сучасної інформатики. В чому відмінність понять "стрічка", "послідовність", "ланцюговий список"? По-перше, в деталях їх представлення, по-друге, в діях що дозволені. Кажучі про послідовності, ми розглядаемо насамперед порядок в деякій множині об’єктів. Можно сказати так: послідовність — це відображення відрізка натурального ряду 1 : k в деяку множину A; це відображення створює набір нумерованих елементів А: а1, а2, ..., аk, в якому (на відміну від множини) один і той самий елемент може з’являтися декілько разів. Ланцюговий список — понятие суто програмістичне. Це спосіб організації множинних даних, що складаються з послідовності однотипових елементів, причому для організації порядка цих елементів використовуються зв’язкі між цими елементами: одностороні, якщо кожний елемент "пам’ятає" наступний за ним (а останній пам’ятаєт, що він останній), або двустороній, якщо кожний елемент пам’ятає і наступний за ним, і попередній елемент.
Ланцюгові списки дуже популярні в програмуванні і часто будут встречаться в этом курсе. Стрічка займає проміжне місце між "чисто математичною" послідовністтю і "чисто програмістичним" ланцюговим списком. В стрічці є суто прикладний зміст — "стрічка текста". В такому розумінні стрічка математично представляє собою послідовність деяких елементів, "букв", а програмістично — відрізок пам’яті, "одномірний масив". Для стрічок характерно поєднання властивостей масива, наприклад доступ до букви за її номером в послідовності, і властивість ланцюгового списку, наприклад можливість змінни її розміру. Ми будемо використовувати в основному термін "стрічка" який наибільше підходить, а вимоги до об’єкту будуть мінятися у мірі викладу. Почнемо з задач, для яких характерно використання рекурсії. Рекурсія основана заснована на можливості розділення рядка на перший елемент і залишок, який розглядається як така сама стрічка, але меньшої довжени. Функції і операції, що визначаються для таких об’єктів, володіють деякою специфікою, яку ми і маємо намір тут обговорити. Почнемо з визначень, що відносяться до рядків з елементів довільного типу. Не дивлячись на цю довільність, називати ми їх будемо для простоти буквами.
Наука, яка визначає правила про зміну слів та сполучення їх у реченні, називається граматикою.
Граматика складається з двох частин: морфології та синтаксису.
Морфологія вивчає правила будови і зміни слів. Синтаксис вивчає правила сполучення слів у реченні.
10.2. Операції над стрічками
Нехай задана деяка кінцева множина А, яка буде називатися алфавітом, а його елементи — буквами. Довільна кінцева послідовність
букв називаеться стрічкою, а кількість букв в цій послідовності — довжиною стрічки. Послідовність нульової довжини називається пустою стрічкою. 1. Знаходження довжини стрічки (Length). Найпростіша операція. Її трудомісткість істотно залежить від форми представлення стрічки в даному алгоритмі або програмній системі: у одних випадках довжина записана в даних про стрічку явно, і тоді трудомісткість, як то кажуть, "константна", а в інших її доводиться рахувати, і трудомісткість "лінійна" - пропорційна самій довжині. В деяких випадках доводиться визначати ширину стрічки як суму ширини букв. Довелося узяти інший термін, оскільки змінився додаток: ширина рядка потрібна при її зображенні на папері або на екрані. 2. Виділення підстрічки (Copy). Операція виділяє підстрічку із заданим числом букв починаючи із заданого місця (вона така важлива, що включена майже у всі сучасні мови програмування). Іноді особливо визначаються операції для виділення підстрічки на початку або в кінці стрічки. Початкова підстрічка стрічки називається її префіксом, а кінцева - її суфіксом. Префікс з однієї букви назвемо головою стрічки (head), а частину стрічки, що залишилася, - її хвостом (tail). Операції виділення голови і хвоста стрічки s позначимо, відповідно, через head s і tail s. 3. Конкатенація стрічок (Insert). З'єднання двох стрічок в одну об’єднанням, одна після іншої. Іноді використовуються терміни катенація і зчеплення. Ця операція всім добре відома. 4. Обернення стрічки. Така природна операція! Я її тільки унаслідок природності і згадую, але жодного разу не зустрічав її використання, хоча звернення ланцюгових списків використовувати доводилося. Обернення стрічки виконується циклом з послідовних "відчеплень" голови початкового списку і "причіплювань" цього елементу як голова списку-результату.
Спільна частина всіх споріднених слів називається коренем. Суфіксом називається частина основи похідного слова, яка стоїть після кореня і надає слову додаткового або нового значення. Префіксом називається частина основи похідного слова, яка стоїть перед коренем і надає слову додаткового або нового значення
5. Порівняння стрічки по передуванню. Операція використовується для завдання впорядкування стрічок. Як правило, використовується лексикографічне порівняння стрічок, засноване на впорядкуванні букв. Нехай букви алфавіту А можна порівнювати (на алфавіті "задано відношення порядку") і про будь-які дві можна сказати, яка з них повинна стояти в цьому порядку раніше. Використовуючи операцію порівняння букв, ми можемо визначити результат порівняння рядків а і b як a = b, якщо обидва рядки порожні, а < b, якщо стрічка а пуста, а b ні, b < a, якщо стрічка b пуста, а а ні, а < b, якщо head а передує head b, b < a, якщо head Ь передує head a, результатом порівняння tail а і tail b, якщо head a — head b. Сформульоване правило порівняння зручне формально, але для сприйняття "людини" варто визначити його по-іншому: щоб порівняти дві стрічки .1 і .2 потрібно відкинути у них співпадаючі початки і порівняти залишки t1 і t2. Якщо один із залишків порожній, то відповідна йому стрічка повина стояти раніше. Інакше результат порівняння визначається першими елементами залишків. Приклад. При порівнянні слів колекціонер() і колектив відкидаються співпадаючи частини залищаючи ціонер и тив; у зв’язку з тим що буква т є попередньою букві ц, то слово колектив розміщається перед словом колекціонер. При порівнянні слов класти і клас відкидаються співпадаючи частини залишаючи ти і пусте слово; що відповідає пустому залишку, слово клас предшествует слову класти.
6. Пошук зразка в стрічці (Pos). Ця операція дуже важлива при комп'ютерній обробці текстів, з нею добре знайомі всі, хто працював з яким-небудь текстовим редактором: є видимий текст (його можна розглядати як один великий рядок) і в ньому розшукується заданий підрядок - зразок. 7. Підстановка. У текстових редакторах підстановка завжди є сусідами з пошуком за зразком, знайдений зразок часто потрібно замінити другим. Тут нам нічого сказати, крім того, що така операція існує. Головні хитрощі, пов'язані з нею, відносяться до способу зберігання текстів в комп'ютері, який повинен забезпечувати просте багатократне виправлення тексту. 8. Перетворення. Цю дію можна розглядати як математичний розвиток "текстової" підстановки: задається відображення елементів стрічки-аргументу в деяку множину В, а далі є видимим стрічка і кожному її елементу зіставляється в образі стрічки образ цього елементу. Але не зовсім так: по-перше, при підстановці задається часткове відображення, і тексти, яким у відображенні нічого не відповідає, залишаються без змін. По-друге, при підстановці один фрагмент тексту замінюється іншим, а слово перетворення подразумеваєт заміну елементу на елемент. Зрозуміло, можливі і використовуються численні проміжні форми підстановок- перетворень. 9. Фільтрація. Це ще одна операція з того ж сімейства. Всі символи діляться на дві підмножини, елементи одного залишаються без змін, елементи іншого виключаються з стрічки. Наприклад, розглядається послідовність натуральних чисел, і з неї відбираються тільки прості числа. 10. Злиття. Це операція з декількома аргументами (частіше всього з двома). Вона характерна скоріше для послідовностей, а не для суцільних рядків. Її важливою особливістю є одночасний перегляд двох списків для отримання з них одного (злитого) списку. Хай на безлічі елементів списків (алфавіті) заданий порядок. В ході операції порівнюються початкові елементи списків, і менший з них записується в результат, віддаляючись з свого списку.
11. Пошук максимального співпадіння. Хай задано два списки а[1:m] і b[1:n] над одним алфавітом, і на алфавіті визначений порядок. Потрібно знайти такі монотонно зростаючі послідовності індексів i1, ..., is, і j1 ..., js, щоб 1 . i1, is . m, 1 . j1, js . n, a[ik] = b[jk] для будь-якого k Є 1:s і довжина цих послідовностей s була б максимальна. Потреба в такій операції виникає, наприклад, коли потрібно скласти список поправок до зміненого текстового файлу, - старий і новий файли є два списки, а рядки тексту виступають як елементи наших списків. У параграфі 4.6 ми розглянемо алгоритм пошуку такої пари послідовностей, що має трудомісткість порядку O(mn). На нім буде зручно показати техніку роботи із списками як допоміжним засобом.
10.3. Логічна структура стрічки. Стрічки - це лінійно впорядкована послідовність символів, символів, що належать кінцевій множині, яка називається алфавітом. Стрічка мають наступні важливі властивості: їх довжина, як правило, змінна, хоча алфавіт фіксований; звернення до символів стрічки йде з будь-якого боку послідовності, тим самим важлива впорядкованість цієї послідовності, а не її індексація; у зв'язку з цим властивістю стрічки часто називають також ланцюжками; найчастіше метою доступу до стрічки є не окремий її елемент (хоча це теж не виключається), а деякий ланцюжок символів в рядку. Кажучи про стрічки, маємо на увазі текстові стрічки - стрічки, що складаються з символів, що входять в алфавіт деякої(якої-небудь) вибраної мови, цифр, розділового і інших службових символів знаків. Текстова стрічка є найбільш універсальною формою представлення будь-якої інформації. Відзначимо, що залежно від особливості завдання, властивостей алфавіту і мови яка використовується, що представляється ним, і властивостей носіїв інформації можуть застосовуватися і інші способи
кодування символів. У сучасних обчислювальних системах, прийняте кодування всієї безлічі символів на розрядній сітці фіксованого розміру (2 байт). Основні операції над рядками реалізовані як прості операції або вбудовані функції. Можливі також бібліотеки, що забезпечують розширений набір рядкових операцій.
Додатково
1.5. Функція складності алгоритму Для вирішення багатьох проблем існує безліч різних алгоритмів. Який з них вибрати для вирішення конкретного завдання? Це питання дуже ретельно опрацьовується в програмуванні. Ефективність програми є дуже важливою її характеристикою. Ефективність програми має дві складові: пам'ять (або простір) і час. Просторова ефективність вимірюється кількістю пам'яті, потрібної для виконання програми. Комп'ютери володіють обмеженим об'ємом пам'яті. Якщо дві програми реалізують ідентичні функції, то та, яка використовує менший об'єм пам'яті, характеризується більшою просторовою ефективністю. Іноді пам'ять стає домінуючим чинником в оцінці ефективності програм. Проте останніми роками у зв'язку з швидким її здешевленням ця складова ефективності поступово втрачає своє значення. Тимчасова ефективність програми визначається часом, необхідним для її виконання. Кращий спосіб порівняння эффективностей алгоритмів полягає в зіставленні їх порядків складності. Цей метод застосовний як до тимчасової, так і просторовій складності. Порядок складності алгоритму виражає його ефективність зазвичай через кількість оброблюваних даних. Наприклад, деякий алгоритм може істотно залежати від розміру оброблюваного масиву. Якщо, скажімо, час обробки подвоюється з подвоєнням розміру масиву, то порядок тимчасової складності алгоритму визначається як розмір масиву. Порядок алгоритму — це функція, домінуюча над точним виразом тимчасовій складності. Функція f(n) має порядок 0(g(n)), якщо є константа K і лічильник n0 такі,
що f(n)(K*g(n)) для n>n0. Наприклад: відомо, що точний час обробки масиву визначається з рівняння:
Дійсний час (довжина масиву) = = Довжина масиву2 + 5*Длина масиву + 100. Грубе значення визначається допоміжною функцією: Оцінка часу (довжина масиву) = 1,1*Довжина масиву2 . Функція складності O виражає відносну швидкість алгоритму залежно від деякої змінної (або змінних). Існують три важливих правила для визначення функції складності: 1. O(к*f)= O(f). 2. O(f*g) = O(f)*O(g) або O(f/g)= O(f) /O(g). 3. O(f+g) рівна домінанті O(f) і O(g). Тут до позначає константу, f і g — функції. Перше правило декларує, що постійні множники не мають значення для визначення порядку складності O(1,5*N)=O(N). З другого правила виходить, що порядок складності множення двох функцій дорівнює множенню їх складнощів O((17*N)*N)= O(17*N)*O(N) = O(N)*O(N) = O(N*N)= O(N2). З третього правила виходить, що порядок складності суми функцій визначається як порядок домінанти першого і другого доданків, тобто вибирається найбільший порядок O(N5 + N2) = O(N5). 1.5.1. ВИДИ функції складності алгоритмів O(1) У алгоритмах константної складності більшість операцій в програмі виконуються один або кілька разів. Будь-який алгоритм, що завжди вимагає незалежно від розміру даних одного і того ж часу, має константну складність. O(N)
Час роботи програми лінійний, зазвичай коли кожен елемент вхідних даних потрібно обробити лише лінійне число разів. O(N2), O(N3), O(Na) Поліноміальна складність. O(N2) — квадратична складність, O(N3) — кубічна складність O(Log(N)) Коли час роботи програми логарифмічний, програма починає працювати набагато повільніше із збільшенням N. Такий час роботи зустрічається зазвичай в програмах, які ділять велику проблему на маленьких і вирішують їх окремо. O(N*log(N)) Такий час роботи мають ті алгоритми, які ділять велику проблему на маленькі, а потім, вирішивши їх, об’єднують їх рішення. O(2N) Експоненціальна складність. Такі алгоритми найчастіше виникають в результаті підходу, що називаються - “методом грубої сили”. 1.5.2. Часова функція складності Програміст повинен уміти проводити аналіз алгоритмів і визначати їх складність. Тимчасова складність алгоритму може бути підрахована виходячи з аналізу його структур, що управляють. Вид структури, що управляє Складність Привласнення ... O( 1) Простий вираз ... O(1) S1; ... Домінанта для O(Обчис1) і S2 ... O(Обчис2) IF Умова THEN ... Домінанта для S1 O(Обчис1) і О(Обчис2) і ELSE О(ОбчисУмов) S2 (* це якнайгірший випадок *) FOR I:=l ТЕ N DO ... O( N * Обчис1)
S1 END Зауваження. О(Обчис1), О(Обчис2) і О(ОбчисУмов) позначають відповідно складність обчислення для SI, S2 і для Умова. Алгоритми без циклів і рекурсивних викликів мають константну складність. Якщо немає рекурсії і циклів, всі структури, що управляють, можуть бути зведені до структур константної складності. Отже, і весь алгоритм також характеризується константною складністю. Визначення складності алгоритму в основному зводиться до аналізу циклів і рекурсивних викликів. Наприклад, розглянемо алгоритм обробки елементів масиву. For i:=1 to N do Begin ... End; Складність цього алгоритму O(N), оскільки тіло циклу виконується N разів, і складність тіла циклу рівна O(1). Якщо один цикл вкладений в інший і обидва цикли залежать від розміру однієї і тієї ж змінної, то вся конструкція характеризується квадратичною складністю. For i:=1 to N do For j:=1 to N do Begin ... End; Складність цієї програми — O(N2). 1.5.3. Аналіз функції складності за програмою
Оцінимо складність програми «Трійки Піфагора» (мал. 1.26). Існують два способи аналізу складності алгоритму: висхідний (від внутрішніх структур, що управляють, до зовнішніх) і низхідний (від зовнішніх до внутрішніх). 0(H)= 0(1)+ 0(1)+0(1)=0(1); 0(I)= 0(N)*(0(F)+ 0(J)) = 0(N)*0 (домінанти умови) = 0(N); 0(G) = 0(N)*(0(C) + 0(I)+ 0(K)) = 0(N)*(0(l)+ 0(N) + + 0(1)) = 0(N2); 0(E) = 0(N)*(0(B) + 0(G) + 0(L)) = 0(N)*0(N2) = 0(N3); 0(D)= 0(A)+ 0(E)= 0(1)+ 0(N3)= 0(N3) Таким чином, складність даного алгоритму — 0(N3). Як правило, близько 90% часу роботи програми вимагає виконання повторень і лише 10% складають безпосередньо
Writeln('Bвести обмеження'); A Readln(N); small:=l; While small < N do begin B {next:=small; While next <= N do Begin C { last:=next; While last<=N do Begin D if (last<=small*2) and (next<=small*2) and (last*last=small*small-next*next) then E G begin I F writeln(small); H writeln(next); writeln(last); end; J { inc(last); end; K { inc(next); end; L { inc(small); end;
Мал. 1.26. Програма «Трійки Піфагора» обчислення. Аналіз складності програм показує, на які фрагменти випадають ці 90 % — це цикли найбільшої глибини вкладеності. Повторення можуть бути організовані у вигляді вкладених циклів або вкладеної рекурсії. Ця інформація може використовуватися програмістом для побудови ефективнішої програми таким чином. Перш за все можна спробувати скоротити глибину вкладеності повторень. Потім слід розглянути можливість скорочення кількості операторів в циклах з найбільшою глибиною вкладеності. Якщо 90 % часу виконання складає виконання внутрішніх циклів, то 30 %-ве скорочення цих невеликих секцій приводить до 27 %-ому зниженню часу виконання всієї програми.
1.5.4. Оцінка алгоритму бінарного пошуку
Проведемо оцінку алгоритму бінарного пошуку в масиві. function search(low, high, key: integer): integer; var mid, data: integer; begin while low<=high do begin mid:=(low+high) div 2; data:=a[mid]; if key=data then search:=mid else if key < data then high:=mid-1 else low:=mid+1; end; search:=-1; end;
Перша ітерація циклу має справу зі всім списком. Кожна подальша ітерація ділить навпіл розмір масиву. Так, розмірами списку для алгоритму є n n/21 n/22 n/23 n/24 ... n/2n. Врешті-решт буде таке ціле n, що n/2m<2 або n< 2m + 1 Оскільки n — це перше ціле, для якого n/2m<2, то повинно бути вірно n/2m-1>=2 або 2m<=n. З цього виходить, що 2m<=n<2m + 1. Візьмемо логарифм кожної частини нерівності і отримаємо m<= log2n < m + 1.
Звідси, O(log2n).
1.5.5. Теоретична і практична функції складності Функція f(n) у ряді випадків може мати достатньо складну (навіть громіздку) аналітичну форму. Оскільки для тимчасової теоретичної складності більше значення має не стільки вид функції, скільки порядок її зростання, то в багатьох математичних дисциплінах, у тому числі і в теорії алгоритмів, функцию f(n) визначають як O(g(n)) і кажуть, що вона порядку g(n) для великих n, якщо lim f(n)/g(n)= const . 0 де f(n) і g(n) — експериментальна і теоретична функції складності. Приклад. Визначити функцію складності алгоритму за наслідками експерименту:
N Кількість порівнянь 6 54
де N — кількість початкових даних в алгоритмі. Рішення. Спочатку знайдемо експериментальну функцію складності (Ое). Експериментальна функція складності алгоритму приймає наступний ряд значень: an an log2n an2 an3 аеn an! -----------------------------------------------------> Експериментальна функція а) допустимий Ое = an, тоді an = 54; 6а = 54; a=54/6 — (не задовольняє умові 1 <= а <= 2).
При а = 1 значення експериментальної функції співпадає із значенням теоретичної функції складності;
б) допустимий Ое = an log2 n, тоді an log2 n= 54; аn log2 6= 54; 54 9 а = ------ =------ (а > 2 — не задовольняє умові); 6log2 6 log2 6 в) допустимий Ое = an2, тоді an2 = 54; а36= 54; 54 а = ------- = 1,5 (а < 2 — задовольняє умові). 36 Таким чином, експериментальна функція складності має вид Oe(1,5n2). Знайдемо теоретичну функцію складності lim Oe(n) /Om(n) = const . 0; lim 1.5n2/X = const . 0; lim 1.5n2/n2 = const . 0; Звідси, теоретична функція складності — 0(n2).
