5TBのテキストから任意の文字列のoffset取得

企業の面談のさいに出た問題ですが、わからなかったのでご教示いただければと思います。
※プログラミングもそうですが、構成についても問われている問題とのことです。


5TBのテキストデータから任意の文字列のoffset取得したい。
strpos等の関数を用いず、取得するにはどうすればよいか？効率的な方法を答えよ。

言語はPerlかPHPです。
単純にfgetをforで回す方法しか思いつきませんがこの規模のデータでは効率的でない気がします。

ご指導の程よろしくお願い致します。

No.4 ベストアンサー 回答者： mokokomi 回答日時： 2011/01/19 18:16

> strpos等の関数を用いず...

というのがよくわかりませんが。

大まかな方針としては、以下のことがあてはまりそうです:

● 一回限りの検索で、かつ時間がかかっても良い => grepで工夫すれば事足りそうです。
● そうではなく、なんども検索する処理で、リアルタイムでそれなりにスループットが必要 => 全文検索エンジンを作る or 利用する
● バッチ処理でいい => HadoopとかのMapReduceを使う。

具体的な事は検索してみてください（丸投げすいません）。
全文検索エンジンについては N-Gram、形態素解析、転置インデックス、SuffixArray などのキーワードで検索するとよいかもです。

この回答へのお礼

ありがとうございます。
いろいろ自分でも考えてみたのですが、面接官はmokokomiさんが上げてくださったような答えを期待していたのかもしれません。

明確な答えではなく、どうやって解決するか・できるかの能力を見たかったではないかと思ってきました。


具体名までお教えいただきありがとうございます。
調べてみます。

お礼日時：2011/01/21 13:33

No.3 回答者： shiren2 回答日時： 2011/01/19 15:49

ANo. 1です。

＞5TBのテキストはどういったフォーマットで
このフォーマットは、テキストの格納形式のことです。
簡単な例では、巨大なファイルは固定長レコードで記録されているかもしれません。
あるいは二分探索が有効な形式かもしれません。

ファイルシステムのフォーマットは、今回の問題ではあまり関係ないですね。
誤解を招く書き込みで申し訳ありませんでした。

この回答へのお礼

ありがとうございます。
ファイルフォーマットと勘違いしておりました。
二分探索調べてみます。

お礼日時：2011/01/21 13:30

No.2 回答者： yuu_x 回答日時： 2011/01/18 23:08

取り込めるだけ取り込んで、ランダム検索辺り。

ついでに、 T（テラ）の場合 int の範囲を超えるので、GMP ライブラリ を使うなど。

この回答へのお礼

回答いただきありがとうございます。

GMPライブラリというものがあることは知りませんでした。
この質問の解となるヒントが含まれているかもしれません。
調べてみます。

お礼日時：2011/01/19 15:16

No.1 回答者： shiren2 回答日時： 2011/01/17 17:19

これは字句通りの問題なのでしょうか。

効率的もなにも、5TBのフォーマットすらわからない状況では逐次探索するほかありません。

これは恐らく、要件定義が出来るかを確認しているのだと思います。
もしそうなら、正しい答えは「5TBのテキストはどういったフォーマットで格納されていますか」と先方にきちんと尋ねることですね。

フォーマットを確認するまでが一次試験。
フォーマットを確認後、最適なアルゴリズムを答えることが二次試験。
そんなところではないでしょうか。
あくまでも私の考えですが…。

この回答へのお礼

回答いただきありがとうございます。
期待していた答えとしてはそのようなものだったのかもしれません。

仮にext2フォーマットだった場合、どのようなアルゴリズムが考えられるでしょうか？

お礼日時：2011/01/19 15:14