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

Сорт	Алгоритм поиска строк
Структура данных	Любая строка с упорядоченным алфавитом
Худшая производительность	На)
Лучшая производительность	На)
Наихудшая пространственная сложность	⌈log₂ m ⌉

В информатике алгоритм двустороннего сопоставления строк — это алгоритм поиска строк , открытый Максимом Крошмором и Домиником Перреном в 1991 году. Он принимает шаблон размера m , называемый «иголкой», предварительно обрабатывает его за линейное время O ( m ), создавая информацию, которую затем можно использовать для поиска иголки в любой строке «стога сена», занимая только линейное время O( n ), где n — длина стога сена.

Двусторонний алгоритм можно рассматривать как комбинацию прямого алгоритма Кнута – Морриса – Пратта (KMP) и обратного алгоритма поиска строки Бойера – Мура (BM). Как и эти два, двусторонний алгоритм предварительно обрабатывает шаблон, чтобы найти частично повторяющиеся периоды, и на их основе вычисляет «сдвиги», указывая, к какому смещению «перейти» в стоге сена при обнаружении данного символа.

В отличие от BM и KMP, он использует только O (log m ) дополнительного пространства для хранения информации об этих частичных повторах: шаблон поиска разбивается на две части (его критическая факторизация), представленные только позицией этого разделения. Будучи числом меньшим, чем m , оно может быть представлено в ⌈log₂ m ⌉ битах. Иногда это рассматривается как «достаточно близкое к O(1) на практике», поскольку размер иглы ограничен размером адресуемой памяти ; накладные расходы — это число, которое может храниться в одном регистре, и рассматривать его как O(1) — это все равно, что рассматривать размер счетчика цикла как O(1), а не журнал количества итераций. Фактическая операция сопоставления выполняет не более 2 n - m сравнений.

Позже Бреслауер опубликовал два улучшенных варианта, выполняющих меньше сравнений за счет хранения дополнительных данных о предварительно обработанной игле:

• Первый выполняет не более n + ⌊( n − m )/2⌋ сравнений, что на ⌈( n − m )/2⌉ меньше, чем исходный. Однако он должен хранить ⌈log _$\varphi$ m ⌉ дополнительные смещения иглы, используя O(log ² м ) пространство.
• Второй адаптирует его для хранения только постоянного количества таких смещений, обозначенного c , но должен выполнять n + ⌊( 1 ⁄ 2 + ε) * ( n − m )⌋ сравнения, при этом ε = 1 ⁄ 2 ( F _{c +2} - 1) ⁻¹ =О( $\varphi$^{− с} ) экспоненциально быстро стремится к нулю по мере увеличения c .

На практике алгоритм считается довольно эффективным, он удобен для кэша и использует несколько операций, которые можно реализовать в хорошо оптимизированных подпрограммах. Он используется стандартными библиотеками C glibc , newlib и musl для реализации memmem и strstr семейства функций подстроки . Как и в большинстве продвинутых алгоритмов поиска строк, простая реализация может быть более эффективной на достаточно небольших экземплярах; это особенно актуально, если иголка не ищется в нескольких стогах сена, что амортизирует затраты на предварительную обработку.

Критическая факторизация

Прежде чем мы определим критическую факторизацию, мы должны определить:

• Факторизация: строка считается факторизованной, если она разделена на две части. Предположим, строка x разбита на две части (u, v) , тогда (u, v) называется факторизацией x .
• Период : период p для строки x определяется как такое значение, что для любого целого числа 0 < i ≤ len(x) − p , x [ i ] = x [ i + p ] . Другими словами, « p является периодом x , если две буквы x на расстоянии p всегда совпадают». Минимальный период x — это положительное целое число, обозначаемое как p(x) .
• Повторение — w в (u, v) это такая строка, что:
  • w — суффикс слова u или u — суффикс слова w ;
  • w — префикс v или v — префикс w ;

  Другими словами, w возникает по обе стороны от разреза с возможным переливом с обеих сторон. Каждая факторизация тривиально имеет по крайней мере одно повторение — строку vu .

• Локальный период — это длина повторения в (u, v) . Наименьший локальный период в (u, v) обозначается как r(u, v) . Для любой факторизации 0 < r(u, v) ≤ len(x) .
• Критическая факторизация — это факторизация (u, v) числа x такая, что r(u, v) = p(x) . Для иглы длины m в упорядоченном алфавите ее можно вычислить за 2 m сравнений путем вычисления лексикографически большего из двух упорядоченных максимальных суффиксов, определенных для порядка ≤ и ≥.

Алгоритм

Алгоритм начинается с критической факторизации иглы на этапе предварительной обработки. На этом этапе создается индекс (начальная точка) периодической правой половины и период этого растяжения. Вычисление суффикса здесь следует формулировке авторов. В качестве альтернативы его можно вычислить с использованием алгоритма Дюваля , который более прост и по-прежнему линеен по времени, но на практике медленнее.

Shorthand for inversion.
function cmp(a, b)
    if a > b return 1
    if a = b return 0
    if a < b return -1

function maxsuf(n, rev)
    l ← len(n)
    p ← 1       currently known period.
    k ← 1       index for period testing, 0 < k <= p.
    j ← 0       index for maxsuf testing. greater than maxs.
    i ← -1      the proposed starting index of maxsuf
    
    while j + k < l
        cmpv ← cmp(n[j + k], n[i + k])
        if rev
            cmpv ← -cmpv   invert the comparison
        if cmpv < 0
            Suffix (j+k) is smaller. Period is the entire prefix so far.
            j ← j + k
            k ← 1
            p ← j - i
        else if cmpv = 0
            They are the same - we should go on.
            if k = p
                We are done checking this stretch of p. reset k.
                j ← j + p
                k ← 1
            else
                k ← k + 1
        else
            Suffix is larger. Start over from here.
            i ← j
            j ← j + 1
            p ← 1
            k ← 1
   return [i, p]

function crit_fact(n)
    [idx1, per1] ← maxsuf(n, false)
    [idx2, per2] ← maxsuf(n, true)
    if idx1 > idx2
        return [idx1, per1]
    else
        return [idx2, per2]

Сравнение продолжается путем сопоставления сначала правой части, а затем — левой части, если она совпадает. Пропуск по линейному времени осуществляется с использованием периода.

function match(n, h)
    nl ← len(n)
    hl ← len(h)
    [l, p] ← crit_fact(n)
    P ← {}                  set of matches. 
    
    Match the suffix.
    Use a library function like memcmp, or write your own loop.
    if n[0] ... n[l] = n[l+1] ... n[l+p]
        P ← {}
        pos ← 0
        s ← 0
        
    TODO. At least put the skip in.