Text is usually assumed to contain a positive amount of entropy per symbol, precluding the possibility of such dramatic compression.

That was one of my concerns, indeed. Note, however, that I'm considering a logarithmic compression without regard to constant factors. Aside from that, it's somehow cumbersome (if not hard) to translate this problem from a function-based perspective into a rate-based one, which relates to the entropy of the source.

If the entropy per symbol is $H$, then you would need at least $Hn$ bits, on average, to compress a text of length $n$. Shannon proved this in 1948.

That's, in fact, my reasoning for why the non-extended Huffman encoding cannot work. However, what if you don't correspond each symbol $x_i$ in the source string $X$ to another symbol in the output string $Y$? Shouldn't that change things?

Also, the entropy relates to how many bits you need on average for the compression of an input string, meaning that it is possible to do better for a few, specific ones (provably so? that's what I'm trying to understand). It's okay for me to restrain the compression algorithm $C$ to a rather restricted scenario, even if unrealistic.

Shannon's source coding theorem applies to any compression scheme, not just character-by-character. If you are willing to pass to a subset, you could always restrict yourself to all-zeroes strings, which can be compressed to their length, encodable using roughly $\log n$ bits.

Hey, thanks for reaching out. Would you mind moving the conversation to the chat? Take your time, I don't want to interfere with your other duties!

I'd also like to know how entropy relates to dictionary coders. Despite all the literature I've got my hands on, the two things are seldom related to each other, so I'm not able to make certain statements as "No, LZ77 can't work here because the entropy... such and such"

Finally: yes, I'm willing to focus my attention to specific strings with a certain regularity, which is what I meant by "under what sources?" in my post title. I am new (and self-taught) to information theory so maybe I wasn't careful enough with the choice of words

If your source S is known to often send "redundant" messages, then you could dramatically compress the messages using this knowledge. As an extreme example, if every message sent by the source begins and ends with long polite formulations, you could compress the messages by omitting these formulations, or by numbering the different polite formulations and only including their number.

Another good example is images. The bitmap format stores an image as a sequence of pixels. Most other image formats dramatically compress the image compared to a bitmap. This is because the subset of sequences of pixels that correspond to what a human think of as an "image" is very small compared to the set of all possible sequences of pixels.

For instance, most images have large areas where the colour is more-or-less uniform. So, you can write down "the next 100 pixels are blue" rather than "blue, blue, blue, blue, blue, blue, blue, blue..."

(In fact, image formats can make use of fourier transforms for an even more efficient encoding that doesn't consider the pixels one by one - and if you're willing to accept a small loss in quality of the image, this can result in very lightweight images)

@Stef Yes, that's the point. In other words: fix a compression algorithm $C$ (extended Huffman, LZ77, LZ78, arithmetic encoding, whatever you want...) and determine what source $S$ (however narrow) lends itself to logarithmic compression

Not sure if I'm misusing language here, but by source I mean any process producing those patterned, regular strings

You can also make some messages shorter at the cost of making other messages longer. For instance, for an alphabet of 26 letters, you need 4 bits per character in average. Consider morse-code: letter 'e' uses only 2 bits, while letters x,y,z need 5 bits each (I'm making an approximation here, More code technically uses three symbols: dot, dash, and letter-separation)

Ideally I'd like to determine an as large as possible logarithmically-compressible source $S$ for an algorithm $C$, not just giving the example of a string that can be logarithmically compressible. However, I don't need an extended theory of all sources where this is possible either

Yuval gave you an example earlier: if your algorithm counts the number of repeated characters, then any message consisting in n identical characters is compressed logarithmically

@Stef Yes, in that case $C =$ run-length encoding

Now, if you want the exact subset of all messages compressed logarithmically by this algorithm, it's a bit harder; because this is going to include all messages that contain "enough repetitions" and it's a pain to determine what "enough" means precisely

@Stef He he, if it was plain easy I wouldn't be asking for help :-)

It doesn't seem super hard either. Specifically, I worry I'm overlooking some critical piece of literature (textbook, article) that could be instrumental to the solution

It does seem hard. For one thing, I think you have to choose your constant first (the constant k so that the subset is defined as the messages that are compressed to k log2(n) at most)