3 ms·

I’m encoding a set of runs. Each run has a value component and a length. The only difference from traditional RLE is that, when expanded, the values are compute

I’m encoding a set of runs. Each run has a value component and a length. The only difference from traditional RLE is that, when expanded, the values are computed from the base+offset rather than repeated. Eg the IDs expand to 1000,1001,1002,… instead of just repeating; 1000,1000,1000,… What would you call that?

yencabulator 2y ago
I can't tell from your writing if this is really a compression of an output format or an inherent part of your data structure. What determines when the repeating or sequential IDs are skipped? Is it part of the shape of the data structure, or is it a pure byte manipulation at encode time? If it's purely in the encoder, "The encoded runs omit repetitive or sequential values of IDs.", and describe how the decoder knows what was done (e.g. naive RLE might have to say 1h1e2l1o, repeating lengths everywhere). If it's part of the data structure, say something like "Within a <chunk>, only origin-left of the first item and the common origin-right need to be stored, as the individual item origin-left and origin-right values can be derived from those."
- josephg 2y ago
  > I can't tell from your writing if this is really a compression of an output format or an inherent part of your data structure. It’s both. It’s part of the internal in-memory data structure, and part of the encoded output format. At runtime, the data structure also needs to support split and join operations (when possible). For example, a user types a paragraph of text then moves their cursor in the middle of the paragraph and types more text. Initially we create (and extend) a single run representing the paragraph as it’s typed. Inserting in the middle of the run will split the run with the added text. So we end up with 3 entries in our order statistic tree. I like your suggested text - but we’re talking about this in the context of order statistic trees. I have a generic order statistic tree implementation that splits and, when possible, joins the stored items. I’ve been calling that “internal run length encoding”, but you’re right that that’s not the common use of the “rle” term. But I would like a term for that that doesn’t involve explaining my actual data. My order statistic tree implementation doesn’t understand origin-left and origin-right values. That’s an implementation detail of how my particular data implements its splitting and joining operations.
  - yencabulator 2y ago
    That sounds like how the Zed editor's SumTree is parameterized with Summary, which is whatever means of summarizing information makes sense for that use. https://zed.dev/blog/zed-decoded-rope-sumtree https://zed.dev/blog/zed-decoded-rope-sumtree
    - josephg 2y ago
      Yes they’re quite similar. And I don’t think that’s a coincidence. But they have some important differences too: - Sumtree at its heart is a tree of characters, with a summary per node in the tree. I haven’t read that link in detail, but I assume summaries are derived from the stored text itself. I’m storing a tree of metadata entries, not text. The metadata is not derived from the text. A string of 100 characters in the document may be able to be summarised by 1 metadata entry, or we may need up to 100 entries - 1 for each character. Each leaf node in my tree stores up to 32 metadata entries. These entries are split when needed, and opportunistically joined. Entries describe characters which were at some point inserted. (We also need to keep around the metadata even after the text has been deleted.) - My metadata entries also have IDs, and my data structure also needs to be able to look up any item in log(n) time via its ID. The text itself is stored in a separate data structure. I assume any text editor which integrates a crdt will, like zed, have its own data structure for this purpose already. You’re right that the data structures are similar, but the implementations are not interchangeable.
kragen 2y ago
you're rle-compressing the first differences of the ids (x[n] - x[n-1]) rather than the ids themselves. though maybe only in the special case of a run of 1s
- josephg 2y ago
  Yep, only in the case of runs of 1s - since that’s the predominant case when typing. Runs with other difference values show up when typing in multi-cursor mode in vscode and other editors, but I haven’t optimised my data structure for that use case.
  - kragen 2y ago
    yeah, that seems quite reasonable reversibly transforming a data sequence into a more easily compressible one of the same size (sometimes called 'whitening' or 'predicting') is a very general technique for data compression, and first differences are a very commonly used transformation here. others include the burrows–wheeler transform, paeth prediction, and linear predictive coding
    - josephg 2y ago
      I didn't know that had a name! Thanks - time to do some reading.

yencabulator 2y ago

I can't tell from your writing if this is really a compression of an output format or an inherent part of your data structure. What determines when the repeating or sequential IDs are skipped? Is it part of the shape of the data structure, or is it a pure byte manipulation at encode time? If it's purely in the encoder, "The encoded runs omit repetitive or sequential values of IDs.", and describe how the decoder knows what was done (e.g. naive RLE might have to say 1h1e2l1o, repeating lengths everywhere). If it's part of the data structure, say something like "Within a <chunk>, only origin-left of the first item and the common origin-right need to be stored, as the individual item origin-left and origin-right values can be derived from those."

josephg 2y ago
> I can't tell from your writing if this is really a compression of an output format or an inherent part of your data structure. It’s both. It’s part of the internal in-memory data structure, and part of the encoded output format. At runtime, the data structure also needs to support split and join operations (when possible). For example, a user types a paragraph of text then moves their cursor in the middle of the paragraph and types more text. Initially we create (and extend) a single run representing the paragraph as it’s typed. Inserting in the middle of the run will split the run with the added text. So we end up with 3 entries in our order statistic tree. I like your suggested text - but we’re talking about this in the context of order statistic trees. I have a generic order statistic tree implementation that splits and, when possible, joins the stored items. I’ve been calling that “internal run length encoding”, but you’re right that that’s not the common use of the “rle” term. But I would like a term for that that doesn’t involve explaining my actual data. My order statistic tree implementation doesn’t understand origin-left and origin-right values. That’s an implementation detail of how my particular data implements its splitting and joining operations.
- yencabulator 2y ago
  That sounds like how the Zed editor's SumTree is parameterized with Summary, which is whatever means of summarizing information makes sense for that use. https://zed.dev/blog/zed-decoded-rope-sumtree https://zed.dev/blog/zed-decoded-rope-sumtree
  - josephg 2y ago
    Yes they’re quite similar. And I don’t think that’s a coincidence. But they have some important differences too: - Sumtree at its heart is a tree of characters, with a summary per node in the tree. I haven’t read that link in detail, but I assume summaries are derived from the stored text itself. I’m storing a tree of metadata entries, not text. The metadata is not derived from the text. A string of 100 characters in the document may be able to be summarised by 1 metadata entry, or we may need up to 100 entries - 1 for each character. Each leaf node in my tree stores up to 32 metadata entries. These entries are split when needed, and opportunistically joined. Entries describe characters which were at some point inserted. (We also need to keep around the metadata even after the text has been deleted.) - My metadata entries also have IDs, and my data structure also needs to be able to look up any item in log(n) time via its ID. The text itself is stored in a separate data structure. I assume any text editor which integrates a crdt will, like zed, have its own data structure for this purpose already. You’re right that the data structures are similar, but the implementations are not interchangeable.

kragen 2y ago

you're rle-compressing the first differences of the ids (x[n] - x[n-1]) rather than the ids themselves. though maybe only in the special case of a run of 1s

josephg 2y ago
Yep, only in the case of runs of 1s - since that’s the predominant case when typing. Runs with other difference values show up when typing in multi-cursor mode in vscode and other editors, but I haven’t optimised my data structure for that use case.
- kragen 2y ago
  yeah, that seems quite reasonable reversibly transforming a data sequence into a more easily compressible one of the same size (sometimes called 'whitening' or 'predicting') is a very general technique for data compression, and first differences are a very commonly used transformation here. others include the burrows–wheeler transform, paeth prediction, and linear predictive coding
  - josephg 2y ago
    I didn't know that had a name! Thanks - time to do some reading.