ΠΊΠΎΠ΄ шСннона Ρ„Π°Π½ΠΎ ΠΊΠΎΠ΄ Ρ…Π°Ρ„Ρ„ΠΌΠ°Π½Π°

Π‘Ρ€Π°Π²Π½ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ характСристика Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ ΠΈ Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π° (ΠΊΠΎΠ΄ΠΎΠ²)

Primary tabs

ΠΊΠΎΠ΄ шСннона Ρ„Π°Π½ΠΎ ΠΊΠΎΠ΄ Ρ…Π°Ρ„Ρ„ΠΌΠ°Π½Π°. picture 19 1455465074. ΠΊΠΎΠ΄ шСннона Ρ„Π°Π½ΠΎ ΠΊΠΎΠ΄ Ρ…Π°Ρ„Ρ„ΠΌΠ°Π½Π° Ρ„ΠΎΡ‚ΠΎ. ΠΊΠΎΠ΄ шСннона Ρ„Π°Π½ΠΎ ΠΊΠΎΠ΄ Ρ…Π°Ρ„Ρ„ΠΌΠ°Π½Π°-picture 19 1455465074. ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΊΠΎΠ΄ шСннона Ρ„Π°Π½ΠΎ ΠΊΠΎΠ΄ Ρ…Π°Ρ„Ρ„ΠΌΠ°Π½Π°. ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° picture 19 1455465074. ΠœΠ΅Ρ‚ΠΎΠ΄ΠΈΠΊΠ° ШСннона–Ѐано Π½Π΅ всСгда ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ ΠΊ ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½ΠΎΠΌΡƒ ΠΏΠΎΡΡ‚Ρ€ΠΎΠ΅Π½ΠΈΡŽ ΠΊΠΎΠ΄Π°. Π’Π΅Π΄ΡŒ ΠΏΡ€ΠΈ Ρ€Π°Π·Π±ΠΈΠ΅Π½ΠΈΠΈ Π½Π° ΠΏΠΎΠ΄Π³Ρ€ΡƒΠΏΠΏΡ‹ Π½Π° 1-ΠΉ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΄Π΅Π»Π°Ρ‚ΡŒ большСй ΠΏΠΎ вСроятности ΠΊΠ°ΠΊ Π²Π΅Ρ€Ρ…Π½ΡŽΡŽ, Ρ‚Π°ΠΊ ΠΈ ниТнюю ΠΏΠΎΠ΄Π³Ρ€ΡƒΠΏΠΏΡƒ. Π’ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ срСднСС число символов Π½Π° Π±ΡƒΠΊΠ²Ρƒ окаТСтся Π΄Ρ€ΡƒΠ³ΠΈΠΌ. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, построСнный ΠΊΠΎΠ΄ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΎΠΊΠ°Π·Π°Ρ‚ΡŒΡΡ Π½Π΅ самым Π»ΡƒΡ‡ΡˆΠΈΠΌ.

Forums:

ΠœΠ΅Ρ‚ΠΎΠ΄ΠΈΠΊΠ° ШСннона–Ѐано Π½Π΅ всСгда ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ ΠΊ ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½ΠΎΠΌΡƒ ΠΏΠΎΡΡ‚Ρ€ΠΎΠ΅Π½ΠΈΡŽ ΠΊΠΎΠ΄Π°.
Π’Π΅Π΄ΡŒ ΠΏΡ€ΠΈ Ρ€Π°Π·Π±ΠΈΠ΅Π½ΠΈΠΈ Π½Π° ΠΏΠΎΠ΄Π³Ρ€ΡƒΠΏΠΏΡ‹ Π½Π° 1-ΠΉ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΄Π΅Π»Π°Ρ‚ΡŒ большСй ΠΏΠΎ вСроятности ΠΊΠ°ΠΊ Π²Π΅Ρ€Ρ…Π½ΡŽΡŽ, Ρ‚Π°ΠΊ ΠΈ ниТнюю ΠΏΠΎΠ΄Π³Ρ€ΡƒΠΏΠΏΡƒ. Π’ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ срСднСС число символов Π½Π° Π±ΡƒΠΊΠ²Ρƒ окаТСтся Π΄Ρ€ΡƒΠ³ΠΈΠΌ.
Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, построСнный ΠΊΠΎΠ΄ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΎΠΊΠ°Π·Π°Ρ‚ΡŒΡΡ Π½Π΅ самым Π»ΡƒΡ‡ΡˆΠΈΠΌ.

ΠžΡ‚ ΡƒΠΊΠ°Π·Π°Π½Π½ΠΎΠ³ΠΎ нСдостатка свободна ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΈΠΊΠ° Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π°. Она Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΡƒΠ΅Ρ‚ ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½ΠΎΠ΅ построСниС ΠΊΠΎΠ΄Π° с наимСньшим для Π΄Π°Π½Π½ΠΎΠ³ΠΎ распрСдСлСния вСроятностСй срСдним числом символов Π½Π° Π±ΡƒΠΊΠ²Ρƒ.

ΠœΠ΅Ρ‚ΠΎΠ΄ Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π° ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚ идСальноС сТатиС (Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ, сТимаСт Π΄Π°Π½Π½Ρ‹Π΅ Π΄ΠΎ ΠΈΡ… энтропии), Ссли вСроятности символов Ρ‚ΠΎΡ‡Π½ΠΎ Ρ€Π°Π²Π½Ρ‹ ΠΎΡ‚Ρ€ΠΈΡ†Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΌ стСпСням числа 2. Π Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹ эффСктивного кодирования ΠΏΠΎ ΠΌΠ΅Ρ‚ΠΎΠ΄Ρƒ Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π° всСгда Π»ΡƒΡ‡ΡˆΠ΅ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ΠΎΠ² кодирования ΠΏΠΎ ΠΌΠ΅Ρ‚ΠΎΠ΄Ρƒ Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ.

ΠŸΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½Π½Ρ‹ΠΉ Π₯Π°Ρ„Ρ„ΠΌΠ°Π½ΠΎΠΌ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ построСния ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Ρ… Π½Π΅Ρ€Π°Π²Π½ΠΎΠΌΠ΅Ρ€Π½Ρ‹Ρ… ΠΊΠΎΠ΄ΠΎΠ² – ΠΎΠ΄Π½ΠΎ ΠΈΠ· самых Π²Π°ΠΆΠ½Ρ‹Ρ… достиТСний Ρ‚Π΅ΠΎΡ€ΠΈΠΈ ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΈ, ΠΊΠ°ΠΊ с тСорСтичСской, Ρ‚Π°ΠΊ ΠΈ с ΠΏΡ€ΠΈΠΊΠ»Π°Π΄Π½ΠΎΠΉ Ρ‚ΠΎΡ‡Π΅ΠΊ зрСния. Π­Ρ‚ΠΎΡ‚ вСсьма популярный Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ слуТит основой ΠΌΠ½ΠΎΠ³ΠΈΡ… ΠΊΠΎΠΌΠΏΡŒΡŽΡ‚Π΅Ρ€Π½Ρ‹Ρ… ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ сТатия тСкстовой ΠΈ графичСской ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΈ. НСкоторыС ΠΈΠ· Π½ΠΈΡ… ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ нСпосрСдствСнно Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π°, Π° Π΄Ρ€ΡƒΠ³ΠΈΠ΅ Π±Π΅Ρ€ΡƒΡ‚ Π΅Π³ΠΎ Π² качСствС ΠΎΠ΄Π½ΠΎΠΉ ΠΈΠ· ступСнСй ΠΌΠ½ΠΎΠ³ΠΎΡƒΡ€ΠΎΠ²Π½Π΅Π²ΠΎΠ³ΠΎ процСсса сТатия.

Π’Ρ€ΡƒΠ΄Π½ΠΎ ΠΏΠΎΠ²Π΅Ρ€ΠΈΡ‚ΡŒ, Π½ΠΎ этот Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π±Ρ‹Π» ΠΏΡ€ΠΈΠ΄ΡƒΠΌΠ°Π½ Π² 1952 Π³. студСнтом Дэвидом Π₯Π°Ρ„Ρ„ΠΌΠ°Π½ΠΎΠΌ Π² процСссС выполнСния домашнСго задания =).

ΠšΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π° Π½Π°Π·Ρ‹Π²Π°ΡŽΡ‚ Π΄Π²ΡƒΡ…ΠΏΡ€ΠΎΡ…ΠΎΠ΄Π½Ρ‹ΠΌ, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ Π΅Π³ΠΎ рСализация распадаСтся Π½Π° Π΄Π²Π° этапа:

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊ

ΠŸΡ€ΠΈΠΌΠ΅Ρ€Π°ΠΌΠΈ прСфиксных ΠΊΠΎΠ΄ΠΎΠ² ΡΠ²Π»ΡΡŽΡ‚ΡΡ ΠΊΠΎΠ΄Ρ‹ Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ ΠΈ Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π°.

Код ШСннона-Ѐано

БообщСния Π°Π»Ρ„Π°Π²ΠΈΡ‚Π° источника Π²Ρ‹ΠΏΠΈΡΡ‹Π²Π°ΡŽΡ‚ Π² порядкС убывания вСроятностСй ΠΈΡ… появлСния. Π”Π°Π»Π΅Π΅ Ρ€Π°Π·Π΄Π΅Π»ΡΡŽΡ‚ ΠΈΡ… Π½Π° Π΄Π²Π΅ части Ρ‚Π°ΠΊ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ суммарныС вСроятности сообщСний Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΠ· этих частСй Π±Ρ‹Π»ΠΈ ΠΏΠΎ возмоТности ΠΏΠΎΡ‡Ρ‚ΠΈ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹ΠΌΠΈ. ΠŸΡ€ΠΈΠΏΠΈΡˆΠ΅ΠΌ сообщСниям ΠΏΠ΅Ρ€Π²ΠΎΠΉ части Π² качСствС ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ символа – 0, Π° Π²Ρ‚ΠΎΡ€ΠΎΠΉ – 1 (ΠΌΠΎΠΆΠ½ΠΎ Π½Π°ΠΎΠ±ΠΎΡ€ΠΎΡ‚). Π—Π°Ρ‚Π΅ΠΌ каТдая ΠΈΠ· этих частСй (Ссли ΠΎΠ½Π° содСрТит Π±ΠΎΠ»Π΅Π΅ ΠΎΠ΄Π½ΠΎΠ³ΠΎ сообщСния) дСлится Π½Π° Π΄Π²Π΅ ΠΏΠΎ возмоТности равновСроятныС части, ΠΈ Π² качСствС Π²Ρ‚ΠΎΡ€ΠΎΠ³ΠΎ символа для ΠΏΠ΅Ρ€Π²ΠΎΠΉ ΠΈΠ· Π½ΠΈΡ… бСрСтся 0, Π° для Π²Ρ‚ΠΎΡ€ΠΎΠΉ – 1. Π­Ρ‚ΠΎΡ‚ процСсс повторяСтся, ΠΏΠΎΠΊΠ° Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΠ· ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π½Ρ‹Ρ… частСй Π½Π΅ останСтся ΠΏΠΎ ΠΎΠ΄Π½ΠΎΠΌΡƒ ΡΠΎΠΎΠ±Ρ‰Π΅Π½ΠΈΡŽ.

