[Algorytmy] Optymalna sekwencja indukowania kubełków

Wibowit
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 24 sie 2011, o 20:09
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 1 raz

[Algorytmy] Optymalna sekwencja indukowania kubełków

Post autor: Wibowit »

Cześć,

Tworzę współbieżny algorytm sortowania blokowego, tzn coś w stylu algorytmu stosowanego w bzip2. Przy sortowaniu blokowym (block-sorting) można wyindukować posortowany porządek pewnych podciągów z posortowanego porządku innych podciągów, korzystając z faktu, że sortowanie blokowe sortuje podciągi tego samego ciągu bazowego.

W moim programie używam Copy Transform, wymyślonego przez Juliana Sewarda, autora bzip2. Opiszę jak działa ten algorytm w przypadku sufiksów, najpierw trochę objaśnię sposób zapisu:

B_a to duży kubełek, zawierający wszystkie sufiksy zaczynające się na literę a,
b_ab to mały kubełek, zawierający wszystkie sufiksy zaczynające się od liter "ab"

Duży kubełek B_a składa się z kubełków {b_aa, b_ab, ..., b_az}

Mając posortowany kubełek B_d mogę z niego wyindukować posortowany porządek kubełków {b_ad, b_bd, b_cd, b_ed, ..., b_zd} w zaledwie jednym przejściu po tym dużym kubełku. Tak jest w oryginalnym Copy Transform. Później Seward zorientował się, że kubełek b_dd można wyindukować z kubełków {b_da, b_db, b_dc, d_de, ..., d_dz} (co widocznie przyspieszyło jego bzipa na niektórych danych wejściowych).

Moim problemem jest obliczenie optymalnej sekwencji indukowania kubełków, tzn kubełki mają różne rozmiary, a ja chcę zminimalizować łączny rozmiar kubełków, które muszę posortować za pomocą porównań, aby wyindukować resztę.

Aktualnie wydajność wygląda tak:

Kod: Zaznacz cały

                   Copy ascending      Copy simple-ratio   Improved two-stage
chr22.dna          35.56               31.67               26.68
etext99            49.75               38.64               31.10
gcc-3.0.tar        42.63               33.46               26.77
howto              45.51               36.13               28.55
jdk13c             47.63               35.05               30.06
linux-2.4.5.tar    44.12               35.20               26.80
rctail96           49.00               36.57               30.28
rfc                40.17               32.28               25.83
sprot34.dat        43.14               38.07               29.26
w3c2               47.46               36.22               29.90
 
mean               44.50               35.33               28.52
Gdzie:
- Copy ascending, to normalna wersja Copy Transform, gdzie sortuje się kubełki od najmniejszego do największego,
- Copy simple-ratio, to Copy Transform z moją heurezą do obliczania sekwencji indukowania,
- Improved two-stage to inny algorytm indukowania posortowanego porządku, ale nie ma pomysłu jak by go sensownie zrównoleglić,

Liczby oznaczają procent sufiksów, które trzeba posortować, aby móc wyindukować resztę. Jak widać moja heureza znacznie poprawia efektywność Copy Transform, ale i tak daleko jej do ITS. (Nota bene: ITS jest opisany w dokumencie: ).

Ma ktoś pomysł czego użyć, aby uzyskać optymalną sekwencję indukowania?
Ostatnio zmieniony 24 sie 2011, o 22:01 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawka nazwy tematu.
Awatar użytkownika
paladin
Użytkownik
Użytkownik
Posty: 148
Rejestracja: 24 sty 2005, o 22:15
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 19 razy

[Algorytmy] Optymalna sekwencja indukowania kubełków

Post autor: paladin »

Jak rozumiem, nie sortujesz akurat sufiksów, tylko jakieś inne podsłowa. Ciężko jest coś powiedzieć, nie wiedząc, jakie konkretnie.
Wibowit
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 24 sie 2011, o 20:09
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 1 raz

