Optymalna sekwencja indukowania kubełków

3

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:

                   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: http://homepage3.nifty.com/wpage/software/itssort.txt ).

Ma ktoś pomysł czego użyć, aby uzyskać optymalną sekwencję indukowania?

0

Trochę dodatkowych podpowiedzi nt działania Copy Transform:

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:
abbababababbbab

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

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:

babbababababbba
bababbababababb
babbbababbababa
bababbbababbaba
babababbbababba
bababababbbabab

Po posortowaniu wygląda tak:

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:

bababababbbabab
bababbababababb

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

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:

bbababababbbaba
bbababbabababab
bbbababbabababa

Teraz mamy już gotowy kubełek B_b:

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:

babababbbababba
bababbbababbaba
babbababababbba
babbbababbababa
bbababababbbaba
bbbababbabababa

Indukujemy z nich zawartość kubełka b_ab w "tradycyjny" sposób:

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.

1 użytkowników online, w tym zalogowanych: 0, gości: 1