8. Dynamické programovanie a spracovanie textov

Na riešenie niektorých úloh, v ktorých hľadáme nejaké optimálne riešenie, môžeme niekedy použiť metódu dynamické programovanie. Idea sa trochu podobá metóde rozdeľuj a panuj, preto si ju pripomeňme:

  1. ak sa ešte dá rozdeľ veľký problém na (disjunktné) podproblémy
  2. (rekurzívne) vyrieš každý z podproblémov
  3. spoj dokopy všetky tieto čiastkové riešenia do riešenia celého problému

Videli sme napr. ako sa táto metóda využila pre merge sort aj quick sort. Uvedomte si, že pri tom sa problém rieši zhora nadol.

Metóda dynamické programovanie postupuje opačne:

  1. vyriešime najjednoduchšie prípady zložitého problému - riešenia si zapamätáme najlepšie v nejakej tabuľke (podproblémy nemusia byť navzájom disjunktné - bolo by dokonca dobré, keby sa navzájom prekrývali)
  2. z týchto jednoduchých riešení postupne skladáme riešenia stále zložitejších a zložitejších prípadov problému a všetko toto zapisujeme do tabuľky
  3. takto pokračujeme, kým sa nedostaneme k riešeniu požadovaného problému

Táto metóda funguje na princípe zdola nahor a väčšinou využíva pomocnú pamäť na pamätanie si čiastkových riešení - často sú to jednorozmerné alebo dvojrozmerné tabuľky (veľkosti O(n) alebo O(n**2)). Vďaka tejto metóde sa niekedy podarí z problému exponenciálnej zložitosti O(2**n) vyrobiť riešenie zložitosti O(n) alebo O(n**2).

Na riešenie úloh pomocou dynamického programovania treba mať veľkú skúsenosť s analýzou problému, rozdelením na podproblémy, vymyslením, ako skladať z riešení malých podproblémov väčšie, ako využívať tabuľky. Ukážeme to na sérii jednoduchých úloh: mnohé z nich sme už veľakrát riešili, ale netušili sme, že za nimi sú skryté princípy dynamického programovania.

Fibonacciho postupnosť

Poznáme rekurzívnu verziu funkcie:

def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

Už vieme, že táto funkcia má exponenciálnu zložitosť.

Ak by sme najprv postupne (bez rekurzie) vypočítali do tabuľky prvých n členov postupnosti a potom n-tý vrátili ako výsledok funkcie, zložitosť tohto zápisu by bola len O(n). Hoci v tomto prípade sme tiež minuli O(n) pomocnej pamäte:

def fib(n):
    tab = [0, 1]
    for i in range(2, n+1):
        tab.append(tab[i-1] + tab[i-2])
    return tab[n]

Toto je najjednoduchší prípad použitia dynamického programovania: veľký problém (zložitosti O(2**n)) sme pomocou postupného zostavovania tabuľky (v nej sme riešili jednoduchšie podproblémy a z nich sme zostavovali stále zložitejšie a zložitejšie riešenia) previedli na úlohu zložitosti O(n). Vidíme tu, že úloha sa rieši metódou zdola nahor, t.j. najprv najjednoduchšie podúlohy a potom stále zložitejšie, ktoré sa blížia k požadovanému problému.

Fibonacciho postupnosť tiež vieme vyriešiť aj bez rekurzie a bez pomocnej tabuľky, napr.

def fib(n):
    f1, f2 = 1, 0
    for i in range(n):
        f1, f2 = f2, f1+f2
    return f2

V tomto riešení sme prepísali rekurzívnu úlohu postupným riešením najprv najjednoduchších podproblémov (postupne pre n=0 a n=1) a z nich zostavujeme zložitejšie riešenia - tu sme tabuľku veľkosti n nahradili len dvomi pomocnými premennými.

Inokedy sa pri riešení iných úloh pomocou dynamického programovania ukáže, že namiesto kompletnej dvojrozmernej tabuľky stačí zostavovať len jej posledný riadok (prípadne posledné dva). Podobne ako nám z jednorozmernej tabuľky pre fibonacciho čísla nakoniec stačili len dve posledné hodnoty.

Túto istú úlohu môžeme riešiť pomocou memoizácie (riešili sme to na 2. cvičení v (7) úlohe):

  • je to spôsob, ktorým si funkcia pamätá už raz vypočítané výsledky a keď ju voláme druhýkrát, tak už nič nepočíta, len zapamätanú hodnotu vráti ako svoj výsledok
  • vďaka tomu nemusíme funkciu prerábať na nerekurzívnu verziu s vytváraním tabuľky, ale tabuľka sa vytvára automaticky

Potom fib() vyzerá takto:

mem = {}               # globálna premenná

def fib(n):
    if n in mem:
        return mem[n]
    if n < 2:
        mem[i] = n
        return n
    res = fib(n-1) + fib(n-2)
    mem[n] = res
    return res

alebo s využitím inicializovaného mutable parametra:

def fib(n, mem={}):
    if n in mem:
        return mem[n]
    if n < 2:
        mem[i] = n
        return n
    res = fib(n-1) + fib(n-2)
    mem[n] = res
    return res

Vidíme, že toto riešenie je zhora nadol, ale tiež sa v ňom vytvára tabuľka s riešeniami všetkých podúloh. Hovoríme, že memoizácia je špeciálnym prípadom dynamického programovania. Využije sa hlavne pri jednoduchších úlohách, ktoré vieme zapísať rekurzívne. V Pythone existuje machanizmus, pomocou ktorého sa dá memoizácia zapísať veľmi elegantne (tzv. dekorátory), napr.

import functools

@functools.lru_cache(maxsize=None)          # dekorátor
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)
>>> print(*(fib(n) for n in range(16)))
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

Kombinačné čísla

Kombinačné čísla vieme vypočítať aj pomocou rekurzívneho vzťahu:

komb(n, k) = komb(n-1, k) + komb(n-1, k-1)

