# String compression algorithms for simplifying an expression by introducing variables

I have a very long algebraic expression computed with Maple, and when I inspect it visually, it is clear that it consists of a set of terms that appear over and over again. For purposes of human readibility (and possibly for floating point computations), I think it makes sense to introduce new variables that represent these terms, such as transforming the expression $$\log(\sqrt{x^{2}+3y^{2}})+\frac{e^{y}}{\sqrt{x^{2}+3y^{2}}}-\frac{\sqrt{x^{2}+3y^{2}}}{e^{y}}$$ into $$\log a+\frac{b}{a}+\frac{a}{b}$$ obviously setting $$a=\sqrt{x^{2}+3y^{2}}$$ and $$b=e^y$$. I can do this manually, but I'm wondering if there is a name for this process, and if there are any good heuristics for minimizing the total length of the expression in question? I have googled this extensively but cannot seem to hit on the right search term.

• In a sense this is what lossless data compression (en.wikipedia.org/wiki/Lossless_compression), e.g., a .zip file, does. – Sam Hopkins Mar 10 at 4:34
• (In more words, the basic idea is: find patterns that occur often in your data; preface your data with a dictionary that represents each pattern by a shorter string; if your data really is structured enough and these patterns occur often enough, this saves space overall.) – Sam Hopkins Mar 10 at 4:36

Maple used to do this automatically. In a sense, it still does (internally), but the new interface doesn't let you see it, even though the documentation says otherwise - see ?interface for 'labelling' where it says that in Typeset Notation, labels will appear. This is now false, it only does so in Character notation. But if you go to Tools -> Options -> Display and set output to Character notation and then do

interface(labelwidth = 9);


you'll get almost what you want.

The other routine to be familiar with is codegen[optimize], viz:

expr := log(sqrt(x^2+3*y^2))+exp(y)/sqrt(x^2+3*y^2)+sqrt(x^2+3*y^2)/exp(y):
codegen[optimize](expr);
2        2                                                   (1/2)
t1 = x , t2 = y , t4 = t1 + 3 t2, t5 = ln(t4), t7 = exp(y), t8 = t4     ,

1      t7   t8
t13 = - t5 + -- + --
2      t8   t7


which also has a nifty tryhard option. The above is even more DAGified than what you asked for, but in practice, it's a very good starting point.