Gdy koduję tekst do kompresji z użyciem słowników, uzywam drzewa sufiksowego.
To jest przykład dla ciągu "Mississippi" (ale obrazek za duży)
a to Dot, który generuje obrazek: (ale za dużo linków, więc podam tylko jedenL to program, który generuje podobne Dot:
Pytanie: rozmiar ciągu to 11, a zarówno liczba węzłów jak i krawędzi drzewa jest bliska dwukrotności rozmiaru ciągu. Czy da się udowodnić, że nie przekroczy tej dwukrotności, choc teoretycznie może się zdawac że będzie \(\displaystyle{ \frac{n \cdot (n+1)}{2}}\) ponieważ węzeł odpowiada ciągowi zaczynajacemu się i kończącemu w jakiejś pozycji..