static dictionary methods of text compression

时间：2022-11-07 17:20:26

　　Now I will introduce a way to compress a text. When we are confronted with numerous data, and the data has a similar structure, we can take advantage of the feature to improve the performance of compression. In most of times, we could take the method to compress a text as its feature of data structure.

　　we classify the method named dictionary method into two categories. One is static dictionary method, and the other is auto or dynamic dictionary method.

Now I plan to describe the first shortly with a routine example.

　　if we have much information about a structure of a text , it is available to take the static dictionary method. We could use many ways to implement the method varying with occasions, but a way named double letters code is popular with programmers.

　　To make it clearer, I prefer to take a simple example to explain the method, as follows.

　　Now there is a signal composed by five letters, that is 'a', 'b', 'c', 'd' and 'r'. Then we get a dictionary accroding to our signal knowledge. The dictionary is

code letter
000 a
001 b
010 c
011 d
100 r
101 ab
110 ac
111 ad

　　Then I will code a sequence that is 'abracadabra'.

　　At first, the coder will read the first of two letters, which are 'ab'. After that, the coder have to find if the pair of letters is in our dictionary. If it does,  the coder will return the letters's code and read the next letters. otherwise it will return the first letter's code and read the following letter. In this example, the coder will find the code in the dictionary, and return '101'. Following the step, the coder reads 'ra', but it cann't find the value of our dictionary by key 'ra'. So it have to return the code of 'r' that is '100', and read the letter 'c' following 'a' to compose of a new pair of letters  that is 'ac'. The coder return '110'. Then read 'ad', return '110'. ...

　　The output is '101100110111101100000'.

　　The routine written by python is as follows.　　

 def getCodeDict():

     codeDict = {}

     codeDict['a'] = ''

     codeDict['b'] = ''

     codeDict['c'] = ''

     codeDict['d'] = ''

     codeDict['r'] = ''

     codeDict['ab'] = ''

     codeDict['ac'] = ''

     codeDict['ad'] = ''

     return codeDict

 def compress(code):

     print('start to compress')

     result = ''

     codeDict = getCodeDict()

     offset = 2

     unCodedCode = code

     while unCodedCode != '':

         targetCode = unCodedCode[0 : 2]

         if targetCode in codeDict:

             #find a pair of letters, and move two steps

             result = result + codeDict[targetCode]

             offset = 2

         else :

             #not find a pair of letters, and move only one step

             result = result + codeDict[targetCode[0]]

             offset = 1

         unCodedCode = unCodedCode[offset : ]

     print('complete to compress')

     return result  

 if __name__=='__main__':

     signals = 'abracadabra'

     result = compress(signals)

     print(result)

相关文章