http://www.martinreddy.net/gfx/2d/GIF-comp.txt
본문중
Now let's consider the possibility that <code> is not in the string table.
이제 <코드>가 테이블에 없는 경우를 생각해보자.
Think back to compression, and try to understand what happens
when you have a string like P[...]P[...]PQ appear in the charstream.
압축 과정으로 돌아가서 생각해보자. 만약 당신이 "P[...]P[...]PQ"란 문자열을
보게 되었을때 어떻게 될지 살펴보자.
Suppose P[...] is already in the string table, but P[...]P is not.
"P[...]" 는 이미 테이블에 있지만, P[...]P는 아직 없다고 해보자.
Thecompressor will parse out P[...], and find that P[...]P is not in the string table.
압축기는 P[...]를 분리해내고, P[...]P가 아직 테이블에 없다는 걸 발견한다.
It will output the code for P[...], and add P[...]P to the string table.
그러면 P[...]의 코드를 출력한 다음, P[...]P를 테이블에 추가할 것이다.
Then it will get up to P[...]P for the next string,
그리고는 다음 문자열에서 P[...]P를 마주치게 된다.
and find that P[...]P is in the table, as the code just added.
그리고 방금 테이블에 추가된 P[...]P의 코드를 찾게된다.
So it will output the code for P[...]P if it finds that P[...]PQ is not in the table.
그러고 P[...]PQ는 테이블에 없다는 걸 알고 P[...]P의 코드를 출력한다.
The decompressor is always "one step behind" the compressor.
해제기는 항상 압축기보다 한 발 처져있다.
When the decompressor sees the code for P[...]P, it will not have added that code to it's string table yet because it
해제기가 P[...]P의 코드를 봤을 때, 그것은 아직 테이블에 추가하기 전일 것이다.
needed the beginning character of P[...]P to add to the string for the last code, P[...], to form the code for P[...]P.
왜냐하면 P[...]P의 시작문자를 마지막 코드의 문자열, P[...], 뒤에 덧붙여야 P[...]P의 코드를 얻을 수 있기 때문이다.
However, when a decompressor finds a code that it doesn't know yet, it will always be the very next one to be added to the string table. So it can guess at what the string for the code should be, and, in fact, it will always be correct.
그렇지만, 해제기가 아직 모르는 코드를 발견했다면 그건 항상 바로 다음번에 테이블에 추가될 코드다.
그러니 그 코드를 위한 문자열이 무엇이 되어야 할지 짐작할 수 있고, 사실 그건 항상 옳다.
(즉 마지막으로 사용한 문자열의 첫 문자를 끝에 붙인 문자열이 새 코드에 해당된다는것.
좀 이상한 논리지만, 반복되는 부분이 많은게 이미지 파일의 특성이니 어찌보면 자연스럽다.)
If I am a decompressor, and I see code#124, and yet my string table has entries only up to code#123, I can figure out what
code#124 must be, add it to my string table, and output the string. If code#123 generated the string, which I will refer to here as a prefix, [...], then code#124, in this special case, will be [...] plus the first character of [...].
해제기의 입장에서 보자면, 내가 [124]란 코드를 발견했는데 아직 테이블은 [123]까지 밖에 없다. 그러면 나는 [124]가 뭐가
되야할지 알 수 있고, 그걸 테이블에 추가한 후 출력한다. 만약 코드[123]이 문자열을 만들어냈다면, 내가 접두사로 찾을 것은,
[...]에서, 그리고 코드[124]란 경우에는, [...]에다가 [...]의 첫 문자를 더하면 된다.
So just add the first character of [...] to the end of itself. Not too bad.
그러니 그냥 [...]의 첫문자만 끝에 추가하면 된다. 별거 아니군.
As an example (and a very common one)
예를 들어보자
of this special case, let's assume we have a raster image in which the
first three pixels have the same color value. That is, my charstream
looks like: QQQ....
3픽셀이 같은 값을 갖고 있는 특수한 경우에 대해서.
문자열로 보면 이렇게 보일 것이다: QQQ...
For the sake of argument, let's say we have 32 colors, and Q is the
color#12. The compressor will generate the code sequence 12,32,....
우리가 32색으로 작업하고 있다고 가정하자. 그리고 Q는 색번호 12번이다.
압축기는 [12],[32] 라는 코드들을 만들어 낼 것이다.
(if you don't know why, take a minute to understand it.) Remember that
(당신이 아직 이유를 모른다해도, 잠깐 생각해보면 이해할 것이다.) 기억하라
#32 is not in the initial table, which goes from #0 to #31. The
[32]란 코드는 초기 테이블, 32색이므로 0~31까지 있는, 에 없다.
decompressor will see #12 and translate it just fine as color Q. Then
압축해제기는 [12]란 코드를 보고 Q로 해석할 것이다.
it will see #32 and not yet know what that means. But if it thinks
그리고는 [32]란 코드를 보게 되는데 아직 그 의미를 모른다.
about it long enough, it can figure out that QQ should be entry#32 in
그러나 잠시 생각해보면, [32]란 코드에 맞는 건 "QQ"밖에 없고
the table and QQ should be the next string output. So the
테이블의 그 자리에 들어갈 것은 QQ이며 출력할 문자열도 그것이 되어야 한다는걸 알아낼 수 있다.
decompression pseudo-code goes something like:
그래서 압축해제 알고리즘은 다음과 같을 것이다...
