Стиснення двійкових послідовностей на основі системи числення Штерна-Броко
The new algorithm of compression is examined without losses for binary sequences, that is based on the use of scale of notation of Shterna–Broko. For the estimation of efficiency of algorithm middle length of binary sequence is determined after a compression, mid-coefficient of compression.
Saved in:
| Date: | 2010 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Фізико-механічний інститут ім. Г.В. Карпенка НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/16233 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Стиснення двійкових послідовностей на основі системи числення Штерна-Броко / Л.Я. Глинчук // Відбір і оброб. інформації: Міжвід. зб. наук. пр. — 2010. — Вип. 33(109). — С. 117-122. — Бібліогр.: 6 назв. — укp. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859889011320946688 |
|---|---|
| author | Глинчук, Л.Я. |
| author_facet | Глинчук, Л.Я. |
| citation_txt | Стиснення двійкових послідовностей на основі системи числення Штерна-Броко / Л.Я. Глинчук // Відбір і оброб. інформації: Міжвід. зб. наук. пр. — 2010. — Вип. 33(109). — С. 117-122. — Бібліогр.: 6 назв. — укp. |
| collection | DSpace DC |
| description | The new algorithm of compression is examined without losses for binary sequences, that is based on the use of scale of notation of Shterna–Broko. For the estimation of efficiency of algorithm middle length of binary sequence is determined after a compression, mid-coefficient of compression.
|
| first_indexed | 2025-12-07T15:53:52Z |
| format | Article |
| fulltext |
ISSN 0474-8662. . 2010. . 33 (109) 117
681.397.6
. .
The new algorithm of compression is examined without losses for binary sequences, that is
based on the use of scale of notation of Shterna–Broko. For the estimation of efficiency of
algorithm middle length of binary sequence is determined after a compression, mid-coefficient
of compression.
Keywords: binary sequence, compression, aspect ratio.
, -
. -
-
.
: , , .
, ,
, -
, .
– -
, , .
-
. , -
, .
[1].
[3]. -
[2], [4], [6]. -
,
. [4], [6] -
, , -
.
[5] -
. -
, , – .
. ( ) –
, ,
) -
– , . , -
( ) -
[3].
( . 1)
,
. ( . 2) – . -
, -
, .
. . , 2010
ISSN 0474-8662. Information Extraction and Proces. 2010. Issue 33 (109)118
. 1. . . 2. .
, -
.
, -
. .
n .
: c , z . -
: -
, dc –
dz .
l n : l = dc + dz.
, 0111111111 1
10/11, 4
, l = 8 , 2 .
li i n
, -
cpil
1
cp
m
i
i
i
l
l
m
, m – ,
!
!( )!
k
n
nm C
k n k
, n – , k .
i n
k :
cp
i
i
nK
l
.
pi,
0
cp
n
cp i i
i
l p l .
Y
/cp cpY n l . Y ,
.
ISSN 0474-8662. . 2010. . 33 (109) 119
, -
Y lcp. . 1 -
n 8, 16, 32 . -
pi (
n). 2 Y .
1. lcp
pi
n k
. 0 1 2 3 4
lcp cpil 5,000 7,620 9,320 10,300 10,660
= 1 0,900 0,100
5,262
cpi ip l 4,500 0,762
= 2 0,800 0,100 0,100
5,694
cpi ip l 4,000 0,762 0,932
= 3 0,600 0,200 0,100 0,100
6,486
cpi ip l 3,000 1,524 0,932 1,030
= 4 0,400 0,300 0,100 0,100 0,100
8
7,314
cpi ip l 2,000 2,286 0,932 1,030 1,066
lcp cpil 6,000 10,000 12,910 15,220 16,950
= 1 0,900 0,100
6,400
cpi ip l 5,400 1,000
= 2 0,800 0,100 0,100
7,091
cpi ip l 4,800 1,000 1,291
= 3 0,600 0,200 0,100 0,100
8,413
cpi ip l 3,600 2,000 1,291 1,522
= 4 0,400 0,300 0,100 0,100 0,100
16
9,908
cpi ip l 2,400 3,000 1,291 1,522 1,695
lcp cpil 7,000 12,410 16,910 20,640 23,700
= 1 0,900 0,100
7,541
cpi ip l 6,300 1,241
= 2 0,800 0,100 0,100
8,532
cpi ip l 5,600 1,241 1,691
= 3 0,600 0,200 0,100 0,100
10,437
cpi ip l 4,200 2,482 1,691 2,064
= 4 0,400 0,300 0,100 0,100 0,100
32
12,648
cpi ip l 2,800 3,723 1,691 2,064 2,370
ISSN 0474-8662. Information Extraction and Proces. 2010. Issue 33 (109)120
2. Ycp,
. 1 lcp
n 8 16 32
= 1 1,520 2,500 4,243
= 2 1,405 2,256 3,751
= 3 1,233 1,902 3,066
= 4 1,094 1,615 2,530
. 1 2 :
1) -
, , , ;
2) , -
.
Ycp -
, , -
, Y<1. -
Ki -
cpil n = 8, 16, 32
. ,
i n-i . . 3,
4, .
3. Ki cpil
n = 8, 16, 32
n k 0 1 2 3 4 5 6 7 8
m 1 8 28 56 70
cpil 5,00 7,62 9,32 10,30 10,668
Ki 1,60 1,05 0,86 0,78 0,75
m 1 16 120 560 1820 4368 8008 11440 11700
cpil 6,00 10,00 12,91 15,22 16,95 18,20 19,08 19,57 21,7116
Ki 2,67 1,60 1,24 1,05 0,94 0,88 0,84 0,82 0,74
m 1 32 496 4960 35960 201376 906192 3365856 10518300
cpil 7,00 12,41 16,91 20,64 23,70 26,34 28,60 30,54 32,1232
Ki 4,57 2,58 1,89 1,55 1,35 1,22 1,12 1,05 0,99
k 9 10 11 12 13 14 15 16
m 28048800 64512240 129024480 ... ... ... ... ...
cpil 33,64 34,85 35,84 36,65 37,26 37,67 37,89 38,34
32
Ki 0,95 0,92 0,89 0,87 0,86 0,85 0,84 0,83
ISSN 0474-8662. . 2010. . 33 (109) 121
4. Ki n
k
n
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
8 1,60 1,05 0,86 0,78 0,75
16 2,67 1,60 1,24 1,05 0,94 0,88 0,84 0,82 0,74
32 4,57 2,58 1,89 1,55 1,35 1,22 1,12 1,05 0,99 0,95 0,92 0,89 0,87 0,86 0,85 0,84 0,83
/ 2k n ,
( . 3), :
. 3. n.
2n
. ( ) [0; n/4–1]
[3/4n+1; n] n , –
. , -
– .
. 3, ,
, -
. -
.
, -
n -
,
. , -
, -
.
-
[6]. , ,
ISSN 0474-8662. Information Extraction and Proces. 2010. Issue 33 (109)122
256 -
[6].
-
CalgCC ( 8 ). . 5
, n 8 ( -
NA) CalgCC .
5. NA
ARJ PKZIP ACE RAR 7-Zip NA(8)
Bib 3,08 3,16 3,38 3,39 3,62 1,24
Book1 2,41 2,46 2,78 2,80 2,94 1,23
Book2 2,90 2,95 3,36 3,39 3,59 1,24
News 2,56 2,61 3,00 3,00 3,16 1,23
Paper1 2,84 2,85 2,91 2,93 3,07 1,22
Paper2 2,74 2,77 2,86 2,88 3,01 1,22
Progp 4,32 4,37 4,55 4,57 4,73 1,18
Trans 4,65 4,79 5,19 5,23 5,56 1,26
3,188 3,245 3,504 3,524 3,710 1,228
. 5 , ,
, , -
, .
:
1) ( -
),
, ;
2) -
;
3)
.
1. ( ) / . . . – : . .,
1978. – 252 .
2. . ., . . // -
. – 2006. – 4(88). – . 56–61.
3. ., ., . . . – .:
, 1998. – 703 .
4. . ., . . -
// . – 2006. – 4(88). – . 73–79.
5. – . – ]. – :
www.wikiznanie.ru/ru-wz/index.php/ .
6. . . //
. – 2006. – 4(88). – . 61–68.
.
22.03.2010
УДК 681.397.6
УДК 681.397.6
Л. Я. Глинчук
СТИСНЕННЯ ДВІЙКОВИХ ПОСЛІДОВНОСТЕЙ НА ОСНОВІ СИСТЕМИ ЧИСЛЕННЯ ШТЕРНА–БРОКО
|
| id | nasplib_isofts_kiev_ua-123456789-16233 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0474-8662 |
| language | Ukrainian |
| last_indexed | 2025-12-07T15:53:52Z |
| publishDate | 2010 |
| publisher | Фізико-механічний інститут ім. Г.В. Карпенка НАН України |
| record_format | dspace |
| spelling | Глинчук, Л.Я. 2011-02-08T17:56:27Z 2011-02-08T17:56:27Z 2010 Стиснення двійкових послідовностей на основі системи числення Штерна-Броко / Л.Я. Глинчук // Відбір і оброб. інформації: Міжвід. зб. наук. пр. — 2010. — Вип. 33(109). — С. 117-122. — Бібліогр.: 6 назв. — укp. 0474-8662 https://nasplib.isofts.kiev.ua/handle/123456789/16233 681.397.6 The new algorithm of compression is examined without losses for binary sequences, that is based on the use of scale of notation of Shterna–Broko. For the estimation of efficiency of algorithm middle length of binary sequence is determined after a compression, mid-coefficient of compression. uk Фізико-механічний інститут ім. Г.В. Карпенка НАН України Математичне та програмне забезпечення Стиснення двійкових послідовностей на основі системи числення Штерна-Броко Compression of binary sequences on basis of Stern-Brocot system calculation Article published earlier |
| spellingShingle | Стиснення двійкових послідовностей на основі системи числення Штерна-Броко Глинчук, Л.Я. Математичне та програмне забезпечення |
| title | Стиснення двійкових послідовностей на основі системи числення Штерна-Броко |
| title_alt | Compression of binary sequences on basis of Stern-Brocot system calculation |
| title_full | Стиснення двійкових послідовностей на основі системи числення Штерна-Броко |
| title_fullStr | Стиснення двійкових послідовностей на основі системи числення Штерна-Броко |
| title_full_unstemmed | Стиснення двійкових послідовностей на основі системи числення Штерна-Броко |
| title_short | Стиснення двійкових послідовностей на основі системи числення Штерна-Броко |
| title_sort | стиснення двійкових послідовностей на основі системи числення штерна-броко |
| topic | Математичне та програмне забезпечення |
| topic_facet | Математичне та програмне забезпечення |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/16233 |
| work_keys_str_mv | AT glinčuklâ stisnennâdvíikovihposlídovnosteinaosnovísistemičislennâšternabroko AT glinčuklâ compressionofbinarysequencesonbasisofsternbrocotsystemcalculation |