ΠΊΠΎΠ΄ шСннона Ρ„Π°Π½ΠΎ ΠΊΠΎΠ΄ Ρ…Π°Ρ„Ρ„ΠΌΠ°Π½Π°. image012. ΠΊΠΎΠ΄ шСннона Ρ„Π°Π½ΠΎ ΠΊΠΎΠ΄ Ρ…Π°Ρ„Ρ„ΠΌΠ°Π½Π° Ρ„ΠΎΡ‚ΠΎ. ΠΊΠΎΠ΄ шСннона Ρ„Π°Π½ΠΎ ΠΊΠΎΠ΄ Ρ…Π°Ρ„Ρ„ΠΌΠ°Π½Π°-image012. ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΊΠΎΠ΄ шСннона Ρ„Π°Π½ΠΎ ΠΊΠΎΠ΄ Ρ…Π°Ρ„Ρ„ΠΌΠ°Π½Π°. ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° image012. ΠœΠ΅Ρ‚ΠΎΠ΄ΠΈΠΊΠ° ШСннона–Ѐано Π½Π΅ всСгда ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ ΠΊ ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½ΠΎΠΌΡƒ ΠΏΠΎΡΡ‚Ρ€ΠΎΠ΅Π½ΠΈΡŽ ΠΊΠΎΠ΄Π°. Π’Π΅Π΄ΡŒ ΠΏΡ€ΠΈ Ρ€Π°Π·Π±ΠΈΠ΅Π½ΠΈΠΈ Π½Π° ΠΏΠΎΠ΄Π³Ρ€ΡƒΠΏΠΏΡ‹ Π½Π° 1-ΠΉ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΄Π΅Π»Π°Ρ‚ΡŒ большСй ΠΏΠΎ вСроятности ΠΊΠ°ΠΊ Π²Π΅Ρ€Ρ…Π½ΡŽΡŽ, Ρ‚Π°ΠΊ ΠΈ ниТнюю ΠΏΠΎΠ΄Π³Ρ€ΡƒΠΏΠΏΡƒ. Π’ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ срСднСС число символов Π½Π° Π±ΡƒΠΊΠ²Ρƒ окаТСтся Π΄Ρ€ΡƒΠ³ΠΈΠΌ. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, построСнный ΠΊΠΎΠ΄ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΎΠΊΠ°Π·Π°Ρ‚ΡŒΡΡ Π½Π΅ самым Π»ΡƒΡ‡ΡˆΠΈΠΌ.

ΠΊΠΎΠ΄ шСннона Ρ„Π°Π½ΠΎ ΠΊΠΎΠ΄ Ρ…Π°Ρ„Ρ„ΠΌΠ°Π½Π°. image014. ΠΊΠΎΠ΄ шСннона Ρ„Π°Π½ΠΎ ΠΊΠΎΠ΄ Ρ…Π°Ρ„Ρ„ΠΌΠ°Π½Π° Ρ„ΠΎΡ‚ΠΎ. ΠΊΠΎΠ΄ шСннона Ρ„Π°Π½ΠΎ ΠΊΠΎΠ΄ Ρ…Π°Ρ„Ρ„ΠΌΠ°Π½Π°-image014. ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΊΠΎΠ΄ шСннона Ρ„Π°Π½ΠΎ ΠΊΠΎΠ΄ Ρ…Π°Ρ„Ρ„ΠΌΠ°Π½Π°. ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° image014. ΠœΠ΅Ρ‚ΠΎΠ΄ΠΈΠΊΠ° ШСннона–Ѐано Π½Π΅ всСгда ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ ΠΊ ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½ΠΎΠΌΡƒ ΠΏΠΎΡΡ‚Ρ€ΠΎΠ΅Π½ΠΈΡŽ ΠΊΠΎΠ΄Π°. Π’Π΅Π΄ΡŒ ΠΏΡ€ΠΈ Ρ€Π°Π·Π±ΠΈΠ΅Π½ΠΈΠΈ Π½Π° ΠΏΠΎΠ΄Π³Ρ€ΡƒΠΏΠΏΡ‹ Π½Π° 1-ΠΉ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΄Π΅Π»Π°Ρ‚ΡŒ большСй ΠΏΠΎ вСроятности ΠΊΠ°ΠΊ Π²Π΅Ρ€Ρ…Π½ΡŽΡŽ, Ρ‚Π°ΠΊ ΠΈ ниТнюю ΠΏΠΎΠ΄Π³Ρ€ΡƒΠΏΠΏΡƒ. Π’ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ срСднСС число символов Π½Π° Π±ΡƒΠΊΠ²Ρƒ окаТСтся Π΄Ρ€ΡƒΠ³ΠΈΠΌ. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, построСнный ΠΊΠΎΠ΄ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΎΠΊΠ°Π·Π°Ρ‚ΡŒΡΡ Π½Π΅ самым Π»ΡƒΡ‡ΡˆΠΈΠΌ.

Рис. КодовоС Π΄Π΅Ρ€Π΅Π²ΠΎ ΠΊΠΎΠ΄Π° Π¨Π΅Π½Π½ΠΎΠ½Π° – Π€Π°Π½ΠΎ

ΠœΠ΅Ρ‚ΠΎΠ΄ΠΈΠΊΠ° Π¨Π΅Π½Π½ΠΎΠ½Π° – Π€Π°Π½ΠΎ Π½Π΅ всСгда ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ ΠΊ ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½ΠΎΠΌΡƒ ΠΏΠΎΡΡ‚Ρ€ΠΎΠ΅Β­Π½ΠΈΡŽ ΠΊΠΎΠ΄Π°, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ ΠΏΡ€ΠΈ Ρ€Π°Π·Π±ΠΈΠ΅Π½ΠΈΠΈ Π½Π° части ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΄Π΅Π»Π°Ρ‚ΡŒ большС ΠΏΠΎ вСро­ятности ΠΊΠ°ΠΊ Π²Π΅Ρ€Ρ…Π½ΡŽΡŽ, Ρ‚Π°ΠΊ ΠΈ ниТнюю части. ΠšΡ€ΠΎΠΌΠ΅ Ρ‚ΠΎΠ³ΠΎ, ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΈΠΊΠ° Π½Π΅ обСспС­чиваСт отыскания ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ мноТСства ΠΊΠΎΠ΄ΠΎΠ²Ρ‹Ρ… слов для кодирования Π΄Π°Π½Π½ΠΎΠ³ΠΎ мноТСства сообщСний. (Под ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ подразумСваСтся Ρ‚ΠΎ, Ρ‡Ρ‚ΠΎ Π½ΠΈΠΊΠ°ΠΊΠΎΠ΅ Π΄Ρ€ΡƒΠ³ΠΎΠ΅ ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½ΠΎ Π΄Π΅ΠΊΠΎΠ΄ΠΈΡ€ΡƒΠ΅ΠΌΠΎΠ΅ мноТСство ΠΊΠΎΠ΄ΠΎΠ²Ρ‹Ρ… слов Π½Π΅ ΠΈΠΌΠ΅Π΅Ρ‚ ΠΌΠ΅Π½ΡŒΡˆΡƒΡŽ ΡΡ€Π΅Π΄Π½ΡŽΡŽ Π΄Π»ΠΈΠ½Ρƒ ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠ³ΠΎ слова, Ρ‡Π΅ΠΌ Π·Π°Π΄Π°Π½Π½ΠΎΠ΅ мноТСство.) ΠŸΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½Π½Π°Ρ Π₯Π°Ρ„Ρ„ΠΌΠ°Π½ΠΎΠΌ конструктивная ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΈΠΊΠ° свободна ΠΎΡ‚ ΠΎΡ‚ΠΌΠ΅Ρ‡Π΅Π½Β­Π½Ρ‹Ρ… нСдостатков.

Код Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π°

Π‘ΡƒΠΊΠ²Ρ‹ Π°Π»Ρ„Π°Π²ΠΈΡ‚Π° сообщСний Π²Ρ‹ΠΏΠΈΡΡ‹Π²Π°ΡŽΡ‚ Π² основной столбСц Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ кодирования Π² порядкС убывания вСроятностСй. Π”Π²Π΅ послСдниС Π±ΡƒΠΊΠ²Ρ‹ ΠΎΠ±ΡŠΠ΅Π΄ΠΈΠ½ΡΡŽΡ‚ Π² ΠΎΠ΄Π½Ρƒ Π²ΡΠΏΠΎΠΌΠΎΠ³Π°Ρ‚Π΅Π»ΡŒΠ½ΡƒΡŽ Π±ΡƒΠΊΠ²Ρƒ, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ ΠΏΡ€ΠΈΠΏΠΈΡΡ‹Π²Π°ΡŽΡ‚ ΡΡƒΠΌΠΌΠ°Ρ€Π½ΡƒΡŽ Π²Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΡŒ. Π’Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΡŒ Π±ΡƒΠΊΠ², Π½Π΅ ΡƒΡ‡Π°ΡΡ‚Π²ΠΎΠ²Π°Π²ΡˆΠΈΡ… Π² объСдинСнии, ΠΈ получСнная суммарная Π²Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΡŒ слова Ρ€Π°ΡΠΏΠΎΠ»Π°Π³Π°ΡŽΡ‚ΡΡ Π² порядкС убывания вСроятностСй Π² Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠΌ столбцС, Π° Π΄Π²Π΅ послСдниС ΠΎΠ±ΡŠΠ΅Π΄ΠΈΠ½ΡΡŽΡ‚. ΠŸΡ€ΠΎΡ†Π΅ΡΡ продолТаСтся Π΄ΠΎ Ρ‚Π΅Ρ… ΠΏΠΎΡ€, ΠΏΠΎΠΊΠ° Π½Π΅ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠΌ Π΅Π΄ΠΈΠ½ΡΡ‚Π²Π΅Π½Π½ΡƒΡŽ Π²ΡΠΏΠΎΠΌΠΎΠ³Π°Ρ‚Π΅Π»ΡŒΠ½ΡƒΡŽ Π±ΡƒΠΊΠ²Ρƒ с Π²Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΡŒΡŽ, Ρ€Π°Π²Π½ΠΎΠΉ Π΅Π΄ΠΈΠ½ΠΈΡ†Π΅.

Для нахоТдСния ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠΉ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΠΈ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΏΡ€ΠΎΡΠ»Π΅Π΄ΠΈΡ‚ΡŒ ΠΏΡƒΡ‚ΡŒ ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄Π° Π·Π½Π°ΠΊΠ° ΠΏΠΎ строкам ΠΈ столбцам Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹. Π­Ρ‚ΠΎ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ наглядно осущСствимо ΠΏΠΎ ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠΌΡƒ Π΄Π΅Ρ€Π΅Π²Ρƒ. Из Ρ‚ΠΎΡ‡ΠΊΠΈ, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚Β­ΡΡ‚Π²ΡƒΡŽΡ‰Π΅ΠΉ вСроятности 1, Π½Π°ΠΏΡ€Π°Π²Π»ΡΡŽΡ‚ΡΡ Π΄Π²Π΅ Π²Π΅Ρ‚Π²ΠΈ, ΠΏΡ€ΠΈΡ‡Π΅ΠΌ Π²Π΅Ρ‚Π²ΠΈ с большСй Π²Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΡŒΡŽ присваиваСм символ 1, Π° с мСньшСй – 0. Π’Π°ΠΊΠΎΠ΅ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΒ­Π½ΠΎΠ΅ Π²Π΅Ρ‚Π²Π»Π΅Π½ΠΈΠ΅ продолТаСтся Π΄ΠΎ Ρ‚Π΅Ρ… ΠΏΠΎΡ€, ΠΏΠΎΠΊΠ° Π½Π΅ Π΄ΠΎΠΉΠ΄Π΅ΠΌ Π΄ΠΎ вСроятности ΠΊΠ°ΠΆΒ­Π΄ΠΎΠΉ Π±ΡƒΠΊΠ²Ρ‹. Π”Π²ΠΈΠ³Π°ΡΡΡŒ ΠΏΠΎ ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠΌΡƒ Π΄Π΅Ρ€Π΅Π²Ρƒ свСрху Π²Π½ΠΈΠ·, ΠΌΠΎΠΆΠ½ΠΎ Π·Π°ΠΏΠΈΡΠ°Ρ‚ΡŒ для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ сообщСния ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠ΅ Π΅ΠΌΡƒ ΠΊΠΎΠ΄ΠΎΠ²Ρ‹Π΅ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΠΈ.

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊ

