Введение в Z-блоки

Скорее всего, вы нашли этот пост по одной из двух причин:

Либо вы не слышали о Z-блоках и интересуетесь, могут ли они как-то помочь вам
или вам нужно изучить Z-блоки, и вы абсолютно не представляете, как понять математические определения.

В любом случае, мы собираемся исследовать Z-блоки — не используя набор формул, а используя примеры и Python-код.

Что такое Z-блоки?

Если вы слышали о Z-блоках на лекции или читали о них в книге, вы, вероятно, столкнулись с

$$\begin{array}{ll}(1)&\;\text{Let }s:=s_0\cdots s_{n-1}\in\Sigma^n\\(2)&\;\forall i\in\{1\cdots n-1\}:\;Z_i:=max\{j\in[0\cdots n]: s_i\cdots s_{i+j-1}=s_0\cdots s_{j-1}\}\\(3)&\;\text{Z-Box starting at position i}:=s_i\cdots s_{i+Z_i-1}\,\text{if }Z_i\neq0\end{array}$$

Но будем честны. Эти определения в основном для людей, которые уже понимают, что это значит. Для большинства студентов это не очень полезно для понимания алгоритма.

Давайте всё равно разберём это и посмотрим, что мы можем извлечь.

$(1)$ Это просто говорит, что $s$ — строка длины $n$ (это определение используется). Технически $\Sigma$ — алфавит строки — но для всех практических целей это определяется контекстом программирования в любом случае, поэтому мы просто проигнорируем $\Sigma$.

Допустим, $n=6$. Тогда каждое из этих соответствовало бы определению:

is_valid_zbox.py

s = "abc123"
s = "fo bar"
s = "      "
s = "abcabc"

s = "abc123"
s = "fo bar"
s = "      "
s = "abcabc"

Почти во всех определениях для алгоритмов, работающих со строками, вы найдёте похожее определение.

$(2)&(3)$ немного сложнее. Я объясню это, не говоря сначала о определении.

Вот простая часть: Z-блок, начинающийся в позиции i — это просто подстрока s, начинающаяся в позиции $i$. $Z_i$ — её длина.

К сожалению, сложная часть в том, что это не просто любая подстрока, начинающаяся в позиции $i$. Но как мы можем проверить, является ли Z-блок действительным?

Давайте просто посмотрим на фрагмент python-кода:

zbox_algorithm.py

def is_valid_zbox(s, i, zi):
    # zi — длина z-блока, вычислить z-блок
    zbox = s[i:i + zi]
    # Вычислить префикс той же длины
    prefix = s[0:zi]
    return zbox == prefix

is_valid_zbox("abcabc", 2, 2) # "ca" != "ab" => False
is_valid_zbox("abcabc", 2, 3) # "cab" != "abc" => False
is_valid_zbox("abcabc", 3, 2) # "ab" == "ab" => True
is_valid_zbox("abcabc", 3, 3) # "abc" == "abc" => True

def is_valid_zbox(s, i, zi):
    # zi — длина z-блока, вычислить z-блок
    zbox = s[i:i + zi]
    # Вычислить префикс той же длины
    prefix = s[0:zi]
    return zbox == prefix

is_valid_zbox("abcabc", 2, 2) # "ca" != "ab" => False
is_valid_zbox("abcabc", 2, 3) # "cab" != "abc" => False
is_valid_zbox("abcabc", 3, 2) # "ab" == "ab" => True
is_valid_zbox("abcabc", 3, 3) # "abc" == "abc" => True

Так что Z-блок действителен, если две строки равны: Сам Z-блок и префикс s.

Как мы видим в примерах, может быть несколько действительных Z-блоков в любой позиции $i$. Какой мы используем? Из-за max в $(2)$ мы всегда используем самый длинный.

Простой алгоритм Z-блоков

Итак, вот как вычислить Z-блоки, используя то, что мы знаем на данный момент:

zbox_examples.py

