Optimal parse with phminposuw | purplesyringa's blog<br>Optimal parse with phminposuw<br>July 11, 2026This problem arose when I was writing a specialized data compressor.Okay, full disclosure: “optimal parse” usually refers to something else than described in this article, but I have no clue what else to call it, so optimal parse it is.<br>Say you want to encode a byte stream, and bytes can be encoded in different formats, e.g. optimized for ASCII, numbers, raw binary, etc. These formats prioritize better compression of a specific type of data. Realistic byte streams may contain all of them at different points, so we want to switch between formats on the fly optimally.The easiest way to do so is to split data into, say, 50-byte chunks, find the best format for each chunk, and use those formats. But that doesn’t take into account that we need to store which format is used for which chunk, and choosing formats greedily may increase the size of this metadata because it itself compresses worse. Not to mention that it’s not very precise. So what should we do?Let’s look at this problem from another angle. Let’s make a table, where for each format we track how many bits it would take to encode each symbol with that format:abracadabraFormat 163465696346Format 272674737267Format 337836383783<br>(Don’t look too much into the numbers, they’re chosen randomly. For example, I’m assuming the letter a always takes 7 bits to encode with format 2, but you can imagine fractional costs here, or use a measure other than bits, or chunk symbols.)If switching formats was cheap, we could just choose the optimal format independently in each column, for instance:<br>abracadabraFormat 1634 6569634 6Format 272 674 73 72 67Format 33 783 63 83 783<br>But switching formats is not cheap. The effect is already visible even if it takes, let’s say, just 2 bits – the optimal selection changes to this one:abracadabraFormat 163 4 656963 4 6Format 27267473 7267Format 33 783 6 3 83 783<br>In this example, we switch for a short while to code d more optimally, but don’t bother switching for b, since it’s not as expensive in formats chosen for nearby symbols.The question, then, is how to compute this “path” most efficiently.DP<br>The textbook approach to this problem is dynamic programming. For each cell in this table, we can iteratively compute the optimal path from that cell to the right side of the table, and then take the best path from the first column as optimal.Here’s how to do that. Each path starting at cell (i,j) can be split into three parts:Optionally switching the format to some other format j′ (costing 2 bits), or keeping j′=j (costing 0 bits). This corresponds to moving within the column.Coding the symbol at index i with format j′, using the cost written in cell (i,j′). This corresponds to moving one cell to the right.Coding the rest of the data, starting from cell (i+1,j′).In pseudocode (we’ll switch to C once we get to low-level details),best_path_length[i, j] = min(<br>(j != j_new) * 2 # (1)<br>+ cost[i, j_new] # (2)<br>+ best_path_length[i + 1, j_new] # (3)<br>for j_new in range(n_formats)<br>Since each value best_path_length[i, j] only depends on values to the right of it, they can be computed starting from the right column and iterating backwards:# Initialize paths starting out-of-bounds as having cost 0.<br>for j in range(n_formats):<br>best_path_length[n, j] = 0
# Compute the optimal paths starting at each cell.<br>for i in range(n_symbols - 1, -1, -1):<br>for j in range(n_formats):<br>best_path_length[i, j] = min(<br>(j != j_new) * 2 # (1)<br>+ cost[i, j_new] # (2)<br>+ best_path_length[i + 1, j_new] # (3)<br>for j_new in range(n_formats)
# Infer the optimal path starting in the first column.<br>global_best_path_length = min(best_path_length[0, j] for j in range(n_formats))<br>print("Optimal path length:", global_best_path_length)<br>Path<br>This computes the minimal possible cost, but not the specific path that produces it. To find the path, we can save the choice made at each cell and retrace our steps in the opposite direction: for i in range(n_symbols - 1, -1, -1):<br>for j in range(n_formats):<br>- best_path_length[i, j] = min(<br>+ (best_path_length[i, j], next_j[i, j]) = min(<br>+ (<br>(j != j_new) * 2 # (1)<br>+ cost[i, j_new] # (2)<br>+ best_path_length[i + 1, j_new] # (3)<br>+ , j_new<br>+ )
+# Find the first optimal j (can also be fixed to some initial value, depending on specifics)<br>+j = min(range(n_formats), key = lambda j: best_path_length[0, j])<br>+# Record and recover next `j` column by column.<br>+for i in range(n_symbols):<br>+ j = next_j[i, j]<br>+ format[i] = j<br>If this doesn’t make much sense, try to look at next_j as an intrusive linked list: next_j[i, j] represents the head of the linked list denoting the best path from (i,j), and nodes are efficiently reused between multiple linked lists, CoW-style.In this article, we’ll pretend this part of the algorithm doesn’t exist. Doing it justice requires writing another post, because there’s plenty of subtleties here as well, but it’ll have to wait until next time. (Edit:...