2.1. АлфавитноС Π½Π΅Ρ€Π°Π²Π½ΠΎΠΌΠ΅Ρ€Π½ΠΎΠ΅ Π΄Π²ΠΎΠΈΡ‡Π½ΠΎΠ΅ ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ сигналами Ρ€Π°Π²Π½ΠΎΠΉ Π΄Π»ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ. ΠŸΡ€Π΅Ρ„ΠΈΠΊΡΠ½Ρ‹Π΅ ΠΊΠΎΠ΄Ρ‹

ΠŸΠ°Ρ€Π°Π»Π»Π΅Π»ΡŒΠ½ΠΎ Π΄ΠΎΠ»ΠΆΠ½Π° Ρ€Π΅ΡˆΠ°Ρ‚ΡŒΡΡ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΠ° различимости ΠΊΠΎΠ΄ΠΎΠ². На Π²Ρ‹Ρ…ΠΎΠ΄Π΅ ΠΊΠΎΠ΄Π΅Ρ€Π° ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π° ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π°Ρ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ элСмСнтарных сигналов:

Каким ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ ΠΎΠ½Π° ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ Π΄Π΅ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½Π°? Если Π±Ρ‹ ΠΊΠΎΠ΄ Π±Ρ‹Π» Ρ€Π°Π²Π½ΠΎΠΌΠ΅Ρ€Π½Ρ‹ΠΌ, ΠΏΡ€ΠΈΠ΅ΠΌΠ½ΠΎΠ΅ устройство просто отсчитывало Π±Ρ‹ Π·Π°Π΄Π°Π½Π½ΠΎΠ΅ (фиксированноС) число элСмСнтарных сигналов (Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, 5, ΠΊΠ°ΠΊ Π² ΠΊΠΎΠ΄Π΅ Π‘ΠΎΠ΄ΠΎ) ΠΈ ΠΈΠ½Ρ‚Π΅Ρ€ΠΏΡ€Π΅Ρ‚ΠΈΡ€ΠΎΠ²Π°Π»ΠΎ ΠΈΡ… Π² соотвСтствии с ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠΉ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ΠΉ. ΠŸΡ€ΠΈ использовании Π½Π΅Ρ€Π°Π²Π½ΠΎΠΌΠ΅Ρ€Π½ΠΎΠ³ΠΎ кодирования Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹ Π΄Π²Π° ΠΏΠΎΠ΄Ρ…ΠΎΠ΄Π° ΠΊ ΠΎΠ±Π΅ΡΠΏΠ΅Ρ‡Π΅Π½ΠΈΡŽ различимости ΠΊΠΎΠ΄ΠΎΠ².

НСравномСрный ΠΊΠΎΠ΄ с Ρ€Π°Π·Π΄Π΅Π»ΠΈΡ‚Π΅Π»Π΅ΠΌ

Π’ соотвСтствии с пСрСчислСнными ΠΏΡ€Π°Π²ΠΈΠ»Π°ΠΌΠΈ строится кодовая Ρ‚Π°Π±Π». 3.1 для Π±ΡƒΠΊΠ² русского Π°Π»Ρ„Π°Π²ΠΈΡ‚Π°, ΠΎΡΠ½ΠΎΠ²Ρ‹Π²Π°ΡΡΡŒ Π½Π° ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π½Ρ‹Ρ… Ρ€Π°Π½Π΅Π΅ (Ρ‚Π°Π±Π». 1.3) вСроятностях появлСния ΠΎΡ‚Π΄Π΅Π»ΡŒΠ½Ρ‹Ρ… Π±ΡƒΠΊΠ².

Π’Π΅ΠΏΠ΅Ρ€ΡŒ ΠΏΠΎ Ρ„ΠΎΡ€ΠΌΡƒΠ»Π΅ нахоТдСния срСднСго для Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ случайных нСзависимых Π²Π΅Π»ΠΈΡ‡ΠΈΠ½ ΠΌΠΎΠΆΠ½ΠΎ Π½Π°ΠΉΡ‚ΠΈ ΡΡ€Π΅Π΄Π½ΡŽΡŽ Π΄Π»ΠΈΠ½Ρƒ ΠΊΠΎΠ΄Π° К(r,2) для Π΄Π°Π½Π½ΠΎΠ³ΠΎ способа кодирования:

ΠŸΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ для русского языка I1 ( r ) = 4,356 Π±ΠΈΡ‚, ΠΈΠ·Π±Ρ‹Ρ‚ΠΎΡ‡Π½ΠΎΡΡ‚ΡŒ Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΠΊΠΎΠ΄Π°, согласно (3.9), составляСт:

это ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ ΠΏΡ€ΠΈ Π΄Π°Π½Π½ΠΎΠΌ способС кодирования Π±ΡƒΠ΄Π΅Ρ‚ ΠΏΠ΅Ρ€Π΅Π΄Π°Π²Π°Ρ‚ΡŒΡΡ ΠΏΡ€ΠΈΠ±Π»ΠΈΠ·ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ Π½Π° 14% большС ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΈ, Ρ‡Π΅ΠΌ содСрТит исходноС сообщСниС. АналогичныС вычислСния для английского языка Π΄Π°ΡŽΡ‚ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ К(Π΅,2) = 4,716, Ρ‡Ρ‚ΠΎ ΠΏΡ€ΠΈ I1 ( e ) = 4,036 Π±ΠΈΡ‚ приводят ΠΊ избыточности ΠΊΠΎΠ΄Π° Q(Π΅,2) = 0,168.

РассмотрСв ΠΎΠ΄ΠΈΠ½ ΠΈΠ· Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² Π΄Π²ΠΎΠΈΡ‡Π½ΠΎΠ³ΠΎ Π½Π΅Ρ€Π°Π²Π½ΠΎΠΌΠ΅Ρ€Π½ΠΎΠ³ΠΎ кодирования, Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΎΡ‚Π²Π΅Ρ‚ΠΈΡ‚ΡŒ Π½Π° ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠ΅ вопросы: Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ Π»ΠΈ Ρ‚Π°ΠΊΠΎΠ΅ ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ Π±Π΅Π· использования раздСлитСля Π·Π½Π°ΠΊΠΎΠ²? БущСствуСт Π»ΠΈ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ эффСктивный (ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ) способ Π½Π΅Ρ€Π°Π²Π½ΠΎΠΌΠ΅Ρ€Π½ΠΎΠ³ΠΎ Π΄Π²ΠΎΠΈΡ‡Π½ΠΎΠ³ΠΎ кодирования?

Π‘ΡƒΡ‚ΡŒ ΠΏΠ΅Ρ€Π²ΠΎΠΉ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡ‹ состоит Π² Π½Π°Ρ…ΠΎΠΆΠ΄Π΅Π½ΠΈΠΈ Ρ‚Π°ΠΊΠΎΠ³ΠΎ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π° кодирования сообщСния, ΠΏΡ€ΠΈ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ ΠΏΠΎΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅Π΅ Π²Ρ‹Π΄Π΅Π»Π΅Π½ΠΈΠ΅ ΠΈΠ· Π½Π΅Π³ΠΎ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΎΡ‚Π΄Π΅Π»ΡŒΠ½ΠΎΠ³ΠΎ Π·Π½Π°ΠΊΠ° (Ρ‚.Π΅. Π΄Π΅ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅) оказываСтся ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½Ρ‹ΠΌ Π±Π΅Π· ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½Ρ‹Ρ… ΡƒΠΊΠ°Π·Π°Ρ‚Π΅Π»Π΅ΠΉ раздСлСния Π·Π½Π°ΠΊΠΎΠ². НаиболСС простыми ΠΈ ΡƒΠΏΠΎΡ‚Ρ€Π΅Π±ΠΈΠΌΡ‹ΠΌΠΈ ΠΊΠΎΠ΄Π°ΠΌΠΈ Ρ‚Π°ΠΊΠΎΠ³ΠΎ Ρ‚ΠΈΠΏΠ° ΡΠ²Π»ΡΡŽΡ‚ΡΡ Ρ‚Π°ΠΊ Π½Π°Π·Ρ‹Π²Π°Π΅ΠΌΡ‹Π΅ прСфиксныС ΠΊΠΎΠ΄Ρ‹, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΡƒΠ΄ΠΎΠ²Π»Π΅Ρ‚Π²ΠΎΡ€ΡΡŽΡ‚ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΌΡƒ ΡƒΡΠ»ΠΎΠ²ΠΈΡŽ (ΡƒΡΠ»ΠΎΠ²ΠΈΡŽ Π€Π°Π½ΠΎ):

НСравномСрный ΠΊΠΎΠ΄ ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½ΠΎ Π΄Π΅ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½, Ссли Π½ΠΈΠΊΠ°ΠΊΠΎΠΉ ΠΈΠ· ΠΊΠΎΠ΄ΠΎΠ² Π½Π΅ совпадаСт с Π½Π°Ρ‡Π°Π»ΠΎΠΌ (прСфиксом) ΠΊΠ°ΠΊΠΎΠ³ΠΎ-Π»ΠΈΠ±ΠΎ ΠΈΠ½ΠΎΠ³ΠΎ Π±ΠΎΠ»Π΅Π΅ Π΄Π»ΠΈΠ½Π½ΠΎΠ³ΠΎ ΠΊΠΎΠ΄Π°.

НапримСр, Ссли имССтся ΠΊΠΎΠ΄ 110, Ρ‚ΠΎ ΡƒΠΆΠ΅ Π½Π΅ ΠΌΠΎΠ³ΡƒΡ‚ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒΡΡ ΠΊΠΎΠ΄Ρ‹ 1, 11, 1101, 110101 ΠΈ ΠΏΡ€. Если условиС Π€Π°Π½ΠΎ выполняСтся, Ρ‚ΠΎ ΠΏΡ€ΠΈ ΠΏΡ€ΠΎΡ‡Ρ‚Π΅Π½ΠΈΠΈ (Ρ€Π°ΡΡˆΠΈΡ„Ρ€ΠΎΠ²ΠΊΠ΅) Π·Π°ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ сообщСния ΠΏΡƒΡ‚Π΅ΠΌ сопоставлСния с Ρ‚Π°Π±Π»ΠΈΡ†Π΅ΠΉ ΠΊΠΎΠ΄ΠΎΠ² всСгда ΠΌΠΎΠΆΠ½ΠΎ Ρ‚ΠΎΡ‡Π½ΠΎ ΡƒΠΊΠ°Π·Π°Ρ‚ΡŒ, Π³Π΄Π΅ заканчиваСтся ΠΎΠ΄ΠΈΠ½ ΠΊΠΎΠ΄ ΠΈ начинаСтся Π΄Ρ€ΡƒΠ³ΠΎΠΉ.

ΠŸΡƒΡΡ‚ΡŒ имССтся ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π°Ρ Ρ‚Π°Π±Π»ΠΈΡ†Π° прСфиксных ΠΊΠΎΠ΄ΠΎΠ²:

ВрСбуСтся Π΄Π΅ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ сообщСниС:

