Eine Einführung in Z-Boxen

Du hast diesen Beitrag höchstwahrscheinlich aus einem von zwei Gründen gefunden:

• Entweder hast du noch nie von Z-Boxen gehört und bist interessiert, ob sie dir irgendwie helfen können
• oder du musst etwas über Z-Boxen lernen und hast absolut keine Idee, wie du die mathematischen Definitionen verstehen sollst.

Egal aus welchem Grund, wir werden Z-Boxen untersuchen — nicht mit einer Box voller Formeln, sondern mit Beispielen und Python-Code.

Was sind Z-Boxen?

Wenn du von Z-Boxen in einer Vorlesung gehört oder in einem Buch darüber gelesen hast, bist du wahrscheinlich auf

Aber seien wir ehrlich. Diese Definitionen sind hauptsächlich für Leute, die bereits verstehen, was das bedeutet. Für die meisten Studierenden ist das nicht sehr nützlich, um einen Algorithmus zu verstehen.

Lass es uns trotzdem aufschlüsseln und sehen, was wir daraus machen können.

$(1)$ Das besagt einfach, dass $s$ ein String der Länge $n$ ist (diese Definition wird verwendet). Technisch gesehen ist $\Sigma$ das Alphabet des Strings — aber für alle praktischen Zwecke wird dies durch den Programmierkontext definiert, also ignorieren wir $\Sigma$ einfach.

Nehmen wir also $n=6$ an. Dann würde jede dieser Möglichkeiten die Definition erfüllen:

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

In fast allen Definitionen für Algorithmen, die mit Strings arbeiten, findest du eine ähnliche Definition.

$(2)&(3)$ ist etwas komplizierter. Ich werde es erklären, ohne zuerst über die Definition zu sprechen.

Hier ist der einfache Teil: Die Z-Box ab Position i ist einfach ein Teilstring von s, der an Position $i$ beginnt. $Z_i$ ist ihre Länge.

Leider ist der schwere Teil, dass es nicht einfach irgendein Teilstring ist, der an Position $i$ beginnt. Aber wie können wir prüfen, ob eine Z-Box gültig ist?

Schauen wir uns einfach ein Fragment Python-Code an:

def is_valid_zbox(s, i, zi):
    # zi ist die Länge der Z-Box, berechne die Z-Box
    zbox = s[i:i + zi]
    # Berechne das Präfix derselben Länge
    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

Eine Z-Box ist also gültig, wenn zwei Strings gleich sind: Die Z-Box selbst und ein Präfix von s.

Wie wir in den Beispielen sehen können, kann es an jeder Position $i$ mehrere gültige Z-Boxen geben. Welche verwenden wir? Aufgrund des max in $(2)$ verwenden wir immer die längste.

Ein einfacher Z-Box-Algorithmus

Hier ist, wie man die Z-Boxen berechnet, mit dem, was wir bisher wissen:

def is_valid_zbox(s, i, zi):
    # zi ist die Länge der Z-Box, berechne die Z-Box
    zbox = s[i:i + zi]
    # Berechne das Präfix derselben Länge
    prefix = s[0:zi]
    return zbox == prefix

def zbox(s, i):
    # Maximale Länge des Teilstrings ab Position i
    # (s hat nur so viele Zeichen)
    maxlen = len(s) - i
    # Probiere jede Z-Box aus, beginnend mit der längsten
    # d.h. maxlen, maxlen-1, ..., 1
    for zi in range(maxlen, 0, -1):
        if is_valid_zbox(s, i, zi):
            # Gib die erste gültige Z-Box zurück
            # Da wir bei der längsten beginnen,
            #  ist dies immer die längste Z-Box
            zbox = s[i:i + zi]
            return zbox

# Z-Boxen berechnen
s = "abcabc"
[zbox(s, i) for i in range(1, len(s))]
# [None, None, 'abc', None, None]

Warum gibt es so viele None-Werte im Ergebnis? Weil, wie man im String sehen kann, a, das erste Zeichen im String, nur an Position 3 wieder vorkommt.

Und warum berechnen wir nur Z-Boxen ab $[1\cdots n-1]$? Wir könnten sie genauso gut für $[0\cdots n-1]$ berechnen!?!? Aber wenn du einen beliebigen Teilstring von $s$ der Länge $j$ ab Position 0 nimmst und ihn mit dem Präfix von $s$ der Länge $j$ vergleichst — sie sind gleich, egal wie lang sie sind! Das liegt daran, dass das Präfix von $s$ der Länge $j$ genau der Teilstring von $s$ der Länge $j$ ab Position 0 ist (pre bedeutet vor, daher beginnen wir bei 0!)

Schauen wir uns ein weiteres Beispiel an:

# Z-Boxen berechnen
s = "ananas"
[zbox(s, i) for i in range(1, len(s))]
# [None, 'ana', None, 'a', None]

Und es gibt auch Beispiele, bei denen wir gar keine Z-Box finden!

# Z-Boxen berechnen
s = "foobar"
[zbox(s, i) for i in range(1, len(s))]
# [None, None, None, None, None]

Aber bei einigen finden wir viele!

# Z-Boxen berechnen
s = "abaabaabab"
[zbox(s, i) for i in range(1, len(s))]
# [None, 'a', 'abaaba', None, 'a', 'aba', None, 'ab', None]

Weiterführende Literatur:

Ein weiterer leicht verständlicher Blogbeitrag über Z-Boxen inklusive eines effizienteren Algorithmus

Vorlesungsmaterial:

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