Reprezentace dat:

jak peresistentně ukládat data?

  • prostorová náročnost
  • transparentnost
  • přenositelnost
  • jaké data lze reprezentovat
  • (bezpečnost)

Běžně používané "general purpose" datové formáty

Textové formáty (data jsou reprezentovány jako string)

CSV

https://cs.wikipedia.org/wiki/CSV

  • textová reprezentace
  • jednoduchá syntax, snadno napsatelný parser (ve většině jazyků k dispozici, třeba pandas.read_csv())
  • pouze 2D reprezentace dat, nelze (jednoduše) reprezentovat složitější datové typy
  • neznámá semantika dat, chybí typová kontrola (co je "002456"?)

JSON

https://www.json.org/json-cz.html

  • textová reprezentace
  • vytvořeno na základě objektů v JavaScriptu +/- odpovídá dictionary v Pythonu vč. syntaxe
  • libovolná hloubka informace (lze přímočaře reprezentovat složitější data než v CSV)
  • parser: https://www.w3schools.com/python/python_json.asp (load a dump metody)
  • nevýhoda: datově náročnější než CSV (opakují se klíče)
  • potenciálně proměnná struktura dat, chybí typová kontrola (co je "002456"?)

XML

https://cs.wikipedia.org/wiki/Extensible_Markup_Language

  • značkovací jazyk (obdoba HTML bez fixně definovaných tagů a jejich atributů)
  • lze definovat schéma dokumentu (třeba DTD) -> lze dodat semantiku dat
  • navázané jazyky jako XPath pro dotazování, konverze dokumentů (xslt) apod.
  • datově náročné, složitější tvorba (definice schématu apod.)

Výhody / nevýhody

  • horší prostorová náročnost
  • lepší transparentnost a přenositelnost
  • lepší bezpečnost
  • horší možnosti co lze reprezentovat

Běžný pracovní postup:

Vstupní entita prog. jazyka -> [konvertor] -> data -> stored data in some format -> load data -> [konvertor] -> výstupní entita prog. jazyka

  • kdo se postará o správnou konverzi?
  • je vstupní a výstupní konstrukt stejný? (pomocí json.load() dostanu dictionary, ale co když jsem chtěl instanci nějaké třídy?)
  • prostorová náročnost reprezentace "12" vs. "12.000000000000" vs. "1.200000000000e1" vs. 12 (integer) vs. 12.0 (float)

Je nutná přenositelnost mezi různými systémy?

NE: API pro (de)serializaci, např. Pickle@Python

https://docs.python.org/3/library/pickle.html#comparison-with-json https://wiki.python.org/moin/UsingPickle

  • odpadá nutnost konvertoru, shoda vstupního a výstupního konstruktu jazyka
  • poměrně široké spektrum entit, které lze ukládat
  • zjevná nevýhoda: absence kompatibility napříč prog. jazyky
  • skrytá nevýhoda: v některých případech bezpečnostní riziko (spuštěná arbitrary kódu v Pythonu)

ANO: custom binární reprezentace

  • zásadní je přesná definice datového formátu a podpora napříč platformami
  • obvykle task-oriented reprezentace, často nějaká forma komprese dat (ztrátová nebo bezeztrátová)

Několik příkladů z domény grafiky

(základní jednotka informace je pixel, R-G-B, dohromady 3byty)

Kolik bitů potřebuju k reprezentaci jednotky informace?

BMP:

https://cs.wikipedia.org/wiki/BMP

  • variabilní počet bitů dle barevné hloubky, variabilní paleta barev (256 barev -> 1pixel = 1byte)

Mohu více jednotek informace reprezentovat pomocí jednoho identifikátoru?

GIF:

https://cs.wikipedia.org/wiki/GIF

https://cs.wikipedia.org/wiki/LZW

  • algoritmus si postupně vytváři seznam běžných sekvencí v objektu -> více pixelů je reprezentováno jedním integerem
  • aby alg. mohl rozumně fungovat, je třeba omezit variabilitu sekvencí -> omezit počet barev (256) -> ztrátová komprese

Jaké informace nejsou nezbytné pro daný účel?

JPEG:

https://www.imaging.org/Site/IST/Resources/Tutorials/Inside_JPEG.aspx?WebsiteKey=6d978a6f-475d-46cc-bcf2-7a9e3d5f8f82&hkey=f9946f90-9f14-452d-897c-ac1612116e2d

https://cs.wikipedia.org/wiki/Huffmanovo_k%C3%B3dov%C3%A1n%C3%AD

  • ztrátová komprese. Lidské oko je citlivé ke změnám jasu, ale méně už ke změnám barev na malé ploše -> lze subsamplovat (reprezentuju 4 sousední pixely jejich průměrnou hodnotou).
  • použití obdoby diskretni fourierovy transformace (cosinová transformace) a její kvantizace
    • kvantizace: stanovení k hodnot a zaokrouhlení na nejbližší hodnotu -> úspornější bit. reprezentace za cenu vnesení nepřesností

