Corpus Storage IB047 Pavel Rychlý pary@fi.muni.cz March 20, 2017 Pavel Rychlý Corpus Storage Corpus storage ■ enumeration, lexicon ■ text, compression ■ indexes, suffix trees ■ structures Corpus model Structures each one has name (= file prefix) to to each one is independent, they are be VB linked by token numbers corpus is sequence of tokens, or c token numbers from 0 to the size of , HX not not the corpus (-1) to to standard attribute names: word, tag, be VB lemma, lempos Pavel Rychlý Corpus Storage Enumeration ■ using numbers instead of objects ■ example: charsets ■ corpus: ■ object: value of attributes on each token, value of structures' attributes ■ words, tags, ... ■ each type has its own sequence of numbers Pavel Rychlý Corpus Storage Lexicon enumaration of an attribute values ■ basic functions: ■ word number ■ number word ■ word = character string without any structure ■ basic functions: ■ find words matching a regular expression ■ sorting using locales Pavel Rychlý Corpus Storage Lexicon implementation attr.lex r\or separated strings attr.lex.idx array of string starts attr.lex.srt alphabetically sorted string numbers Use ■ islex for listing ■ islex -mfor building .srt file ■ isclex for listing corpus lexicon (with freqs) Pavel Rychlý Corpus Storage Storage of corpus text sequence of positions one word ID on each position simple storage = array of 32-bit numbers used for attributes of structures file attr. text the biggest part of stored data -> compression Pavel Rychlý Corpus Storage Compression of corpus text ■ codes for each number ■ different code length ■ shorter codes for more frequent words ■ Huffman coding ■ optimal code ■ requires code table Pavel Rychlý Corpus Storage non-parametric, prefix-free, universal N unary binary gamma delta 0 1 0000 1 1 1 01 0001 01 0 010 0 2 001 0010 01 1 010 1 3 0001 0011 001 00 Oil 00 4 00001 0100 001 01 Oil 01 5 000001 0101 001 10 Oil 10 6 0000001 0110 001 11 Oil 11 7 00000001 0111 0001 000 00100 000 8 000000001 1000 0001 001 00100 001 9 0000000001 1001 0001 010 00100 010 Compressed text implementation attr.text delta codes of numbers attr.text.seg starts of a segments (64 positions) in bits Pavel Rychlý Corpus Storage Indexes ■ store hits for each word ■ basic functions: ■ word ID list of positions ■ word ID^ number of hits Index implementation attr.rev lists of positions delta coding used for position differences attr.rev.idx array of lists' starts attr.rev.cnt array of lists' sizes Pavel Rychlý Corpus Storage Structures ■ struct. rng - array of (begin,end) pairs ■ 32-bit or 64-bit (if TYPE is map64 or file64) ■ attributes form a "corpus" to TO be VB or C not NOT to TO be VB Main corpus to be or not to be TO VB C NOT TO VB doc phr S001 Sha V V Pavel Rychlý Corpus Storage Sufixové stromy suffix tree, position tree, subword tree pro řetězec znaků ■ všechny podřetězce končící posledním znakem ■ přidáváme speciální symbol "konec", aby žádný řetězec nebyl prefixem jiného ■ z podřetězců vytvoříme trie (digitální strom) Pavel Rychlý Corpus Storage Sufixové stromy - příklad ■ řetězec: abab$ ■ podřetězce: H abab$ Q bab$ Q ab$ □ b$ h $ Sufixové stromy - vlastnosti řetězec délky N ■ N listů ■ v kompaktním trie max. 2*N uzlů listy ohodnoceny pozicí vnitřní uzly ohodnoceny velikostí podstromu ab $r ab$r $r ab$r $r Pavel Rychlý Corpus Storage Sufixové stromy pro korpus znaky -> slova řetězec text korpusu funkce strom (seznam) pozic pro každé slovo i posloupnost slov be not /\ i or $ to not to be be $ upořádaní pozic je lexikografické $ Pavel Rychlý Corpus Storage Sufixová pole ■ suffix array, PAT array ■ optimální uložení sufixových stromů ■ uložení pozic v listech suf. stromu podle pevného uspořádání hran ■ stejné funkce jako suf. stromy abab$: 1 3 2 4 5 to be or not to be $: 1 5 3 2 0 4 6 Pavel Rychlý Corpus Storage