Kolmogorov Complexity Meta Golfer
Retina, worst case (3+original length) bytes

EDIT: added support for newlines, in order to try this code in actual kolmogorov complexity challenges. Behaviour on strings without newlines remains unchanged.

Retina is great at substituting substrings, so that's what we're going to do!

This program looks for repeated sequences of characters and replaces them every time with a single character not appearing in the full string. The generated program then starts with the "compressed" string and applies all substitutions in reverse.

This code adds 3 bytes of boilerplate (a newline at the beginning, and a \` towards the end to suppress a trailing newline), so in the worst case (when there are no repeated sequences worth substituting) we have a length of 3 bytes more than the starting string. On average, this will shave a few bytes from the original length, not much but still a compression.

Here's the code with some comments:

First, we use a trick with transliteration ranges to change newlines into ¶, which is how newlines are printed in a Retina program

T`µ¶·`µ-·


then we start the main loop, duplicating the first line

{`^.+
$&amp;¶$&amp;


we only substitute when the sequence is repeated enough times (depending on its length)

^.*?((......+).*?\2|(.....?).*?\3.*?\3|(...).*?\4.*?\4.*?\4|(..).*?\5.*?\5.*?\5.*?\5.*?\5).*
"$2$3$4$5
^"(.+)|^.*
$+


to find a character not in the string, we append a list of candidates to the string, using " as separator, and then remove duplicates

^(.*)¶(.*)
$2" 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!#%&amp;\'()*+,-./:;?@\^_`{|}~¶$2¶$1
D`(?&lt;=^.*).
^.*"(.)?.*¶(.+)
$2¶$1


here the actual substitution in the text happens

+`^(.*)(.+)(.*¶(.)¶\2(¶|$))
$1$4$3


in case we couldn't find a repeated sequence or an unused character, we restore the string to the original state (which makes us break from the loop)

}`(.*)¶(¶.*|.*¶)(¶|$)
$1$3


at the end, we add the 3 bytes of boilerplate

^
¶
\-1=`.*¶
\`$&amp;


Try it online!

In the linked example, the 292 bytes paragraph gets compressed to a 286 bytes Retina code.

NOTE: the substitutions made are not optimal, we just make every time the first suitable substitution we find; I don't know if an algorithm finding the optimal substitutions could run in a reasonable amount of time.