IB047 usové lingvistiky a počítačové lexikograf Pavel Rychlý pary@fi.muni.cz March 16, 2015 Pavel Rychlý IB047 Corpus storage ■ enumeration, lexicon ■ text, compression ■ indexes, suffix trees ■ structures Corpus model ■ corpus consists of attributes and structures ■ each one has name (= file prefix) ■ each one is independent, they are linked by token numbers ■ corpus is sequence of tokens, token numbers from 0 to the size of the corpus (-1) ■ standard attribute names: word, tag, lemma, lempos to TO be VB or C not NOT to TO be VB 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 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 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) < □ ► 4 ► < 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 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ý IB047 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ý IB047 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ý IB047 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ý IB047 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 Sufixové stromy - příklad ■ řetězec: ■ abab$ ■ podřetězce: ■ 0: abab$ ■ 1: bab$ ■ 2: ab$ ■ 3: b$ ■ 4: $ 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 < □ ► 4 ► 4 Sufixove stromy pro korpus ■ znaky -> slova ■ řetězec -> text korpusu ■ funkce ■ strom (seznam) pozic pro každé slovo i posloupnost slov ■ upořádání pozic je lexikografické 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 Pavel Rychlý IB047