20.500.12556/RUL-162007 Kontekstno-neodvisne gramatike za kodiranje in stiskanje podatkov delo diplomskega seminarja Context-Free Grammars for Data Encoding and Compression Stiskanje podatkov je kodiranje, katerega cilj je zapisati sporočilo v zgoščeni obliki. V tem okviru definiramo podrazred kontekstno-neodvisnih gramatik imenovan dopustne gramatike. Nizu $w$ priredimo dopustno gramatiko $G_w$, katere jezik je $\{ w \}$. Predstavimo dva razreda prirejanj dopustne gramatike nizu in za vsak razred podamo primer prirejanja. Binarno kodiranje prepisovalnih pravil dopustne gramatike $G_w$ skupaj s predstavljenim prirejanjem zagotavlja dobro zgornjo mejo odvečnosti. Takšno stiskanje podatkov je univerzalen kod, kar v splošnem zagotavlja skoraj optimalno stiskanje. Data compression is a form of encoding aimed at representing the message in a compact form. Within this framework, we define a subclass of context-free grammars, referred to as admissible grammars. For each string $w$, we assign an admissible grammar $G_w$, such that its language is $\{ w \}$. We present two classes of assignments of admissible grammars to a string and provide an example for each class. Binary encoding of the production rules of an admissible grammar $G_w$ together with the underlying admissible grammar assignment results in a good redundancy bound. Such data compression constitutes a universal code, generally providing near-optimal compression. kontekstno-neodvisna gramatika stiskanje podatkov teorija informacij stiskanje brez izgube univerzalen kod context-free grammar data compression information theory lossless compression universal code true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2024-09-18 08:15:05 2024-09-18 08:15:11 2024-09-20 11:43:12 0000-00-00 00:00:00 2024 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004 143625 208307715 14069.pdf 14069.pdf 1 AC14FA786D5B2048F4A7990FFDF0EAAF 0c5d6355b110aa7c676b72ce507e362d343531762758e3423c6b1d5e0b1d68ec 4111fa94-7585-11ef-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=191021 Fakulteta za matematiko in fiziko 0 0 0