Π”Π΅ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ производится цикличСским ΠΏΠΎΠ²Ρ‚ΠΎΡ€Π΅Π½ΠΈΠ΅ΠΌ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΡ… дСйствий:

(a) ΠΎΡ‚Ρ€Π΅Π·Π°Ρ‚ΡŒ ΠΎΡ‚ Ρ‚Π΅ΠΊΡƒΡ‰Π΅Π³ΠΎ сообщСния ΠΊΡ€Π°ΠΉΠ½ΠΈΠΉ Π»Π΅Π²Ρ‹ΠΉ символ, ΠΏΡ€ΠΈΡΠΎΠ΅Π΄ΠΈΠ½ΠΈΡ‚ΡŒ справа ΠΊ Ρ€Π°Π±ΠΎΡ‡Π΅ΠΌΡƒ ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠΌΡƒ слову;

(b) ΡΡ€Π°Π²Π½ΠΈΡ‚ΡŒ Ρ€Π°Π±ΠΎΡ‡Π΅Π΅ ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠ΅ слово с ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠΉ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ΠΉ; Ссли совпадСния Π½Π΅Ρ‚, ΠΏΠ΅Ρ€Π΅ΠΉΡ‚ΠΈ ΠΊ (Π°);

(c) Π΄Π΅ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ Ρ€Π°Π±ΠΎΡ‡Π΅Π΅ ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠ΅ слово, ΠΎΡ‡ΠΈΡΡ‚ΠΈΡ‚ΡŒ Π΅Π³ΠΎ;

(d) ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΈΡ‚ΡŒ, ΠΈΠΌΠ΅ΡŽΡ‚ΡΡ Π»ΠΈ Π΅Ρ‰Π΅ Π·Π½Π°ΠΊΠΈ Π² сообщСнии; Ссли Β«Π΄Π°Β», ΠΏΠ΅Ρ€Π΅ΠΉΡ‚ΠΈ ΠΊ (Π°).

ΠŸΡ€ΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ Π΄Π°Π½Π½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π΄Π°Π΅Ρ‚:

Рис. 3.1. Π Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ примСнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°

ДовСдя ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Ρƒ Π΄ΠΎ ΠΊΠΎΠ½Ρ†Π°, получаСтся сообщСниС: Β«ΠΌΠ°ΠΌΠ° ΠΌΡ‹Π»Π° Ρ€Π°ΠΌΡƒΒ».

Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, использованиС прСфиксного кодирования позволяСт Π΄Π΅Π»Π°Ρ‚ΡŒ сообщСниС Π±ΠΎΠ»Π΅Π΅ ΠΊΠΎΡ€ΠΎΡ‚ΠΊΠΈΠΌ, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ Π½Π΅Ρ‚ нСобходимости ΠΏΠ΅Ρ€Π΅Π΄Π°Π²Π°Ρ‚ΡŒ Ρ€Π°Π·Π΄Π΅Π»ΠΈΡ‚Π΅Π»ΠΈ Π·Π½Π°ΠΊΠΎΠ². Однако условиС Π€Π°Π½ΠΎ Π½Π΅ устанавливаСт способа формирования прСфиксного ΠΊΠΎΠ΄Π° ΠΈ, Π² частности, Π½Π°ΠΈΠ»ΡƒΡ‡ΡˆΠ΅Π³ΠΎ ΠΈΠ· Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Ρ….

ΠŸΡ€Π΅Ρ„ΠΈΠΊΡΠ½Ρ‹ΠΉ ΠΊΠΎΠ΄ Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ

ΠŸΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Π° построСния ΠΊΠΎΠ΄ΠΎΠ²

Из ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Ρ‹ построСния ΠΊΠΎΠ΄ΠΎΠ² Π»Π΅Π³ΠΊΠΎ Π²ΠΈΠ΄Π΅Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎ ΠΎΠ½ΠΈ ΡƒΠ΄ΠΎΠ²Π»Π΅Ρ‚Π²ΠΎΡ€ΡΡŽΡ‚ ΡƒΡΠ»ΠΎΠ²ΠΈΡŽ Π€Π°Π½ΠΎ ΠΈ, ΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ, ΠΊΠΎΠ΄ являСтся прСфиксным. БрСдняя Π΄Π»ΠΈΠ½Π° ΠΊΠΎΠ΄Π° Ρ€Π°Π²Π½Π°:

I1 ( A ) = 2,390 Π±ΠΈΡ‚. ΠŸΠΎΠ΄ΡΡ‚Π°Π²Π»ΡΡ ΡƒΠΊΠ°Π·Π°Π½Π½Ρ‹Π΅ значСния Π² (3.5), получаСтся ΠΈΠ·Π±Ρ‹Ρ‚ΠΎΡ‡Π½ΠΎΡΡ‚ΡŒ ΠΊΠΎΠ΄Π° Q(A,2) = 0,0249, Ρ‚.Π΅. ΠΎΠΊΠΎΠ»ΠΎ 2,5%. Однако, Π΄Π°Π½Π½Ρ‹ΠΉ ΠΊΠΎΠ΄ нСльзя ΡΡ‡ΠΈΡ‚Π°Ρ‚ΡŒ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ вСроятности появлСния 0 ΠΈ 1 Π½Π΅ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹ (0,35 ΠΈ 0,65, соотвСтствСнно). ΠŸΡ€ΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ ΠΈΠ·Π»ΠΎΠΆΠ΅Π½Π½ΠΎΠΉ схСмы построСния ΠΊ русскому Π°Π»Ρ„Π°Π²ΠΈΡ‚Ρƒ Π΄Π°Π΅Ρ‚ ΠΈΠ·Π±Ρ‹Ρ‚ΠΎΡ‡Π½ΠΎΡΡ‚ΡŒ ΠΊΠΎΠ΄Π° 0,0147.

ΠŸΡ€Π΅Ρ„ΠΈΠΊΡΠ½Ρ‹ΠΉ ΠΊΠΎΠ΄ Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π°

Рис. 3.2. ΠŸΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Π° построСния ΠΊΠΎΠ΄ΠΎΠ²

К(А,2) = 0,3 βˆ™ 2 + 0,2 βˆ™ 2 + 0,2 βˆ™ 2 +0,15 βˆ™ 3 + 0,1 βˆ™ 4 + 0,05 βˆ™ 4 = 2,45. (3.13)

Рис. 3.3. ΠžΠ±Ρ€Π°Ρ‚Π½Π°Ρ ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Π° построСния ΠΊΠΎΠ΄ΠΎΠ²

Π˜Π·Π±Ρ‹Ρ‚ΠΎΡ‡Π½ΠΎΡΡ‚ΡŒ снова оказываСтся Ρ€Π°Π²Π½ΠΎΠΉ Q(A, 2) = 0,0249, ΠΎΠ΄Π½Π°ΠΊΠΎ, вСроятности 0 ΠΈ 1 сблизились (0,47 ΠΈ 0,53, соотвСтствСнно). Π‘ΠΎΠ»Π΅Π΅ высокая ΡΡ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ ΠΊΠΎΠ΄ΠΎΠ² Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π° ΠΏΠΎ ΡΡ€Π°Π²Π½Π΅Π½ΠΈΡŽ с ΠΊΠΎΠ΄Π°ΠΌΠΈ Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ становится ΠΎΡ‡Π΅Π²ΠΈΠ΄Π½ΠΎΠΉ, Ссли ΡΡ€Π°Π²Π½ΠΈΡ‚ΡŒ избыточности ΠΊΠΎΠ΄ΠΎΠ² для ΠΊΠ°ΠΊΠΎΠ³ΠΎ-Π»ΠΈΠ±ΠΎ СстСствСнного языка. ΠŸΡ€ΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ описанного ΠΌΠ΅Ρ‚ΠΎΠ΄Π° для Π±ΡƒΠΊΠ² русского Π°Π»Ρ„Π°Π²ΠΈΡ‚Π° ΠΏΠΎΡ€ΠΎΠΆΠ΄Π°Π΅Ρ‚ ΠΊΠΎΠ΄Ρ‹, прСдставлСнныС Π² Ρ‚Π°Π±Π». 3.4. (для удобства сопоставлСния ΠΎΠ½ΠΈ ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Ρ‹ Π² Ρ„ΠΎΡ€ΠΌΠ°Ρ‚Π΅ Ρ‚Π°Π±Π». 3.1).

ΠšΠΎΠ΄Ρ‹ для Π±ΡƒΠΊΠ² русского Π°Π»Ρ„Π°Π²ΠΈΡ‚Π°

БрСдняя Π΄Π»ΠΈΠ½Π° ΠΊΠΎΠ΄Π° оказываСтся Ρ€Π°Π²Π½ΠΎΠΉ К(r,2) = 4,395; ΠΈΠ·Π±Ρ‹Ρ‚ΠΎΡ‡Π½ΠΎΡΡ‚ΡŒ ΠΊΠΎΠ΄Π° Q(r,2) = 0,0090, Ρ‚.Π΅. Π½Π΅ ΠΏΡ€Π΅Π²Ρ‹ΡˆΠ°Π΅Ρ‚ 1 %, Ρ‡Ρ‚ΠΎ Π·Π°ΠΌΠ΅Ρ‚Π½ΠΎ мСньшС избыточности ΠΊΠΎΠ΄Π° Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ (см. Π²Ρ‹ΡˆΠ΅).

Код Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π° Π²Π°ΠΆΠ΅Π½ Π² тСорСтичСском ΠΎΡ‚Π½ΠΎΡˆΠ΅Π½ΠΈΠΈ, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ ΠΌΠΎΠΆΠ½ΠΎ Π΄ΠΎΠΊΠ°Π·Π°Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎ ΠΎΠ½ являСтся самым экономичным ΠΈΠ· всСх Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Ρ…, Ρ‚.Π΅. Π½ΠΈ для ΠΊΠ°ΠΊΠΎΠ³ΠΎ ΠΌΠ΅Ρ‚ΠΎΠ΄Π° Π°Π»Ρ„Π°Π²ΠΈΡ‚Π½ΠΎΠ³ΠΎ кодирования Π΄Π»ΠΈΠ½Π° ΠΊΠΎΠ΄Π° Π½Π΅ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΎΠΊΠ°Π·Π°Ρ‚ΡŒΡΡ мСньшС, Ρ‡Π΅ΠΌ ΠΊΠΎΠ΄ Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π°.

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊ

27. Код Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ. Код Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π°.

koralexand.ru > 27. Код Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ. Код Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π°.

Код ШСннона-Ѐано

Код строится ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ:

1) Π±ΡƒΠΊΠ²Ρ‹ Π°Π»Ρ„Π°Π²ΠΈΡ‚Π° сообщСний Π²Ρ‹ΠΏΠΈΒ­ΡΡ‹Π²Π°ΡŽΡ‚ΡΡ Π² Ρ‚Π°Π±Π»ΠΈΡ†Ρƒ Π² порядкС убывания вСроятностСй;

2) Π·Π°Ρ‚Π΅ΠΌ ΠΎΠ½ΠΈ Ρ€Π°Π·Π΄Π΅Π»ΡΒ­ΡŽΡ‚ΡΡ Π½Π° Π΄Π²Π΅ Π³Ρ€ΡƒΠΏΠΏΡ‹ Ρ‚Π°ΠΊ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ суммы вСроятностСй Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΠ· Π³Ρ€ΡƒΠΏΠΏ Π±Ρ‹Β­Π»ΠΈ ΠΏΠΎ возмоТности ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹;

