配列項目を含む行を検索する最も効率的な方法

Question

私は100項目の配列を持っています。私は百万行の大きなファイルを持っており、各行について、これらの100項目のそれぞれが各行に含まれているかどうかを調べたいと思います。検索するにはどのような方法が最適ですか？

私は巨大なログファイルに彼らのために検索する必要があり

array = [ '10.10.10.10', '20.20.20.20', ... ] # contains ip addresses 

...

感謝：今、ここに項目のちょうど

open file do each line 
    array.each do each item 
      if line contains item 
       found 
    end 
end 

例である私のアルゴリズムは、です。

Answer 1

String#include?方法は便利ですが、あなたは（計算上）最も効率的な方法について尋ねる場合は、接頭辞と接尾辞木を提供triez宝石（gem install triez）を使用shoud。例：

file = <<~TEXT 
    lorem ipsum dolor sit amet, 
    consectetur adipiscing elit, 
    sed do eiusmod tempor incididunt 
    ut labore et dolore magna aliqua. 
TEXT 

lines = file.split "\n" 

require 'triez' # if necessary, gem install triez 

t = Triez.new 
lines.each_with_index { |line, line_number| 
    t.change_all(:suffix, line) { line_number } 
} 

あなたはあなたのリストにすべての単語を反復処理し、非常に効率的に彼らが発生するライン上で見つけることができます：ところで

words = %w[lorem dolor elit foobar] 
words.each do |word| 
    t.search_with_prefix word do |suffix, line_number| 
    position = lines[line_number].size - suffix.size - word.size 
    puts "'#{word} occurs on line #{line_number}, position #{position}" 
    end 
end 
#=> 'lorem occurs on line 0, position 0 
#=> 'dolor occurs on line 0, position 12 
#=> 'dolor occurs on line 3, position 13 
#=> 'elit occurs on line 1, position 23 

。 Web検索エンジンがWebページをダウンロードした後に最初に行うことは、その接尾辞ツリーを構築することです。文字列検索のための別の宝石はfast_trieです。

Answer 2

解決したい一般的な問題は、の文字列一致問題でよく知られています。この問題は次のように定義されます。

与えられた2つの文字列TとPは、アルファベットの英字Σに与えられます。 文字列マッチングの問題は、与えられたパターンPがT

だからあなたは以下の通り文字列マッチング-問題にあなたの問題を軽減することができます与えられたテキストで発生すると、すべての有効なシフト（インデックス）を見つけることについてです。

1. 入力ファイル - テキスト
2. の>系列配列内のアイテム - >パターンのシーケンス

次の表は、いくつかの文字列マッチングアルゴリズムを示し、それらの前処理と一致するランタイム。 n = | T_1 | + | T_2 | + ... + | T_i | m = | p_1 | + | p_2 | + ... + | p_j |あなたは次のリンクhttps://www.youtube.com/watch?v=NinWEPPrkDQ、または読み取り章32 ,,文字列照合」[ページ985から1013]の下の文字列にするアルゴリズムについてエリックドメーヌの講義を見ることができます詳細については

| Algorithm   | Preprocessing time | Matching time  | 
|:-------------------|-------------------:|:-------------------:| 
| Naive    |  0   |  O((n - m + 1)m) |  
| Rabin-Karp   |  Theta(m)  | O((n - m + 1)m) | 
| Finite Automaton |  O(m|∑|)  |  Theta(n)  | 
| Knuth-Morris-Pratt |  Theta(n)  |  Theta(n)  | 

本の紹介では、既知のアルゴリズムしますCLRSで