Kontekstno-neodvisne gramatike za kodiranje in stiskanje podatkov: delo diplomskega seminarja

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.
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.