3) всСм Π±ΡƒΠΊΠ²Π°ΠΌ Π²Π΅Ρ€Ρ…Π½Π΅ΠΉ ΠΏΠΎΠ»ΠΎΠ²ΠΈΠ½Ρ‹ Π² качСствС ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ символа приписываСтся 1, Π° всСм Π½ΠΈΠΆΠ½ΠΈΠΌ β€” 0;

4) каТдая ΠΈΠ· ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Β­Π½Ρ‹Ρ… Π³Ρ€ΡƒΠΏΠΏ, Π² свою ΠΎΡ‡Π΅Ρ€Π΅Π΄ΡŒ, разбиваСтся Π½Π° Π΄Π²Π΅ ΠΏΠΎΠ΄Π³Ρ€ΡƒΠΏΠΏΡ‹ с ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹ΠΌΠΈ суммарными вСроятностями ΠΈ Ρ‚. Π΄.

ΠŸΡ€ΠΎΡ†Π΅ΡΡ повторяСтся Π΄ΠΎ Ρ‚Π΅Ρ… ΠΏΠΎΡ€, ΠΏΠΎΠΊΠ° Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΏΠΎΠ΄Π³Ρ€ΡƒΠΏΠΏΠ΅ останСтся ΠΏΠΎ ΠΎΠ΄Π½ΠΎΠΉ Π±ΡƒΠΊΠ²Π΅.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€. Рассмотрим Π°Π»Ρ„Π°Π²ΠΈΡ‚ ΠΈΠ· восьми Π±ΡƒΠΊΠ² (Ρ‚Π°Π±Π». 12). ΠŸΡ€ΠΈ ΠΎΠ±Ρ‹Ρ‡Π½ΠΎΠΌ (Π½Π΅ ΡƒΡ‡ΠΈΡ‚Ρ‹Π²Π°ΡŽΡ‰Π΅ΠΌ статистичСских характСристик) ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠΈ для прСд­ставлСния ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Π±ΡƒΠΊΠ²Ρ‹ трСбуСтся Ρ‚Ρ€ΠΈ символа.

Π’Π°Π±Π»ΠΈΡ†Π° 8.12 Π’Π°Π±Π»ΠΈΡ†Π° 13

Π‘ΡƒΠΊΠ²Ρ‹Π’Π΅Ρ€ΠΎΡΡ‚Β­Π½ΠΎΡΡ‚ΠΈΠšΠΎΠ΄ΠΎΠ²Ρ‹Π΅ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΠΈΠ‘ΡƒΠΊΠ²Ρ‹Π’Π΅Ρ€ΠΎΡΡ‚Β­Π½ΠΎΡΡ‚ΠΈΠšΠΎΠ΄ΠΎΠ²Ρ‹Π΅ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΠΈ
0,22110,2211
0,201010,2010
0,161000,16011
0,16010,16010
0,100010,10001
0,1000010,100001
0,04000010,0400001
0,02000000,0200000

Вычислим ΡΠ½Ρ‚Ρ€ΠΎΠΏΠΈΡŽ Π½Π°Π±ΠΎΡ€Π° Π±ΡƒΠΊΠ²: Н

ΠΈ срСднСС число символов Π½Π° Π±ΡƒΠΊΠ²Ρƒ

Π³Π΄Π΅ n() β€” число символов Π² ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠΉ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΠΈ, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π΅ΠΉ Π±ΡƒΠΊΠ²Π΅.

ЗначСния Н(z) ΠΈ lср Π½Π΅ ΠΎΡ‡Π΅Π½ΡŒ Ρ€Π°Π·Π»ΠΈΡ‡Π°ΡŽΡ‚ΡΡ ΠΏΠΎ Π²Π΅Π»ΠΈΡ‡ΠΈΠ½Π΅. УсловиС Ρ‚Π΅ΠΎΡ€Π΅ΠΌΡ‹ Π¨Π΅Π½Π½ΠΎΠ½Π° Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΎ Н(z) 2 Π½Π΅ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½ΠΎΡΡ‚ΡŒ ста­новится Π΅Ρ‰Π΅ большС.

ΠœΠ΅Ρ‚ΠΎΠ΄ Π₯Π°Ρ„Ρ„ΠΌΠ΅Π½Π°

ΠœΠ΅Ρ‚ΠΎΠ΄ Π₯Π°Ρ„Ρ„ΠΌΠ΅Π½Π° свободСн ΠΎΡ‚ нСдостатка связанного с Π½Π΅ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½ΠΎΡΡ‚ΡŒΡŽ построСния ΠΊΠΎΠ΄Π°. Данная ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΈΠΊΠ° Ρ‚Π°ΠΊΠΆΠ΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ статистичСскиС свойства источника сообщСний. ΠœΠ΅Ρ‚ΠΎΠ΄ Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΡƒΠ΅Ρ‚ ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½ΠΎΠ΅ построСниС ΠΊΠΎΠ΄Π° с наимСньшим для Π΄Π°Π½Π½ΠΎΠ³ΠΎ распрСдСлСния вСроятностСй срСдним числом символов Π½Π° Π±ΡƒΠΊΠ²Ρƒ.

Π’ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ 14 ΠΏΠΎΠΊΠ°Π·Π°Π½Ρ‹ основныС шаги построСния ΠΊΠΎΠ΄Π°.

Π‘ΡƒΠΊΠ²Ρ‹Π’Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΠΈΠ’ΡΠΏΠΎΠΌΠΎΠ³Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ столбцы
1234567
0,220,220,220,260,320,420,581
0,200,200,200,220,260,320,42
0,160,160,160,200,220,26
0,160,160,160,160,20
0,100,100,160,16
0,100,100,10
0,040,06
0,02

Для Π΄Π²ΠΎΠΈΡ‡Π½ΠΎΠ³ΠΎ ΠΊΠΎΠ΄Π° ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΈΠΊΠ° сводится ΠΊ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΌΡƒ:

1) Π‘ΡƒΠΊΠ²Ρ‹ Π°Π»Ρ„Π°Π²ΠΈΡ‚Π° сообщСний Π²Ρ‹ΠΏΠΈΡΡ‹Π²Π°ΡŽΡ‚ΡΡ Π² основной столбСц Π² порядкС убывания вСроят­ностСй;

2) Π΄Π²Π΅ послСдниС Π±ΡƒΠΊΠ²Ρ‹ ΠΎΠ±ΡŠΠ΅Π΄ΠΈΠ½ΡΡŽΡ‚ΡΡ Π² ΠΎΠ΄Π½Ρƒ Π²ΡΠΏΠΎΠΌΠΎΠ³Π°Ρ‚Π΅Π»ΡŒΠ½ΡƒΡŽ Π±ΡƒΠΊΒ­Π²Ρƒ, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ приписываСтся суммарная Π²Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΡŒ;

3) вСроятности Π±ΡƒΠΊΠ², Π½Π΅ ΡƒΡ‡Π°ΡΡ‚Π²ΠΎΠ²Π°Π²ΡˆΠΈΡ… Π² объСдинСнии, ΠΈ полу­чСнная суммарная Π²Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΡŒ снова Ρ€Π°ΡΠΏΠΎΠ»Π°Π³Π°ΡŽΡ‚ΡΡ Π² порядкС убывания вС­роятностСй Π² Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠΌ столбцС, Π° Π΄Π²Π΅ послСдниС Π±ΡƒΠΊΠ²Ρ‹ снова ΠΎΠ±ΡŠΠ΅Π΄ΠΈΠ½ΡΡŽΡ‚ΡΡ.

ΠŸΡ€ΠΎΡ†Π΅ΡΡ продолТаСтся Π΄ΠΎ Ρ‚Π΅Ρ… ΠΏΠΎΡ€, ΠΏΠΎΠΊΠ° Π½Π΅ ΠΏΠΎΠ»ΡƒΒ­Ρ‡ΠΈΠΌ Π΅Π΄ΠΈΠ½ΡΡ‚Π²Π΅Π½Π½ΡƒΡŽ Π²ΡΠΏΠΎΠΌΠΎΠ³Π°Ρ‚Π΅Π»ΡŒΠ½ΡƒΡŽ Π±ΡƒΠΊΠ²Ρƒ с Π²Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΡŒΡŽ, Ρ€Π°Π²Π½ΠΎΠΉ Π΅Π΄ΠΈΠ½ΠΈΡ†Π΅.

Для составлСния ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠΉ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Β­Ρ†ΠΈΠΈ, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π΅ΠΉ Π΄Π°Π½Π½ΠΎΠΌΡƒ ΡΠΎΠΎΠ±Ρ‰Π΅Β­Π½ΠΈΡŽ, Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΏΡ€ΠΎΡΠ»Π΅Π΄ΠΈΡ‚ΡŒ ΠΏΡƒΡ‚ΡŒ ΠΏΠ΅Ρ€Π΅Β­Ρ…ΠΎΠ΄Π° сообщСний ΠΏΠΎ строкам ΠΈ столбцам Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹. Для наглядности строится ΠΊΠΎΠ΄ΠΎΒ­Π²ΠΎΠ΅ Π΄Π΅Ρ€Π΅Π²ΠΎ(рис.1).

Рис.1 КодовоС Π΄Π΅Ρ€Π΅Π²ΠΎ

Из Ρ‚ΠΎΡ‡ΠΊΠΈ, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π΅ΠΉ вСроятности 1, Π½Π°ΠΏΡ€Π°Π²Π»ΡΡŽΡ‚ΡΡ Π΄Π²Π΅ Π²Π΅Ρ‚Π²ΠΈ, ΠΏΡ€ΠΈΡ‡Π΅ΠΌ Π²Π΅Ρ‚Π²ΠΈ с большСй Π²Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΡŒΡŽ присваиваСтся символ 1, Π° с мСньшСй β€” 0. Π’Π°ΠΊΠΎΠ΅ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΠ΅ Π²Π΅Ρ‚Π²Π»Π΅Π½ΠΈΠ΅ продолТаСтся Π΄ΠΎ Ρ‚Π΅Ρ… ΠΏΠΎΡ€, ΠΏΠΎΠΊΠ° Π½Π΅ Π΄ΠΎΠΉΠ΄Π΅ΠΌ Π΄ΠΎ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Π±ΡƒΠΊΠ²Ρ‹ (рис. 1).

Π’Π΅ΠΏΠ΅Ρ€ΡŒ, двигаясь ΠΏΠΎ ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠΌΡƒ Π΄Π΅Ρ€Π΅Π²Ρƒ свСрху Π²Π½ΠΈΠ·, ΠΌΠΎΠΆΠ½ΠΎ Π·Π°ΠΏΠΈΡΠ°Ρ‚ΡŒ для ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Π±ΡƒΠΊΠ²Ρ‹ ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΡƒΡŽ Π΅ΠΉ ΠΊΠΎΠ΄ΠΎΠ²ΡƒΡŽ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΡŽ;

01 00 111 110 100 1011 10101 10100

ΠžΡΡ‚Π°Π²ΠΈΡ‚ΡŒ ΠΊΠΎΠΌΠΌΠ΅Π½Ρ‚Π°Ρ€ΠΈΠΉ ΠžΡ‚ΠΌΠ΅Π½ΠΈΡ‚ΡŒ ΠΎΡ‚Π²Π΅Ρ‚

Для ΠΎΡ‚ΠΏΡ€Π°Π²ΠΊΠΈ коммСнтария Π²Π°ΠΌ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ Π°Π²Ρ‚ΠΎΡ€ΠΈΠ·ΠΎΠ²Π°Ρ‚ΡŒΡΡ.

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊ

ΠšΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ

Алгоритм Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ β€” ΠΎΠ΄ΠΈΠ½ ΠΈΠ· ΠΏΠ΅Ρ€Π²Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² сТатия, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π²ΠΏΠ΅Ρ€Π²Ρ‹Π΅ сформулировали амСриканскиС ΡƒΡ‡Ρ‘Π½Ρ‹Π΅ Π¨Π΅Π½Π½ΠΎΠ½ ΠΈ Π€Π°Π½ΠΎ. Π”Π°Π½Π½Ρ‹ΠΉ ΠΌΠ΅Ρ‚ΠΎΠ΄ сТатия ΠΈΠΌΠ΅Π΅Ρ‚ большоС сходство с Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠΌ Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π°, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ появился Π½Π° нСсколько Π»Π΅Ρ‚ ΠΏΠΎΠ·ΠΆΠ΅. Алгоритм ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ ΠΊΠΎΠ΄Ρ‹ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ Π΄Π»ΠΈΠ½Ρ‹: часто Π²ΡΡ‚Ρ€Π΅Ρ‡Π°ΡŽΡ‰ΠΈΠΉΡΡ символ кодируСтся ΠΊΠΎΠ΄ΠΎΠΌ мСньшСй Π΄Π»ΠΈΠ½Ρ‹, Ρ€Π΅Π΄ΠΊΠΎ Π²ΡΡ‚Ρ€Π΅Ρ‡Π°ΡŽΡ‰ΠΈΠΉΡΡ β€” ΠΊΠΎΠ΄ΠΎΠΌ большСй Π΄Π»ΠΈΠ½Ρ‹. ΠšΠΎΠ΄Ρ‹ Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ прСфиксныС, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ, Π½ΠΈΠΊΠ°ΠΊΠΎΠ΅ ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠ΅ слово Π½Π΅ являСтся прСфиксом любого Π΄Ρ€ΡƒΠ³ΠΎΠ³ΠΎ. Π­Ρ‚ΠΎ свойство позволяСт ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½ΠΎ Π΄Π΅ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ Π»ΡŽΠ±ΡƒΡŽ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ ΠΊΠΎΠ΄ΠΎΠ²Ρ‹Ρ… слов.

Π‘ΠΎΠ΄Π΅Ρ€ΠΆΠ°Π½ΠΈΠ΅

ΠžΡΠ½ΠΎΠ²Π½Ρ‹Π΅ свСдСния

ΠšΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ (Π°Π½Π³Π». Shannon-Fano coding) β€” Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ прСфиксного Π½Π΅ΠΎΠ΄Π½ΠΎΡ€ΠΎΠ΄Π½ΠΎΠ³ΠΎ кодирования. ΠžΡ‚Π½ΠΎΡΠΈΡ‚ΡΡ ΠΊ вСроятностным ΠΌΠ΅Ρ‚ΠΎΠ΄Π°ΠΌ сТатия (Ρ‚ΠΎΡ‡Π½Π΅Π΅, ΠΌΠ΅Ρ‚ΠΎΠ΄Π°ΠΌ контСкстного модСлирования Π½ΡƒΠ»Π΅Π²ΠΎΠ³ΠΎ порядка). Подобно Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡƒ Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ ΠΈΠ·Π±Ρ‹Ρ‚ΠΎΡ‡Π½ΠΎΡΡ‚ΡŒ сообщСния, Π·Π°ΠΊΠ»ΡŽΡ‡Ρ‘Π½Π½ΡƒΡŽ Π² Π½Π΅ΠΎΠ΄Π½ΠΎΡ€ΠΎΠ΄Π½ΠΎΠΌ распрСдСлСнии частот символов Π΅Π³ΠΎ (ΠΏΠ΅Ρ€Π²ΠΈΡ‡Π½ΠΎΠ³ΠΎ) Π°Π»Ρ„Π°Π²ΠΈΡ‚Π°, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ замСняСт ΠΊΠΎΠ΄Ρ‹ Π±ΠΎΠ»Π΅Π΅ частых символов ΠΊΠΎΡ€ΠΎΡ‚ΠΊΠΈΠΌΠΈ Π΄Π²ΠΎΠΈΡ‡Π½Ρ‹ΠΌΠΈ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡΠΌΠΈ, Π° ΠΊΠΎΠ΄Ρ‹ Π±ΠΎΠ»Π΅Π΅ Ρ€Π΅Π΄ΠΊΠΈΡ… символов β€” Π±ΠΎΠ»Π΅Π΅ Π΄Π»ΠΈΠ½Π½Ρ‹ΠΌΠΈ Π΄Π²ΠΎΠΈΡ‡Π½Ρ‹ΠΌΠΈ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡΠΌΠΈ.

Алгоритм Π±Ρ‹Π» нСзависимо Π΄Ρ€ΡƒΠ³ ΠΎΡ‚ Π΄Ρ€ΡƒΠ³Π° Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Π°Π½ Π¨Π΅Π½Π½ΠΎΠ½ΠΎΠΌ (публикация Β«ΠœΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΡ‡Π΅ΡΠΊΠ°Ρ тСория связи», 1948 Π³ΠΎΠ΄) ΠΈ, ΠΏΠΎΠ·ΠΆΠ΅, Π€Π°Π½ΠΎ (ΠΎΠΏΡƒΠ±Π»ΠΈΠΊΠΎΠ²Π°Π½ΠΎ ΠΊΠ°ΠΊ тСхничСский ΠΎΡ‚Ρ‡Ρ‘Ρ‚).

ΠžΡΠ½ΠΎΠ²Π½Ρ‹Π΅ этапы

Когда Ρ€Π°Π·ΠΌΠ΅Ρ€ ΠΏΠΎΠ΄Π°Π»Ρ„Π°Π²ΠΈΡ‚Π° становится Ρ€Π°Π²Π΅Π½ Π½ΡƒΠ»ΡŽ ΠΈΠ»ΠΈ Π΅Π΄ΠΈΠ½ΠΈΡ†Π΅, Ρ‚ΠΎ дальнСйшСго удлинСния прСфиксного ΠΊΠΎΠ΄Π° для ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΡ… Π΅ΠΌΡƒ символов ΠΏΠ΅Ρ€Π²ΠΈΡ‡Π½ΠΎΠ³ΠΎ Π°Π»Ρ„Π°Π²ΠΈΡ‚Π° Π½Π΅ происходит, Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ присваиваСт Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹ΠΌ символам прСфиксныС ΠΊΠΎΠ΄Ρ‹ Ρ€Π°Π·Π½ΠΎΠΉ Π΄Π»ΠΈΠ½Ρ‹. На шагС дСлСния Π°Π»Ρ„Π°Π²ΠΈΡ‚Π° сущСствуСт Π½Π΅ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½ΠΎΡΡ‚ΡŒ, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ Ρ€Π°Π·Π½ΠΎΡΡ‚ΡŒ суммарных вСроятностСй p0 βˆ’ p1 ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Π° для Π΄Π²ΡƒΡ… Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² раздСлСния (учитывая, Ρ‡Ρ‚ΠΎ всС символы ΠΏΠ΅Ρ€Π²ΠΈΡ‡Π½ΠΎΠ³ΠΎ Π°Π»Ρ„Π°Π²ΠΈΡ‚Π° ΠΈΠΌΠ΅ΡŽΡ‚ Π²Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΡŒ, Π±ΠΎΠ»ΡŒΡˆΡƒΡŽ нуля).

Алгоритм вычислСния ΠΊΠΎΠ΄ΠΎΠ² Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ

Код Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ строится с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ Π΄Π΅Ρ€Π΅Π²Π°. ΠŸΠΎΡΡ‚Ρ€ΠΎΠ΅Π½ΠΈΠ΅ этого Π΄Π΅Ρ€Π΅Π²Π° начинаСтся ΠΎΡ‚ корня. ВсС мноТСство ΠΊΠΎΠ΄ΠΈΡ€ΡƒΠ΅ΠΌΡ‹Ρ… элСмСнтов соотвСтствуСт ΠΊΠΎΡ€Π½ΡŽ Π΄Π΅Ρ€Π΅Π²Π° (Π²Π΅Ρ€ΡˆΠΈΠ½Π΅ ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ уровня). Оно разбиваСтся Π½Π° Π΄Π²Π° подмноТСства с ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π½ΠΎ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹ΠΌΠΈ суммарными вСроятностями. Π­Ρ‚ΠΈ подмноТСства ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‚ Π΄Π²ΡƒΠΌ Π²Π΅Ρ€ΡˆΠΈΠ½Π°ΠΌ Π²Ρ‚ΠΎΡ€ΠΎΠ³ΠΎ уровня, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡŽΡ‚ΡΡ с ΠΊΠΎΡ€Π½Π΅ΠΌ. Π”Π°Π»Π΅Π΅ ΠΊΠ°ΠΆΠ΄ΠΎΠ΅ ΠΈΠ· этих подмноТСств разбиваСтся Π½Π° Π΄Π²Π° подмноТСства с ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π½ΠΎ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹ΠΌΠΈ суммарными вСроятностями. Им ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‚ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ Ρ‚Ρ€Π΅Ρ‚ΡŒΠ΅Π³ΠΎ уровня. Если подмноТСство содСрТит СдинствСнный элСмСнт, Ρ‚ΠΎ Π΅ΠΌΡƒ соотвСтствуСт концСвая Π²Π΅Ρ€ΡˆΠΈΠ½Π° ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠ³ΠΎ Π΄Π΅Ρ€Π΅Π²Π°; Ρ‚Π°ΠΊΠΎΠ΅ подмноТСство Ρ€Π°Π·Π±ΠΈΠ΅Π½ΠΈΡŽ Π½Π΅ ΠΏΠΎΠ΄Π»Π΅ΠΆΠΈΡ‚. ΠŸΠΎΠ΄ΠΎΠ±Π½Ρ‹ΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ поступаСм Π΄ΠΎ Ρ‚Π΅Ρ… ΠΏΠΎΡ€, ΠΏΠΎΠΊΠ° Π½Π΅ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠΌ всС ΠΊΠΎΠ½Ρ†Π΅Π²Ρ‹Π΅ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹. Π’Π΅Ρ‚Π²ΠΈ ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠ³ΠΎ Π΄Π΅Ρ€Π΅Π²Π° Ρ€Π°Π·ΠΌΠ΅Ρ‡Π°Π΅ΠΌ символами 1 ΠΈ 0, ΠΊΠ°ΠΊ Π² случаС ΠΊΠΎΠ΄Π° Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π°.