[Algorytmy] Optymalna sekwencja indukowania kubełków

Post autor: Wibowit »

W rzeczywistości mój program sortuje przesunięcia cykliczne, ale można go przerobić na sortowanie sufiksów poprzez dodatnie sentinela (tzn to angielskie słowo, nie znam polskiego odpowiednika) na koniec.

Objaśnię na przykładzie.

Mamy następujący ciąg:

Kod: Zaznacz cały

abbababababbbab
Generujemy jego wszystkie przesunięcia cykliczne, będziemy je sortować:

Kod: Zaznacz cały

abbababababbbab
babbababababbba
ababbababababbb
bababbababababb
bbababbabababab
bbbababbabababa
abbbababbababab
babbbababbababa
ababbbababbabab
bababbbababbaba
abababbbababbab
babababbbababba
ababababbbababb
bababababbbabab
bbababababbbaba
Zacznijmy od sortowania kubełka b_ba. Oto kubełek przed sortowaniem:

Kod: Zaznacz cały

babbababababbba
bababbababababb
babbbababbababa
bababbbababbaba
babababbbababba
bababababbbabab
Po posortowaniu wygląda tak:

Kod: Zaznacz cały

bababababbbabab
babababbbababba
bababbababababb
bababbbababbaba
babbababababbba
babbbababbababa
Następnie indukujemy kubełek b_bb z pozostałych kubełków dużego kubełka B_b. W naszym przypadku jest tylko jeden pozostały kubełek. Aby wyindukować kubełek b_bb wybieramy te podciągi, które zaczynają i kończą się na literę b:

Kod: Zaznacz cały

bababababbbabab
bababbababababb
Z nich można już wyindukować początek kubełka b_bb:

Kod: Zaznacz cały

bbababababbbaba
bbababbabababab
Widzimy, że dostaliśmy kolejny podciąg, który kończy się na b (i zaczyna się też na b). Indukujemy więc następną pozycję (tak jak poprzednio, bierzemy jego przesunięcie o jedną pozycję w lewo) - dodany element jest na końcu:

Kod: Zaznacz cały

bbababababbbaba
bbababbabababab
bbbababbabababa
Teraz mamy już gotowy kubełek B_b:

Kod: Zaznacz cały

bababababbbabab
babababbbababba
bababbababababb
bababbbababbaba
babbababababbba
babbbababbababa
bbababababbbaba
bbababbabababab
bbbababbabababa
Możemy więc teraz indukować kubełek b_ab. Potrzebne są nam do tego podciągi, które zaczynają się na b i kończą na a:

Kod: Zaznacz cały

babababbbababba
bababbbababbaba
babbababababbba
babbbababbababa
bbababababbbaba
bbbababbabababa
Indukujemy z nich zawartość kubełka b_ab w "tradycyjny" sposób:

Kod: Zaznacz cały

ababababbbababb
abababbbababbab
ababbababababbb
ababbbababbabab
abbababababbbab
abbbababbababab
Teraz mamy już wszystko posortowane, bo kubełek b_aa był pusty.

Uwaga co do indukowania kubełków typu b_cc:
Jak podałem wcześniej, kubełki typu b_cc można wyindukować z kubełków {b_ca, b_cb, b_cd, ..., b_cz}. Należy jednak pamiętać o odpowiednim porządku: kubełki {b_ca, b_cb} (tzn te które mają drugą literę mniejszą leksykograficznie niż c) skanujemy od początku i wyindukowane podciągi kładziemy na początek b_cc. Natomiast kubełki {b_cd, ..., b_cz} skanujemy od końca i wyindukowane podciągi kładziemy na koniec b_cc.




Generalnie mój problem nie polega jednak na tym, jak indukować kubełki (bo to rozumiem), tylko jak obliczyć optymalną sekwencję indukowania, tak aby sortować jak najmniej podciągów bezpośrednio.
ODPOWIEDZ