Tento vzťah sa dá jednoducho zapísať pomocou rekurzie (pre triviálne prípady k=0 a n=k), pričom zložitosť takejto funkcie je O(2**n):

def komb(n, k):
    if k == 0 or n == k:
        return 1
    return komb(n - 1, k) + komb(n - 1, k - 1)

Zo strednej školy poznáme Pascalov trojuholník, ktorý je poskladaný z hodnôt kombinačných čísel:

            1
          1   1
        1   2   1
      1   3   3   1
    1   4   6   4   1
  1   5  10  10   5   1
1   6  15  20  15   6   1

čo sú:

                        komb(0,0)
                   komb(1,0) komb(1,1)
              komb(2,0) komb(2,1) komb(2,2)
         komb(3,0) komb(3,1) komb(3,2) komb(3,3)
    komb(4,0) komb(4,1) komb(4,2) komb(4,3) komb(4,4)
...

Každé číslo (okrem krajných 1) sa dá vypočítať ako súčet dvoch čísel nad ním (vľavo a vpravo). Takže, ak by sme namiesto rekurzie zostavovali tieto hodnoty do dvojrozmernej tabuľky, použili by sme dynamické programovanie: postupným zapĺňaním tabuľky riešime jednoduchšie podúlohy, pričom využívame riešenia ešte jednoduchších podúloh.

Samozrejme, že aj táto úloha sa dá riešiť memoizáciou: aj v tomto prípade je to dynamické programovanie, ale tabuľku za nás postupne zapĺňa Python pri rekurzívnych volaniach.

Mincovka

Známa úloha o rozmieňaní nejakej sumy na čo najmenší počet mincí. Zrejme musíme poznať, aké druhy mincí máme k dispozícii, napr. ak máme mince [1, 2, 5, 10], tak sumu 6 vieme rozmeniť napr. ako 2+2+2 alebo 1+5 ale aj 1+1+1+1+1+1. V tomto prípade je 1+5 hľadaným riešením, lebo na rozmenenie sme použili najmenší počet mincí (zrejme menej ako dvomi mincami sa to nedá).

Postupne ju vyriešime niekoľkými spôsobmi

Pomocou Greedy metódy

Greedy t.j. pažravý algoritmus označuje:

  • na rozmieňanie sa snažíme použiť čo najväčšiu mincu, ktorou sa to ešte dá
  • túto mincu si zapamätáme, odčítame ju od rozmieňanej sumy a celé to opakujeme, kým je rozmieňaná suma väčšia ako 0
def mincovka1(mince, suma):
    zoznam = []
    mince = sorted(mince)
    while suma > 0:
        i = len(mince)-1
        while i >= 0 and mince[i] > suma:
            i -= 1
        if i < 0:
            return None
        suma -= mince[i]
        zoznam.append(mince[i])
    return zoznam[::-1]

otestujeme:

for suma in range(1, 21):
    print(suma, sorted(mincovka1([1, 2, 5, 10], suma)))

Predchádzajúci algoritmus funguje dobre len pre niektoré sady mincí, napr. pre mince [1, 3, 7, 10] by sumu 14 rozmenil ako 1+3+10 pričom správnym riešením by malo byť 7+7 (teda iba 2 mince). Zrejme je tento algoritmus veľmi rýchly, ale nie vždy funguje optimálne: niekedy nájde nie najlepšie riešenie.

Mincovka pomocou hrubej sily

Vyriešme túto úlohu hrubou silou, teda pomocou backtrackingu:

def mincovka2(mince, suma):
    if suma in mince:
        return [suma]
    naj = None
    for minca in mince:
        if minca < suma:
            ries = mincovka2(mince, suma-minca) + [minca]
            if naj is None or len(ries) < len(naj):
                naj = ries
    return naj
>>> mincovka2([1, 3, 7, 10], 14)
[7, 7]

Zloťitosť tohto algoritmu je O(2**n)

Mincovka pomocou memoizácie

Predchádzajúci rekurzívny algoritmus je pre väčšie hodnoty veľmi pomalý (podobne ako rekurzívna fibonacciho funkcia). Môžeme ho výrazne urýchliť pomocou memoizácie:

  • zadefinujeme globálnu premennú mem ako prázdne asociatívne pole a rekurzívna funkcia mincovka3() najprv v tomto poli zistí, či už túto hodnotu nemá vypočítanú a ak áno vráti ju ako výsledok
def mincovka3(mince, suma, mem={}):
    if suma in mem:
        return mem[suma]             # už sme to počítali predtým
    if suma in mince:
        mem[suma] = [suma]
        return [suma]
    naj = None
    for minca in mince:
        if minca < suma:
            ries = mincovka3(mince, suma-minca) + [minca]
            if naj is None or len(ries) < len(naj):
                naj = ries
    mem[suma] = naj
    return naj

Zložitosť tohlo algoritmu je O(mn), ked m je počet mincí a n je samotná rozmieňaná suma.

Vyskúšajte zavolať obe tieto funkcie aj pre väčšie hodnoty, napr.

>>> mincovka2([1, 3, 7, 10, 20], 45)
?
>>> mincovka3([1, 3, 7, 10, 20], 45)
?

Preskúmajme obsah poľa mem po jednom zavolaní mincovka3:

>>> mincovka3([1, 3, 7, 10], 14)
[7, 7]
>>> mincovka3.__defaults__[0]
{10: [10], 7: [7], 3: [3], 1: [1], 4: [3, 1], 2: [1, 1], 5: [3, 1, 1],
 8: [7, 1], 11: [10, 1], 6: [3, 3], 9: [7, 1, 1], 12: [10, 1, 1],
 13: [10, 3], 14: [7, 7]}
>>> sorted(mincovka3.__defaults__[0])
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

Mincovka pomocou Dynamického programovania

