Wygenerowany wcześniej indeks Farragina Manziniego, został zoptymalizowany w odstępach w oparciu o dane wprowadzone przez użytkownika.
Wzór: cad
Stos: abracadabra

Z powyższych danych przykładowych, wyniki są następujące.

Xbwt = Zdrcraaaabba
Macierz Ferragina - Manzini generowana jest jak poniżej, gdy nie ma optymalizacji Occ. Tutaj za wartość K przyjmuje się 1.




W macierzy Ferragina Manzini dla wartości K jest równa 4.




3.3




Implementacja tego algorytmu będzie miała złożoność O(n) + O(m*m), ponieważ funkcja LF wymaga dalszego zaangażowania pętli.

Również optymalizacja Occ obędzie prowadziła do wolniejszych odpowiedzi, ponieważ BWT musi być liczony od indeksu FM. Xibwt można obliczyć bez znajomości xbwt. Ale jeśli będzie więcej indeksów funkcja lokalizacji będzie szybsza, jeśli bęszie mniej indeksów funkcja lokalizacji będzie wolniejsza.

Jak wyszukiwać szybciej korzystając z optymalizacji Occ?
Aby temu zaradzić możemy użyć następujących metod:
 Musimy znaleźć optymalną wartość dla K, gdzie K jest nie za wysokie aby doprowadzić do wolniejszych wyszukiwań, nie jest zbyt zbliżone do 1 i ma duży indeks.
 Wartość K może być ustalona na postawie łańcucha stosu. Jeśli prawdopodobieństwo większego łańcucha jest wyższe, wówczas wartość K może być relatywnie mniejsza, tak, że indeksy są wyższe, a lokalizowanie szybsze. Jednakże jeśli ciąg stosu będzie mały, czyli mniej niż 50 znaków, wartość K może być relatywnie wyższa, tak, że indeksy są niższe, a lokalizacja wystarczająco szybka.


Implementacja dostępna w pliku OccOptimization.zip pod adresem
http://cs.elitepc.pl/OccOptimization
lub
tutaj


Autor: Krzysztof Wołk