Stream of Thoughts

Momentary fascinations & inklings of ideas

Hello!
This is my place for messy drafts and other early-stage writing. Feel free to poke around, or go to the home page.

Recent Notes

TIL: XOR Doubly-Linked List

Neat idea: you can make a doubly-linked list that only needs to store a single pointer – the xor of the prev and next pointers – to allow traversal of the list from either direction.

Looks like author never heard about single pointer double linked list. That could save him 2 pointers per each node.

The idea: for simplicity taking list. single pointer saved in the node is xor of next and previous nodes. When moving forward we xor current ptr with prev. Moving backward xor with next to get prev. That it. How do we get prev/next for xor? The only way to get in the middle of the list is using iterator. Which can hold one extra pointer. For the first/last nodes extra pointer is NULL.

– numba888 on Hacker News


Podcast Vibes Prototyping

I’m considering turning my little research note on podcast vibes into a bit more of a product. The idea would be to track the daily pulse of the podcast ecosystem in terms of the subjects it discusses and the emotions it puts out.

This weekend I played around with a few visualization ideas for looking at the emotional subjects for a single episode at a time.

The picture below shows all of the subjects discussed on a recent podcast interview with a bean enthusiast, with subjects discussed positively colored green and those discussed negatively colored red.

The annotations are picked at regular samples across the emotional spectrum so that the labels don’t overlap. I think it would be better to instead draw attention to the most salient discussion points.

Here’s how the same kind of picture looks for a longer podcast episode:

And here’s one for a podcast with a much more negative slant. Amusingly, the most positive segments of this one are the ads. While looking at the transcript DeepSeek R1 complimented the host on his ability to smoothly and undetectably transition from the interview into an advertising segment.

Here’s how it might look to lay out the dots on a horizontal timeline, with negatives segmented from positives.

Anyway, just some early explorations. Still getting used to publishing this stuff in such an early state, but here we go.


Note: Podcast Vibes

Here’s a research note on my recent explorations into using LLMs to analyze the emotional content of podcasts.

I’m amazed that we have technology that can do this so well.

This project supports my view that one of the most useful features of language models is that they can function as transducers from messy reality to a structured format that can then be dealt with using standard tools that are more efficient, controllable, and well-understood.

It’s also a reminder of just how open the design space is for projects like this, how valuable good tooling for data pipelines is, and the importance of taste.


The Structure of the Wavelet Tree

This is a follow-up to Wavelet Matrix Construction.

(I’m working on a larger post about the wavelet matrix and writing and publishing extremely rough drafts as I go.)

To understand the wavelet matrix it can be useful to understand the wavelet tree first, so here’s a quick primer.

As I’ve mentioned before, I think of the wavelet tree (and matrix) as representing the process of sorting a sequence of integer symbols.

Let’s take an example. Imagine that our integer symbols are picked from a universe of size 2³, consisting of the numbers from 0 to 7.

The wavelet tree represents a quicksort whose pivots are all powers of two. At each level of recursion, the value space is partitioned into two halves based on the universe size, ie. into a lower half containing the numbers 0 to 3, and an upper half containing the numbers 4 to 7. After this first step, each half is recursively sorted using the same approach, terminating when the halves contain a single integer each.

You can see this in the diagram below, where each node is labeled with the range of the as-yet-unsorted integers inside it.

Each level of the diagram corresponds to the next stage of the sorting process. The full sequence of numbers starts in its original order on the top level, made up of symbols from 0 to 7. On the next level those numbers are partitioned into two sublists, with the one on the left containing all of the numbers from 0 to 3 in their original order, and the one on the right containing all numbers from 4 to 7, in their original order.

Then the same process happens again, with the left (0 to 3) node further partitioned into two child nodes, one from 0 to 1 and another from 2 to 3. Then we do this again and arrive at the fully-sorted sequence on the bottom level.

The diagram above shows the process abstractly without any particular sequence of numbers, but let’s see how this would actually work in practice. Here’s a visualization that shows the incremental sorting process for the sequence 5 2 1 3 7 2 6 1 5 2:

We start off with the full sequence in its original order on the top layer, and end up with those same numbers sorted in ascending order on the bottom. In between, you see the process of recursive partitioning, where the numbers “slide” down either the left or the right arrow, depending on whether they belong to the bottom or the top half of the universe.

Now, because the entire sequence is represented in full on each level of the sort, you might think this is a very expensive way to represent the data. But in fact, this is the beautiful trick: the wavelet matrix stores not the boxes, but the arrows!

Here’s the same diagram again, this time with the numbers in parentheses notating the data that actually gets written into the wavelet matrix as individual 0- and 1-bits.

The drawing tool I’m using does not allow me to color the individual zeros and ones red or blue but you should think of the the zeros as colored blue, indicating that the number goes down and to the left along the blue arrow, and ones as red, indicating that the number goes down and to the right following the red arrow.