Obsah pomocného poľa mem, ktoré sa využilo pre memoizáciu môže byť inšpiráciou pre riešenie pomocou ozajstného dynamického programovania:

  • funkcia mincovka4() najprv zostaví tabuľku podobnú mem, ale urobí to bez rekurzie metódou zdola nahor: postupne ju bude zapĺňať zľava doprava, t.j. z hodnôt na menších indexoch vypočíta hodnoty na vyšších
  • prvkami tabuľky budú minimálne počty rozmieňania na mince pre dané sumy, t.j. tab[suma] bude minimálny počet mincí, na ktoré sa dá daná suma rozmeniť
  • bude sa pri tom používať podobný cyklus ako v mincovka2(), ktorý hľadal minimálny počet mincí rozmieňaní, ale namiesto rekurzie tu bude vytiahnutie hodnoty z tabuľky tab
def mincovka4(mince, suma):
    tab = [0] * (suma+1)
    for s in range(1, suma+1):
        ...
    return tab[suma]

Odhadnime časovú zložitosť algoritmu:

Teraz dopíšeme do funkcie mincovka4() záverečnú časť, ktorá na základe tabuľky tab zrekonštruuje zoznam použitých mincí a funkcia potom namiesto počtu mincí vráti zoznam (pole) použitých mincí. Vypíšme túto tabuľku napr. pre mincovka4([1,3,7,10,20], 19):

[0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 1, 2, 3, 2, 2, 3, 3, 2, 3, 4]

V tejto tabuľke posledná 4 označuje, že suma 19 sa dá rozmeniť 4 mincami, preto musí v tejto tabuľke existovať nižšia suma, ktorá sa dá rozmeniť 3 mincami a od 19 sa líši presne o niektorú z mincí (t.j. treba skontrolovať 19-1, 19-3, 19-7, … a ktorá z týchto súm sa dá rozmeniť 3 mincami, tak tú vyberieme), nech je to napr. minca 7. Zaradíme mincu 7 do zoznamu pre výsledok a pokračujeme v hľadaní ďalšej mince: v tabuľke tab[19-7] má hodnotu 3, preto hľadáme takú mincu, že tab[12-minca]==2, ak je tabuľka skonštruovaná korektne, taká minca bude aspoň jedna. Takto pokračujeme, kým neposkladáme kompletný zoznam mincí

Výsledný program:

def mincovka4(mince, suma):
    tab = [0] + [None] * suma
    for s in range(1, suma+1):
        for m in mince:
            if s >= m and tab[s-m] is not None:
                if tab[s] is None or tab[s] > tab[s-m]+1:
                    tab[s] = tab[s-m]+1
    #print(tab)
    return tab[suma]

napr.

>>> mincovka4([3, 5], 7)
[0, None, None, 1, None, 1, 2, None]

Najdlhšie podpostupnosti

Ďalšou skupinou úloh sú problémy, v ktorých sa v jednorozmernom poli čísel (alebo pre dve jednorozmerné polia, nemusia byť číselné) hľadá:

  1. najdlhšiu súvislú rastúcu podpostupnosť (sekvencia)
    • napr. pre 3, 7, 2, 9, 4, 1, 5, 6, 10, 8, 0 dostaneme 1, 5, 6, 10
  2. najdlhšiu vybranú rastúcu podpostupnosť
    • napr. pre 3, 7, 2, 9, 4, 1, 5, 6, 10, 8, 0 dostaneme, napr. 2, 4, 5, 6, 8 alebo 3, 4, 5, 6, 10
  3. najdlhšiu súvislú spoločnú podpostupnosť dvoch postupností
  4. najdlhšiu vybranú spoločnú podpostupnosť dvoch postupností

Algoritmy všetkých štyroch úloh sú navzájom veľmi podobné a samozrejme, že sa riešia pomocou dynamického programovania. My si ukážeme riešenie 2. úlohy.

Najdlhšia vybraná rastúca podpostupnosť

Rieši sa pomocou dynamického programovania napr. takto:

  • postupne sa zostavuje tabuľka tab, v ktorej i-ty prvok obsahuje dĺžku najdlhšej vybranej rastúcej podpostupnosti, ktorá končí i-tym prvkom, zrejme túto hodnotu budeme počítať len z prvých i-1 prvkov, t.j.
    • tab[0] je zrejme 1, lebo ak berieme prvky poľa len po 0, tak tento je 1-prvkovou postupnosťou
    • tab[1] má byť dĺžkou najdlhšej rastúcej podpostupnosti, ak berieme do úvahy len 0. a 1. prvok poľa a pritom vybraná podpostupnosť končí 1. prvkom: bude tu 1 alebo 2
    • tab[2] je opäť dĺžkou najdlhšej, ak berieme len prvé 3 prvky, pričom nás zaujímajú len podpostupnosti, ktoré končia 3. prvkom: tretí prvok môže nadväzovať buď na postupnosť končiacu v prvom alebo končiacu v druhom prvku (závisí to od toho, či je tretí prvok väčší ako prvý alebo druhý a ktorá z týchto podpostupností je dlhšia)
    • takto postupne vybudujeme celú tabuľku tab
  • dynamicky toto pole tab budete vytvárať budete pre vstupnú postupnosť post takto:
    • pre tab[i] nájdeme najväčšiu hodnotu medzi tab[0:i-1] (na indexe j), pre ktorú je post[j] < post[i] - do tab[i] zapíšeme túto najväčšiu hodnotu zvýšenú o 1
    • ak medzi tab[0:i-1] nie je žiadna, pre ktorú by platilo post[j] < post[i], do tab[i] zapíšeme 1 (zrejme post[i] nie je väčšie ako žiadne z post[0:i-1])
  • z takto zostavenej tabuľky tab vieme zistiť hľadanú dĺžku podpostupnosti (je to maximálna hodnota v tabuľke) a tiež vieme zrekonštruovať hľadanú podpostupnosť:
    • v tab pôjdeme od konca a postupne hľadáme prvý výskyt pozícií s jednotlivými dĺžkami (najprv max, potom max-1, max-2, …, 2, 1)

Riešenie:

