ПЕРЕЛІК ДИСЦИПЛІН:
  • Адміністративне право
  • Арбітражний процес
  • Архітектура
  • Астрологія
  • Астрономія
  • Банківська справа
  • Безпека життєдіяльності
  • Біографії
  • Біологія
  • Біологія і хімія
  • Ботаніка та сільське гос-во
  • Бухгалтерський облік і аудит
  • Валютні відносини
  • Ветеринарія
  • Військова кафедра
  • Географія
  • Геодезія
  • Геологія
  • Етика
  • Держава і право
  • Цивільне право і процес
  • Діловодство
  • Гроші та кредит
  • Природничі науки
  • Журналістика
  • Екологія
  • Видавнича справа та поліграфія
  • Інвестиції
  • Іноземна мова
  • Інформатика
  • Інформатика, програмування
  • Юрист по наследству
  • Історичні особистості
  • Історія
  • Історія техніки
  • Кибернетика
  • Комунікації і зв'язок
  • Комп'ютерні науки
  • Косметологія
  • Короткий зміст творів
  • Криміналістика
  • Кримінологія
  • Криптология
  • Кулінарія
  • Культура і мистецтво
  • Культурологія
  • Російська література
  • Література і російська мова
  • Логіка
  • Логістика
  • Маркетинг
  • Математика
  • Медицина, здоров'я
  • Медичні науки
  • Міжнародне публічне право
  • Міжнародне приватне право
  • Міжнародні відносини
  • Менеджмент
  • Металургія
  • Москвоведение
  • Мовознавство
  • Музика
  • Муніципальне право
  • Податки, оподаткування
  •  
    Бесплатные рефераты
     

     

     

     

     

     

         
     
    Алгоритм Кнута - Морріса - Пратта
         

     

    Інформатика, програмування

    Алгоритм Кнута - Морріса - Пратта

    Реферат

    Алгоритм Кнута-Моріса-Пратта (КМП) одержує на вхід слово

    X = x [1] x [2] ... x [n]

    і переглядає його зліва направо буква за буквою, заповнюючи при це масив натуральних чисел l [1] ... l [n], де

    l [i] = длина слова l (x [1] ... х [i])

    (функція l визначена в попередньому пункті). Словами: l [i] є довжина найбільшого початку слова x [1] ... x [i], одночасно є його кінцем.

    Яке відношення все це має до пошуку подслова?

    Іншими словами, як використовувати алгоритм КМП для визначення того, чи є слово A подсловом слова B?

    Рішення. Застосуємо алгоритм КМП до слова A # B, де # - спеціальна буква, не зустрічається ні в A, ні в B. Слово A є подсловом слова B тоді і тільки тоді, коли серед чисел в масиві l буде число, яке дорівнює довжині слова A.

    Описати алгоритм заповнення таблиці l [1] ... l [n].

    Рішення. Припустимо, що перший i значень l [1] ... l [i] вже знайдені. Ми читаємо чергову літеру слова (тобто x [i +1]) і повинні обчислити l [i +1].

    Іншими словами, нас цікавлять початку Z слова

    x [1] ... x [i +1,

    що одночасно є його кінцями-з них нам треба брати саме довге. Звідки беруться ці початку? Кожне з них (не рахуючи порожнього) виходить з деякого слова Z 'приписуванням букви x [i +1]. Слово Z ' є початком і

    кінцем слова x [1] ... x [i]. Однак не будь-яке слово, яке є початком і кінцем слова x [1] ... x [i], годиться - треба, щоб за ним слідувала буква x [i +1].

    Отримуємо такий рецепт відшукання слова Z. Розглянемо всі початку слова x [1] ... x [i], що є одночасно його кінцями. З них виберемо підходящі - ті, за якими йде буква x [i +1]. З відповідних виберемо саме довге. Приписавши в його кінець х [i +1], отримаємо шукане слово Z. Тепер пора скористатися зробленими нами приготуваннями і згадати, що всі слова, що є одночасно початками і кінцями даного слова, можна отримати повторними застосуваннями до нього функції l з попереднього розділу.

    Ось що виходить:

    i: = 1; 1 [1]: = 0;

    (таблиця l [1] .. l [i] заповнена правильно)

    while i <> n do begin

    len: = l [i]

    (len - довжина початку слова x [1] .. x [i], яке є

    його кінцем; дедалі довші початку виявилися

    невідповідними)

    while (x [len +1] <> х [i +1]) and (len> 0) do begin

    (початок не підходить, застосовуємо до нього функцію l)

    len: = l [len];

    end;

    (знайшли підходяще або переконалися у відсутності)

    if x [len +1] = x [i +1] do begin

    (х [1] .. x [len] - найдовше підходяще початок)

    l [i +1]: = len +1;

    end else begin

    (відповідних немає)

    l [i +1]: = 0;

    end;

    i: = i +1;

    end;

    Довести, що число дій у наведеному тільки що алгоритм не перевершує Cn для деякої константи C.

    Рішення. Це не цілком очевидно: обробка кожної чергової букви може зажадати багатьох ітерацій у внутрішньому циклі. Однак кожна така ітерація зменшує len принаймні на 1, і в цьому випадку l [i +1] виявиться помітно менше l [i]. З іншого боку, при збільшенні i на одиницю величина l [i] може зрости не більше ніж на 1, так що часто і сильно спадати вона не може - інакше спадання не буде скомпенсовано зростанням.

    Більш точно, можна записати нерівність

    l [i +1]

    або

    (число ітерацій на i-му кроці) <= l [i]-l [i +1] 1

    Залишається скласти ці нерівності по всіх i і отримати оцінку

    зверху для загального числа ітерацій.

    Будемо використовувати цей алгоритм, щоб з'ясувати, чи є слово X довжини n подсловом слова Y довжини m. (Як це робити за допомогою спеціального роздільник #, описано вище.) При цьому число дій буде не більш C (n + m), і використовувана пам'ять теж. Придумати, як обійтися пам'яттю не більше Cn (що може бути істотно менше, якщо шуканий зразок короткий, а слово, в якому його шукають - довге).

    Рішення. Застосовуємо алгоритм КМП до слова А # В. При цьому: обчислення значень l [1 ],..., l [n] проводимо для слова X довжини n і запам'ятовуємо ці значення. Далі ми пам'ятаємо тільки значення l [i] для поточного i - окрім нього і крім таблиці

    l [1] ... l [n], нам для обчислень нічого не потрібно.

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

    Написати відповідний алгоритм (перевіряє, чи є слово X = x [1] ... x [n] подсловом слова Y = y [1] ... y [m]

    Рішення. Спочатку обчислюємо таблицю l [1] ... l [n] як раніше. Потім пишемо таку програму:

    j: = 0; len: = 0;

    (len - довжина максимального хитала слова X, одночасно

    що є кінцем слова y [1] .. j [j])

    while (len <> n) and (j <> m) do begin

    while (x [len +1] <> у [j +1]) and (len> 0) do begin

    (початок не підходить, застосовуємо до нього функцію l)

    len: = l [len];

    end;

    (знайшли підходяще або переконалися у відсутності)

    if x [len +1] = y [j +1] do begin

    (x [1] .. x [len] - найдовше підходяще початок)

    len: len = 1;

    end else begin

    (відповідних немає)

    len: = 0;

    end;

    j: = j +1;

    end;

    (якщо len = n, слово X зустрілося; інакше ми дійшли до кінця

    слова Y, так і не зустрівши X)

    Алгоритм Бойєр - Мура

    Цей алгоритм робить те, що на перший погляд здається неможливим: в типовій ситуації він читає лише невелику частину всіх літер слова, в якому шукається заданий зразок. Як так може бути? Ідея проста. Нехай, наприклад, ми шукаємо зразок abcd. Подивимося на четверту букву слова: якщо, приміром, це буква e, то немає ніякої необхідності читати перші три букви. (Насправді, в зразку букви e немає, тому він може початися не раніше п'ятого літери.)

    Ми наведемо найпростіший варіант цього алгоритму, який не гарантує швидкої роботи у всіх випадках. Нехай x [1] ... х [n] - зразок, який треба шукати. Для кожного символу s знайдемо саме праве його входження в слово X, тобто найбільшу k, при якому х [k] = s. Ці відомості будемо зберігати в масиві pos [s]; якщо символ s зовсім не зустрічається, то нам буде зручно покласти pos [s] = 0 (ми побачимо далі, чому).

    Як заповнити масив pos?

    Рішення.

    покласти всі pos [s] рівними 0

    for i: = 1 to n do begin

    pos [x [i]]: = i;

    end;

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

    last: = n;

    (всі попередні положення зразка вже перевірені)

    while last <= m do begin (слово не скінчилося)

    if x [m] <> y [last] then begin (останні букви різні)

    last: = last + (n-pos [y [last ]]);

    (n - pos [y [last]] - це мінімальний зсув зразка,

    при якому навпроти y [last] постане така ж

    буква в зразку. Якщо такої літери немає взагалі,

    то зсувається на всю довжину зразка)

    end else begin

    якщо нинішній стан підходить, тобто якщо

    x [i] .. х [n] = y [last-n +1] .. y [last],

    то повідомити про збіг;

    last: = last 1;

    end;

    end;

    Знавці рекомендують перевірку збігу проводити справа наліво, тобто починаючи з останньої букви зразка (у якій збіг завідомо є). Можна також трохи заощадити, зробивши віднімання заздалегідь і зберігають не pos [s], а n-pos [s],

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

    last: = last + i

    замінити на

    last: = last + (n-u),

    де u - координата другий праворуч входження букви x [n] в зразок.

    Як простіше за все врахувати це у програмі

    Рішення. При побудові таблиці pos написати

    for i: = 1 to n-1 do ...

    (далі як раніше), а в основній програмі замість

    last: = last 1

    написати

    last: = last + n-pos [y [last ]];

    Наведений спрощений варіант алгоритму Бойєр-Мура в деяких випадках вимагає істотно більше n дій (число дій порядку mn), програючи алгоритму Кнута-Моріса-Пратта.

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

    Рішення. Нехай зразок має вигляд baaa ... aa, а саме слово складається тільки з літер а. Тоді на кожному кроці невідповідність з'ясовується лише в останній момент.

    Справжній (не спрощений) алгоритм Бойєр-Мура гарантує, що число дій не перевершує C (m + n) в гіршому випадку. Він використовує ідеї, близькі до ідей алгоритму Кнута-Моріса-Пратта. Уявімо собі, що ми порівнювали зразок з вхідним словом, йдучи справа наліво. При цьому деякий шматок Z (який є кінцем зразка) збігся, а потім виявилося відмінність: перед Z у зразку варто не те, що у вхідному слові. Що можна сказати на цей момент про вхідному слові? У ньому виявлений фрагмент, рівний Z, а перед ним стоїть не та буква, що у зразку. Ця інформація може дозволити зрушити зразок на декілька позицій праворуч без ризику пропустити його входження. Ці зрушення слід вирахувати заздалегідь для кожного кінця Z нашого зразка. Як кажуть знавці, все це (обчислення таблиці зрушень та її використання) можна укласти в C (m + n) дій.

    Алгоритм Рабіна

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

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

    Привести приклад зручною для обчислення функції.

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

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

    Привести приклад сімейства зручних функцій.

    Рішення. Виберемо деякий число p (бажано просте, дивись далі) і деякий вирахування x за модулем p. Кожне слово довжини n будемо розглядати як послідовність цілих чисел (замінивши літери кодами). Ці числа будемо розглядати як коефіцієнти многочлена мірою n-1 і обчислимо значення цього многочлена за модулем p в точці x. Це і буде одна з функцій сімейства (для кожної пари p і x виходить, таким чином, своя функція). Зрушення віконця на 1 відповідає вирахуванню старшого члена (хn-1 слід вирахувати заздалегідь), множення на x і додаванню вільного члена.

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

    Список літератури

    Для підготовки даної роботи були використані матеріали з сайту http://www.monax.ru/

         
     
         
    Реферат Банк
     
    Рефераты
     
    Бесплатные рефераты
     

     

     

     

     

     

     

     
     
     
      Все права защищены. Reff.net.ua - українські реферати ! DMCA.com Protection Status