<p>I am implementing a WASM backend and I hope to optimize the size.</p>
<p>I have collected a series of static data. After erasing the type, it can be simply
considered as <code>list&lt;u8&gt;</code>.</p>
<p>However, these data may be repeated or partially covered. I hope to find a way to arrange them, so that the overall size will reduce.</p>
<p>In other words, such a transformation:</p>
<p><code>list&lt;list&lt;u8&gt;&gt; -&gt; (data: list&lt;u8&gt;, span: list&lt;(start: u32, length: u32)&gt;)</code></p>
<p>But I don't know how to achieve this efficiently. And is there a special name for this kind of optimization?</p>

<optimization><static-analysis>
How to minimize total size of static data?
CC BY-SA 4.0
2023-12-06T12:21:40.137Z
It is not clear to me that this is really a question about programming languages, at least without adding more details. As asked, it seems like you are just asking about lossless data compression, which is a rather vast field of its own. Can you clarify what sorts of things you have in mind?
Alexis King
CC BY-SA 4.0
2023-12-06T14:26:17.470Z
Assuming I understand correctly, you want to produce a shortest string (of bytes) which contains all of the desired substrings. This is a variant of the travelling saleman problem on a directed graph, where edges have lower weights when the overlap between the two strings is greater. I agree with Alexis; this problem isn't really specific to PLs, it's the kind of thing I'd expect to see in an algorithms textbook. Chances are, for a compiler the possible space savings are small, and for performance it's probably more important to have word-aligned pointers.
kaya3
CC BY-SA 4.0
2023-12-06T17:50:09.803Z
[Related question on Stack Overflow](https://stackoverflow.com/questions/1285434/efficient-algorithm-for-string-concatenation-with-overlap)
dan04
CC BY-SA 4.0
2023-12-06T19:58:12.647Z
I think it is impossible to provide an adequate answer without knowing anything about the source language or how much you can influence its semantics or that of core types.
feldentm
<h1>Compression algorithms</h1>
<p>Data compression is about finding repeated data of arbitrary size inside bigger sequential data.</p>
<p>You may not store the data in compressed form, but the <em>dictionary-building</em> stage of most compression algorithms are well-studied part of computer sciences.</p>
<p>I suggest starting with classical compression formats like <a href="https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch" rel="nofollow noreferrer">LZW</a> and <a href="https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform" rel="nofollow noreferrer">BWT</a>.</p>
<p>The BWT in particular can be extremely efficient in finding <em>all</em> substrings in a string, as its algorithm &quot;generates&quot; all rotations of input string and compares all rotations: any two or more rotations that compare equals more than one &quot;letter&quot; is repetition <em>or</em> a substring.</p>

CC BY-SA 4.0
2023-12-06T13:37:52.390Z
2023-12-10T04:07:43.753Z
2023-12-10T04:07:43.753Z
André L F S Bacci
# How to minimize total size of static data?
Posted by: username_0 on 2023-12-06
I am implementing a WASM backend and I hope to optimize the size.

I have collected a series of static data. After erasing the type, it can be simply
considered as `list`.

However, these data may be repeated or partially covered. I hope to find a way to arrange them, so that the overall size will reduce.

In other words, such a transformation:

`list> -> (data: list, span: list<(start: u32, length: u32)>)`

But I don't know how to achieve this efficiently. And is there a special name for this kind of optimization?
**Tags:** optimization static-analysis
> **Comments:**
> **username_1**: It is not clear to me that this is really a question about programming languages, at least without adding more details. As asked, it seems like you are just asking about lossless data compression, which is a rather vast field of its own. Can you clarify what sorts of things you have in mind?  
> **username_2**: Assuming I understand correctly, you want to produce a shortest string (of bytes) which contains all of the desired substrings. This is a variant of the travelling saleman problem on a directed graph, where edges have lower weights when the overlap between the two strings is greater. I agree with Alexis; this problem isn't really specific to PLs, it's the kind of thing I'd expect to see in an algorithms textbook. Chances are, for a compiler the possible space savings are small, and for performance it's probably more important to have word-aligned pointers.  
> **username_3**: [Related question on Stack Overflow](https://stackoverflow.com/questions/1285434/efficient-algorithm-for-string-concatenation-with-overlap)  
> **username_4**: I think it is impossible to provide an adequate answer without knowing anything about the source language or how much you can influence its semantics or that of core types.  
---
## 1 answers
### Answer by username_5 on 2023-12-06. Score: 3
# Compression algorithms

Data compression is about finding repeated data of arbitrary size inside bigger sequential data.

You may not store the data in compressed form, but the *dictionary-building* stage of most compression algorithms are well-studied part of computer sciences.

I suggest starting with classical compression formats like [LZW](https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch) and [BWT](https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform).

The BWT in particular can be extremely efficient in finding *all* substrings in a string, as its algorithm "generates" all rotations of input string and compares all rotations: any two or more rotations that compare equals more than one "letter" is repetition *or* a substring.
---
