Алгоритм Z для пошуку шаблонів у рядках

Що вимірює масив Z

Для рядка S довжиною n, масив Z також має довжину n, і кожен елемент Z[i] визначається відносно всього рядка S, починаючи з першого символу. Конкретно, Z[i] дорівнює довжині найдовшого загального префікса між самим рядком S та суфіксом рядка S, що починається з позиції i. Простіше кажучи: почніть порівнювати S від початку проти S, починаючи з позиції i, порахуйте скільки символів співпадає до першої невідповідності, і цей рахунок є Z[i]. Позиція 0 є особливим випадком і зазвичай залишається невизначеною або встановлюється рівною n, оскільки порівняння S з самим собою безпосередньо повністю співпадає; цікава інформація міститься в позиціях від 1 до n-1. Розглянемо рядок abcabcabx. З позиції 3 суфікс є abcabx, і порівнюючи його з повним рядком від початку, отримуємо відповідність abc до появи невідповідності, тому Z[3] дорівнює 3. З позиції 6 суфікс є abx, який співпадає лише з ab проти префікса, даючи Z[6] = 2. З позиції 1 суфікс bcabcabx не має спільних символів із префіксом, починаючи з a, тому Z[1] = 0. Переглядаючи кожну позицію, отримуємо повний профіль того, наскільки строка самоподібна на кожному зміщення, що є точною інформацією, необхідною пізніше для пошуку шаблонів. Варто розглядати масив Z як відповідь на кожен початок рядка питання: наскільки це схоже на початок всюди? Рядки з сильною внутрішньою повторністю, такі як aaaaa або abcabcabc, виробляють масиви Z з великими, структурованими значеннями, тоді як рядки з малою внутрішньою повторністю виробляють масиви Z, що складаються переважно з нулів і малих чисел. Розуміння цього визначення є важливим, оскільки вся техніка лінійного часу залежить від міркувань про перекриваючись інтервали зіподібних символів, а не від повторного обчислення кожного елемента з нуля за допомогою грубого порівняння.

Непрямий підхід і чому він не виправдовується

Найбільш прямий спосіб обчислення Z-масиву – це перебір кожної стартової позиції *i* від 1 до *n* - 1, а для кожної з них порівнювати символи рядка *S*, починаючи з позиції 0, із символами рядка *S*, що починаються з позиції *i*, рахуючи відповідності до тих пір, поки не виникне розбіжність або рядок не закінчиться. Це абсолютно працює і дає правильний Z-масив, але його вартість може бути квадратичною в найгіршому випадку. Уявіть рядковий символ, який складається повністю з однакових повторюваних символів, наприклад, aaaaaaaaaa. На позиції 1 порівняння майже досягає кінця рядка до того, як знайдеться розбіжність, оскільки все відповідає. На позиції 2 такий же довгий процес повторюється знову, і так далі для кожної стартової позиції. Загальна робота стає пропорційною *n* у квадраті, що набагато занадто повільно для довгих рядків, таких як послідовності геному, журнали логів або великі документи, де *n* може сягати мільйонів. Розчаровуючий момент полягає в тому, що вся ця повторювана робота порівняння є у певному сенсі марною, оскільки порівняння, які виконуються під час обчислення Z для 1, вже розкривають багато інформації про те, що станеться при обчисленні Z для 2, Z для 3 і далі. Якщо рядок збігається з префіксом на довгий відрізок, починаючи з позиції 1, цей відрізок сам є підрядком *S*, а його внутрішня структура вже була захоплена попередніми значеннями Z, обчисленими для позицій у межах цього відрізка. Непрямий алгоритм викидає цю інформацію і починає порівнювати кожен символ з нуля, починаючи з позиції 0.

Z-Box: Перевикористання роботи за допомогою зсувного вікна