ΠŸΡ€ΠΈ построСнии ΠΊΠΎΠ΄Π° Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ Ρ€Π°Π·Π±ΠΈΠ΅Π½ΠΈΠ΅ мноТСства элСмСнтов ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΎ, Π²ΠΎΠΎΠ±Ρ‰Π΅ говоря, нСсколькими способами. Π’Ρ‹Π±ΠΎΡ€ разбиСния Π½Π° ΡƒΡ€ΠΎΠ²Π½Π΅ n ΠΌΠΎΠΆΠ΅Ρ‚ ΡƒΡ…ΡƒΠ΄ΡˆΠΈΡ‚ΡŒ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Ρ‹ разбиСния Π½Π° ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΌ ΡƒΡ€ΠΎΠ²Π½Π΅ (n+1) ΠΈ привСсти ΠΊ Π½Π΅ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ ΠΊΠΎΠ΄Π° Π² Ρ†Π΅Π»ΠΎΠΌ. Π”Ρ€ΡƒΠ³ΠΈΠΌΠΈ словами, ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ΅ ΠΏΠΎΠ²Π΅Π΄Π΅Π½ΠΈΠ΅ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ шагС ΠΏΡƒΡ‚ΠΈ СшС Π½Π΅ Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΡƒΠ΅Ρ‚ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ всСй совокупности дСйствий. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ ΠΊΠΎΠ΄ Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ Π½Π΅ являСтся ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ Π² ΠΎΠ±Ρ‰Π΅ΠΌ смыслС, хотя ΠΈ Π΄Π°Π΅Ρ‚ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹ ΠΏΡ€ΠΈ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… распрСдСлСниях вСроятностСй. Для ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΈ Ρ‚ΠΎΠ³ΠΎ ΠΆΠ΅ распрСдСлСния вСроятностСй ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΡΡ‚Ρ€ΠΎΠΈΡ‚ΡŒ, Π²ΠΎΠΎΠ±Ρ‰Π΅ говоря, нСсколько ΠΊΠΎΠ΄ΠΎΠ² Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ, ΠΈ всС ΠΎΠ½ΠΈ ΠΌΠΎΠ³ΡƒΡ‚ Π΄Π°Ρ‚ΡŒ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Π΅ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹. Если ΠΏΠΎΡΡ‚Ρ€ΠΎΠΈΡ‚ΡŒ всС Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Π΅ ΠΊΠΎΠ΄Ρ‹ Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ для Π΄Π°Π½Π½ΠΎΠ³ΠΎ распрСдСлСния вСроятностСй, Ρ‚ΠΎ срСди Π½ΠΈΡ… Π±ΡƒΠ΄ΡƒΡ‚ Π½Π°Ρ…ΠΎΠ΄ΠΈΡ‚ΡŒΡΡ ΠΈ всС ΠΊΠΎΠ΄Ρ‹ Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π°, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ ΠΊΠΎΠ΄Ρ‹.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠ³ΠΎ Π΄Π΅Ρ€Π΅Π²Π°

A (частота встрСчаСмости 50), B (частота встрСчаСмости 39), C (частота встрСчаСмости 18), D (частота встрСчаСмости 49), E (частота встрСчаСмости 35), F (частота встрСчаСмости 24).

ΠΊΠΎΠ΄ шСннона Ρ„Π°Π½ΠΎ ΠΊΠΎΠ΄ Ρ…Π°Ρ„Ρ„ΠΌΠ°Π½Π°. b9664401806e31c5fcb8a03bba1b06b8. ΠΊΠΎΠ΄ шСннона Ρ„Π°Π½ΠΎ ΠΊΠΎΠ΄ Ρ…Π°Ρ„Ρ„ΠΌΠ°Π½Π° Ρ„ΠΎΡ‚ΠΎ. ΠΊΠΎΠ΄ шСннона Ρ„Π°Π½ΠΎ ΠΊΠΎΠ΄ Ρ…Π°Ρ„Ρ„ΠΌΠ°Π½Π°-b9664401806e31c5fcb8a03bba1b06b8. ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΊΠΎΠ΄ шСннона Ρ„Π°Π½ΠΎ ΠΊΠΎΠ΄ Ρ…Π°Ρ„Ρ„ΠΌΠ°Π½Π°. ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° b9664401806e31c5fcb8a03bba1b06b8. ΠœΠ΅Ρ‚ΠΎΠ΄ΠΈΠΊΠ° ШСннона–Ѐано Π½Π΅ всСгда ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ ΠΊ ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½ΠΎΠΌΡƒ ΠΏΠΎΡΡ‚Ρ€ΠΎΠ΅Π½ΠΈΡŽ ΠΊΠΎΠ΄Π°. Π’Π΅Π΄ΡŒ ΠΏΡ€ΠΈ Ρ€Π°Π·Π±ΠΈΠ΅Π½ΠΈΠΈ Π½Π° ΠΏΠΎΠ΄Π³Ρ€ΡƒΠΏΠΏΡ‹ Π½Π° 1-ΠΉ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΄Π΅Π»Π°Ρ‚ΡŒ большСй ΠΏΠΎ вСроятности ΠΊΠ°ΠΊ Π²Π΅Ρ€Ρ…Π½ΡŽΡŽ, Ρ‚Π°ΠΊ ΠΈ ниТнюю ΠΏΠΎΠ΄Π³Ρ€ΡƒΠΏΠΏΡƒ. Π’ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ срСднСС число символов Π½Π° Π±ΡƒΠΊΠ²Ρƒ окаТСтся Π΄Ρ€ΡƒΠ³ΠΈΠΌ. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, построСнный ΠΊΠΎΠ΄ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΎΠΊΠ°Π·Π°Ρ‚ΡŒΡΡ Π½Π΅ самым Π»ΡƒΡ‡ΡˆΠΈΠΌ.

A β€” 11, B β€” 101, C β€” 100, D β€” 00, E β€” 011, F β€” 010.

ΠšΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ являСтся достаточно старым ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ сТатия, ΠΈ Π½Π° сСгодняшний дСнь ΠΎΠ½ΠΎ Π½Π΅ прСдставляСт особого практичСского интСрСса. Π’ Π±ΠΎΠ»ΡŒΡˆΠΈΠ½ΡΡ‚Π²Π΅ случаСв, Π΄Π»ΠΈΠ½Π° сТатой ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ, ΠΏΠΎ Π΄Π°Π½Π½ΠΎΠΌΡƒ ΠΌΠ΅Ρ‚ΠΎΠ΄Ρƒ, Ρ€Π°Π²Π½Π° Π΄Π»ΠΈΠ½Π΅ сТатой ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ с использованиСм кодирования Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π°. Но Π½Π° Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡΡ… всё ΠΆΠ΅ Ρ„ΠΎΡ€ΠΌΠΈΡ€ΡƒΡŽΡ‚ΡΡ Π½Π΅ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ ΠΊΠΎΠ΄Ρ‹ Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ, поэтому сТатиС ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π° принято ΡΡ‡ΠΈΡ‚Π°Ρ‚ΡŒ Π±ΠΎΠ»Π΅Π΅ эффСктивным.

Π›ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΡƒΡ€Π°

Бсылки

ΠœΠ΅Ρ‚ΠΎΠ΄Ρ‹ сТатияВСория

Π˜Π½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΡΠ‘ΠΎΠ±ΡΡ‚Π²Π΅Π½Π½Π°Ρ Β· Взаимная Β· Энтропия Β· Условная энтропия Β· Π‘Π»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Β· Π˜Π·Π±Ρ‹Ρ‚ΠΎΡ‡Π½ΠΎΡΡ‚ΡŒ
Π•Π΄ΠΈΠ½ΠΈΡ†Ρ‹ измСрСнияБит Β· Нат Β· Ниббл Β· Π₯Π°Ρ€Ρ‚Π»ΠΈ Β· Π€ΠΎΡ€ΠΌΡƒΠ»Π° Π₯Π°Ρ€Ρ‚Π»ΠΈ
Π‘Π΅Π· ΠΏΠΎΡ‚Π΅Ρ€ΡŒ
Π­Π½Ρ‚Ρ€ΠΎΠΏΠΈΠΉΠ½ΠΎΠ΅ сТатиСАлгоритм Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π° Β· Адаптивный Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π° Β· АрифмСтичСскоС ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ ( Алгоритм Π¨Π΅Π½Π½ΠΎΠ½Π° β€” Π€Π°Π½ΠΎ Β· Π˜Π½Ρ‚Π΅Ρ€Π²Π°Π»ΡŒΠ½ΠΎΠ΅) Β· ΠšΠΎΠ΄Ρ‹ Π“ΠΎΠ»ΠΎΠΌΠ±Π° Β· Π”Π΅Π»ΡŒΡ‚Π° Β· Π£Π½ΠΈΠ²Π΅Ρ€ΡΠ°Π»ΡŒΠ½Ρ‹ΠΉ ΠΊΠΎΠ΄ (Элиаса Β· Π€ΠΈΠ±ΠΎΠ½Π°Ρ‡Ρ‡ΠΈ)
Π‘Π»ΠΎΠ²Π°Ρ€Π½Ρ‹Π΅ ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹RLE Β· Β· LZ ( Β· LZSS Β· LZW Β· LZWL Β· Β· Β· LZX Β· LZRW Β· LZJB Β· LZT)
ΠŸΡ€ΠΎΡ‡Π΅Π΅RLE Β· CTW Β· BWT Β· PPM Β· DMC
Аудио
ВСорияБвёртка Β· PCM Β· Алиасинг Β· ДискрСтизация Β· Π’Π΅ΠΎΡ€Π΅ΠΌΠ° ΠšΠΎΡ‚Π΅Π»ΡŒΠ½ΠΈΠΊΠΎΠ²Π°
ΠœΠ΅Ρ‚ΠΎΠ΄Ρ‹LPC (LAR Β· LSP) Β· WLPC Β· CELP Β· ACELP Β· A-Π·Π°ΠΊΠΎΠ½ Β· ΞΌ-Π·Π°ΠΊΠΎΠ½ Β· MDCT Β· ΠŸΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Π½ΠΈΠ΅ Π€ΡƒΡ€ΡŒΠ΅ Β· ΠŸΡΠΈΡ…ΠΎΠ°ΠΊΡƒΡΡ‚ΠΈΡ‡Π΅ΡΠΊΠ°Ρ модСль
ΠŸΡ€ΠΎΡ‡Π΅Π΅Dynamic range compression Β· Π‘ΠΆΠ°Ρ‚ΠΈΠ΅ Ρ€Π΅Ρ‡ΠΈ Β· ПолосноС ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅
Π˜Π·ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½ΠΈΡ
Π’Π΅Ρ€ΠΌΠΈΠ½Ρ‹Π¦Π²Π΅Ρ‚ΠΎΠ²ΠΎΠ΅ пространство Β· ПиксСл Β· Chroma subsampling Β· АртСфакты сТатия
ΠœΠ΅Ρ‚ΠΎΠ΄Ρ‹RLE Β· DPCM Β· Π€Ρ€Π°ΠΊΡ‚Π°Π»ΡŒΠ½Ρ‹ΠΉ Β· Wavelet Β· EZW Β· SPIHT Β· LP Β· Π”ΠšΠŸ Β· ΠŸΠšΠ›
ΠŸΡ€ΠΎΡ‡Π΅Π΅Π‘ΠΈΡ‚Ρ€Π΅ΠΉΡ‚ Β· Test images Β· PSNR Β· ΠšΠ²Π°Π½Ρ‚ΠΎΠ²Π°Π½ΠΈΠ΅
Π’ΠΈΠ΄Π΅ΠΎ
Π’Π΅Ρ€ΠΌΠΈΠ½Ρ‹Π₯арактСристики Π²ΠΈΠ΄Π΅ΠΎ Β· ΠšΠ°Π΄Ρ€ Β· Π’ΠΈΠΏΡ‹ ΠΊΠ°Π΄Ρ€ΠΎΠ² Β· ΠšΠ°Ρ‡Π΅ΡΡ‚Π²ΠΎ Π²ΠΈΠ΄Π΅ΠΎ
ΠœΠ΅Ρ‚ΠΎΠ΄Ρ‹ΠšΠΎΠΌΠΏΠ΅Π½ΡΠ°Ρ†ΠΈΡ двиТСния Β· Π”ΠšΠŸ Β· ΠšΠ²Π°Π½Ρ‚ΠΎΠ²Π°Π½ΠΈΠ΅
ΠŸΡ€ΠΎΡ‡Π΅Π΅Π’ΠΈΠ΄Π΅ΠΎΠΊΠΎΠ΄Π΅ΠΊ Β· Rate distortion theory (CBR Β· ABR Β· VBR)
Π‘ΠΌ. Ρ‚Π°ΠΊΠΆΠ΅: ΠŸΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ для сТатия Π΄Π°Π½Π½Ρ‹Ρ… β€’ Π‘Ρ‚Π°Π½Π΄Π°Ρ€Ρ‚Ρ‹ ΠΈ Ρ„ΠΎΡ€ΠΌΠ°Ρ‚Ρ‹ сТатия

