2005-12-04 圧縮されたデータから検索 [長年日記]
■少佐とバトーじゃん
一瞬取り乱してしまいました。
子供と一緒にマジレンジャーを見たらゴーゴンとダゴンの声が……。
■圧縮されたデータから検索
圧縮されたデータを対象に検索を行うアルゴリズムで
下記のようなもので、目ぼしい成果を上げているものを探してください。
http://www.hatena.ne.jp/1133642504
そんなことできるんかいな?
圧縮したらデータの大きさあたりの情報量が上がるわけで、ま、要するにデータがランダムに近づく――エントロピーが増大する。
圧縮データのまま検索可能だとしたら元のデータの特徴が残ったままだということで、それじゃ圧縮アルゴリズムとしては下だよなぁ。
などと思って、URLを見てみたら「高速検索可能なテキスト圧縮法」だった。
あ、なるほど。
追記
上の「エントロピーが増大する」は誤解があったか。詳細は
を読んでもらうとして、「データの量(≠情報量)あたりのエントロピーが増大する」と書くべきだったかしらん。ま、その前に「データの大きさあたりの情報量が上がる」とも書いておいたから杞憂だったか。どうだろう?
質問の「検索インデックスを圧縮することにより高速に検索が行えるようになりました」の意味が実は判らん。