How to decompose a complex expression containing repeated subexpressions? [duplicate]

Question

Suppose I have an expression like

1/8 + 1/8 Sqrt[1 - 28 (2/(3 (Sqrt[4197] - 9)))^(1/3) + 2 (2/3)^(2/3) (Sqrt[4197] - 9)^(1/3)]
 - 1/2 Sqrt[1/8 - (1/2 (Sqrt[4197] - 9))^(1/3)/(4 3^(2/3)) + 7/(2 2^(2/3) (3 (Sqrt[4197] - 9))^(1/3))
 - 7/(8 Sqrt[1 - 28 (2/(3 (Sqrt[4197] - 9)))^(1/3) + 2 (2/3)^(2/3) (Sqrt[4197] - 9)^(1/3)])]

which contains repeated common subexpressions. I am interested in an algorithm that can decompose it into parts of the minimal (or close to minimal) total complexity. The expected output should be something like this:

(1 + α - Sqrt[3 - β - 14/α]) / 8 
  /. α -> Sqrt[β]
  /. β -> 1 + 2 γ - 56/(3 γ)  
  /. γ -> (4 Sqrt[4197]/9 - 4)^(1/3)

(if you ever worked with Maple, this is similar to how it formats complex output expressions)

Answer 1

I once tried doing something like this myself, and ended up with a semi-manual process.

Clear[branches, tallyBranches];
branches[b_?AtomQ] := {};
branches[b_?NumberQ] := {};
branches[h_[b___]] := Flatten@Append[branches /@ List[b], h[b]];
tallyBranches[e_, k_Integer: 2] := 
  TableForm[Reverse /@ Cases[Tally[branches[e]], {_, t_ /; t >= k}]]

Let's take the solution to the cubic as an example:

cube = Solve[a x^3 + b x^2 + c x + d == 0, x];

Generate a table of common branches (with at least 9 occurrences):

tallyBranches[cube, 9]

9   1/a
9   b^2
9   -b^2
9   3 a c
9   -b^2+3 a c
12  b^3
12  -2 b^3
12  9 a b c
12  a^2
12  -27 a^2 d

Then we can manually pick a branch to substitute:

cube2 = cube //. -b^2 + 3 a c -> α;

And then repeat:

tallyBranches[cube2, 6];

Etc..

After three substitutions we end up with something like this:

$$\left\{\left\{x\to -\frac{\sqrt[3]{2} \alpha }{3 a \sqrt[3]{\gamma }}-\frac{b}{3 a}+\frac{\sqrt[3]{\gamma }}{3 \sqrt[3]{2} a}\right\},\left\{x\to \frac{\left(1+i \sqrt{3}\right) \alpha }{3\ 2^{2/3} a \sqrt[3]{\gamma }}-\frac{b}{3 a}-\frac{\left(1-i \sqrt{3}\right) \sqrt[3]{\gamma }}{6 \sqrt[3]{2} a}\right\},\left\{x\to \frac{\left(1-i \sqrt{3}\right) \alpha }{3\ 2^{2/3} a \sqrt[3]{\gamma }}-\frac{b}{3 a}-\frac{\left(1+i \sqrt{3}\right) \sqrt[3]{\gamma }}{6 \sqrt[3]{2} a}\right\}\right\}$$

where $\alpha =3 a c-b^2$, $\beta =-27 a^2 d+9 a b c-2 b^3$, and $\gamma =\sqrt{4 \alpha ^3+\beta ^2}+\beta$.