文字列の検索高速化について

大容量の文字列から文字列を検索するのに四苦八苦しております。
現在は文字列を構造体→メモリを確保でなんとかやっておりますが、データの容量が大きい為、時間が掛かりすぎてしまいます。

データ 70文字×30000行程度（行数可変）の文字列ファイル（すべて半角英数）

検索する側、検索される側共に同じファイルを使用します。
検索する側から一行ずつ文字列を取得→特定のカラムから文字列を抜き出す→検索される側からヒットした行を抜き出す→別処理を行う
（検索に使用した行はスルー、検索される側には検索文字列が複数存在する可能性あり→すべて抜き出したい）

また、抜き出した行は検索する側、される側共に次以降二重処理して速度が遅くなってしまうかと思うので、できれば削除したい。（現在は二重処理も致仕方ないとしてそのままやっています）

過去ログを読むとハッシュテーブルが良いかと言われていますが、このような場合はどのようなアルゴリズムが良いのでしょうか。
質問がわかりずらく申し訳ないですが、アドバイスを頂ければと思います。
また、使用方法等が詳しく記載されているページ等がありましたら教えて頂ければ幸いです。

No.4 回答者： fonera 回答日時： 2008/02/04 13:03

恐れ入ります。

データサイズに変更がない場合は、固定長のメモリを確保するのが良いと思います。
今回のデータが、「常に3万行」なのか「3万行程度」なのか判りませんので、動的メモリ割当を想定しました。

>p = 新しくメモリを確保する;
>↑この場合どのようにメモリを確保したらよいでしょうか。
>（mallocを使用するのでしょうか？）

はい。mallocを使います。通常は以下のように書くと思います。
p = (struct node *) malloc(sizeof(struct node));