def hladaj(post):
    tab = [0] * len(post)
    for i in range(len(post)):
        max = 0
        for j in range(i):
            if post[j] < post[i]:
                if tab[j] > max:
                    max = tab[j]
        tab[i] = max + 1
    print('tabulka:', *tab)
    max_i = 0
    for i in range(len(tab)):
        if tab[i] > tab[max_i]:
            max_i = i
    dlzka = tab[max_i]
    print('naj dlzka =', dlzka)
    vysl = [post[max_i]]
    i = max_i
    for d in reversed(range(1, dlzka)):
        for j in range(i):
            if tab[j] == d and post[j] < post[i]:
                break
        vysl.insert(0, post[j])
        i = j
    print('hladana podpostupnost:', *vysl)
    return vysl
>>> pole = [3, 7, 2, 9, 4, 1, 5, 6, 10, 8, 0]
>>> hladaj(pole)
tabulka: 1 2 1 3 2 1 3 4 5 5 1
naj dlzka = 5
hladana podpostupnost: 3 4 5 6 10
[3, 4, 5, 6, 10]

Spracovanie textov

Otestujme štandardnú metódu str.find(), ktorá hľadá prvý výskyt nejakého podreťazca:

>>> 'python'.find('th')
2
>>> 'python'.find('ty')
-1

Je to rýchle aj pre dlhšie reťazce:

>>> ('a'*1000000).find('a'*10000+'b')
-1

ale toto už trvá citeľne dlhšie:

>>> ('a'*1000000).find('a'*10000+'b'+'a'*10000)
-1
>>> ('a'*1000000).find('a'*100000+'b'+'a'*100000)
-1

Prečo? Skúsme naprogramovať túto metódu - použijeme tzv. hrubú silu (brute force):

def hladaj(ret, pod):         # podobné ako str.find(ret, pod)
    n, m = len(ret), len(pod)
    for j in range(n-m+1):
        k = 0
        while k < m and ret[j+k] == pod[k]:
            k += 1
        if k == m:
            return j
    return -1

Funkcia hľadá najľavejší výskyt reťazca pod v nejakom reťazci ret. To, čo sme skúšali s str.find() už pomocou našej funkcie hladaj() trvá nepoužiteľne pomaly. Už len toto:

>>> hladaj('a'*10000, 'a'*500+'b'+'a'*500)
-1

trvá niekoľko sekúnd.

Zložitosť nášho algoritmu hladaj() je O(n*m), kde n je dĺžka reťazca ret a m je dĺžka hľadaného podreťazca pod. Pre veľké m blížiace sa k n je to vlastne kvadratické a teda dosť pomalé.

