3.2: Codificación de longitud de ejecución

Última actualización
Guardar como PDF

Page ID: 82062

Paul Penfield, Jr.
Massachusetts Institute of Technology via MIT OpenCourseWare

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Supongamos que un mensaje consiste en secuencias largas de un pequeño número de símbolos o caracteres. Entonces el mensaje podría codificarse como una lista del símbolo y el número de veces que ocurre. Por ejemplo, el mensaje “a B B B B B a a a B B a a a a” podría codificarse como “a 1 B 5 a 3 B 2 a 4”. Esta técnica funciona muy bien para un número relativamente pequeño de circunstancias. Un ejemplo es la bandera alemana, que podría codificarse como tantos píxeles negros, tantos píxeles rojos y tantos píxeles amarillos, con un gran ahorro sobre especificar cada píxel. Otro ejemplo proviene de la tecnología de fax, donde se escanea un documento y se transmiten grupos largos de píxeles blancos (o negros) como meramente el número de dichos píxeles (ya que solo hay píxeles blancos y negros, ni siquiera es necesario especificar el color ya que se puede suponer que es el otro color).

La codificación por longitud de ejecución no funciona bien para mensajes sin secuencias repetidas del mismo símbolo. Por ejemplo, puede funcionar bien para dibujos e incluso imágenes escaneadas en blanco y negro, pero no funciona

Figura 3.3: Bandera de Alemania (banda negra en la parte superior, roja en el centro, amarilla en la parte inferior)

bien para fotografías ya que pequeños cambios en el sombreado de un píxel al siguiente requerirían que se definan muchos símbolos.