Mohu reprezentovat informace pomocí variabilního počtu bitů?

Huffmanovo kódování (JPEG, PNG i další):

https://cs.wikipedia.org/wiki/Huffmanovo_k%C3%B3dov%C3%A1n%C3%AD

  • čím je informace častější, tím méně bitů by mělo být potřeba k její reprezentaci.
  • konstrukce kódování zaručuje jednoznačnost reprezentace

PS: bylo by složité / jednoduché / nemožné provést např. pixel-wise součet dvou obrázků v BMP, GIF nebo JPG formátu?

  • občas je třeba přemýšlet i v kontextu operací, které hodláte s daty provádět
  • Pro BMP je sečtení snadné, JPG a GIF by bylo třeba zkonvertovat do pixel-wise reprezentace

Odbočka 1: Mohu nějakou informaci vynechat a uvažovat implicitně?

  • nulové hodnoty v matici (nejsou potřeba pro sčítání a násobení matic ani obdobné operace) #### Př: Jak velká matice (třeba ve formátu int32) se mi vejde do paměti?
  • Např. matice 10 000 x 25 000 x 4byty = 1GB (a to je pořád relativně malá matice).
  • Co když je ale 99.5% buněk matice = 0?
  • Reprezentace nenulových hodnot pomocí souřadnic (i, j, value) by zabrala 3x 4byty x 10 000 x 25 000 x 0.005 = 15MB
  • Kolik operací by si vyžádalo sečtení dvou sparse nebo dvou dense matic? https://docs.scipy.org/doc/scipy/reference/sparse.html

Odbočka 2: Co takhle zvolit jinou reprezentaci informace, která je méně datově náročná?

SVG:

https://cs.wikipedia.org/wiki/Scalable_Vector_Graphics -> místo pixelu je jednotkou informace objekt s vlastnostmi (tvar, pozice, barva atd.)

  • reprezentované pomocí XML

Odbočka 3: Je možné se naučit vhodnou reprezentaci entit?

  • Co když mě ale zajímá podobnost dvou obrázků? Ale jak definuju podobnost?
  • znamená to, že na stejných souřadnicích jsou podobné hodnoty pixelů? Nebo spíš že obojí jsou fotky západu slunce nad mořem?
  • Pro "semantickou" podobnost obrázků je "pixelová" reprezentace zcela nevhodná.
  • Pokud ale máme dostatek trénovacích dat - např. obrázky a jim odpovídající tagy, je možné se vhodné reprezentace naučit #### Embeddings
  • reprezentace entit pomocí vektoru reálných čísel, které zachovávají podobnost, t.j. pokud jsou si podobné (podle nějaké metriky) původní entity, jsou i jejich vektorové reprezentace podobné.
  • vede na Deep learning (out of scope předmětu), ale jinak velmi zajímavá oblast
  • pro zájemce doporučuju pro začátek mrknout na Word2Vec a jednoduché konvoluční neuronové sítě (CNN)
    • obojí lze poměrně snadno implementovat v TensorFlow, resp. hrát si s již existujícími implementacemi

https://adventuresinmachinelearning.com/word2vec-tutorial-tensorflow/

https://www.learnopencv.com/understanding-alexnet/

Konkrétní využití výše zmíněných principů v DNA sekvencing

slides from Petr Danecek: https://www.ksi.mff.cuni.cz/~peska/vyuka/nswi178/hts-qc_part.pdf

  • FASTQ (slide 5): kvalita sekvencování

    • vyjádřená jako exponent -> větší rozsah hodnot za cenu určité redukce v přesnosti odhadu
    • zápis se vejde do 1 bytu / bázi
    • Je definován v zobrazitelné části ASCII znaků -> transparentnost

  • SAM/BAM (slide 14)

    • CIGAR string (slide 17) - meta-informace o průběhu mapování. Redukce porobnosti (M = match or mismatch)
    • Flags (slide 20) - všechny flags lze (sečtením) reprezentovat v jednom integeru; každý bit odpovídá jednomu příznaku
    • BAM (slide 27) - efektivní reprezentace (2 bity) pro každou aminokyselinu
    • BAM block gzip - blokový gzip je vlastně gzip aplikovaný na dostatečně malé bloky dat -> lze uchovat a indexovat pozici v referenční DNA -> lze provádět rychlé dotazy typu "vrať všechny mapování okolo pozice X

  • CRAM (slide 30)

    • reference based compression - ukládám pouze informace, které se liší od referenční DNA (ostatní implicitně považuju za stejné)
    • redukuju přesnost informace o kvalitě sekvencování
      • méně bitů na bázi
      • pouze jedna hodnota pro vícero bází
    • pro různé typy dat (sekvence, kvalita, meta-data) používá různé druhy komprese -> potenciálně vyšší efektivita

Další detaily na:

In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]: