私は次のことを行い関数を記述しようとしているテキストファイル

Question

内の文字列のすべての出現箇所の行番号を見つける：

テキストファイルを考えると、私は特定の文字列のすべての出現箇所を検索しますこのファイル;各出現について、それが見つかった行をリストに追加する必要があります。各行にはたかだか1つしか存在しないと仮定します。テキストファイルは非常に大きくなる可能性があります。つまり、単純なfor-loopで各行を繰り返し処理することができます。ファイルは遅すぎます。

例えば、我々はコンテンツのファイルを持っていると言う：

1. ABCDEFG
2. HJKLMNO
3. GFEDCBA
4. PQRSTUV

私が "A" で検索した場合関数は1行目と3行目でそれを見つけ、1と3をリストに追加してからリストを返します。

私はバイナリ検索を検討していましたが、リストをソートする必要があると思われ、要素が区別される必要があります - 私は同じ値を探しています。

私の関数の基底となる検索アルゴリズムは、バイナリ検索とほぼ同じですか？

ありがとうございます！

Answer 1

頻繁に変更されずに多くの検索を実行する場合は、行のインデックスを作成できます。それらを索引付けする1つの方法は、どの行に文字が存在するか（おそらく何回）、ヒストグラムを作成することです。これを反転させて、例えばAの文字が5,10,20行目に現れると言うことができます。 "ABF"を検索している場合は、反転したヒストグラムを使ってどの行が候補かを判断することができます文字 'A'、 'B'、 'F'）を入力し、それらの行のみを表示します。

これが効果的な戦略であるかどうかは、検索の選択性と検索文字列の長さなどによって決まります。特定の使用パターンにメリットがあるかどうかは、テストによってのみ明らかになります。