《密码学与网络安全 教学课件 ppt 作者 978-7-302-19727-0附录M》由会员分享，可在线阅读，更多相关《密码学与网络安全 教学课件 ppt 作者 978-7-302-19727-0附录M（6页珍藏版）》请在金锄头文库上搜索。
1、 645 APPENDIX M ZIP PGP (Chapter 16) uses the ZIP data compression technique. ZIP, created by Jean-lup Gailey, Mark Adler, and Richard Wales, is based on an algorithm, called LZ77 (Lempel- Ziv 77), devised by Jacop Ziv and Abraham Lempel. In this appendix, we briefl y discuss LZ77 as the basis for Z
2、IP. M.1LZ77 ENCODING LZ77 encoding is an example of dictionary-based encoding. The idea is to create a dictionary (table) of strings used during the communication session. If both the sender and the receiver have a copy of the dictionary, then already-encountered strings can be replaced by their ind
3、ices in the dictionary to reduce the amount of information transmitted. Although the idea appears simple, several diffi culties surface in the implementa- tion. First, how can a dictionary be created for each session? It cannot be universal due to its length. Second, how can the receiver acquire the
4、 dictionary made by the sender? If you send the dictionary, you are sending extra data, which defeats the whole purpose of compression. A practical algorithm that uses the idea of adaptive dictionary-based encoding is the LZ77 algorithm. We introduce the basic idea of this algorithm with an example
5、but do not delve into the details of different versions and implementations. In our example, assume that the following string is to be sent. We have chosen this specifi c string to simplify the discussion. BAABABBBAABBBBAA Using our simple version of the LZ77 algorithm, the process is divided into t
6、wo phases: compressing the string and decompressing the string. for70220_appM.fm Page 645 Saturday, January 27, 2007 1:41 PM 646 APPENDIX MZIP Compression In this phase, there are two concurrent events: building an indexed dictionary and com- pressing a string of symbols. The algorithm extracts from
7、 the remaining noncompressed string the smallest substring that cannot be found in the dictionary. It then stores a copy of this substring in the dictionary, (as a new entry) and assigns it an index value. Compres- sion occurs when the substring, except for the last character, is replaced with the i
8、ndex found in the dictionary. The process then inserts the index and the last character of the substring into the compressed string. For example, if the substring is ABBB, you search for ABB in the dictionary. You fi nd that the index for ABB is 4; the compressed substring is therefore 4B. Figure M.
9、1 shows the process for our sample string. Figure M.1 Example of LZ77 encoding Uncompressed BAABABBBAABBBBAA Compressed B, A, 2B, 3B, 1A, 4B, 5A BAABABBBAABBBBAA BAA 7 ABBB 6 BA 5 ABB 4 AB 3 A 2 B 1 ABBB 6 BA 5 ABB 4 AB 3 A 2 B 1 BA 5 ABB 4 AB 3 A 2 B 1 ABB 4 AB 3 A 2 B 1 AB 3 A 2 B 1 A 2 B 1 B 1 B
10、AABABBBAABBBBAA B, A ABABBBAABBBBAA B, A, 2B ABBBAABBBBAA B, A, 2B, 3B BAABBBBAA B, A, 2B, 3B, 1A ABBBBAA BAA B, A, 2B, 3B, 1A, 4B ABBB BA ABB AB A B B, A, 2B, 3B, 1A, 4B, 5A BAA Parsed String Parsed String Parsed String Parsed String Parsed String Parsed String Parsed String for70220_appM.fm Page 6
11、46 Saturday, January 27, 2007 1:41 PM SECTION M.1LZ77 ENCODING 647 Let us go through a few steps in Figure M.1: Step 1. The process extracts from the original string the smallest substring that is not in the dictionary. Because the dictionary is empty, the smallest character is one character (the fi
12、 rst character, B). The process stores a copy of it as the fi rst entry in the dictionary. Its index is 1. No part of this substring can be replaced with an index from the dictionary (it is only one character). The process inserts B in the compressed string. So far, the compressed string has only on
13、e character: B. The remaining noncompressed string is the original string without the fi rst character. Step 2. The process extracts from the remaining string the next smallest substring that is not in the dictionary. This substring is the character A, which is not in the dictionary. The process sto
14、res a copy of it as the second entry in the dictionary. No part of this substring can be replaced with an index from the dictionary (it is only one character). The process inserts A in the compressed string. So far, the com- pressed string has two characters: B and A (we have placed commas between t
15、he substrings in the compressed string to show the separation). Step 3. The process extracts from the remaining string the next smallest substring that is not in the dictionary. This situation differs from the two previous steps. The next character (A) is in the dictionary, so the process extracts t
16、wo characters (AB) that are not in the dictionary. The process stores a copy of AB as the third entry in the dictionary. The process now fi nds the index of an entry in the dictionary that is the substring without the last character (AB without the last character is A). The index for A is 2, so the process replaces A with 2 and inserts 2B in the compressed string. Step 4 . Next the process extracts the substring ABB (because A and AB are already in the dictionary). A copy of ABB is store
