# An introduction to Z-boxes

You most likely found this post for one of two reasons:

- Either you haven’t heard of Z-Boxes and are interested in if they can somehow help you
- or you have to learn about Z-Boxes and you have absolutely no idea how to understand the mathematical definitions.

Either way, we’re going to investigate Z-Boxes - not using a box of formulas but using examples and Python code.

### What are Z-Boxes?

If you have heard of Z-Boxes in a lecture or read about them in a book, you probably encountered

$$\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}$$But let’s be honest. These definitions are mainly for people who already understand what this means. To most students this is not very useful in understanding an algorithm.

Let’s break it down anyway and see what we can salvage.

$(1)$ This just says that $s$ is a string of length $n$ (this definition is used). Technically $\Sigma$ is the *alphabet* of the string - but for *all* practical intents and purposes this is defined by the programming context anyway, so we’ll just ignore $\Sigma$.

So let’s assume $n=6$. Then each of those would meet the definition:

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

In almost all defitions for algorithms dealing with strings, you’ll find a similar definition.

$(2)&(3)$ is slightly more complicated. I’ll explain it without talking about the definition at first.

Here’s the easy part: The *Z-Box starting at position i* is just a substring of s, starting at position $i$. $Z_i$ is its length.

Unfortunately, the hard part is that it’s not just *any* substring starting at position $i$. But how can we check if a *Z-Box* is valid?

Let’s just have a look at a fragment of python code:

```
def is_valid_zbox(s, i, zi):
# zi is the length of the zbox, compute the zbox
zbox = s[i:i + zi]
# Compute the prefix of the same length
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
```

So a *Z-Box* is valid if two strings are equal: The *Z-Box* itself and a *prefix* of s.

As we can see in the examples, there can be multiple valid *Z-boxes* at any position $i$. Which one do we use?
Due to the `max`

in $(2)$, we always use the longest one.

### A simple Z-Box algorithm

So here’s how to compute the *Z-boxes*using what we know so far:

```
def is_valid_zbox(s, i, zi):
# zi is the length of the zbox, compute the zbox
zbox = s[i:i + zi]
# Compute the prefix of the same length
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]
```

Why are there so many `None`

values in the result? Because, as you can see in the string, `a`

, the first character in the string, only occurs again at position 3.

And why do we only compute *Z-boxes* starting at $[1\cdots n-1]$? We could as well compute them for $[0\cdots n-1]$!?!?
But if you take any substring of $s$ of length $j$ starting at 0, and compare it to the prefix of $s$ of length $j$ - they are the same, no matter how long they are! That’s because the prefix of $s$ of length $j$ *is* the $s$ of length $j$ starting at 0 (*pre* means *before,* therefore we start at 0!)

Let’s have a look at another example:

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

And there are also examples where we can’t find *any*Z-box!

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

But for some we can find a lot!

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

### Additional reading:

Another easy-to-understand blogpost about Z-boxes including a more efficient algorithm

Lecture-type material:

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