>for (ファイルの終わりまで） {
>要素を1つ読み出す;
>element = create_hash(element, 読み出した要素, 読み出した行);
>}
>
>↑ここをもう少し詳しくお願いできませんでしょうか。
>（日本語部分）

できません。データの形式が不明だからです。
# No.1の方の補足にソースを開示しておられますが、char[75]を抱える単方向リンクリストにしか見えません。
# 単方向リンクリストは挿入削除が高速なのが利点で、検索の高速性とは無関係な為、今回の質問と関連があるか判らない。
データの形式が不明な為、回答できません。
・カンマ区切りなのか、タブ区切りなのか、ハイフン区切りなのか
・リンクリストに入れて、他に処理を行うのか
・質問に書かれていない処理が別途入り、検索自体は数値で行っているのか
・メモリをどの程度まで使用して良いのか


なにをするどんなプログラムなのかを詳らかにしていただくか、
一切手を加えてないデータ（ダミーデータでも形式・数値範囲があっているもの）と
検索過程にに入る処理ＡＰＩ全てをお教え願えないと、回答が難しいです。
# アルゴリズムでなく、コーディングレベルの回答をしなければならない為。


# （個人的には）要素を単純に一つづつ読み出しているだけなので、
# 現在お使いのソースを変更するだけで対処できるものかとは思いますが・・・


以上、ご参考になれば幸いです。

No.3 回答者： fonera 回答日時： 2008/01/31 18:08

恐れ入ります。

条件が明確でないため、参考になるか判りませんが、現時点での情報から回答いたします。
# この手の問題は、アルゴリズムではなく設計が問題だったりする為。


C4-------$79------A1------20----3030----2099
C4-------$80------A1-------1------12----1117
C4-------$62------A1----3030----3031----1802
C4-------$82------A1----1139----3023----1109
C4-------$83------A1----1803----1802----3031
C4-------$32------B1----1582-------1----3030
C4-------$85------B1----1109----1114----1117

上記データでの処理を書き出すと、以下の流れであっていますか？

1. 1行, 4要素[20]で検索する。
2. 1行, 5要素[3030]で検索する。
3. 3行, 4要素でヒット。3行目を別処理へ。
4. 6行, 6要素でヒット。6行目を別処理へ。
5. 1行, 6要素[2099]で検索する。
6. 2行, 4要素[1]で検索する
7. 6行, 5要素でヒット。6行目を別処理へ。
8. 2行, 5要素[12]で検索する
(中略)

・3行, 4要素の[3030]や、6行, 5要素[1]では、検索しない。 （一度検索しているから）
・別処理を行った、3行目も、検索元になる。（3行, 5要素の[3031]では検索する）


上記の処理であっており、前処理が可能であるという前提でお話しします。
# 3万行x3要素を、3万行x3要素全てに対してチェックしている = 81億回のチェックを行っている

まず、検索元数字は行数に関係なく処理を行っているので、まとめられます。また、二度同じ数字で検索を書けないのでそこも削れます。

＜最も簡単な手法＞
例えば4, 5, 6要素に現れる数字が1～9999なのであれば9999個の変数を用意することで無駄を省けます。

int element[10000];

elementに、全て0を代入する。
for (ファイルの終わりまで） {
要素を1つ読み出す;
element[読み出した要素] = 1;
}

for (i = 1; i < 10000; i++) {
for (ファイルの終わりまで) {
要素を1つ読み出す;
if (element[i] == 読み出した要素) {その行を別処理へ;}
}
}
↑のソースは、要素を全部で9億回読み取っています。81億回→9億回の読み取り回数になりました。
# 処理内容が変わったので、処理時間が20%になったりはしませんが。


＜多少面倒な方法＞
ハッシュを使います。

struct node {
int number;
int line_number;
struct node *same_number;
struct node *next_number;
};

create_hash(struct node *p, read_number, read_line) {
if (p == NULL) {
p = 新しくメモリを確保する;
p->number = read_number;
p->line_number = read_line;
p->same_number = p->next_number = NULL;
} else if (p->number == read_number) {
create_hash(p->same_number, read_number, read_line);
} else {
create_hash(p->next_number, read_number, read_line);
}
}
}


main() {
struct node *element;
element = NULL

for (ファイルの終わりまで） {
要素を1つ読み出す;
element = create_hash(element, 読み出した要素, 読み出した行);
}
for (ファイルの終わりまで） {
要素を1つ読み出す;
ハッシュのp->numberが一致したら、p->same_numberがNULLになるまでp->line_numberを読み取り続ける
読み取ったline_numberは、別処理へ
}
}

↑のソースでは、ハッシュテーブルを作るのに9万回、行列を調べるのに9万回、併せて18万回要素を読み取っています。
81億回→18万回の読み取り回数です。
# 実はハッシュテーブルの検索に時間がかかるので、処理時間が0.002%になったりはしませんが。

以上、ご参考になれば幸いです。

この回答への補足

ご返事ありがとうございます。

p = 新しくメモリを確保する;
↑この場合どのようにメモリを確保したらよいでしょうか。
（mallocを使用するのでしょうか？）

for (ファイルの終わりまで） {
要素を1つ読み出す;
element = create_hash(element, 読み出した要素, 読み出した行);
}

↑ここをもう少し詳しくお願いできませんでしょうか。
（日本語部分）

だいたいのことは理解いたしました。
もう少し教えて頂ければ幸いです。
宜しくお願いします。

補足日時：2008/02/01 14:28

No.2 回答者： fonera 回答日時： 2008/01/31 15:23

恐れ入ります。

データの検索方法について確認させてください。

>また、検索文字列は行ごとというわけではなく例えば
>検索文字列 "67891"
>aaa 123456 67892 23456 bbb ccc
>aaa 123456 67891 23456 bbb ccc
>aaa 123456 67832 23456 bbb ccc
>（二行目だけを抽出したい）
この場合、例えば「123456」を抜き出す可能性はありますか？
つまり、検索対象は特定の列のみですか？（例では、３列目）

特定の列のみであれば、ソートしてから検索することで高速化が可能です。また削除してしまっても問題ありません。

特定の列ではなく、例えば
>aaa 123456 67892 23456 bbb ccc
>aab 123457 67891 23457 bbc ccd
>aac 123458 67832 23458 bbd cce
の様なデータがあったときに、
・1回目は、[67892]を検索する
・2回目は、[bbc]を検索する
このような処理を行いたい場合は、技術的には一工夫必要です。
ダミーのデータでも良いので、処理対象のデータと実際の検索手順を提示していただけませんでしょうか？
（例えば、処理順序が重要な場合は検索元データはソートできませんし、抜き出した後の別処理に必要なデータが限定されていれば削れますし、検索ヒット率が低ければメモリに載せる必要もなかったりします）

この回答への補足

ご返信ありがとうございます。
具体的なというか使用する方法をそのままご説明させて頂きます。

C4-------$79------A1------20----3030----2099
C4-------$80------A1-------1------12----1117
C4-------$62------A1----3030----3031----1802
C4-------$82------A1----1139----3023----1109
C4-------$83------A1----1803----1802----3031
C4-------$32------B1----1582-------1----3030
C4-------$85------B1----1109----1114----1117

というような文字列が30000行あります。（データはそのまま使ってます）
(-はブランクを意味します)
最初に一行目を取り出し、４番目の要素（------20）を同じファイル内で検索無ければ５番目の要素（----3030）を検索
三行目と四行目がヒットしたらその行を抜き出し、別の処理を行う
六番目の要素を検索し同様の手順を行う
これを二行目の４、５、６要素の検索、三行目の４、５、６要素の検索とループさせています。
ブランクを含めた数字のみの検索を行うので、４、５、６要素以外にはヒットしないようになっています。

これでうまく説明になったでしょうか・・・
ご教示宜しくお願いします。

補足日時：2008/01/31 15:57

No.1 回答者： Oh-Orange 回答日時： 2008/01/31 13:16

★アドバイス

＞現在は文字列を構造体→メモリを確保でなんとかやっておりますが、
＞データの容量が大きい為、時間が掛かりすぎてしまいます。
　↑
　どの程度でしょうか？
　ファイルをメモリと同じように扱える方法があります。
　『メモリ・マップド・ファイル』です。
　http://marupeke296.com/DXCLS_MemoryMappedFile.html→『メモリマップドファイルクラス』
　これが利用できる場合はメモリを確保してセットしない分高速になると思います。
＞また、抜き出した行は検索する側、される側共に次以降二重処理して速度が
＞遅くなってしまうかと思うので、できれば削除したい。
＞（現在は二重処理も致仕方ないとしてそのままやっています）
　↑
　１行あたり１ビットのフラグで処理したら『1』とチェックします。
　行数が30,000ですから3,750バイトで済みます。
　抽出処理するときにはこのフラグを見て『0』の行だけを処理します。
　これで重複処理を避けられます。
＞検索する側から一行ずつ文字列を取得
＞→特定のカラムから文字列を抜き出す
＞→検索される側からヒットした行を抜き出す
＞→別処理を行う
　↑
　良く理解できていないと思いますが、膨大な文字列データから複数の文字列を一度に
　検索して取り出したいのですか？
・過去に複数文字列の一括置換プログラムを作成したときの考えを書きます。
　(1)置換する(検索)文字列をソートしてリスト化します。
　(2)検索する(対象)文字列から行単位で検索を開始。
　　(a)行の１桁目から順番にリスト化したデータをバイナリーサーチ＆リニアサーチ。
　　(b)リスト化したデータの長さより本当に一致したかを調査。
　　(c)一致したら抽出。
　　(d)次の桁に移動して(a)に戻る。行の末尾で終了。
　(3)抽出処理した行はフラグを『1』にチェック。
　(4)次の行へ移動して(2)に戻る。膨大な文字列データの最後に来たら全処理終了。
　※上記は置換ですが抽出(検索)も同じ考えていけると思います。
　※置換をしないで抽出すれば良いだけなので。
　上記の方法でそこそこ高速化できます。
　でも、もっと改良する余地がありそうです。
　※私の場合、これ以上の工夫はしませんでした。(笑)
・上記の置換する(検索)文字列をソートしてリスト化するときに、(検索)文字列の長さも管理します。
　それから(a)のバイナリーサーチ＆リニアサーチは
　(1)最初はバイナリーサーチします。このときにリスト化のデータ長で比較(strncmpなどで)
　(2)続いてリニアサーチします。
　　これは『abc』『abcd』『abcdef』が(検索)文字列だった場合に一番長い『abcdef』に
　　一致させるために必要です。
・説明不十分と思いますので補足などをどうぞ。

この回答への補足

ご返信ありがとうございます。
イメージ的には理解することができました。
何点か補足させて頂きます。

>現在は文字列を構造体→メモリを確保でなんとかやっておりますが、
>データの容量が大きい為、時間が掛かりすぎてしまいます。
>　↑
>　どの程度でしょうか？
struct list {
struct list *next;
char *str;
};
struct list *next;
struct list *charstr;
struct list *top = NULL;
char Buff[75]
while (fgets(Buff, 71, "ファイル") != NULL) {
charstr = malloc(sizeof(struct list));
charstr->str = (char*)malloc(strlen(Buff) + 1);
strcpy(charstr->str, Buff);
if (top == NULL) {
charstr->next = NULL;
} else {
charstr->next = top;
}
top = charstr;
}
こんな感じで30000行分メモリに格納しています。

フラグについてはまだ勉強不足でわかりません。
できれば説明等あるページを教えて頂ければと思います。

>良く理解できていないと思いますが、膨大な文字列データから複数の文字列を一度に検索して取り出したいのですか？

一つの検索文字列からファイル内にある検索文字列を含む行（検索文字列を含む行が複数ある可能性が有る為）全てを抽出したいと考えています。

また、検索文字列は行ごとというわけではなく例えば
検索文字列 "67891"
aaa 123456 67892 23456 bbb ccc
aaa 123456 67891 23456 bbb ccc
aaa 123456 67832 23456 bbb ccc
（二行目だけを抽出したい）

説明不足で申し訳ありませんが、宜しくお願い致します。

補足日時：2008/01/31 14:03