55
правок
Изменения
Нет описания правки
Таким образом, используя LZW мы сократили сообщение на 29 бит из 125 — это почти 22 %. Если сообщение будет длиннее, то элементы словаря будут представлять всё более и более длинные части текста, благодаря чему повторяющиеся слова будут представлены очень компактно.
=== Декодирование ===
Теперь представим что мы получили закодированное сообщение, приведённое выше, и нам нужно его декодировать. Прежде всего, нам нужно знать начальный словарь, а последующие записи словаря мы можем реконструировать уже на ходу, поскольку они являются просто конкатенацией предыдущих записей.
{| class="wikitable" style="text-align: right; margin-left: auto; margin-right: auto;"
|-
! colspan="2" | Input
! scope="col" width="6em" rowspan="2" | Output Sequence
! colspan="4" | New Dictionary Entry
! rowspan="2" | Comments
|-
! Bits !! Code
! scope="col" width="6em" colspan="2" | Full
! scope="col" width="6em" colspan="2" | Conjecture
|-
| 10100 || 20
| style="text-align: center;" | T
| style="border-right: none;" |
| style="border-left: none;" |
| style="border-right: none;" | 27:
| style="border-left: none;" | T? ||
|-
| 01111 || 15
| style="text-align: center;" | O
| style="border-right: none;" | 27:
| style="border-left: none;" | TO
| style="border-right: none;" | 28:
| style="border-left: none;" | O? ||
|-
| 00010 || 2
| style="text-align: center;" | B
| style="border-right: none;" | 28:
| style="border-left: none;" | OB
| style="border-right: none;" | 29:
| style="border-left: none;" | B? ||
|-
| 00101 || 5
| style="text-align: center;" | E
| style="border-right: none;" | 29:
| style="border-left: none;" | BE
| style="border-right: none;" | 30:
| style="border-left: none;" | E? ||
|-
| 01111 || 15
| style="text-align: center;" | O
| style="border-right: none;" | 30:
| style="border-left: none;" | EO
| style="border-right: none;" | 31:
| style="border-left: none;" | O? ||
|-
| 10010 || 18
| style="text-align: center;" | R
| style="border-right: none;" | 31:
| style="border-left: none;" | OR
| style="border-right: none;" | 32:
| style="border-left: none;" | R?
| style="text-align: left;" | created code 31 (last to fit in 5 bits)
|-
| 001110 || 14
| style="text-align: center;" | N
| style="border-right: none;" | 32:
| style="border-left: none;" | RN
| style="border-right: none;" | 33:
| style="border-left: none;" | N?
| style="text-align: left;" | so start using 6 bits
|-
| 001111 || 15
| style="text-align: center;" | O
| style="border-right: none;" | 33:
| style="border-left: none;" | NO
| style="border-right: none;" | 34:
| style="border-left: none;" | O? ||
|-
| 010100 || 20
| style="text-align: center;" | T
| style="border-right: none;" | 34:
| style="border-left: none;" | OT
| style="border-right: none;" | 35:
| style="border-left: none;" | T? ||
|-
| 011011 || 27
| style="text-align: center;" | TO
| style="border-right: none;" | 35:
| style="border-left: none;" | TT
| style="border-right: none;" | 36:
| style="border-left: none;" | TO? ||
|-
| 011101 || 29
| style="text-align: center;" | BE
| style="border-right: none;" | 36:
| style="border-left: none;" | TOB
| style="border-right: none;" | 37:
| style="border-left: none;" | BE?
| style="text-align: left;" | 36 = TO + 1st symbol (B) of
|-
| 011111 || 31
| style="text-align: center;" | OR
| style="border-right: none;" | 37:
| style="border-left: none;" | BEO
| style="border-right: none;" | 38:
| style="border-left: none;" | OR?
| style="text-align: left;" | next coded sequence received (BE)
|-
| 100100 || 36
| style="text-align: center;" | TOB
| style="border-right: none;" | 38:
| style="border-left: none;" | ORT
| style="border-right: none;" | 39:
| style="border-left: none;" | TOB? ||
|-
| 011110 || 30
| style="text-align: center;" | EO
| style="border-right: none;" | 39:
| style="border-left: none;" | TOBE
| style="border-right: none;" | 40:
| style="border-left: none;" | EO? ||
|-
| 100000 || 32
| style="text-align: center;" | RN
| style="border-right: none;" | 40:
| style="border-left: none;" | EOR
| style="border-right: none;" | 41:
| style="border-left: none;" | RN? ||
|-
| 100010 || 34
| style="text-align: center;" | OT
| style="border-right: none;" | 41:
| style="border-left: none;" | RNO
| style="border-right: none;" | 42:
| style="border-left: none;" | OT? ||
|-
| 000000 || 0
| style="text-align: center;" | #
| style="border-right: none;" |
| style="border-left: none;" |
| style="border-right: none;" |
| style="border-left: none;" | ||
|-
|}
