Editing Incremental encoding (section)

'''Incremental encoding''', also known as '''front compression''', '''back compression''', or '''front coding''', is a type of [[delta encoding]] [[compression algorithm]] whereby common [[Prefix (linguistics)|prefix]]es or [[Affix|suffixes]] and their lengths are recorded so that they need not be duplicated. This algorithm is particularly well-suited for compressing [[sorting|sorted]] [[data#Uses of data in computing|data]], e.g., a list of [[word]]s from a [[dictionary]].

For example:
{| class="wikitable"
|-
! Input
! Common prefix
! Compressed output
|-
|
<pre>
myxa
myxophyta
myxopod
nab
nabbed
nabbing
nabit
nabk
nabob
nacarat
nacelle
</pre>
|
<pre>
no preceding word
'myx'
'myxop'
no common prefix
'nab'
'nabb'
'nab'
'nab'
'nab'
'na'
'nac'
</pre>
|
<pre>
0 myxa
3 ophyta
5 od
0 nab
3 bed
4 ing
3 it
3 k
3 ob
2 carat
3 elle
</pre>
|-
| align="right" | 64 bytes
|
| align="left" | 46 bytes
|-
|}

The encoding used to store the common prefix length itself varies from application to application. Typical techniques are storing the value as a single byte; [[delta encoding]], which stores only the change in the common prefix length; and various [[Universal code (data compression)|universal codes]]. It may be combined with other general [[lossless data compression]] techniques such as [[entropy encoding]] and [[dictionary coder]]s to compress the remaining suffixes.