{"id":4334,"date":"2013-10-28T21:48:30","date_gmt":"2013-10-28T12:48:30","guid":{"rendered":"http:\/\/umezawa.dyndns.info\/wordpress\/?p=4334"},"modified":"2020-03-16T11:15:59","modified_gmt":"2020-03-16T02:15:59","slug":"%e3%83%8f%e3%83%95%e3%83%9e%e3%83%b3%e3%83%87%e3%82%b3%e3%83%bc%e3%83%89%e3%83%86%e3%83%bc%e3%83%96%e3%83%ab%e3%81%ae%e3%82%b5%e3%82%a4%e3%82%ba%ef%bc%88%e3%81%9d%e3%81%ae%ef%bc%91%ef%bc%89","status":"publish","type":"post","link":"http:\/\/umezawa.dyndns.info\/wordpress\/?p=4334","title":{"rendered":"\u30cf\u30d5\u30de\u30f3\u30c7\u30b3\u30fc\u30c9\u30c6\u30fc\u30d6\u30eb\u306e\u30b5\u30a4\u30ba\uff08\u305d\u306e\uff11\uff09"},"content":{"rendered":"<p>\u5358\u7d14\u306a\u30c6\u30fc\u30d6\u30eb\u53c2\u7167\u3092\u7e70\u308a\u8fd4\u3059\u3053\u3068\u306b\u3088\u308a\u30cf\u30d5\u30de\u30f3\u30c7\u30b3\u30fc\u30c9\u3059\u308b\u5834\u5408\u306e\u30c7\u30b3\u30fc\u30c9\u30c6\u30fc\u30d6\u30eb\u306e\u30b5\u30a4\u30ba\u306b\u3064\u3044\u3066\u8003\u3048\u3066\u307f\u308b\u3002<\/p>\n<p>2014-01-19 \u66f4\u65b0: \u8a3c\u660e\u3092\u8a70\u3081\u3066\u7d50\u8ad6\u304c\u5909\u308f\u308a\u307e\u3057\u305f\u3002<\/p>\n<p><!--more--><\/p>\n<p>\u307e\u305a\u3001\u30cf\u30d5\u30de\u30f3\u7b26\u53f7\u306b\u5bfe\u3059\u308b\u4eee\u5b9a\u306f\u4ee5\u4e0b\u306e\u901a\u308a\u3068\u3059\u308b\uff08Ut Video Codec Suite \u3067\u4f7f\u308f\u308c\u3066\u3044\u308b\u3082\u306e\u3068\u540c\u4e00\uff09<\/p>\n<ul>\n<li>\u30b7\u30f3\u30dc\u30eb\u306f 8bit \u3067\u3042\u308b\u3002\u30b7\u30f3\u30dc\u30eb\u6570 <img src='http:\/\/s0.wp.com\/latex.php?latex=+n+%5Cleq+256+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt=' n \\leq 256 ' title=' n \\leq 256 ' class='latex' \/> \u3067\u3042\u308b\u3002\u5fc5\u305a\u3057\u3082 256 \u3067\u306f\u306a\u3044\u306e\u306f\u3001\u51fa\u73fe\u3057\u306a\u3044\u30b7\u30f3\u30dc\u30eb\u306f\u5b58\u5728\u3057\u306a\u3044\u3082\u306e\u3068\u3057\u3066\u6271\u3046\u304b\u3089\u3067\u3042\u308b\u3002<\/li>\n<li>\u7b26\u53f7\u8a9e\u306e\u9577\u3055\u306e\u4e0a\u9650 <img src='http:\/\/s0.wp.com\/latex.php?latex=+L_%7Bmax%7D+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt=' L_{max} ' title=' L_{max} ' class='latex' \/> \u306f 24 \u3068\u3059\u308b\u3002<\/li>\n<li>\u9577\u3044\u7b26\u53f7\u8a9e\u307b\u3069\u30bc\u30ed\u3067\u59cb\u307e\u308b\u7b26\u53f7\u8a9e\u3092\u5272\u308a\u5f53\u3066\u308b\u3002\u305f\u3068\u3048\u3070\u3001\u7b26\u53f7\u8a9e\u306e\u9577\u3055\u306e\u96c6\u5408\u304c 3, 3, 2, 1 \u306e\u5834\u5408\u3001000, 001, 01, 1 \u3068\u3044\u3046\u7b26\u53f7\u8a9e\u3092\u5272\u308a\u5f53\u3066\u308b\u3002<\/li>\n<\/ul>\n<p>\u305d\u3057\u3066\u4ee5\u4e0b\u306e\u3088\u3046\u306a\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u8003\u3048\u308b\uff08\u3053\u3061\u3089\u306f Ut Video Codec Suite \u3067\u4f7f\u308f\u308c\u3066\u3044\u308b\u3082\u306e\u3068\u306f\u7570\u306a\u308b\uff09<\/p>\n<p>\u7b26\u53f7\u5217\u306e\u5148\u982d\u304b\u3089 m \u30d3\u30c3\u30c8\u898b\u3066\u3001\u305d\u308c\u3067\u30c6\u30fc\u30d6\u30eb\u3092 lookup \u3059\u308b\u3002<\/p>\n<ul>\n<li>\u3082\u3057\u5148\u982d\u306e\u7b26\u53f7\u8a9e\u306e\u9577\u3055\u304c m \u30d3\u30c3\u30c8\u4ee5\u4e0b\u3067\u3042\u3063\u305f\u3089\u3001\u5bfe\u5fdc\u3059\u308b\u30b7\u30f3\u30dc\u30eb\u304c lookup \u306b\u3088\u308a\u5206\u304b\u308b\u305f\u3081\u305d\u3053\u3067\u30c7\u30b3\u30fc\u30c9\u306f\u5b8c\u4e86\u3057\u3001\u6b21\u306e\u30b7\u30f3\u30dc\u30eb\u306b\u79fb\u308b\u3002<\/li>\n<li>\u3082\u3057\u5148\u982d\u306e\u7b26\u53f7\u8a9e\u304c m \u30d3\u30c3\u30c8\u3088\u308a\u9577\u304b\u3063\u305f\u3089\u3001m \u30d3\u30c3\u30c8\u3088\u308a\u9577\u3044\u7b26\u53f7\u8a9e\u306b\u5171\u901a\u306e prefix \u306e\u9577\u3055\u3060\u3051\u8aad\u307f\u98db\u3070\u3057\u3001\u307e\u305f m \u30d3\u30c3\u30c8\u898b\u3066\u65b0\u305f\u306a\u30c6\u30fc\u30d6\u30eb\u3092 lookup \u3059\u308b\u3002\u4ee5\u4e0b\u7e70\u308a\u8fd4\u3057\u3002<\/li>\n<\/ul>\n<p>\u306a\u304a\u3001m = 12 \u3042\u305f\u308a\u3092\u60f3\u5b9a\u3057\u3066\u3044\u308b\u3002<\/p>\n<p>\u3055\u3066\u3001\u7e70\u308a\u8fd4\u3057\u56de\u6570 = \u30c6\u30fc\u30d6\u30eb\u306e\u500b\u6570 \u306e\u4e0a\u9650\uff08\u3042\u308b\u3044\u306f\u4e0a\u754c\uff09\u306f\u3044\u304f\u3064\u304b\u3001\u3068\u3044\u3046\u4e8b\u304c\u6c17\u306b\u306a\u308b\u3002<\/p>\n<ul>\n<li>\u4e0a\u9650\u304c\u5341\u5206\u306b\u5c0f\u3055\u3044\u306e\u3067\u3042\u308c\u3070\u3001\u6700\u521d\u304b\u3089\u305d\u306e\u4e0a\u9650\u56fa\u5b9a\u30b5\u30a4\u30ba\u306e\u69cb\u9020\u4f53\u3092\u4f7f\u3046\u3053\u3068\u304c\u3067\u304d\u308b\u3002<\/li>\n<li>\u4e0a\u9650\u304c\u59a5\u5f53\u306b\u5c0f\u3055\u304f\u5927\u62b5\u306e\u5834\u5408\u306f\u5341\u5206\u306b\u5c0f\u3055\u3044\u306e\u3067\u3042\u308c\u3070\u3001\u3068\u308a\u3042\u3048\u305a\u5c0f\u3055\u3044\u30c6\u30fc\u30d6\u30eb\u3092\u78ba\u4fdd (malloc) \u3057\u3066\u5fc5\u8981\u306b\u5fdc\u3058\u3066\u62e1\u5f35 (realloc) \u3059\u308b\u65b9\u6cd5\u3092\u4f7f\u3046\u3053\u3068\u304c\u3067\u304d\u308b\u3002<\/li>\n<li>\u4e0a\u9650\u304c\u59a5\u5f53\u3067\u306f\u306a\u3044\u5927\u304d\u3055\u306b\u306a\u3063\u3066\u3057\u307e\u3046\u5834\u5408\u3001\u3042\u308b\u3044\u306f\u7e70\u308a\u8fd4\u3057\u56de\u6570\u304c\u6709\u9650\u306b\u306a\u3089\u306a\u3044\u5834\u5408\u306f\u3001\u3053\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u81ea\u4f53\u3092\u3042\u304d\u3089\u3081\u308b\u5fc5\u8981\u304c\u3042\u308b\u3002<\/li>\n<\/ul>\n<p>\u5b9a\u5f0f\u5316<\/p>\n<p><img src='http:\/\/s0.wp.com\/latex.php?latex=+L_i+%280+%5Cleq+i+%3C+n%29+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt=' L_i (0 \\leq i &lt; n) ' title=' L_i (0 \\leq i &lt; n) ' class='latex' \/> \u3092\u5404\u30b7\u30f3\u30dc\u30eb\u306b\u5bfe\u5fdc\u3059\u308b\u7b26\u53f7\u8a9e\u306e\u9577\u3055\u3068\u3059\u308b\u3002 <img src='http:\/\/s0.wp.com\/latex.php?latex=+%5Csum+2%5E%7B-L_i%7D+%3D+1+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt=' \\sum 2^{-L_i} = 1 ' title=' \\sum 2^{-L_i} = 1 ' class='latex' \/> \u3067\u3042\u308b\u3002<\/p>\n<p>m \u30d3\u30c3\u30c8\u3088\u308a\u9577\u3044\u7b26\u53f7\u8a9e\u306b\u5171\u901a\u306e prefix \u306e\u9577\u3055\u304c\u6700\u5927\u306b\u306a\u308b\u3088\u3046\u306b\u7b26\u53f7\u8a9e\u3092\u5272\u308a\u5f53\u3066\u3066\u3044\u308b\u305f\u3081\u3001\u3053\u306e prefix \u306e\u9577\u3055 <img src='http:\/\/s0.wp.com\/latex.php?latex=+Lp+%3D+%5Cleft%5Clfloor+-+%5Clog+%5Csum+%5C%7B+2%5E%7B-L_i%7D+%7C+L_i+%3E+m+%5C%7D+%5Cright%5Crfloor+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt=' Lp = \\left\\lfloor - \\log \\sum \\{ 2^{-L_i} | L_i &gt; m \\} \\right\\rfloor ' title=' Lp = \\left\\lfloor - \\log \\sum \\{ 2^{-L_i} | L_i &gt; m \\} \\right\\rfloor ' class='latex' \/> \u3068\u306a\u308b\u3002<img src='http:\/\/s0.wp.com\/latex.php?latex=+L_i+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt=' L_i ' title=' L_i ' class='latex' \/> \u3082 m \u3082\u6574\u6570\u306a\u306e\u3067\u3001<img src='http:\/\/s0.wp.com\/latex.php?latex=+Lp+%3D+%5Cleft%5Clfloor+-+%5Clog+%5Csum+%5C%7B+2%5E%7B-L_i%7D+%7C+L_i+%5Cgeq+m+%2B+1+%5C%7D+%5Cright%5Crfloor+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt=' Lp = \\left\\lfloor - \\log \\sum \\{ 2^{-L_i} | L_i \\geq m + 1 \\} \\right\\rfloor ' title=' Lp = \\left\\lfloor - \\log \\sum \\{ 2^{-L_i} | L_i \\geq m + 1 \\} \\right\\rfloor ' class='latex' \/> \u3068\u3082\u66f8\u3051\u308b\u3002\uff08\u6ce8\uff1a\u60c5\u5831\u79d1\u5b66\u306e\u5206\u91ce\u306a\u306e\u3067\u5358\u306b log \u3068\u66f8\u3044\u305f\u3089\u5e95\u306f2\u3067\u3042\u308b\uff09<\/p>\n<p><img src='http:\/\/s0.wp.com\/latex.php?latex=+%5Csum+%5C%7B+2%5E%7B-L_i%7D+%7C+L_i+%5Cgeq+m+%2B+1+%5C%7D+%3C+n+2%5E%7B-%28m+%2B+1%29%7D+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt=' \\sum \\{ 2^{-L_i} | L_i \\geq m + 1 \\} &lt; n 2^{-(m + 1)} ' title=' \\sum \\{ 2^{-L_i} | L_i \\geq m + 1 \\} &lt; n 2^{-(m + 1)} ' class='latex' \/> \u306a\u306e\u3067\u3001<img src='http:\/\/s0.wp.com\/latex.php?latex=+-+%5Clog+%5Csum+%5C%7B+2%5E%7B-L_i%7D+%7C+L_i+%5Cgeq+m+%2B+1+%5C%7D+%3E+-+%5Clog+n+2%5E%7B-%28m+%2B+1%29%7D+%3D+m+%2B+1+-+%5Clog+n+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt=' - \\log \\sum \\{ 2^{-L_i} | L_i \\geq m + 1 \\} &gt; - \\log n 2^{-(m + 1)} = m + 1 - \\log n ' title=' - \\log \\sum \\{ 2^{-L_i} | L_i \\geq m + 1 \\} &gt; - \\log n 2^{-(m + 1)} = m + 1 - \\log n ' class='latex' \/> \u3067\u3042\u308b\u3002\u3064\u307e\u308a\u3001<img src='http:\/\/s0.wp.com\/latex.php?latex=+Lp+%3E+%5Cleft%5Clfloor+m+%2B+1+-+%5Clog+n+%5Cright%5Crfloor+%3D+m+%2B+1+-+%5Cleft%5Clceil+%5Clog+n+%5Cright%5Crceil+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt=' Lp &gt; \\left\\lfloor m + 1 - \\log n \\right\\rfloor = m + 1 - \\left\\lceil \\log n \\right\\rceil ' title=' Lp &gt; \\left\\lfloor m + 1 - \\log n \\right\\rfloor = m + 1 - \\left\\lceil \\log n \\right\\rceil ' class='latex' \/> \u3067\u3042\u308b\u3002<\/p>\n<p>\u306a\u304a\u3001\u65e2\u306b lookup \u3092\u7e70\u308a\u8fd4\u3057\u3066 q \u30d3\u30c3\u30c8\u8aad\u307f\u98db\u3070\u3057\u3066\u3044\u308b\u72b6\u614b\u306b\u3042\u308b\u5834\u5408\u3001\u300cq + m \u30d3\u30c3\u30c8\u3088\u308a\u9577\u3044\u7b26\u53f7\u8a9e\u306b\uff5e\u300d\u3068\u306a\u308b\u304c\u3001\u305d\u306e\u5834\u5408 <img src='http:\/\/s0.wp.com\/latex.php?latex=+Lp+%3E+q+%2B+m+%2B+1+-+%5Cleft%5Clceil+%5Clog+n+%5Cright%5Crceil+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt=' Lp &gt; q + m + 1 - \\left\\lceil \\log n \\right\\rceil ' title=' Lp &gt; q + m + 1 - \\left\\lceil \\log n \\right\\rceil ' class='latex' \/> \u306b\u306a\u308b\u306e\u3067\u3001\u8ffd\u52a0\u3067\u8aad\u307f\u98db\u3070\u3059\u30d3\u30c3\u30c8\u6570\u306e\u4e0b\u754c\u306f\u540c\u3058\u5f0f\u3067\u8868\u3059\u3053\u3068\u304c\u3067\u304d\u308b\u3002<\/p>\n<p>\u4eca\u3001<img src='http:\/\/s0.wp.com\/latex.php?latex=+n+%5Cleq+256%2C+m+%3D+12+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt=' n \\leq 256, m = 12 ' title=' n \\leq 256, m = 12 ' class='latex' \/> \u3092\u60f3\u5b9a\u3057\u3066\u3044\u308b\u306e\u3067 <img src='http:\/\/s0.wp.com\/latex.php?latex=+Lp+%3E+12+%2B+1+-+%5Cleft%5Clceil+%5Clog+256+%5Cright%5Crceil+%3D+5+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt=' Lp &gt; 12 + 1 - \\left\\lceil \\log 256 \\right\\rceil = 5 ' title=' Lp &gt; 12 + 1 - \\left\\lceil \\log 256 \\right\\rceil = 5 ' class='latex' \/> \u3064\u307e\u308a <img src='http:\/\/s0.wp.com\/latex.php?latex=+Lp+%5Cgeq+6+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt=' Lp \\geq 6 ' title=' Lp \\geq 6 ' class='latex' \/> \u3067\u3042\u308b\u3002 <img src='http:\/\/s0.wp.com\/latex.php?latex=+L_%7Bmax%7D+%3D+24+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt=' L_{max} = 24 ' title=' L_{max} = 24 ' class='latex' \/> \u306a\u306e\u3067 <img src='http:\/\/s0.wp.com\/latex.php?latex=+%5Cleft%5Clceil+%2824+-+12%29+%2F+6+%5Cright%5Crceil+%2B+1+%3D+3+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt=' \\left\\lceil (24 - 12) \/ 6 \\right\\rceil + 1 = 3 ' title=' \\left\\lceil (24 - 12) \/ 6 \\right\\rceil + 1 = 3 ' class='latex' \/> \u304c\u30c6\u30fc\u30d6\u30eb\u6570\u306e\u4e0a\u754c\u3068\u306a\u308b\u3002<\/p>\n<p>\u306a\u304a\u30018bit \u30b7\u30f3\u30dc\u30eb, m=12 \u3067\u30c6\u30fc\u30d6\u30eb\u65703\u3060\u3068\u30c6\u30fc\u30d6\u30eb\u30b5\u30a4\u30ba\u306f 2^12 * 2 * 3 = 24KB \u3068\u306a\u3063\u3066\u3001\u6700\u8fd1\u306e Intel CPU \u306e1\u6b21\u30ad\u30e3\u30c3\u30b7\u30e5\u306e\u30b5\u30a4\u30ba\u306b\u8fd1\u304f\u306a\u308b\u3002\u3057\u304b\u3057\u3001\u307b\u3068\u3093\u3069\u306e\u5834\u5408\u306f\u6700\u521d\u306e\u30c6\u30fc\u30d6\u30eb\u3060\u3051\u306b\u30a2\u30af\u30bb\u30b9\u3057\u3001\u5f8c\u308d\u306e\u30c6\u30fc\u30d6\u30eb\u307b\u3069\u30a2\u30af\u30bb\u30b9\u3055\u308c\u308b\u78ba\u7387\u304c\u6975\u7aef\u306b\u5c0f\u3055\u304f\u306a\u308b\u305f\u3081\u3001\u30c7\u30b3\u30fc\u30c9\u30c6\u30fc\u30d6\u30eb\u306b\u3088\u3063\u3066\u30ad\u30e3\u30c3\u30b7\u30e5\u304c\u5727\u8feb\u3055\u308c\u308b\u5fc3\u914d\u306f\u3057\u306a\u304f\u3066\u3088\u3044\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u5358\u7d14\u306a\u30c6\u30fc\u30d6\u30eb\u53c2\u7167\u3092\u7e70\u308a\u8fd4\u3059\u3053\u3068\u306b\u3088\u308a\u30cf\u30d5\u30de\u30f3\u30c7\u30b3\u30fc\u30c9\u3059\u308b\u5834\u5408\u306e\u30c7\u30b3\u30fc\u30c9\u30c6\u30fc\u30d6\u30eb\u306e\u30b5\u30a4\u30ba\u306b\u3064\u3044\u3066\u8003\u3048\u3066\u307f\u308b\u3002 2014-01-19 \u66f4\u65b0: \u8a3c\u660e\u3092\u8a70\u3081\u3066\u7d50\u8ad6\u304c\u5909\u308f\u308a\u307e\u3057\u305f\u3002<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[27],"tags":[],"class_list":["post-4334","post","type-post","status-publish","format-standard","hentry","category-technology"],"_links":{"self":[{"href":"http:\/\/umezawa.dyndns.info\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/4334","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/umezawa.dyndns.info\/wordpress\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/umezawa.dyndns.info\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/umezawa.dyndns.info\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/umezawa.dyndns.info\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4334"}],"version-history":[{"count":23,"href":"http:\/\/umezawa.dyndns.info\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/4334\/revisions"}],"predecessor-version":[{"id":7470,"href":"http:\/\/umezawa.dyndns.info\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/4334\/revisions\/7470"}],"wp:attachment":[{"href":"http:\/\/umezawa.dyndns.info\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4334"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/umezawa.dyndns.info\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4334"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/umezawa.dyndns.info\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4334"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}