Editace stránky Implementace databázových systémů/Komprese

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

Varování: Nejste přihlášen(a). Pokud uložíte jakoukoli editaci, bude vaše IP adresa zveřejněna v historii této stránky. Pokud se přihlásíte nebo si vytvoříte účet, budou vaše editace připsány vašemu uživatelskému jménu a získáte i další výhody.

Editace může být zrušena. Zkontrolujte a pak potvrďte změny zobrazené níže.
Aktuální verze Váš text
Řádka 6: Řádka 6:
 
[[Image:Komprese.png|right|thumb|604px|komprese textu]]
 
[[Image:Komprese.png|right|thumb|604px|komprese textu]]
 
obecné typy redukce dat:
 
obecné typy redukce dat:
*'''ztrátová '''(nazývá se <u>kompakce</u>) - např. obraz, zvuk, video
+
*ztrátová (nazývá se kompakce) - např. obraz, zvuk, video
*'''bezeztrátová '''(nazývá se <u>komprese</u> a je reverzibilní přes dekopresi)
+
*bezeztrátová (nazývá se komprese a je reverzibilní přes dekopresi)
  
 
Proces komprese má 2 fáze:
 
Proces komprese má 2 fáze:
* '''modelování '''(modely textu) - přiřazení pravděpodobností jednotkám textu (znaky nebo m-tice znaků pevné délky)
+
* modelování (modely textu) - přiřazení pravděpodobností jednotkám textu (znaky nebo m-tice znaků pevné délky)
* '''kódování '''- transformace do nového kódu pomocí modelu
+
* kódování - transformace do nového kódu pomocí modelu
  
dělení modelů (💡 jako by slovníky):
+
dělení modelů:
*statické - model je statický pro všechny dokumenty (uložen jednou)
+
*statická - model je statický pro všechny dokumenty (uložen jednou)
*semiadaptivní (polostatické) -  ∀dokument má vlastní model (pošle se s dokumentem)
+
*semiadaptivní (polostatické) -  každý dokument má vlastní model (pošle se s dokumentem)
*dynamické (adaptivní) - oba algoritmy si model tvoří na základě již zpracovaných dat (musí se dekodovat od zacatku)
+
*dynamická (adaptivní) - oba algoritmy si model tvoří na základě již zpracovaných dat (musí se dekodovat od zacatku)
 
[[Soubor:200px-Injection.svg.png|thumb|200x200px|f: A → C⁺ je <u>prosté</u> kódové zobrazení znaků z abecedy A do prostoru slov v abecedě C]]
 
[[Soubor:200px-Injection.svg.png|thumb|200x200px|f: A → C⁺ je <u>prosté</u> kódové zobrazení znaků z abecedy A do prostoru slov v abecedě C]]
====kódování====
+
====Kódování (čísel)====
 