def is_valid_zbox(s, i, zi):
    # zi — длина z-блока, вычислить z-блок
    zbox = s[i:i + zi]
    # Вычислить префикс той же длины
    prefix = s[0:zi]
    return zbox == prefix

def zbox(s, i):
    # Maximum length of substring starting at pos. i
    # (s has only so many characters)
    maxlen = len(s) - i
    # Try out every zbox, starting at the longest
    # i.e. maxlen, maxlen-1, ..., 1
    for zi in range(maxlen, 0, -1):
        if is_valid_zbox(s, i, zi):
            # Return the first valid zbox
            # As we're starting from the longest,
            #  this is always the longest zbox
            zbox = s[i:i + zi]
            return zbox

# Compute zboxes
s = "abcabc"
[zbox(s, i) for i in range(1, len(s))]
# [None, None, 'abc', None, None]

def is_valid_zbox(s, i, zi):
    # zi — длина z-блока, вычислить z-блок
    zbox = s[i:i + zi]
    # Вычислить префикс той же длины
    prefix = s[0:zi]
    return zbox == prefix

def zbox(s, i):
    # Maximum length of substring starting at pos. i
    # (s has only so many characters)
    maxlen = len(s) - i
    # Try out every zbox, starting at the longest
    # i.e. maxlen, maxlen-1, ..., 1
    for zi in range(maxlen, 0, -1):
        if is_valid_zbox(s, i, zi):
            # Return the first valid zbox
            # As we're starting from the longest,
            #  this is always the longest zbox
            zbox = s[i:i + zi]
            return zbox

# Compute zboxes
s = "abcabc"
[zbox(s, i) for i in range(1, len(s))]
# [None, None, 'abc', None, None]

Почему в результате так много значений None? Потому что, как видно из строки, a, первый символ в строке, встречается снова только в позиции 3.

И почему мы вычисляем только Z-блоки, начинающиеся с $[1\cdots n-1]$? Мы могли бы также вычислить их для $[0\cdots n-1]$!?!? Но если вы возьмёте любую подстроку $s$ длины $j$, начинающуюся с 0, и сравните её с префиксом $s$ длины $j$ — они одинаковые, независимо от того, какой они длины! Это потому, что префикс $s$ длины $j$ и есть $s$ длины $j$, начинающийся с 0 (pre означает перед, поэтому мы начинаем с 0!)

Давайте посмотрим на другой пример:

zbox_ananas_example.py

# Compute zboxes
s = "ananas"
[zbox(s, i) for i in range(1, len(s))]
# [None, 'ana', None, 'a', None]

# Compute zboxes
s = "ananas"
[zbox(s, i) for i in range(1, len(s))]
# [None, 'ana', None, 'a', None]

И есть также примеры, где мы не можем найти ни одного Z-блока!

zbox_foobar_example.py

# Compute zboxes
s = "foobar"
[zbox(s, i) for i in range(1, len(s))]
# [None, None, None, None, None]

# Compute zboxes
s = "foobar"
[zbox(s, i) for i in range(1, len(s))]
# [None, None, None, None, None]

Но для некоторых мы можем найти много!

zbox_many_example.py

# Compute zboxes
s = "abaabaabab"
[zbox(s, i) for i in range(1, len(s))]
# [None, 'a', 'abaaba', None, 'a', 'aba', None, 'ab', None]

# Compute zboxes
s = "abaabaabab"
[zbox(s, i) for i in range(1, len(s))]
# [None, 'a', 'abaaba', None, 'a', 'aba', None, 'ab', None]

Дополнительное чтение:

Ещё один легко понятный пост в блоге о Z-блоках, включающий более эффективный алгоритм

Материал лекционного типа:

https://www.bio.ifi.lmu.de/mitarbeiter/volker-heun/notes/ab6.pdf раздел 2.5.1 https://www.informatik.hu-berlin.de/de/forschung/gebiete/wbi/teaching/archive/ws0506/bioinformatik/03_zbox.pdf