Uvádzame ukážku riešení dvoch problémov: najprv je to KMP, ktorý hľadá prvý výskyt podreťazca efektívnejšie ako naša funkcia `hladaj(). Druhým algoritmom je LCS t.j. hľadanie najdlhšej (vybranej) spoločnej podpostupnosti dvoch reťazcov. S oboma algoritmami sa podrobnejšie zoznámite vo vyšších ročníkoch.

Knuth-Morris-Pratt

Algoritmus KMP publikovali 1976:

def hladaj_kmp(ret, pod):
    n, m = len(ret), len(pod)
    if m == 0:
        return 0
    skok = pocitaj_kmp(pod)
    k = 0
    for j in range(n):
        while k > 0 and ret[j] != pod[k]:
            k = skok[k-1]
        if ret[j] == pod[k]:
            k += 1
        if k == m:
            return j-m+1
    return -1

Aby toto fungovalo, konštruuje sa špeciálna tabuľka rýchlych skokov:

def pocitaj_kmp(p):
    m = len(p)
    skok = [0] * m
    k = 0
    for j in range(1, m):
        while k > 0 and p[j] != p[k]:
            k = skok[k-1]
        if p[j] == p[k]:
            k += 1
        skok[j] = k
    return skok

Vďaka tomuto sú niektoré vyhľadávania veľmi rýchle, napr.

>>> hladaj_kmp('a'*1000000, 'a'*10000+'b'+'a'*10000)
-1

je rýchlejšie ako pythonovská štandardná metóda:

>>> ('a'*1000000).find('a'*10000+'b'+'a'*10000)
-1

Zložitosť algoritmu KMP je O(m+n). Keď porovnáme s algoritmom hrubej sily, v ktorom sme niektoré znaky reťazca ret porovnávali s reťazcom pod veľakrát, v algoritme KMP sa index j do poľa ret iba zvyšuje o 1 a nikdy sa nevracia späť (ako pri hrubej sile), t.j. každý znak reťazca ret sa spracuje len raz.

Algoritmus KMP má veľmi názorné vizualizácie na stránkach:

Longest Common Subsequence

Algoritmus LCS označuje hľadanie najdlhšej (vybranej) spoločnej podpostupnosti dvoch reťazcov (resp. dvoch polí):

  • predpokladajme, že máme dané 2 reťazce x a y s dĺžkami n a m znakov, úlohou je vybrať čo najdlhšiu podpostupnosť znakov z prvého reťazca (znaky sa nemuseli nachádzať tesne vedľa seba, len ich z postupne vyberáme zľava doprava) takú, že sa celá nachádza v druhom reťazci (tiež to nemuseli byť znaky tesne vedľa seba, len sa v reťazci nachádzali postupne na pozíciách zľava doprava)
  • napr. reťazce 'programovanie' a 'krasokorculovanie' majú najdlhší spoločný podreťazec 'rorovanie'

Doteraz by sme túto úlohu riešili asi hrubou silou:

  1. postupne by sme z prvého reťazca generovali všetky podpostupnosti znakov (asi od najdlhších po najkratšie)
  2. pre každý jeden vygenerovaný reťazec by sme skontrolovali, či sa celý presne v tomto poradí znakov nachádza v druhom reťazci
  3. ak áno, našli by sme najdlhší a môžeme skončiť

Tento algoritmus má zložitosť O(2**n), lebo všetkých vygenerovaných podreťazcov reťazca dĺžky n je 2**n.

Ukážeme riešenie pomocou metódy dynamické programovanie.

Algoritmus LCS (longest common subsequence) je typickým predstaviteľom dynamického programovania. Aby sme mohli túto úlohu riešiť touto metódou, musíme vymyslieť, ako na to využijeme postupné budovanie (možno dvojrozmernej) tabuľky: čo si budeme v tejto tabuľke pamätať (aké podúlohy) a ako sa z nich budú dať vytvárať riešenia zložitejších podúloh.

Na riešenie využijeme dvojrozmernú tabuľku, v ktorej si budeme uchovávať informácie o dĺžkach LCS, ale len pre nejaké podreťazce (teda nie pre celé reťazce x a y). Predpokladajme, že reťazec x má dĺžku n (s indexmi od 0 do n-1) a reťazec y má dĺžku m (s indexmi od 0 do m-1). Potom v tabuľke tab[i][j] bude dĺžka LCS (najdlhšej spoločnej podpostupnosti) ale vypočítaná len pre časť reťazca x[:i] a časť reťazca y[:j]. Preto:

  • nultý riadok tabuľky označuje, že z reťazca x berieme len rez x[:0], t.j. prázdny reťazec a preto tento riadok obsahuje samé 0 (LCS prázdneho reťazca a reťazca y je vždy 0)
  • podobne nultý stĺpec tiež obsahuje samé 0
  • prvý riadok tab[1][j] označuje LCS, ak je x iba jednoznakové, teda môže byť buď 0, kým sú rôzne znaky v x[0] a v y alebo 1, ak sme našli prvú zhodu, t.j. pozíciu j, v ktorej x[0]==y[j+1] - uvedomte si, že od tejto pozície bude mať v tabuľke tab[1] všetky hodnoty 1, lebo LCS x[0] a y[:j] je 1 (existuje v ňom podreťazec dĺžky 1)
  • každý ďalší, teda i -ty riadok, budeme postupne počítať takto:
    • ak x[i]==y[j], nám umožní predĺžiť doterajšie LCS o 1, ktoré boli pre podreťazce x[:i] a y[:j] (teda o 1 kratšie) - ale pre tieto kratšie x a y už máme vypočítanú dĺžku LCS v našej tabuľke na pozícii tab[i][j], preto nová hodnota v tabuľke tab[i+1][j+1] bude tab[i][j]+1
    • ak sa x[i]!=y[j], nič sa predlžovať nebude, budeme len kopírovať niektorú z hodnôt v doteraz vytvorenej tabuľke tab: zoberieme buď hodnotu tab[i][j+1] (o jedna kratšie x) alebo tab[i+1][j] (o jedna kratšie y), zrejme to bude väčšia z týchto hodnôt

Týmto postupom vytvoríme dvojrozmernú tabuľku maximálnych dĺžok LCS pre všetky podreťazce x a y (ktoré začínajú na index 0) a zrejme hľadaná dĺžka LCS bude v tabuľke na tab[n][m].

Ukážme to na reťazcoch:

x = 'abbccbddbd'
y = 'cadbddbbada'

Náš postup z nich vytvorí takúto tabuľku:

    c a d b d d b b a d a
  0 0 0 0 0 0 0 0 0 0 0 0
a 0 0 1 1 1 1 1 1 1 1 1 1
b 0 0 1 1 2 2 2 2 2 2 2 2
b 0 0 1 1 2 2 2 3 3 3 3 3
c 0 1 1 1 2 2 2 3 3 3 3 3
c 0 1 1 1 2 2 2 3 3 3 3 3
b 0 1 1 1 2 2 2 3 4 4 4 4
d 0 1 1 2 2 3 3 3 4 4 5 5
d 0 1 1 2 2 3 4 4 4 4 5 5
b 0 1 1 2 3 3 4 5 5 5 5 5
d 0 1 1 2 3 4 4 5 5 5 6 6

Tu sme do prvého riadka nad príslušné stĺpce tabuľky tab zapísali zodpovedajúce znaky reťazca y. Podobne sme na začiatok každého riadka zapísali znaky reťazca x. Všimnite si, že aj v tomto výpise i -temu znaku x zodpovedá i+1 riadok tabuľky a j -temu znaku y zodpovedá j+1 stĺpec tabuľky. Tabuľka má zrejme o 1 riadok viac ako je dĺžka reťazca x a o 1 stĺpec viac ako je dĺžka reťazca y.

Zapíšme funkciu, ktorá vytvára túto tabuľku:

def lcs_tab(x, y):
    n, m = len(x), len(y)
    tab = [[0]*(m+1) for i in range(n+1)]
    for i in range(n):
        for j in range(m):
            if x[i] == y[j]:
                tab[i+1][j+1] = tab[i][j] + 1
            else:
                tab[i+1][j+1] = max(tab[i][j+1], tab[i+1][j])
    return tab

Ak by nám stačila informácia o dĺžke LCS, mohli by sme skončiť s hodnotou tab[n][m]. Ak ale potrebujeme získať aj konkrétny podreťazec, môžeme z tejto tabuľky toto zrekonštruovať:

  • začneme v pravom dolnom rohu tabuľky - tu vieme, aká je dĺžka hľadaného podreťazca:

    i, j = len(x), len(y)
    
  • hľadáme smerom „hore“ (i-=1) a „vľavo“ (j-=1) znak, ktorý majú x aj y rovnaký - keďže v tabuľke tab[i][j] označuje znaky x[i-1] a y[j-1], testujeme:

    if x[i-1] == y[j-1]:
    
  • v prípade, že nájdeme hľadaný spoločný znak, zaradíme ho do výsledku (na začiatok, lebo výsledok skladáme od konca):

    ries = x[i-1] + ries
    
  • keď sa hýbeme „hore“ alebo „vľavo“ vyberáme si smer, kde je väčšia hodnota, teda porovnávame tab[i-1][j] a tab[i][j-1]

Funkcia, ktorá z tabuľky vytvorí hľadanú podpostupnosť:

def lcs_ries(x, y):
    tab = lcs_tab(x, y)
    ries = ''
    i, j = len(x), len(y)
    while tab[i][j] > 0:
        if x[i-1] == y[j-1]:
            #print(i-1, j-1, x[i-1])
            tab[i][j] = -tab[i][j]
            ries = x[i-1] + ries
            i -= 1
            j -= 1
        elif tab[i-1][j] >= tab[i][j-1]:
            i -= 1
        else:
            j -= 1
    return ries

Otestujme:

x, y = 'abbccbddbd', 'cadbddbbada'
print(f'x = {x!r}\ny = {y!r}')
print('lcs =', lcs_ries(x, y))
x = 'abbccbddbd'
y = 'cadbddbbada'
lcs = abddbd

Aj algoritmus LCS má veľmi názornú vizualizáciu na stránke:

Kompresia

Rôzne postupnosti znakov treba niekedy čo najviac zhustiť do čo najmenšej postupnosti bitov. Napr.

'aaabacaabada'

môžeme pomocou ord() zakódovať do 12 * 8 bitov (každý ASCII znak má 8 bitov), teda 96. Keďže sú to len 4 rôzne znaky, vieme každý z nich zakódovať do 2 bitov, napr. takto

'a'  00
'b'  01
'c'  10
`d`  11

'aaabacaabada' => 000000010010000010001100

Teraz by náš skomprimovaný reťazec mal iba 12 * 2 bity, teda spolu 24 bitov. Lenže 'a' sa v reťazci vyskytuje výrazne častejšie ako zvyšné znaky. Možno by sme ho mohli zakódovať len 1 bitom a zvyšné môžu mať prípadne bitov viac, napr. takto

'a'  0
'b'  10
'c'  110
`d`  111

'aaabacaabada' => 000100110001001110

V tomto prípade sme to skomprimovali na 18 bitov. Teraz treba dať pozor, aby sme zvolili také kódovanie, ktoré budeme vedieť spätne jednoznačne rozkódovať:

  • nemalo by sa stať, že kód jedného znaku je spoločný nejakému začiatku (prefixu) iného kódu

Zrejme časté znaky by mohli byť kódované menším počtom bitov a zriedkavé môžu byť aj dlhšie. Na toto slúži tzv. Huffmanovo kódovanie. Algoritmus pre toto kódovanie pracuje na tomto princípe:

  • zoberie sa nejaký text, ktorý reprezentuje reťazce, ktoré sa budú komprimovať týmto kódovaním
  • vytvorí sa frekvenčná tabuľka ft[c] výskytov jednotlivých znakov
  • pripraví sa prázdny prioritný front q
  • pre každý znak z množiny vstupných znakov sa vytvorí binárny strom s jediným vrcholom, ktorý je koreňom a zároveň listom stromu, a obsahuje tento znak, potom sa dvojica ft[c] a tento jednovrcholový strom vloží do prioritného frontu q, pričom frekvenčná hodnota je kľúčom a strom je príslušnou hodnotou
  • prioritný front teraz obsahuje dvojice (číslo, strom) usporiadané od najmenšieho čísla (najmenšieho počtu výskytov)
  • v ďalšej fáze algoritmu sa z q vyberajú vždy prvé dva prvky: z týchto dvoch stromov sa poskladá nový tak, že do koreňa ite súčet ich frekvencií, ľavý podstrom je prvý vybratý strom a pravý podstrom je druhý vybratý strom - do q sa teraz vloží nová dvojica: kľúčom je súčet frekvencií a hodnotou je tento nový strom
  • toto sa opakuje, kým vo fronte neostane jediný prvok a tým je kompletný binárny strom

Tento strom budeme používať na kódovanie jednotlivých znakov zo vstupu:

  • vyhľadáme pozíciu kódovaného znaku od koreňa stromu a cesta k nemu bude kódom: posun vľavo je bit 0 a posun vpravo 1
  • čím je nejaký znak v strome hlbšie, aj jeho cesta je dlhšia a teda aj jeho bitová reprezentácia je dlhšia
  • čím je znak v strome vyššie, má kratšiu cestu a teda aj kratšiu bitovú reprezentáciu

Strom sme predsa skonštruovali tak, že najprv sme spolu skladali znaky s malou frekvenciou a nad ne sme stále pridávali znaky s vyššou a vyššou frekvenciou. Samotnú funkciu by sme mohli zapísať napr. takto:

def huffman(ret):
    ft = {}
    for c in ret:
        ft[c] = ft.get(c, 0) + 1
    q = PriorityQueue()
    for c in set(ret):
        t = BinTree(c)
        q.add(ft[c], t)
    while len(q) > 1:
        f1, t1 = q.remove_min()
        f2, t2 = q.remove_min()
        t = BinTree(f1+f2, t1.root, t2.root)
        q.add(f1+f2, t)
    f, t = q.remove_min()
    return t

Trieda BinTree má konštruktor, ktorý vytvorí koreň s danou hodnotou a prípadne nastaví ľavý a pravý podstrom.

Algoritmus Huffman má tiež veľmi názornú vizualizáciu na stránke:



Cvičenia

L.I.S.T.

kombinačné čísla

  1. Zapíš a otestuj rekurzívne riešenie komb(n, k) = komb(n-1, k) + komb(n-1, k-1)
    • zisti počet rekurzívnych volaní pre n in (20,21,22,…30): komb(n, k=15)

  1. Zapíš nerekurzívnu verziu komb1(n, k), ktorá najprv skonštruuje dvojrozmernú tabuľku pre n riadkov a k stĺpcov a na základe nej vráti výsledok

    • funkcia:

      def komb1(n, k):
          # ... vytvor dvojrozmernú tabuľku veľkosti n x k, kde tab[i][j] = hodnota komb(i, j)
          # ... tabuľku vytvor metódou zdola nahor, t.j. najprv pre malé i a j
          return tab[n][k]
      

  1. (*) Rieš ako v (2) ale namiesto dvojrozmernej tabuľky pracuj len s jedným riadkom (z i-teho vyrob (i+1)-ty riadok)

    • funkcia:

      def komb2(n, k):
          ...
      
    • otestuj správnosť, napr.

      for n in range(10):
          for k in range(0, n+1):
              if not komb(n, k) == komb1(n, k) == komb2(n, k):
                  print(n, k, komb(n, k), komb1(n, k), komb2(n, k))
      

  1. Rieš memoizáciou, t.j. do rekurzívneho riešenia pridaj pamätanie si vypočítaných hodnôt a ich neskoršie použitie

    • funkcia:

      def komb3(n, k, mem={}):
          ...
      
    • otestuj

    • vyskúšaj použiť functools.lru_cache


funkcia P

  1. Funkcia P(i, j) pre nezáporné i a j je zadaná takto:

    • ak j=0, výsledkom je 0
    • ak i=0, výsledkom je 1
    • inak výsledkom je (P(i-1, j) + P(i, j-1))/2

    Ručne vytvor tabuľku veľkosti 4x4 pre hodnoty z range(4)


  1. Zapíš rekurzívnu funkciu
    • skontroluj správnosť ručnej tabuľky z (5)
    • zisti počet rekurzívnych volaní pre i in (10,11,12,…20) a j=10
    • odhadni zložitosť

  1. Vyrieš memoizáciou

  1. (*) Vyrieš vytvorením dvojrozmernej tabuľky veľkosti i x j, ktorú vyplníš po riadkoch bez rekurzie
    • skontroluj správnosť ručnej tabuľky z (5)
    • odhadni zložitosť tejto verzie

najdlhšia vybraná podpostupnosť

  1. Na základe algoritmu z prednášky pre „najdlhšia vybraná rastúca podpostupnosť“ najprv

    • ručne bez počítača vytvor tabuľku dĺžok pre danú postupnosť:

      post = [5, 4, 2, 4, 1, 1, 3, 4, 3, 4, 4, 1, 1, 2, 3, 3, 5, 4, 2, 2]
      
    • z tejto tabuľky dĺžok zrekonštruuj hľadanú vybranú podpostupnosť (úloha môže mať viac riešení)

    • tabuľku aj výsledok skontroluj spustením programu z prednášky


  1. Uprav funkciu hladaj() z prednášky tak, aby hľadal najdlhšiu vybranú neklesajúcu podpostupnosť (z predchádzajucej postupnosti post vie takto vybrať podpostupnosť dĺžky 8)

    • teraz pre postupnosť:

      >>> post = [5, 4, 2, 4, 1, 1, 3, 4, 3, 4, 4, 1, 1, 2, 3, 3, 5, 4, 2, 2]
      >>> len(hladaj_neklesajucu(post))
      8
      

  1. Algoritmus z prednášky najprv vytvára tabuľku maximálnych dĺžok podpostupností, potom v tejto tabuľke nájde maximálny prvok a na koniec z nej zrekonštruuje hľadanú podpostupnosť. Úloha by sa dala vyriešiť aj trochu inak:
    • tabuľka sa vytvára rovnakým postupom, ale zapisujú sa do nej nie dĺžky ale nájdené maximálne podpostupnosti
    • z tejto tabuľky potom stačí vyhľadať ľubovoľnú podpostupnosť maximálnej dĺžky
    • naprogramuj túto ideu a skontrolujte s výsledkami úloh v (9) a (10) - mal by si dostať rovnaké výsledky
    • odhadni pamäťovú zložitosť oboch algoritmov (zaujíma nás použitá pamäť v najhoršom prípade)
      • z porovnania pamäťovej zložitosti týchto dvoch algoritmov by mohlo byť jasné, prečo sa použil variant z prednášky

najdlhšia súvislá rastúca podpostupnosť

  1. (*) Riešenie tejto úlohy sa veľmi podobá predchádzajúcemu algoritmu z prednášky pre vybranú podpostupnosť:

    • najprv sa vytvorí tabuľka maximálnych dĺžok súvislých podpostupností, ktoré končia na danom indexe:

      • ak je post[i-1] < post[i], potom tab[i] = tab[i-1] + 1, inak tab[i] = 1
    • potom sa v tejto tabuľke nájde maximálny prvok - to je dĺžka maximálnej podpostupnosti a index vyjadruje index posledného prvku z tejto podpostupnosti

    • spätne sa vytvorí hľadaná súvislá podpostupnosť

    • ručne vytvor tabuľku pre

      pole = [3, 7, 2, 9, 4, 1, 5, 6, 10, 8, 0]
      
    • zapíš algoritmus a skontroluj vytvorenú tabuľku


  1. (*) Úloha sa dá riešiť aj bez použitia tabuľky: stačí si pamätať doteraz najlepšiu dĺžku a index, kde končí táto podpostupnosť
    • zapíš algoritmus bez použitia tabuľky (pamäťová zložitosť bude teraz O(1))
    • skontroluj výsledky porovnaním s algoritmom, ktorý pracuje s tabuľkou

hľadanie podreťazca

  1. Merajte čas trvania štandardenj metódy str.find() pri práci s dlhými reťazcami, ktoré obsahujú len písmená 'a' a 'b' (podobne ako v prednáške) - reťazec, v ktorom hľadáme nech má aspoň 1000000 znakov, hľadaný reťazec nech má dĺžky od 1000 do 100000.

    • napr. čas trvania príkazov:

      >>> str.find('a'*1000000, 'a'*10000+'b')
      >>> str.find('a'*1000000, 'a'*10000+'b'+'a'*10000)
      
    • porovnajte s algoritmom, ktorý hľadá hrubou silou (asi bude treba testovať kratšie reťazce)


  1. Funkciu hladaj z prednášky sme zapísali pomocou for-cyklu s else vetvou - preskúmaj, ako to funguje:

    • def hladaj(ret, pod):
          n, m = len(ret), len(pod)
          for j in range(n-m+1):
              for k in range(m):
                  if ret[j + k] != pod[k]:
                      break
              else:
                  return j
          return -1
      

  1. (*) Skúmaj, ako funguje algoritmus hladaj_kmp() napr. pre reťazce 'ababadababacabab' a 'ababaca':
    • vypíš zostavené pomocné pole skok
    • zamysli sa nad tým, ako by si toto pole vytváral ručne na papieri
    • pri každom prechode vnútorným while-cyklom vypíš reťazec ret pod ním reťazec pod ale odsunutý tak, aby zodpovedal momentálnym porovnávaným znakom (posun o j-k vpravo) a pod týmto riadkom riadok, v ktorom bude jediný znak '^' na pozícii porovnávaných znakov (t.j. j)
    • zamysli sa nad tým, ako by si tento algoritmus raelizoval ručne na papieri

Huffmanovo kódovanie

  1. Zostav (ručne na papieri) strom Huffmanovho kódovania pre slová nejakej konkrétnej vety , napr. 'mama ma emu a ema ma mamu'
    • vytvor kódovaciu tabuľku pre každé písmeno z tejto vety (t.j. aká postupnosť 0 a 1 zodpovedá, ktorému písmenu)
    • zakóduj (ako postupnosť bitov) celú vstupnú vetu
    • zakóduj reťazec 'uma eum uaa eme' - dostaneš asi 36 bitový reťazec 0 a 1 - teraz tento reťazec bitov ručne rozkóduj

  1. Aký tvar budem mať strom Huffmanovho kódovania a aké budú potom bitové kódy pre každé písmeno, ak máme 16 písmen 'a''p' :
    1. s rovnakou frekvenciou
    2. kde 'a' a 'b' majú frekvenciu 10 a všetky ostatné písmená majú 1
    3. kde prvých osem 'a''h' majú frekvenciu 10 a všetky ostatné písmená majú 1


6. Domáce zadanie

L.I.S.T.

Huffmanovo kódovanie

Definujte všetky metódy triedy Huffman, pomocou ktorej sa budú dať zakódovať a rozkódovať postupnosti údajov (reťazce a polia) Huffmanovým algoritmom. Z úlohového servera L.I.S.T. si stiahnite kostru programu riesenie6.py:

class Strom:
    def __init__(self, info=None, l=None, p=None):
        self.info, self.l, self.p = info, l, p


class Huffman:
    def __init__(self, vzorka):
        '''zostrojí kódovací strom podľa frekvencií údajov vo vzorke

           algoritmus:
                Vytvor frekvenčnú tabuľku ft pre každý prvok vo vzorke
                Initializuj prioritný front q
                for prvok v ft do
                    Vytvor binárny strom t s jediným vrcholom a s info = prvok
                    Vlož t do q s kľúčom ft(prvok)
                while len(q) > 1 do
                    (f1,t1) = q.remove_min()     # remove_min() vráti dvojicu (kľúč,hodnota)
                    (f2,t2) = q.remove_min()
                    Vytvor nový binárny strom t, ktorého ľavý podstrom je t1 a pravý t2
                    Vlož t do q s kľúčom f1+f2
                (f,t) = q.remove_min()           # t je kódovací strom
                self.strom = t
        '''
        self.strom = None    # Strom()

    def __getitem__(self, udaj):
        '''vráti zakódovaný jeden údaj ako postupnosť 0 a 1
           - postupnosť je cesta v strome k danému údaju, v ktorej vľavo značíme 0 a vpravo 1
           - ak sa údaj v strome nenachádza, vráti ''
        '''
        return ''

    def vsetky(self):
        '''vráti zoznam všetkých údajov v strome
        '''
        return []

    def zakoduj(self, udaje):
        '''vráti zakódované dáta ako postupnosť 0 a 1
           - postupne zakóduje všetku údaje
        '''
        return ''

    def odkoduj(self, postupnost):
        '''vráti odkódované dáta na základe danej postupnosti 0 a 1
        '''
        return []

Môžete spustiť tento test:

if __name__ == '__main__':
    h = Huffman([1,2,3,1,3,5,1,4,7,1,5,9,1,2,3,4,5,6,7,8,9])
    print('vsetky =', h.vsetky())
    kod = h.zakoduj(range(9, 0, -1))
    print('kod =', kod)
    print('udaje =', h.odkoduj(kod))
    print()
    h = Huffman('programujeme v programovacom jazyku python')
    print('vsetky =', h.vsetky())
    kod = h.zakoduj('aj v jave aj v c')
    print('kod =', kod)
    print('udaje =', ''.join(h.odkoduj(kod)))

A môžete dostať napr. takýto výstup:

vsetky = [1, 2, 3, 4, 5, 6, 7, 8, 9]
kod = 001000011100001011111111001010
udaje = [9, 8, 7, 6, 5, 4, 3, 2, 1]

vsetky = ['z', 'e', 'p', 'y', 'h', 'j', 'o', 'm', 'u', 't', 'r', ' ', 'n', 'a', 'k', 'g', 'v', 'c']
kod = 00011100010111100101110000011110111110100001110001011110010110101
udaje = aj v jave aj v c

Mali by ste dodržať tieto vlastnosti programu:

  • Nemeňte mená už zadaných atribútov (metódy a premenné).
  • Môžete definovať ďalšie pomocné triedy a aj pridávať vlastné atribúty do existujúcich tried.
  • Pri testovaní vášho riešenia sa bude kontrolovať aj vami vytvorený Huffmanov kódovací strom (v atribúte Huffman.strom).

Aby ste mohli spúšťať testy, program uložte do súboru riesenie6.py. Na začiatok súboru pridajte tieto tri komentárové riadky (s vašim menom a dátumom):

# 6. zadanie: huffman
# autor: Alan Turing
# datum: 1.12.2018

Riešenie odovzdajte na úlohový server L.I.S.T. najneskôr do 23:00 14. decembra. Môžete zaň získať 10 bodov.



© Copyright 2018-2019, Andrej Blaho.
Naposledy aktualizované 14. feb. 2019.
Vytvorené pomocou Sphinx 1.8.4.

Creative Commons License This work is licensed under a Creative Commons Attribution 4.0 International License.