I enjoy weaving. Weaving patterns are known as 'drafts', and have a standardized appearance.
There is a standard file format for weaving patterns: the WIF file, which dates from the 90s and is based on the INI file format. I've written some code for reading and writing WIF files.
I think Typst is pretty neat. I'd written some Typst functions for rendering weaving drafts. You could specify thread colours, different styles for rendering the threading (e.g. shapes vs numbers), and you could indicate that sections of the threading or treadling should be repeated some number of times. Repetitions could even be nested.
Clearly, I should write some code to translate WIF files into weaving drafts! The only problem is that patterns can be quite wide, so I wanted to automatically find repetitions. What's more, while patterns are rarely wider than a few thousand ends (hundreds tend to be typical), and our alphabet size is quite small, I wanted my implementation to be better than the naïve approach.
The Main-Lorentz algorithm dates from 1982, and no longer represents the state of the art. I originally tried to better understand the cutting edge algorithms and quickly ended up shaving a yak hairier than I cared for: reading a paper on an implicit sorting algorithm to properly understand another paper written in response to it, in order to efficiently build a suffix array that I could then use to more efficiently solve the problem that I actually cared about.
Since, as noted, my inputs aren't terribly large, I decided to go with an algorithm that could find all repetitions in $O(n \log n)$ time.
At its core, Main-Lorentz is a divide-and-conquer algorithm. It first finds all repetitions lying entirely inside the left half of the string, then the right half of the string before finding any repetitions that straddle the midpoint of the string. The first two cases are simple recursion, so we focus on the third case.
If a repetition straddles the midpoint, the midpoint must lie inside the first repetition or the second. (Cases where the midpoint falls directly between the repetitions count as the former.) We will call this point corresponding to the position of the midpoint the counterpoint.
For example, given the string
$$
x \mathbf{a b c ◃ d e f a b c | d e f} x x x x x x x
$$
or
$$
x x x x x x x \mathbf{a b c | d e f a b ◃ c d e f} x
$$
the $◃$ represents the counterpoint while | represents the midpoint.
There is an asymmetry to when the counterpoint falls on the left or right side. While frustrating, it's necessary for $x x x | ◃ x x x$ to make sense. The effective position of the counterpoint, in these circumstances, is effectively one further to the right. To make things easier to reason about, I'll replace the $◃$ counterpoint with an $▹$ augmented counterpoint, one symbol over:
$$
x x x x x x x \mathbf{a b c | d e f a b c ▹ d e f} x
$$
For each position in the string, we want to test whether it's a valid (augmented) counterpoint: how many symbols to its left match those to the left of the midpoint ($left\ matches$), how many the symbols to its right match the symbols to the right of the midpoint ($right\ matches$), and do their sum equal or exceed the length of the repeated string?
Every possible counterpoint location fixes the possible length of the string. When the counterpoint is in the left half, we can see that there's a complete copy of the repeated symbols between the counterpoint and the midpoint, albeit slightly out-of-order. $$ x \mathbf{a b c ◃ d e f \underline{a b c} | \underline{d e f}} x x x x x x x $$ Our length must therefore be number of symbols between the counterpoint and midpoint.
If our counterpoint is on the right, we have a (spliced) copy of the repetition between the midpoint and augmented counterpoint. $$ x x x x x x x \mathbf{a b c | d e f \underline{a b c ▹ d e f}} x $$
Thus if $left\ matches + right\ matches \ge length$, we have a valid counterpoint!
It's possible that there are multiple repeating strings overlapping the midpoint. For example, $$ x \mathbf{a b c ◃ d e f a b c | d e f a b c} x x x x $$ has the possible repetitions with first halves $a b c d e f$, $b c d e f a$, $c d e f a b$ and $d e f a b c$ with offsets-from-counterpoint of 3, 2, 1 and 0 symbols. We actually want to exclude that final case, as it would duplicate $$ x a b c \mathbf{d e f a b c | d e f a b c ▹} x x x x $$
There are up to $left\ matches + right\ matches - length + 1$ repetitions to find. (Some possible repetitions might fall entirely on the left or right side, and thus would be disqualified.)
We can start our search $\min(left\ matches, length)$ symbols to the left of the midpoint or counterpoint (whichever is further left), and carry on ensuring that we stop before we run out of symbols before the midpoint or counterpoint. (We need at least one symbol to the left of the counterpoint in order to straddle it, and the string-starts-at-$◃$ case duplicates the string-ends-at-$▹$ case, and is easier to detect.)
We thus find all repeated substrings, with an efficiency depending entirely on how easily we can compute $left\ matches$ and $right\ matches$ for each $◃$ or $▹$ location.
Fortunately, we can compute $left\ matches$ and $right\ matches$ in amortized-constant time: before checking any possible counterpoint positions, we can build tables for the entire string in linear time.
In total, we need four tables: two to compute $left\ matches$ and $right\ matches$ for $◃$, and two to compute $left\ matches$ and $right\ matches$ for $▹$. The algorithm to build these tables is called the $z$-function: given a string $x_0 x_1 x_2 x_3 \dots$ as input, it returns an array $[n_0, n_1, n_2, n_3, \dots]$ where $n_i = k$ if $x_0 x_1 \dots x_{k-1} = x_i x_{i+1} \dots x_{i+k-1}$ for $i > 0$: that is, $k$ characters starting from the $i$th position match the start of the string.
Naïvely, computing this table would take quadratic time:
Mark Sherry
mdsherry
mdsherrydef z_naive(s):
# The 0th entry has no real meaning, but 0 is a sensible enough value
rv = [0]
for i in range(1, len(s)):
matches = 0
for j in range(len(s) - i):
if s[j] == s[i + j]:
matches += 1
else:
break
rv.append(matches)
return rv
Fortunately, we can employ a trick: if we know we're part of a sequence that matches the start of the string, we can check the number of matches the characters in the corresponding starting portion of the string had. This lets us avoid rechecking for matches we can prove exist, and as a result we only check each position in the string at most twice.
def z(s):
# The 0th entry has no real meaning, but 0 is a sensible enough value
rv = [0]
current_run_length = 0
position_in_run = 0
for i in range(1, len(s)):
# If we're in a run and have space before the end, increment our position
if current_run_length > position_in_run + 1:
position_in_run += 1
else:
# Otherwise, reset the values
current_run_length = 0
position_in_run = 0
remaining_run = current_run_length - position_in_run
# Initialize matches to avoid repeated work. We take the min of the historical value,
# and the remaining length of the match: it's possible the actual match will be longer,
# but this is all we can be certain of.
# We also take advantage of the fact that rv[0] = 0 for when we're not in a known run
matches = min(rv[position_in_run], remaining_run)
for j in range(matches, len(s) - i):
if s[j] == s[i + j]:
matches += 1
else:
break
rv.append(matches)
# If we've now seen further into the future, replace the current run
if matches > remaining_run:
current_run_length = matches
position_in_run = 0
return rv
The version of the algorithm I originally studied generated four tables:
where $#$ represents some sentinel character not appearing in $u$ or $v$. In the cases of $right_◃$ and $left_▹$, we never actually use the first halves of outputs, so instead of creating a new string and managing sentinels, we could instead use a modified version of $z$ that takes already-computed first half of the output. This costs us nothing, as we're already computing $z(v)$ and $z(\textrm{rev}(u))$ for $right_▹$ and $left_◃$ respectively. Similarly, we can avoid making a reversed copy of the inputs by processing the strings backwards. The result is four partially specialized copies of the function, but considerably fewer allocations, especially if you reuse the allocations of the z-tables as well.