ふと気になったので、調べ物をお願いします。
圧縮されたデータを対象に検索を行うアルゴリズムで
下記のようなもので、目ぼしい成果を上げているものを探してください。
（人力検索としては、次の類似を検索する形になります。）
[PPT] 高速検索可能なテキスト圧縮法に関する研究
（復号処理を行わずに高速に検索を行う圧縮法の研究）
www.tkl.iis.u-tokyo.ac.jp/~otsuka/profile/kenkyu3.ppt
くどく補足しますが、「検索インデックスを圧縮することにより高速に検索が行えるようになりました」という種類のものを紹介する回答は不要です。
「gzipで圧縮されたファイルを、自動的に解凍して検索できます」という類のソフトの紹介も不要です。
上に挙げたものそのものも不要です。
※ 探すのは難しいかもしれません。
訳も判らず【不要な回答】をしていただいた方は０ｐｔです。
(〓さんとか)怪しいところは既に切ってありますが、あまりに明白な粗悪回答をしていてくれた方については回答拒否のフラグを立てておきます。
No.2
562
71
100pt
1.の様な回答が付かなければ静観するつもりでしたが……。
このgoogle検索で結構ヒットします。もちろん英語論文ですが。
ほとんどabstractぐらいしか見られませんが、その内容をざっと読んでみると基本的な考えは共通している様に思われます。
つまり、テキストを圧縮するのに使う、もしくはテキストを圧縮している過程で構築される辞書データをそのまま検索に使ってしまえ、というアイデアです。
With the explosive growth in content, Internet and Intranet information repositories require efficient mechanisms to store as well as index data.
コンテンツが爆発的に増えるにしたがって、インターネットやイントラネット上の情報をインデクス化して効率的に格納するメカニズムが必要になってきました。
In this paper we discuss the implementation of the Shrink and Search Engine (SASE) framework which unites text compression and indexing to maximize keyword search performance while reducing storage cost.
本論ではストレージコストを減らしつつ、キーワード検索のパフォーマンスを最大限にする様な、テキストの圧縮とインデクス化を統合する方法について論じます。
中身は判りませんが、全文検索用のインデクス作成の過程で、ついでにファイルを圧縮してしまおうというアイデアの様です。(質問とは真逆の考え方かもしれませんが)
http://citeseer.ist.psu.edu/551537.html
Direct Pattern Matching on Compressed Text - de Moura, Navarro, Ziviani, Baeza-Yates (ResearchIndex)
uses a semi-static word-based modeling and a Huffman coding
という箇所が見られますね。
ハフマン符号化に使う、データ-符号の割り当てについて、半分静的な(semi-static)辞書を使う、とあります。
辞書を静的に持ってしまえば、その辞書にある単語を検索するのにデコードが不要だということでしょう
http://portal.acm.org/citation.cfm?id=967612
Regular expression searching on compressed text
Ziv-Lempel LZ78 LZW などの符号化による圧縮されたファイルについて、正規表現による検索を解凍無しでおこなう手法。
具体的には書いていませんが、いずれの圧縮も圧縮の過程でデータの内容から圧縮のための符号化辞書を作っていくアルゴリズムです。
それを利用して検索する手法と思われます。
符号化についての説明のページを最後に。
やはりWebで簡単に検索できるのは論文のabstraactぐらいの様で概要しかわからないという感じでした。
ご回答有難うございます。
> やはりWebで簡単に検索できるのは論文のabstractぐらいの様で概要しかわからないという感じでした。
いえ、Webで分かる情報で結構です。
------------------------------------
Regular expression searching on compressed text
テキスト長：u
圧縮後のテキスト長：n
パタン長：m
テキスト中のパタン出現回数：R
最悪時間計算量：O(2^m + mn + Rm log m)
平均計算時間量（実験値？）：
O(m^2 + (n + Rm) log m)
もしくは
O(m^2 + n + Ru/n)
提案手法は、「解凍＋検索」の半分の時間の所要となった。
------------------------------------
O記法でしか書いていないのがビミョーだと感じますが、適当な事を書くと、
・m^2は、NFA->DFAの変換時間。
・Rが入っている項は、パタンにマッチした場合のコスト。
・残りが、パタンにマッチしなかった場合のコスト。
・「Ru/n」（パタン出現回数÷圧縮率）と書いてあるのが釈然と
しないのですが、パタンにマッチした場合のコストは、マッチ
しなかった場合のコストより強く効く（係数が大きい）などするので、
見かけ上、u/n 倍の係数が入る感じですかね。
「提案手法での検索時間は圧縮後の文字列長に比例する」という主張を
しているのかどうか分からないですがO記法の法からはそう見えます。
もちろん、圧縮前のパタン長と圧縮後のパタン長は比例する罠がある
かもしれませんが。
「解凍＋検索より短い時間で出来た」という報告が、情報量のあるところだと思います。
ふと思いついて気になっていた疑問がおおよそ解消いたしました。
大変有難うございました。
2
1
1
1
1
28
27
ご回答有難うございます。
> データベースなのでまったくインデックスを作成しないわけではありませんが
ちょっと待て。
なぜここで、RDBのインデックス作成の話になる？
データ圧縮で、
http://fw8.bookpark.ne.jp/cm/ipsj/search.asp?flag=6&keyword=...
みたいな話をするのは、質問の主旨から外れています。
ご回答URLを大まかに読んだのですが、要は、相坂ら(1999)をGAでやってみました、という話ですよね。
「データベース圧縮」という話を誰が提案したのかは不勉強にして知りませんが、いわゆるデータ圧縮と違う話ですよね、OKです？
実に微妙で果敢な回答ですが、とりあえず、もうちょっとROMってから回答してくれたほうが有難かったかもしれません。
求めるものとは違いました。回答は継続して募集いたします。