{{Zkazky|
 
{{Zkazky|
 
* '''komprese (2015, konzultace Kopecký)''' - pod kódováním bych já asi viděl obecnou problematiku kódování (tj. věci jako reprezentace nějaké posloupnosti znaků slovy nějaké abecedy, prefixovost, jednoznačnou dekódovatelnost, vztah mezi prefixovostí a jednoznačnou dekódovatelností, entropii, a podobně. To další jsou pak speciální případy s nějakými konkrétními vlastnostmi. Když budete umět Fibbonaciho/Eliasovy kódy jako speciální případy pro nekonečné množiny s nerovnoměrnou pravděpodobností výskytu znaků, určitě to nebude na škodu.
 
* '''komprese (2015, konzultace Kopecký)''' - pod kódováním bych já asi viděl obecnou problematiku kódování (tj. věci jako reprezentace nějaké posloupnosti znaků slovy nějaké abecedy, prefixovost, jednoznačnou dekódovatelnost, vztah mezi prefixovostí a jednoznačnou dekódovatelností, entropii, a podobně. To další jsou pak speciální případy s nějakými konkrétními vlastnostmi. Když budete umět Fibbonaciho/Eliasovy kódy jako speciální případy pro nekonečné množiny s nerovnoměrnou pravděpodobností výskytu znaků, určitě to nebude na škodu.
Řádka 30: Řádka 30:
 
** '''jednoznačně dekódovatelný''' - ∀zakódovaný (cílový) řetěz ''Y'' ∃ max. 1 zdrojový řetěz ''X'' že f(''X'') = ''Y''.
 
** '''jednoznačně dekódovatelný''' - ∀zakódovaný (cílový) řetěz ''Y'' ∃ max. 1 zdrojový řetěz ''X'' že f(''X'') = ''Y''.
 
** '''<u>prefixový</u>''' -  jednotliva kodova slova nejsou prefixem zadneho jineho slova
 
** '''<u>prefixový</u>''' -  jednotliva kodova slova nejsou prefixem zadneho jineho slova
*** 💡 prefixový ⇒ jednoznačně dekódovatelný (opačně neplatí)
+
*** 💡 ∀prefixový kód je jednoznačně dekódovatelný
 
'''Entropie '''(míra informace) znaku ai v textu je rovna hodnotě E(''a''ᵢ) = -log( "pst výskytu znaku aᵢ v textu" ) bitů.
 
'''Entropie '''(míra informace) znaku ai v textu je rovna hodnotě E(''a''ᵢ) = -log( "pst výskytu znaku aᵢ v textu" ) bitů.
* 💡 tj. "obrácená hodnota" - čím je znak častější tím menší má entropii = tím méně informace nese (tím menší počet bitů je potřeba na její reprezentaci)
+
* tj. "obrácená hodnota" - čím je znak častější tím menší má entropii
* 💡 použítí viz: [[Databázové modely a jazyky#Indexace VDIS|IDF/ITF]]
+
  
 
* prům. entropie 1 znaku: AE(A) = -Σ ("pst výskytu znaku ai v textu") log( "pst výskytu znaku ''a''ᵢ v textu" )
 
* prům. entropie 1 znaku: AE(A) = -Σ ("pst výskytu znaku ai v textu") log( "pst výskytu znaku ''a''ᵢ v textu" )
** očekávaná délka 1 znaku přes ∀znaky a jejich psti
 
 
* entropie zprávy: E(A) = E(a₁...aₖ) = -Σ log( "pst výskytu znaku ''a''ᵢ v textu" )
 
* entropie zprávy: E(A) = E(a₁...aₖ) = -Σ log( "pst výskytu znaku ''a''ᵢ v textu" )
** 💡 tj. součet entropií znaků ve zprávě
 
 
** platí že délka zakódované zprávy je |f(A)| > E(A)
 
** platí že délka zakódované zprávy je |f(A)| > E(A)
 
** '''redundance:''' R = |f(A)| - E(A)
 
** '''redundance:''' R = |f(A)| - E(A)
Řádka 77: Řádka 74:
 
  | Huffmanovo k. se pouziva v poslední fázi u  
 
  | Huffmanovo k. se pouziva v poslední fázi u  
 
}}
 
}}
[[Image:Stathuff.png|thumb|205px|StatickyHuffman(EMA MELE MASO)<br>
 
seřadíme podle vyskytu, spojováním uzlů podle nejmenší četnosti zleva vytváříme binární strom
 
]]
 
 
{{Zkazky|* '''Huffmanovo kódování - statické, dynamické (2015, Holubová)''' - Hned na zacatku mi bylo receno, ze se mam zamerit na dynamicke H. kodovani. Mel jsem cokoliv zakodovat a dekodovat.  
 
{{Zkazky|* '''Huffmanovo kódování - statické, dynamické (2015, Holubová)''' - Hned na zacatku mi bylo receno, ze se mam zamerit na dynamicke H. kodovani. Mel jsem cokoliv zakodovat a dekodovat.  
 
* '''Huffmanovo kódování (2009)''' - stručně jsem popsal a nakreslil příklad k statické verzi, popsal jsem jak funguje dynamická, jak se mění strom atd.
 
* '''Huffmanovo kódování (2009)''' - stručně jsem popsal a nakreslil příklad k statické verzi, popsal jsem jak funguje dynamická, jak se mění strom atd.
Řádka 85: Řádka 79:
 
}}
 
}}
 
===='''Staticke Huffmanovo''' kodovaní====
 
===='''Staticke Huffmanovo''' kodovaní====
;Kodování:
+
{{zarovka
 +
|
 
# Spočítáme frekvence výskytů symbolů (včetně mezer).
 
# Spočítáme frekvence výskytů symbolů (včetně mezer).
 
# Seřadíme znaky od nejmenší frekvence.
 
# Seřadíme znaky od nejmenší frekvence.
 
# Spojováním dvojic zleva vytváříme strom. Nové vrcholy zařazujeme do řady (co nejvíce doprava).
 
# Spojováním dvojic zleva vytváříme strom. Nové vrcholy zařazujeme do řady (co nejvíce doprava).
 
# Levé hrany jsou 0, pravé 1.
 
# Levé hrany jsou 0, pravé 1.
 +
| statické kodovani
 +
}}
  
 +
:'''Vstup:''' seznam <math>n</math> zdrojovych jednotek ke kodovaní, <math>p</math> - usporadana posloupnost <math>n</math> vah (pravdepodobností) <math>p[i]</math> (<math>1 ≤ i ≤ n</math>) jejich vyskytu ve zprave
 +
:'''Vystup:''' kodova slova dana zretezením ohodnocení hran na cestach od korene k jednotlivym listum binarního stromu
 
* výsledný strom se nazývá Huffmanův, výsledný kód je prefixový
 
* výsledný strom se nazývá Huffmanův, výsledný kód je prefixový
 
* místo pravděpodobností můžeme použít i četnosti znaku, ohodnocení hran stromu pomocí 0 a 1 je konvencí (je tudíž možno použít i ohodnocení opačné)
 
* místo pravděpodobností můžeme použít i četnosti znaku, ohodnocení hran stromu pomocí 0 a 1 je konvencí (je tudíž možno použít i ohodnocení opačné)
 
* Huffmanuv i Shannon-Fanův kód je možné generovat v čase <math>O(n)</math>
 
* Huffmanuv i Shannon-Fanův kód je možné generovat v čase <math>O(n)</math>
 +
 +
<pre>
 +
BEGIN
 +
∀ jednotku i vytvoř list o(p[i])
 +
(uzel ohodnocený pravděpodobností p[i]);
 +
k := n;
 +
WHILE k ≥ 2 DO
 +
  BEGIN
 +
  vyber z p dvě nejmenší nenulové p[r] a p[s], kde r ≠ s;
 +
  q := p[r]+p[s];
 +
  vytvoř uzel ohodnocený q;
 +
  hranám < o(q); o(p[r]) > a < o(q); o(p[s]) >
 +
    přiřaď ohodnocení 0 a 1;
 +
  p[r] := q; p[s] := 0; k := k-1
 +
  END
 +
END
 +
</pre>
  
 
===='''Dynamické''' (Adaptivní) '''Huffmanovo''' kódování====
 
===='''Dynamické''' (Adaptivní) '''Huffmanovo''' kódování====
[[Image:ahc.png|thumb|300px|'''Sourozenecké pravidlo stromu:''' ∀ uzel má sourozence a četnosti v uspořádání podle červené šipky '''neklesají''']]
+
[[Image:ahc.png|right|thumb|394px|Sourozenecká vlastnost stromu: ∀ uzel má sourozence a četnosti v uspořádání podle č.šipky neklesají]]
 
* strom reorganizován podle toho, jak se mění pravděpodobnosti v průběhu kódování (tj. poruší se sourozenecké pravidlo)
 
* strom reorganizován podle toho, jak se mění pravděpodobnosti v průběhu kódování (tj. poruší se sourozenecké pravidlo)
* nepředpokládají se žádné informace o pravděpodobnostech zdrojových jednotek
+
* nepředpokládají se žádné informace o pravděpodobnostech zdrojových jednotek (strom ale můžeme inicializovat vstupní abecedou)
 
=====FGK (Faller, Galagher, Knuth)=====
 
=====FGK (Faller, Galagher, Knuth)=====
{| class="wikitable" style="font-size: 85%; width:700px;"
+
:'''Vstup:''' daný Huffmanův strom <math>T_1</math>, uzel <math>o</math>
|-
+
:'''Výstup:''' modif. Huff. strom <math>T_2</math>
! style="width:350px" | Dynamické kodovani
+
 
! style="width:350px" | dekódování
+
<pre>
|- 
+
BEGIN
|
+
current:=o;
# '''Init:''' Začínáme se stromem s 1 vrcholem (speciální).
+
WHILE current ≠ root DO
# '''Read:''' Načteme a najdeme znak ve stromu.
+
  BEGIN
#  '''Code:''' Na výstup vypisujeme čísla na hranách (0 vlevo, 1 vpravo). Není ve stromu⇒jdeme do speciálního vrcholu a pak '''vypíšeme znak na výstup'''.
+
  vyměň uzel a jeho příp.podstrom v current s uzlem o', který má nejvyšší pořadí mezi uzly se stejnou frekvencí;
# '''FixTree:''' Pokud znak ve stromu není, přidáme ho a aktualizujeme frekvence postupně až do kořene:
+
  četnost[current]++
#* Kontrolujeme zda ve stromu ve směru doprava nahoru není vrchol s menší frekvencí než je nová hodnota aktualizovaného. Pokud ano, vezmeme poslední takový a přehodíme ho s aktualizovaným (celé podstromy).
+
  current:=predcessor(current)
| style="vertical-align: top;" |
+
END
# '''Init:''' Začínáme se stromem s 1 vrcholem (speciální - ? nebo NYT).
+
END
#  '''Read:''' Čteme bity a podle nich hledáme ve stromě.
+
</pre>
# '''DeCode:''' Pokud dojdeme do listu s písmenem, vypíšeme ho.
+
 
# '''FixTree:''' Dojdeme-li do speciálního vrcholu, načteme znak ze vstupu.
+
* <math>AL_{HD} ≤ 2 . AL_{HS}</math>, kde <math>AL_{HD}</math> je průměrná délka kódových slov dynamického Huffmanova kódování a <math>AL_{HS}</math> statického
#* Znak vypíšeme.
+
{{TODO|příklad na nějakém textu}}
#* Znak přidáme do stromu stejně jako při kódování.
+
|}
+
* speciální vrchol se značí '''?''' nebo NYT
+
* první definice symbolů abecedy se kódují nějakým základním prefixovým kódem
+
* dosahuje mensi (lepsi) delky kodoveho slova oproti staticke verzi
+
{{collapse|1=<h6>příklad kódování "aa bb" (dekódování prakticky stejné):</h6>|2=
+
{{:Implementace_databázových_systémů/HuffmanSandbox}}
+
}}
+
 
{{collapse|💡 '''Λ (Vitter)'''| - složitější úprava FGK s těmito vlastnostmi:
 
{{collapse|💡 '''Λ (Vitter)'''| - složitější úprava FGK s těmito vlastnostmi:
 
* počet výměn podstromů je nejvýše <math>1</math>, přidá se escape sekvenci pro první výskyt nového znaku
 
* počet výměn podstromů je nejvýše <math>1</math>, přidá se escape sekvenci pro první výskyt nového znaku
Řádka 135: Řádka 143:
 
* http://www.stringology.org/DataCompression/fgk/index_en.html
 
* http://www.stringology.org/DataCompression/fgk/index_en.html
 
* http://www.stringology.org/DataCompression/ahv/index_en.html  
 
* http://www.stringology.org/DataCompression/ahv/index_en.html  
* http://www.ics.uci.edu/~dan/pubs/DC-Sec4.html#Algorithm%20FGK
 
* http://courses.cs.washington.edu/courses/csep590a/07au/lectures/lecture02small.pdf
 
 
}}
 
}}
  
Řádka 151: Řádka 157:
 
|2=aritmeticky zakodovat "JUJ!"
 
|2=aritmeticky zakodovat "JUJ!"
 
}}
 
}}
 
 
=== Aritmetické kódování  ===
 
