Yokohama Compression Mystery Cache
Please note Use of geocaching.com services is subject to the terms and conditions
in our disclaimer.
The cache is not at the coods above. The coods above is a factory of compressing (recycling) plastic waste of Yokohama City. On the factory, plastic waste is recycled as fuel (added when iron making) and burned, not recycled as plastic. Did you know?
キャッシュは表記の座標にはありません。表記の座標は、横浜市のプラスチックゴミ圧縮 (リサイクル) 工場です。この工場でリサイクルされたプラスチックは燃料にリサイクルされ、製鉄のとき加えられたりして燃やされます。プラスチックにリサイクルされるわけではないんですね。ご存知でしたか?
Data compression is the basic and essential technology for efficient data communication. Other than obvious coding methods such as MPEG (MP3)/JPEG, many data compression technologies are used at parts of communication channel in the world.
データ圧縮は通信を効率化するためになくてはならない技術です。MPEG (MP3)/JPEGといった、我々が直接意識して利用するところ以外にも、通信経路の送受信端で圧縮・伸張が行なわれていたりします。
MPEG/JPEG coding methods belong to "lossy" compression which discard meaningless information for human beings. Today let's study about "lossless" coding methods on which the compressed data can be decoded to the original data perfectly. They are used for compressing texts/data/programs/etc.
MPEG/JPEGなどは『人間にとって意味のない情報は多少捨てて高圧縮率を得る』非可逆圧縮という方式ですが、今日は『伸張すると完全にデータが元に戻る』可逆圧縮についてお勉強しましょう。1ビットでも違ってしまったら困る、テキスト・データ・プログラムなどの圧縮に用いられます。
The basic of the data compression is "shorter codeword for frequent symbol." For example, let's think about sending 4 symbols A/B/C/D. If we assign equal length codewords
圧縮の基本原理は、『よく出てくるものは短くして送る』ということです。例えばA、B、C、Dの4種類の文字を送るのに
A=00 B=01 C=10 D=11
then a message "ACCBAAACDCAAAB" (15 symbols) will be encoded to 30 bits of codewords. If we assign
としたら、文字列『AACCBAAACDCAAAB』の15文字を送るのに30ビット必要ですね。ところが
A=0 B=110 C=10 D=111
then the encoded message will be "0 0 10 10 110 0 0 0 10 111 10 0 0 0 110" (25 bits). For your convenience spaces are inserted but there're no spaces in actual encoded message. A receiver can decode certainly if he/she read consequently from the top of the message. Now we can save 1/6 of the time, or telephone fee.
として送ったら、『0 0 10 10 110 0 0 0 10 111 10 0 0 0 110』という25ビットで済みます。ここでは読みやすいようにスペースを空けてあります。実際の通信には切れ目はありませんが、頭から読んでいけば元通り復号できます。電話代・時間が1/6ほど節約できたことになります。
With the huffman coding method, we can design the optimal block code (shortest codewords) if the probability of appearance of each symbol is known in advance.
ハフマン符号化法は、各記号が出てくる確率があらかじめ分かっているとき、理論的に最適なブロック符号 (最短の符号語になるような符号語を割り当てる) の設計方法です。
By the way, the cache location and note are in the following message.
ところでキャッシュの座標と注意書きは下のメッセージの通りです。
10010111 01000000 01001000 00000111 11001010 00000110 00001000 01111000
10100000 00100101 10000101 11101000 00010011 10000011 11100000 10000001
10000101 00111101 01110011 11010100 00101101 11011111 00101110 10000110
01110111 11001001 01110010 10100001 01101110 11000010 01100111 00110010
10000001 11100000 10010100 00000100 10111100 00010110 00011101 00000001
00001111 10000010 01010000 00010010 11110000 11000001 00101111 10010111
01000011 00111011 11000001 01001010 00000010 00011000 00111101 10000100
10111000 00001000 01111100 00110000 01001011 11001111 01010000 10110111
01111000 00100101 00000001 00101111 10010010 11100101 01000010 11011101
10000100 11100101 10000110 01100000 00101110 00011000 00100101 11100000
10110000 11101000 00001000 01111100 11110101 00001011 01110111 11001011
10100001 10011101 11100001 00101000 01100100 11000001 01001010 00000010
00011000 00111101 10000100 00111101 01101111 10010100 00001100 00010000
11110001 01000000 01001011 00001011 11010000 00100111 00000111 11101011
01001001 01011010 11100000 10110000 01110001 00101001 01110100 10010111
10011011 00001100 11000111 00000001 01101111 00000100 00001100 11111000
01000000 11110011 11000000 00110000 01111000 00101100 00101101 10000010
11100000 00101101 11100001 00001111 01001001 01000000 00110000 11000010
11100001 01101110 00100101 00101011 01100001 01
This is encoded by a huffman code designed for the symbols with following probability of appearance (i.e. original message consists of 0-9).
このメッセージは、下記の確率で記号が出てくる通信文のために設計したハフマン符号で符号化しました (つまり原文は0-9のシンボルで出来ています)。
0: 0.407
1: 0.193
2: 0.078
3: 0.018
4: 0.051
5: 0.107
6: 0.024
7: 0.007
8: 0.052
9: 0.063
Here I assigned "0" to the branch of higher probability. You also design the same huffman code from the probability table above, and decode the message above.
ただし確率が高い枝に0を割り当てるように設計しています。この確率表から符号を設計して、上記のメッセージを復号してください。
You can check your answers for this puzzle on Geochecker.com (visit link)
*sorry the check coords was wrong until Jul. 1st, 2010.
Additional Hints
(No hints available.)
Treasures
You'll collect a digital Treasure from one of these collections when you find and log this geocache:
Loading Treasures