The data in the wavelet matrix consists of a bit vector per level containing the bits in parentheses, With the one small tweak that, rather than writing the bits down from left to right as they’re shown here, we first write down the bits for all the left nodes, followed by the bits for all the right nodes.

If those bits are all you’ve got it might look like we’ve scrambled the numbers beyond all possibility of repair. But we will soon see that it’s easy to reconstruct the original data from this new representation.

The reason for this is that at each level we’ve actually written out bits from the numbers themselves. For example, the number 5 is represented in binary as 101, and those are the exact bits written out for each 5 in the sequence, in that order – a 1-bit on the top layer, a 0-bit on the middle layer, and another 1-bit on the bottom layer.

(I’d like to make an animated version of this diagram later, but for now I’m happy since this is already quite an improvement from my last post.)

More to come.

Appendix: Scraps

Here are some scraps of visualizations I’m working on that are quick sketches to see whether an idea works. This first one has some promise:

This tree view is an interesting idea, too, and inspired the boxy diagrams below:

The next few are a bit misleading because it is not the case that the bottom half of each node sorts to the left:

I experimented with showing the flow from the full parent node, but that seems even less enlightening, and I think the arrows in the main post are better illustrations of the idea.


Wavelet Matrix Construction

This is a follow-up post to Enter the Wavelet Matrix. Compared to my previous entries this one is much more of a stream-of-consciousness that’s not really designed for anyone else to read (though hopefully on the way to a much more coherent and comprehensive explanation!)

Sidenote: This is very much an early draft, and not really understandable on its own, but I’m practicing the art of forging ahead with partial work.

The wavelet matrix can be constructed using an extremely simple algorithm, though explaining the meaning of the resulting structure will take a little bit more work.

The wavelet matrix is a way to represent a sequence of integers, which we will call symbols, by representing a sorting process – the symbols are incrementally sorted by their successive bits, from high to low, using a stable bucket sort, and the incremental results are written down into the wavelet matrix structure, and later used for reconstituting the elements or performing other algorithms such as ranged quantile queries.

Here’s an image illustrating the construction of a wavelet matrix for the sequence 1 4 2 3 7. The sequence starts out in its original order on the top layer and moves down incrementally through a series of bitwise bucket sorts that sort the elements into ‘left’ and ’right buckets based on whether the element has a 0-bit or 1-bit on that level. The

The data stored in the wavelet matrix is represented by the “pipes” in between the numbers rather than the numbers themselves.

This is what I mean when I say the wavelet matrix represents the process of sorting. It records whether each element “went left” or “went right” in the successive applications of the bucket sort.

The idea behind this picture is that all elements that go left appear before the elements that go right. So for example, the numbers 1, 2, and 3 have a zero for their top bit, and therefore appear on the left of the second row.

The numbers 4 and 7 have a 1 in that top bit, and therefore go right and appear at the end. The numbers that went left are indicated by gray pipes, and the ones right are indicated by black pipes.

The next sorting is based purely on the second bit. The numbers 2 and 3 have a 1 in that position, so they go right.

The same process occurs again on the third layer. Note how 7 was the maximal element on each row indicated and therefore went right on each level.

This is my sixth attempt to try to explain this process, and clearly it’s not working very well, but I will forge ahead, because I think this section does capture something about the practical algorithm I use for large-alphabet wavelet matrices.

I’m beginning to think it’s probably best to start with an introduction to the wavelet tree where the effects of the sort are much more salient, since the bottom row ends up with the symbols sorted by value. In the wavelet matrix, the symbols end up sorted by the bit-reversal of their value.


Actually…

Here’s a visualization of the wavelet tree representation of the sequence

7 6 5 4 3 2 1

The wavelet tree has a nice hierarchical structure where all of the children stay underneath their parent node, though this is not obvious from these matrix-style visualizations that lose the node borders.

And here’s the wavelet matrix version:

Here we can see that each layer is sorted independently of the previous – ie. other than the stability of the sort, whether the elements on each layer go either left or right purely based on the bit at that level, rather than taking into account the previous levels too (which is what gives the preceding picture its tree structure).

As a side note, the reason the wavelet matrix is an improvement over the wavelet tree is because the wavelet tree requires you to store the node offsets at each level, which scales linearly with the size of the maximum symbol. Without this information, it becomes impossible to navigate from one level of the wavelet tree to the next.

The wavelet matrix is based on this ingenious idea of ordering all of the left children before all of the right children on each level, rather than keeping the child nodes “underneath” the parent. This helps because when you’re on a particular level you can compute the number of left children that precede you and the number of right children that precede you with a simple rank query on the bit vector holding that level. Therefore, navigating to a left child involves looking at the number of zeros to your left, and jumping to that location on the next level. Navigating to the right child involves looking at the number of ones to your left and jumping to that location on the next level (plus the total number of zeros, ie. left children, since all the left children precede the right children).

It’s very clever but hard to explain. Hopefully I can find a nice way to present all of this.

References