Лінійний метод часу підтримує два покажчики, які зазвичай називаються L і R, які разом визначають те, що називається Z-box — інтервал від L до R, який представляє собою найправіший фрагмент рядка, який відповідає префіксу S, виявлений під час обчислення ранішої Z-значення. Під час сканування позицій зліва направо алгоритм підтримує L і R, щоб завжди відображати найправіший знайдений фрагмент відповідності. При обчисленні Z для i є дві випадки. Якщо i знаходиться поза поточною Z-box, тобто i знаходиться за межами R, немає можливості використати прискорення, тому алгоритм повертається до безпосереднього порівняння символів від позиції 0, точно так само як і у наївний метод, і якщо це дає не нульову довжину відповідності, L і R оновлюються, щоб відобразити цей новий, більш широкий Z-box. Другий випадок — розумний: якщо i падає всередині існуючого Z-box, тобто L менше або дорівнює i та i менше або дорівнює R, тоді позиція i відповідає певній позиції k всередині префікса, зокрема k дорівнює i - L, оскільки підрядок від L до R вже відомий як префікс тієї ж довжини. Це означає, що значення Z для k, яке було обчислене раніше, оскільки k менше i, надає сильної інформації про Z для i без будь-яких нових порівнянь. Якщо Z для k суворіше ніж відстань до R, тобто відповідність у позиції k безпечно закінчилася перед зустрічем із межею, то Z для i можна просто скопіювати без необхідності в будь-якому порівнянні. Але якщо Z для k досягає або перевищує цю відстань, алгоритм не може бути впевнений, що відповідність продовжується за межами меж Z-box, оскільки немає інформації про символи за межею Z-box, тому потрібно розширити порівняння починаючи точно з позиції R + 1, перевіряючи лише нові, раніше невидимі символи, а потім відповідно оновлювати L і R. Це правило — повторно використовувати те, що довело Z-box, та перевіряти лише невизначений залишок — це те, що зменшує загальну роботу по всьому скану до лінійного часу: кожен символ бере участь у не більше ніж невеликій постійній кількості порівнянь загалом, оскільки R ніколи не рухається назад і ніколи не відхиляється.

Від Z-масиву до пошуку шаблонів у рядках

Для перетворення Z-масиву на повноцінний інструмент для пошуку шаблонів необхідно ще одну ідею: побудову об'єднаного рядка. Враховуючи шаблон P довжиною m та рядок T довжиною n, створити рядок P плюс роздільник плюс T, де роздільник обрано таким чином, щоб він не зустрічався ні в P, ні в T, наприклад, нульовий символ або інший резервний символ, призначений для цього. Обчислити Z-масив цього об'єднаного рядка за допомогою описаної вище лінійного алгоритму. Тепер переглянути кожну позицію i в об’єднаному рядку, яка знаходиться всередині частини тексту (тобто після шаблону та роздільника). Якщо Z[i] дорівнює точно m (довжині шаблону), це означає, що суфікс об'єднаного рядка, починаючи з позиції i, відповідає початковому префіксу об'єднаного рядка, тобто це саме шаблон P, символ за символом. Іншими словами, позиція i позначає початок точного вoccurrence шаблону всередині тексту. Оскільки роздільний символ не може бути присутнім ні в одному з рядків, неможливо, щоб відповідність спонтанно переходила з тексту назад у зону шаблону або випадково включала роздільник, що забезпечує точність відповідності. Оскільки Z-масив об’єднаного рядка довжиною m плюс n плюс 1 будується за лінійним часом відносно власної довжини, а перевірка його елементів, рівних m, також є лінійною, весь процес пошуку шаблонів виконується за час, пропорційний m плюс n, що є значним покращенням порівняно з найгіршим випадком, коли пропорційно m-разово-n. Цей підхід також природним чином повідомляє про кожне вoccurrence, а не лише про перше, оскільки сканування триває по всьому масиву, і він граціозно узагальнюється для пошуку одного й того ж шаблону в різних текстах або для пов’язаних проблем, таких як знаходження найдовшого підрядка, який є префіксом і де іншим чином також присутній всередині одного рядка, або вимірювання самосхожості для завдань, таких як виявлення періодичного повторення.

Z-алгоритм проти KMP: Два шляхи до лінійного часу

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

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте The Z-Algorithm for String Matching і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.