Арифметическое кодирование - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:36:56Z

rollbackEdits.php mass rollback

185.220.101.2 в 03:57, 1 сентября 2022

2022-09-01T03:57:52Z

176.59.23.112 в 17:23, 12 ноября 2021

2021-11-12T17:23:51Z

Капелюшок Георгий Александрович: Отмена правки 81085, сделанной Капелюшок Георгий Александрович ([[User talk:Капелюшок Георгий Ал…

2021-06-23T23:39:27Z

Отмена правки 81085, сделанной Капелюшок Георгий Александрович ([[User talk:Капелюшок Георгий Ал…

Капелюшок Георгий Александрович: /* Оценка длины кодового слова */

2021-06-23T23:30:30Z

‎Оценка длины кодового слова

176.59.17.77: added adaptive coding

2020-04-05T13:26:48Z

added adaptive coding

Внесённые изменения

185.159.156.19 в 18:08, 31 октября 2019

2019-10-31T18:08:08Z

185.159.156.19 в 18:07, 31 октября 2019

2019-10-31T18:07:08Z

Mervap в 22:17, 5 марта 2018

2018-03-05T22:17:14Z

Mervap в 21:26, 5 марта 2018

2018-03-05T21:26:28Z

← Предыдущая		Версия 16:36, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	{{Определение		{{Определение
	\|definition=		\|definition=

← Предыдущая		Версия 03:57, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	{{Определение		{{Определение
	\|definition=		\|definition=

@@ Строка 181: / Строка 181: @@
 == Оценка длины кодового слова ==
 {{Теорема
-|statement=При арифметическом кодировании длина кодового слова не превышает энтропии исходного текста.
+|statement=При арифметическом кодировании длина кодового слова не превышает энтропии Шеннона случайного источника с частотами, равными долям вхождения символа в строку, умноженной на длину строки.
-||proof=Введём следующие обозначения:
-*<tex>l</tex> {{---}} длина текста,
 *<tex>n</tex> {{---}} размер алфавита,
 *<tex>f_i</tex> {{---}} частота встречаемости символа,
-*<tex>p_i</tex> {{---}} вероятность вхождения символа.
+*<tex>p_i = \dfrac{f i}{l}</tex> {{---}} вероятность вхождения символа,
-Размер сообщения <tex>L</tex> можно найти по формуле:
+Энтропия источника вычисляется по следующей формуле <tex>H(p_1 \ldots p_n) = -\sum\limits_{i=1}^n p_i\cdot \log_2 p_i</tex>.
-Число бит в закодированном тексте:
+Следовательно, <tex>A(s) \leq l \cdot H(p_1 \ldots p_n)</tex>.
 }}

@@ Строка 181: / Строка 181: @@
 == Оценка длины кодового слова ==
 {{Теорема
-|statement=При арифметическом кодировании длина кодового слова не превышает энтропии Шеннона случайного источника с частотами, равными долям вхождения символа в строку, умноженной на длину строки.
+|statement=При арифметическом кодировании длина кодового слова не превышает энтропии исходного текста.
-||proof=В результате арифметического кодирования мы получили число <tex>\frac x 2 ^ q</tex>
+||proof=Введём следующие обозначения:
+Размер сообщения <tex>L</tex> можно найти по формуле:
-Энтропия: <tex>H(p_1 \ldots p_n) = -\sum\limits_{i=1}^n p_i\cdot \log_2 p_i</tex>
+<tex> L = \prod\limits_{i=1}^l p_{fi} = \prod\limits_{i=1}^n p_{i}^{f_{i}}</tex>
 Число бит в закодированном тексте:

@@ Строка 181: / Строка 181: @@
 == Оценка длины кодового слова ==
 {{Теорема
-|statement=При арифметическом кодировании длина кодового слова не превышает энтропии исходного текста.
+|statement=При арифметическом кодировании длина кодового слова не превышает энтропии Шеннона случайного источника с частотами, равными долям вхождения символа в строку, умноженной на длину строки.
-||proof=Введём следующие обозначения:
+||proof=В результате арифметического кодирования мы получили число <tex>\frac x 2 ^ q</tex>
-Размер сообщения <tex>L</tex> можно найти по формуле:
-<tex> L = \prod\limits_{i=1}^l p_{fi} = \prod\limits_{i=1}^n p_{i}^{f_{i}}</tex>
+Энтропия: <tex>H(p_1 \ldots p_n) = -\sum\limits_{i=1}^n p_i\cdot \log_2 p_i</tex>
 Число бит в закодированном тексте:

@@ Строка 194: / Строка 194: @@
 Число бит в закодированном тексте:
-<tex>\log_2 L = \sum\limits_{i=1}^n f_i\cdot \log_2 p_i =  -l \cdot \sum\limits_{i=1}^n p_i\cdot \log_2 p_i = -l \cdot H(p_1 \ldots p_n)</tex>
+<tex>\log_2 L = -\sum\limits_{i=1}^n f_i\cdot \log_2 p_i =  -l \cdot \sum\limits_{i=1}^n p_i\cdot \log_2 p_i = -l \cdot H(p_1 \ldots p_n)</tex>
 }}

@@ Строка 92: / Строка 92: @@
       '''for''' i = 0 '''to''' n - 1
           '''for''' j = 0 '''to''' m - 1
-              '''if''' code >= segment[j].left '''and''' code < segment[j].right
+              '''if''' code<tex>\small{~\geqslant~}</tex>segment[j].left '''and''' code < segment[j].right
                   s += segment[j].character
                   code = (code – segment[j].left) / (segment[j].right – segment[j].left)

@@ Строка 2: / Строка 2: @@
 |definition=
 '''Арифметическое кодирование''' (англ. ''Arithmetic coding'') {{---}} алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из отрезка <tex>[0; 1)</tex>.
-Данный метод, как и [[Алгоритм Хаффмана|алгоритм Хаффмана]], является [[Энтропия случайного источника|энтропийным]], т.е. длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов.
+Данный метод, как и [[Алгоритм Хаффмана|алгоритм Хаффмана]], является [[Энтропия случайного источника|энтропийным]], то есть длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов.
 }}
@@ Строка 194: / Строка 194: @@
 Число бит в закодированном тексте:
-<tex>\log_2 L = \sum\limits_{i=1}^n f_i\cdot \log_2 p_i =  l \cdot \sum\limits_{i=1}^n p_i\cdot \log_2 p_i = -l \cdot H(p_1...p_n)</tex>
+<tex>\log_2 L = \sum\limits_{i=1}^n f_i\cdot \log_2 p_i =  l \cdot \sum\limits_{i=1}^n p_i\cdot \log_2 p_i = -l \cdot H(p_1 \ldots p_n)</tex>
 }}