Poczytałem artykuł Marka Nelsona o algorytmie Ukkonena budowania drzew sufiksowych: http://marknelson.us/1996/08/01/suffix-trees/

Nelson używa jednego inta na węzeł plus 4 inty na krawędź. Krawędzi jest mniej więcej tyle samo co węzłów, dokładniej to każdy węzeł oprócz korzenia ma swoją własną krawędź wchodzącą, więc węzłów jest o jeden więcej niż krawędzi. Można więc przyjąć, że u Nelsona mamy 5 intow = 20 bajtów na węzeł. Po dodaniu indeksu rodzica (potrzebne chyba do implementacji przesuwnego drzewa sufiksowego: http://larsson.dogma.net/research.html które chciałbym później zaimplementować) wychodzi 6 intów czyli 24 bajty na węzeł.

Mam pomysł, nieco trikowy, jak by zmniejszyć lekko to zapotrzebowanie.

Format węzła byłby taki (reprezentacja drzewa typu left child - right sibling):
4 bajty - indeks następnego (w kolejności użycia) brata
4 bajty - indeks pierwszego syna
4 bajty - indeks rodzica (to oczywiście brakuje u Nelsona i u niego też trzeba dodać)
4 bajty - indeks węzła z sufiksem
4 bajty - indeks pierwszego znaku z krawędzi wchodzącej

Jak obliczyć indeks ostatniego znaku z krawędzi wchodzącej?

  1. Jeżeli jesteśmy w liściu (tzn nie ma synów) to z własności algorytmu Ukkonena krawędź rozciąga się do ostatniego znaku z ciągu wejściowego.
  2. Jeżeli jesteśmy w węźle wewnętrznym to sprawa się komplikuje. Co możemy zrobić? Po pierwsze wskaźnik na syna powinien wskazywać na syna który był ostatnio dopasowany. Po drugie przy każdorazowym przejściu po danej krawędzi uaktualniamy jej zakres znaków na ten ostatnio odwiedzony (tzn jeżeli w ciągu wejściowym podciąg SS pojawia się wiele razy, to w węźle pamiętamy początek ostatniego takiego wystąpienia). Gdy to spełnimy to indeks pierwszego znaku z krawędzi wchodzącej pierwszego syna będzie występował natychmiast po ostatnim znaku krawędzi wchodzącej aktualnego węzła.
  3. W trakcie działania algorytmu Ukkonena czasem przechodzimy do węzła z sufiksem. W takim przypadku, jeżeli ten sufiks jest pierwszym dzieckiem (swojego rodzica) to musimy zaktualizować indeks krawędzi w tym rodzicu. Podobnie, jeżeli ów rodzic jest pierwszym dzieckiem, to odpalamy tą procedurę rekurencyjnie. Ta rekurencja może popsuć złożoność liniową, nie zastanawiałem się jeszcze nad tym mocno. Każdy wewnętrzny węzeł ma co najmniej dwóch synów. Można oczekiwać, że po przejściu do sufiksa, ten sufiks nie będzie pierwszym synem z co najmniej stałym prawdopodobieństwem. Wtedy ilość uaktualnianych przodków także byłaby stała, a więc złożoność byłaby zachowana.

Co myślicie o takiej reprezentacji? Widzicie jakieś kolejne problemy z nią związane? A może znacie jakieś lepsze, tzn bardziej zwięzłe, ale równie szybkie, albo prostsze, ale równie zwięzłe i szybkie?

Posta wysłałem również w wersji angielskiej na: http://encode.ru/threads/1429-Suffix-Tree-s-internal-representation . Nieco inaczej tam temat opisałem, jak ktoś chce to może porównać.

Update:
Wygląda na to, że mój pomysł działa OK. Zrobiłem program i działa on dobrze nawet dla potencjalnie problematycznych (moim zdaniem) wejść.