ПолСзноС

Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ‡Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ «ΠšΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ» Π² Π΄Ρ€ΡƒΠ³ΠΈΡ… словарях:

Алгоритм Π¨Π΅Π½Π½ΠΎΠ½Π° β€” Π€Π°Π½ΠΎ β€” Алгоритм Π¨Π΅Π½Π½ΠΎΠ½Π° Π€Π°Π½ΠΎ ΠΎΠ΄ΠΈΠ½ ΠΈΠ· ΠΏΠ΅Ρ€Π²Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² сТатия, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π²ΠΏΠ΅Ρ€Π²Ρ‹Π΅ сформулировали амСриканскиС ΡƒΡ‡Ρ‘Π½Ρ‹Π΅ Π¨Π΅Π½Π½ΠΎΠ½ ΠΈ Π€Π°Π½ΠΎ (Π°Π½Π³Π». Fano). Π”Π°Π½Π½Ρ‹ΠΉ ΠΌΠ΅Ρ‚ΠΎΠ΄ сТатия ΠΈΠΌΠ΅Π΅Ρ‚ большоС сходство с Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠΌ Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π°, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ появился Π½Π° нСсколько Π»Π΅Ρ‚ … ВикипСдия

Код Π¨Π΅Π½Π½ΠΎΠ½Π°-Π€Π°Π½ΠΎ β€” Алгоритм Π¨Π΅Π½Π½ΠΎΠ½Π° Π€Π°Π½ΠΎ ΠΎΠ΄ΠΈΠ½ ΠΈΠ· ΠΏΠ΅Ρ€Π²Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² сТатия, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π²ΠΏΠ΅Ρ€Π²Ρ‹Π΅ сформулировали амСриканскиС ΡƒΡ‡Ρ‘Π½Ρ‹Π΅ Π¨Π΅Π½Π½ΠΎΠ½ ΠΈ Π€Π°Π½ΠΎ. Π”Π°Π½Π½Ρ‹ΠΉ ΠΌΠ΅Ρ‚ΠΎΠ΄ сТатия ΠΈΠΌΠ΅Π΅Ρ‚ большоС сходство с Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠΌ Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π°, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ появился Π½Π° нСсколько Π»Π΅Ρ‚ ΠΏΠΎΠ·ΠΆΠ΅. Алгоритм… … ВикипСдия

ΠšΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ энтропии β€” ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ словами (ΠΊΠΎΠ΄Π°ΠΌΠΈ) ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ Π΄Π»ΠΈΠ½Ρ‹, ΠΏΡ€ΠΈ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ Π΄Π»ΠΈΠ½Π° ΠΊΠΎΠ΄Π° символа ΠΈΠΌΠ΅Π΅Ρ‚ ΠΎΠ±Ρ€Π°Ρ‚Π½ΡƒΡŽ Π·Π°Π²ΠΈΡΠΈΠΌΠΎΡΡ‚ΡŒ ΠΎΡ‚ вСроятности появлСния символа Π² ΠΏΠ΅Ρ€Π΅Π΄Π°Π²Π°Π΅ΠΌΠΎΠΌ сообщСнии. ΠžΠ±Ρ‹Ρ‡Π½ΠΎ энтропийныС ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊΠΈ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ для сТатия Π΄Π°Π½Π½Ρ‹Ρ… ΠΊΠΎΠ΄Ρ‹, Π΄Π»ΠΈΠ½Ρ‹ которых… … ВикипСдия

ΠšΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ с минимальной ΠΈΠ·Π±Ρ‹Ρ‚ΠΎΡ‡Π½ΠΎΡΡ‚ΡŒΡŽ β€” ΠšΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ энтропии ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ словами (ΠΊΠΎΠ΄Π°ΠΌΠΈ) ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ Π΄Π»ΠΈΠ½Ρ‹, ΠΏΡ€ΠΈ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ Π΄Π»ΠΈΠ½Π° ΠΊΠΎΠ΄Π° символа ΠΈΠΌΠ΅Π΅Ρ‚ ΠΎΠ±Ρ€Π°Ρ‚Π½ΡƒΡŽ Π·Π°Π²ΠΈΡΠΈΠΌΠΎΡΡ‚ΡŒ ΠΎΡ‚ вСроятности появлСния символа Π² ΠΏΠ΅Ρ€Π΅Π΄Π°Π²Π°Π΅ΠΌΠΎΠΌ сообщСнии. ΠžΠ±Ρ‹Ρ‡Π½ΠΎ энтропийныС ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊΠΈ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ для сТатия данных… … ВикипСдия

ΠšΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ Π΄Π»ΠΈΠ½ сСрий β€” (Π°Π½Π³Π». Run length encoding, RLE) ΠΈΠ»ΠΈ ΠšΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ ΠΏΠΎΠ²Ρ‚ΠΎΡ€ΠΎΠ² простой Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ сТатия Π΄Π°Π½Π½Ρ‹Ρ…, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΎΠΏΠ΅Ρ€ΠΈΡ€ΡƒΠ΅Ρ‚ сСриями Π΄Π°Π½Π½Ρ‹Ρ…, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡΠΌΠΈ, Π² ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΎΠ΄ΠΈΠ½ ΠΈ Ρ‚ΠΎΡ‚ ΠΆΠ΅ символ встрСчаСтся нСсколько Ρ€Π°Π· подряд. ΠŸΡ€ΠΈ кодировании… … ВикипСдия

ΠšΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π° β€” Алгоритм Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π° (Π°Π½Π³Π». Huffman) Π°Π΄Π°ΠΏΡ‚ΠΈΠ²Π½Ρ‹ΠΉ ΠΆΠ°Π΄Π½Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ прСфиксного кодирования Π°Π»Ρ„Π°Π²ΠΈΡ‚Π° с минимальной ΠΈΠ·Π±Ρ‹Ρ‚ΠΎΡ‡Π½ΠΎΡΡ‚ΡŒΡŽ. Π‘Ρ‹Π» Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Π°Π½ Π² 1952 Π³ΠΎΠ΄Ρƒ Π΄ΠΎΠΊΡ‚ΠΎΡ€ΠΎΠΌ ΠœΠ°ΡΡΠ°Ρ‡ΡƒΡΠ΅Ρ‚ΡΠΊΠΎΠ³ΠΎ тСхнологичСского института Дэвидом Π₯Π°Ρ„Ρ„ΠΌΠ°Π½ΠΎΠΌ. Π’ настоящСС… … ВикипСдия

Π¨Π΅Π½Π½ΠΎΠ½Π° Ρ‚Π΅ΠΎΡ€Π΅ΠΌΠ° β€” Π’Π΅ΠΎΡ€Π΅ΠΌΠ° ΠšΠΎΡ‚Π΅Π»ΡŒΠ½ΠΈΠΊΠΎΠ²Π° (Π² англоязычной Π»ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΡƒΡ€Π΅ Ρ‚Π΅ΠΎΡ€Π΅ΠΌΠ° Найквиста) гласит, Ρ‡Ρ‚ΠΎ, Ссли Π°Π½Π°Π»ΠΎΠ³ΠΎΠ²Ρ‹ΠΉ сигнал x(t) ΠΈΠΌΠ΅Π΅Ρ‚ ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½Π½Ρ‹ΠΉ спСктр, Ρ‚ΠΎ ΠΎΠ½ ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ восстановлСн ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½ΠΎ ΠΈ Π±Π΅Π· ΠΏΠΎΡ‚Π΅Ρ€ΡŒ ΠΏΠΎ своим дискрСтным отсчётам, взятым с частотой болСС… … ВикипСдия

ΠšΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ Π“ΠΎΠ»ΠΎΠΌΠ±Π° β€” ΠšΠΎΠ΄Ρ‹ Π“ΠΎΠ»ΠΎΠΌΠ±Π° это сСмСйство энтропийных ΠΊΠΎΠ΄Π΅Ρ€ΠΎΠ², ΡΠ²Π»ΡΡŽΡ‰ΠΈΡ…ΡΡ ΠΎΠ±Ρ‰ΠΈΠΌ случаСм ΡƒΠ½Π°Ρ€Π½ΠΎΠ³ΠΎ ΠΊΠΎΠ΄Π°. Π’Π°ΠΊΠΆΠ΅ ΠΏΠΎΠ΄ ΠΊΠΎΠ΄ΠΎΠΌ Π“ΠΎΠ»ΠΎΠΌΠ±Π° ΠΌΠΎΠΆΠ΅Ρ‚ ΠΏΠΎΠ΄Ρ€Π°Π·ΡƒΠΌΠ΅Π²Π°Ρ‚ΡŒΡΡ ΠΎΠ΄ΠΈΠ½ ΠΈΠ· прСдставитСлСй этого сСмСйства. Код Π“ΠΎΠ»ΠΎΠΌΠ±Π° позволяСт ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²ΠΈΡ‚ΡŒ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ символов Π² видС… … ВикипСдия

Алгоритм Π¨Π΅Π½Π½ΠΎΠ½Π° β€” Алгоритм Π¨Π΅Π½Π½ΠΎΠ½Π° Π€Π°Π½ΠΎ ΠΎΠ΄ΠΈΠ½ ΠΈΠ· ΠΏΠ΅Ρ€Π²Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² сТатия, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π²ΠΏΠ΅Ρ€Π²Ρ‹Π΅ сформулировали амСриканскиС ΡƒΡ‡Ρ‘Π½Ρ‹Π΅ Π¨Π΅Π½Π½ΠΎΠ½ ΠΈ Π€Π°Π½ΠΎ (Π°Π½Π³Π». Robert Fano). Π”Π°Π½Π½Ρ‹ΠΉ ΠΌΠ΅Ρ‚ΠΎΠ΄ сТатия ΠΈΠΌΠ΅Π΅Ρ‚ большоС сходство с Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠΌ Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π°, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ появился на… … ВикипСдия

Π­Π½Ρ‚Ρ€ΠΎΠΏΠΈΠΉΠ½ΠΎΠ΅ ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ β€” Для Ρ‚Π΅Ρ€ΠΌΠΈΠ½Π° Β«ΠšΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅Β» см. Π΄Ρ€ΡƒΠ³ΠΈΠ΅ значСния. Π­Π½Ρ‚Ρ€ΠΎΠΏΠΈΠΉΠ½ΠΎΠ΅ ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ с Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΡŽ ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½ΠΎΠ³ΠΎ восстановлСния с Ρ†Π΅Π»ΡŒΡŽ ΡƒΠΌΠ΅Π½ΡŒΡˆΠ΅Π½ΠΈΡ ΠΎΠ±ΡŠΡ‘ΠΌΠ° Π΄Π°Π½Π½Ρ‹Ρ… (Π΄Π»ΠΈΠ½Ρ‹ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ) с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ усрСднСния… … ВикипСдия

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊ

Π”ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ ΠΊΠΎΠΌΠΌΠ΅Π½Ρ‚Π°Ρ€ΠΈΠΉ

Π’Π°Ρˆ адрСс email Π½Π΅ Π±ΡƒΠ΄Π΅Ρ‚ ΠΎΠΏΡƒΠ±Π»ΠΈΠΊΠΎΠ²Π°Π½. ΠžΠ±ΡΠ·Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ поля ΠΏΠΎΠΌΠ΅Ρ‡Π΅Π½Ρ‹ *