=== Aritmetické kódování  ===
 
[[Soubor:400px-Arithmetic encoding.svg.png|400px|thumb|right|Diagram ukazující dekódování  
 
[[Soubor:400px-Arithmetic encoding.svg.png|400px|thumb|right|Diagram ukazující dekódování  
Řádka 186: Řádka 191:
  
 
==Slovníkové metody==
 
==Slovníkové metody==
 
+
=== LZ algoritmy  ===
 +
{{zkazky|
 +
* '''Komprese PNG a GIF (2012, Grafika, Zara)''' -  Nejhorsi otazku sem si nechal na konec...tuhle sem absolutne nemel pripravenou, navic ji zkousel Zara Snazil sem se co nejdyl mluvit o obecnych metodach komprese obrazu ( RLE, Huffman, LZ77, LZW, Aritmeticke kodovani, Transformace obrazu ) ...to me ale Zara brzo zarazil ze to moc nesouvisi s tim na co se me ptaji at zacnu byt konretnejsi Tak sem otocil papir a tam sem mel par strohych poznamek o PNG a GIF formatech Kdyz sem to zacal komentovat tak me Zara prerusil at je spis vzajemne porovnam kdyz o nich mluvim. Co konkretne ho zajimalo: oba bezeztratove, LZ77 vs LZW, ze oba pouzivaji progresivni metodu zobrazeni, Proc muze mit PNG lepsi kompresni pomer nez GIF kdyz GIF pouziva modernejsi LZW oproti LZ77 ( odpoved ze LZ77 muze byt lepsi nez LZW na nekterych vstupech protoze je to uplne neco jinyho se mu moc nelibila...spravna odpoved je podle Zary ze tam je lepsi prediktor) No casto sem tady tipoval, hodne sem toho nevedel, parkrat me Zara poucil jak ze to vlastne je...celkem bida, ale mel sem pocit ze k vyhazovu sem mel jeste furt nejakou rezervu
 +
}}
 
Kompresni algoritmy vytvareji pri sve praci slovnik, ktery pouzivaji ke kodovani vstupu. Vsechny metody jsou adaptivni, pri cteni kodu vytvari slovnik a zaroven taky generuji vysledny kod. Jsou kodovany "fraze" (shluky znaku nebo slova), cislovany ve slovniku od nuly.
 
Kompresni algoritmy vytvareji pri sve praci slovnik, ktery pouzivaji ke kodovani vstupu. Vsechny metody jsou adaptivni, pri cteni kodu vytvari slovnik a zaroven taky generuji vysledny kod. Jsou kodovany "fraze" (shluky znaku nebo slova), cislovany ve slovniku od nuly.
  
Řádka 192: Řádka 200:
 
# organizujici slova prirozeneho jazyka (BSTW)
 
# organizujici slova prirozeneho jazyka (BSTW)
 
# organizujici retezce (LZ*)
 
# organizujici retezce (LZ*)
=== LZ algoritmy  ===
 
{{zkazky|
 
* '''Komprese PNG a GIF (2012, Grafika, Zara)''' -  Nejhorsi otazku sem si nechal na konec...tuhle sem absolutne nemel pripravenou, navic ji zkousel Zara Snazil sem se co nejdyl mluvit o obecnych metodach komprese obrazu ( RLE, Huffman, LZ77, LZW, Aritmeticke kodovani, Transformace obrazu ) ...to me ale Zara brzo zarazil ze to moc nesouvisi s tim na co se me ptaji at zacnu byt konretnejsi Tak sem otocil papir a tam sem mel par strohych poznamek o PNG a GIF formatech Kdyz sem to zacal komentovat tak me Zara prerusil at je spis vzajemne porovnam kdyz o nich mluvim. Co konkretne ho zajimalo: oba bezeztratove, LZ77 vs LZW, ze oba pouzivaji progresivni metodu zobrazeni, Proc muze mit PNG lepsi kompresni pomer nez GIF kdyz GIF pouziva modernejsi LZW oproti LZ77 ( odpoved ze LZ77 muze byt lepsi nez LZW na nekterych vstupech protoze je to uplne neco jinyho se mu moc nelibila...spravna odpoved je podle Zary ze tam je lepsi prediktor) No casto sem tady tipoval, hodne sem toho nevedel, parkrat me Zara poucil jak ze to vlastne je...celkem bida, ale mel sem pocit ze k vyhazovu sem mel jeste furt nejakou rezervu
 
}}
 
 
====LZW - ''Posíláme jen odkaz do slovníku (na začátku je v něm abeceda)''====
 
====LZW - ''Posíláme jen odkaz do slovníku (na začátku je v něm abeceda)''====
'''Komprese''': pocatecnimi frazemi jsou jednotlive znaky. V kazdem kroku se najde nejdelsi fraze ve slovniku shodna se vstupem a jeji kod se zapise. Nova fraze vznika pridanim dalsiho znaku na konec akt. pouzite fraze.
+
* Komprese:pocatecnimi frazemi jsou jednotlive znaky. V kazdem kroku se najde nejdelsi fraze ve slovniku shodna se vstupem a jeji kod se zapise. Nova fraze vznika pridanim dalsiho znaku na konec akt. pouzite fraze.
 
+
* pr. vstup abacdacacadaad
'''pr. vstup ababababa'''
+
 
* poc. tabulka:
 
* poc. tabulka:
<pre> fraze  a  b
+
<pre> fraze  a  b   c  d
cislo  0  1
+
cislo  0  1   2  3</pre>
</pre>
+
 
*chod alg.
 
*chod alg.
<pre>
+
<pre>krok vstup        fraze  kod nova #
kod   | slovník:
+
abacdacacadaad a    0   ab 4
      | 0 a
+
2    bacdacacadaad b     1   ba 5
      | 1 b
+
3    acdacacadaad a    0  ac 6
a   0 | 2 ab
+
4     cdacacadaad c    2  cd  7
b   1 | 3 ba
+
5       dacacadaad d    3  da  8
ab 2 | 4 aba
+
6        acacadaad ac    6  aca 9
aba 4 | 5 abab
+
7          acadaad aca    9  acad 10
ba 3
+
8            daad da    8  daa  11
</pre>'''Dekomprese''': zacina se tak jako u komprese se slovnikem, ve kterem jsou pouze znaky. Nova fraze se tvori z predchozi plus prvniho pismena aktualni (je mozne, aby "nova" fraze sla hned na vystup - jeji zacatek znam - je z predchozi a posledni pismeno bude shodne s prvnim.
+
9              ad a      0  ad  12
* Komprese i dekomprese vytvori stejny slovnik, používá se v GIF
+
10              d d    3   -
 +
</pre>
 +
* Dekomprese: zacina se tak jako u komprese se slovnikem, ve kterem jsou pouze znaky. Nova fraze se tvori z predchozi plus prvniho pismena aktualni (je mozne, aby "nova" fraze sla hned na vystup - jeji zacatek znam - je z predchozi a posledni pismeno bude shodne s prvnim.
 +
* Komprese i dekomprese vytvori stejny slovnik
  
 
====LZ77 - ''Okénka (posíláme 3 údaje)''====
 
====LZ77 - ''Okénka (posíláme 3 údaje)''====
Řádka 222: Řádka 227:
 
*proč zrovna 7 – vejde se to tak akorát do 3 bitů a je to rychlé
 
*proč zrovna 7 – vejde se to tak akorát do 3 bitů a je to rychlé
 
*pr. EMA MELE MASO se zakoduje <0,0,E>, <0,0,M>, <0,0,A>, <0,0,MEZERA>, <3,1,E>, <0,0,L>, <2,1,MEZERA>, <5,1,A>, <0,0,S>, <0,0,O>,  
 
*pr. EMA MELE MASO se zakoduje <0,0,E>, <0,0,M>, <0,0,A>, <0,0,MEZERA>, <3,1,E>, <0,0,L>, <2,1,MEZERA>, <5,1,A>, <0,0,S>, <0,0,O>,  
* pužívá se v PNG
 
 
Dalsi algoritmy - existuje spousta variant LZ algoritmu (LZ78 – starší obdoba LZW, LZJ – variace na LZW, kde je omezena délka kódovaných řetězců,...)
 
Dalsi algoritmy - existuje spousta variant LZ algoritmu (LZ78 – starší obdoba LZW, LZJ – variace na LZW, kde je omezena délka kódovaných řetězců,...)
 
{{zdroje|
 
{{zdroje|
Řádka 228: Řádka 232:
 
}}
 
}}
  
== Komprese bitových map ==
+
== komprese bitových map, ==
{| class="wikitable" style="text-align:center; float:right"
+
{{TODO|projít}}
|-
+
!rowspan=2| Identifier
+
!rowspan=2| HasInternet
+
!colspan=2| Bitmaps
+
|-
+
!Y !! N
+
|-
+
|1 || Yes || 1|| 0
+
|-
+
|2 || No || 0 || 1
+
|-
+
|3 || No || 0 || 1
+
|-
+
|4 || Unspecified || 0 || 0
+
|-
+
|5 || Yes || 1 || 0
+
|}
+
Bitmapy se používají jako indexy pro atributy s malými doménami (napr.: muž/žena, low/medium/high,...)
+
*velikost bitmapy se rovná počtu záznamů * velikost domény ⇒ rostou lineárně s databází
+
*dotazování se dělá pomocí bitových logických boolovských operací
+
 
+
{{TODO|projít podle OZD1H}}
+
;Komprese:
+
 
Uvažujeme bitovou mapu, resp. její j-tý sloupec (i-tá pozice říká, že záznam i odpovídá určité j-té hodnotě, nebo např. že dokument i obsahuje term j)
 
Uvažujeme bitovou mapu, resp. její j-tý sloupec (i-tá pozice říká, že záznam i odpovídá určité j-té hodnotě, nebo např. že dokument i obsahuje term j)
  
Řádka 268: Řádka 249:
  
 
== Řídké matice ==
 
== Řídké matice ==
řídká matice obsahuje z velké většiny nuly (např. vektorový index - cca 90% nul), lze reprezentovat:
+
řídká matice obsahuje z velké většiny nuly, lze reprezentovat např.
*naivně ve tvaru matice (příliš veliké a neefektivní) ( <math>\vec{d}</math> = [w<sub>1</sub>, w<sub>2</sub>, ... ,  w<sub>k</sub>] )
+
*naivně ve tvaru matice (příliš veliké a neefektivní)
*seznamem indexů, kde se nachází nenulová hodnota ( <math>\vec{d}</math> = [j<sub>1</sub>:w<sub>j<sub>1</sub></sub>, j<sub>2</sub>: w<sub>j<sub>2</sub></sub>, ... ,  j<sub>k</sub>: w<sub>j<sub>k</sub></sub>] )
+
*seznamem indexů, kde se nachází nenulová hodnota  
** kontrukce posuny - matici rozdělit na řádky, vhodně posuneme řádky (zaznamenáme), složíme řádky (sečteme), zaznamenáme do kterého řádku políčko patří
+
*pomocí r^d (radix) stromů
** viz: [http://www.ksi.mff.cuni.cz/~zemlicka/pdf/2011/matcomp.pdf OZD II]  
+
{{TODO|nevim co dál, možná v DIS?}}
 +
[http://www.ksi.mff.cuni.cz/~zemlicka/pdf/2011/matcomp.pdf OZD II]
 +
 
 
{| class="wikitable" style="float:right"
 
{| class="wikitable" style="float:right"
 
!  colspan="4" | Burrowsova-Wheelerova transformace
 
!  colspan="4" | Burrowsova-Wheelerova transformace

Kliknutím na Save page

  • Potvrzujete, že vložené změny jsou vaším dílem, nebo jste oprávněni je zveřejnit a licencovat podle pravidel této stránky.
  • Potvrzujete, že smluvní podmínky níže uvedených licencí znáte a chápete, nebo se s nimi v nejbližší době seznámite.
  • Souhlasíte se zveřejněním svých změn podle licence MatfyzKing copyright
  • Souhlasíte se zveřejněním svých změn podle licence Creative Commons BY-NC-SA 2.0
  • Souhlasíte se zveřejněním svých změn podle licence GNU GFDL

Nevkládejte cizí díla bez prokazatelného souhlasu autora nebo držitelů práv!

Storno | Pomoc při editování (otevře se v novém okně)