python - Pythonでパターンの最初の出現を1GB以上のデータ文字列で検索する最速の方法

Question

次のようなものと同等であると想定できる任意のデータの 1 ギガバイトの文字列があります。

1_gb_string=os.urandom(1*gigabyte)

この文字列を検索して1_gb_string、固定幅の 1 キロバイトパターンを無限に検索します1_kb_pattern。検索するたびにパターンが異なります。したがって、キャッシングの機会は明らかではありません。同じ 1 ギガバイトの文字列が何度も検索されます。何が起こっているかを説明する簡単なジェネレーターを次に示します。

def findit(1_gb_string):
    1_kb_pattern=get_next_pattern()
    yield 1_gb_string.find(1_kb_pattern)

パターンの最初のオカレンスのみを見つける必要があることに注意してください。その後、他の主要な処理は実行されません。

1GB 以上のデータ文字列に対して 1KB のパターンを照合するために、python の bultin find よりも高速に使用できるものは何ですか?

(文字列を分割して並行して検索する方法については既に認識しているため、その基本的な最適化は無視してかまいません。)

更新: メモリ要件を 16 GB に制限してください。

score 12 · Accepted Answer

長い前処理が許容されることを明確にすると、Rabin-Karpのバリアントを提案します：「複数パターン検索に最適なアルゴリズム」、ウィキペディアが述べているように。

「ローリングハッシュ」関数を定義します。つまり、のハッシュがわかっている場合、のハッシュをhaystack[x:x+N]計算するhaystack[x+1:x+N+1]と O(1) となる関数を定義します。(Python のビルトインなどの通常のハッシュ関数にhashはこのプロパティがありません。そのため、独自に作成する必要があります。そうしないと、前処理が単に長くかかるというよりも、非常に長くなります;-)。多項式アプローチは実りがあり、たとえば 30 ビットのハッシュ結果を使用できます (必要に応じてマスキングすることにより、つまり、より高い精度で計算を実行し、選択したマスクされた 30 ビットを格納することができます)。わかりやすくするために、このローリングハッシュ関数を RH と呼びましょう。

したがって、干し草の山 1GB の文字列に沿って転がりながら、1G の RH の結果を計算します。これらを保存しただけの場合、index-in-haystack->RH 値をマッピングする 1G 30 ビット値 (4GB) の配列 H が得られます。ただし、逆のマッピングが必要な場合は、代わりに 2**30 エントリ (1G エントリ) の配列 A を使用します。これにより、各 RH 値に対して、干し草の山 (その RH 値が発生するインデックス) 内の対象のすべてのインデックスが得られます。エントリごとに、最初のおそらく興味深い干し草の山インデックスのインデックスを別の配列 B の 1G インデックスの干し草の山に格納します。干し草の山は、すべてのインデックスを同一の RH 値 (ハッシュ用語で「衝突」) を持つ干し草の山に保持するように命令されます。H、A、B にはそれぞれ 4 バイトの 1G エントリがあるため、合計で 12GB になります。

ここで、入ってくる 1K 針ごとに、その RH を計算し、それを k と呼び、それを A へのインデックスとして使用します。A[k] は、比較する価値がある B への最初のインデックス b を提供します。したがって、次のようにします。

ib = A[k]
b = B[ib]
while b < len(haystack) - 1024:
  if H[b] != k: return "not found"
  if needle == haystack[b:b+1024]: return "found at", b
  ib += 1
  b = B[ib]

適切な RH を使用すると、衝突がほとんど発生しないはずです。そのため、while は、いずれかの方法で戻るまで、ごくわずかしか実行されません。したがって、各ニードル検索は非常に高速である必要があります。

score 5 · Accepted Answer

遺伝学の分野で部分文字列を見つけるために使用される文字列一致アルゴリズムは多数あります。この論文またはこの論文を試すことができます

score 1 · Accepted Answer

私の知る限り、標準の検索アルゴリズムは、考えられるすべてのオフセットに対してパターンをチェックするため、n*mの比較が複雑な単純なアルゴリズムです。より効果的なアルゴリズムがいくつかあり、約n+mの比較が必要です。文字列が自然言語の文字列でない場合は、 Knuth–Morris–Prattアルゴリズムを試すことができます。ボイヤームーア文字の検索アルゴリズムも高速でシンプルです。

score 1 · Accepted Answer

文字列の前処理にかなりの時間を費やしてもよろしいですか?

もしそうなら、あなたができることは、オフセットを持つ n-gram のリストを作成することです。

アルファベットが 16 進バイトで、1 グラムを使用しているとします。

次に、00-ff については、次のような辞書を作成できます (Perlese、ごめんなさい)

$offset_list{00} = @array_of_offsets
$offset_list{01} = #...etc

文字列をたどり、バイトが発生するすべてのポイントから @array_of_offsets を作成します。これは、任意の n-gram に対して実行できます。

これは、歩くために使用できる「検索の開始点」を提供します。

もちろん、欠点は、文字列を前処理する必要があることです。これはトレードオフです。

編集：

ここでの基本的な考え方は、プレフィックスを一致させることです。情報が非常に類似している場合、これはひどく爆発する可能性がありますが、n-gram 間にかなりの相違がある場合は、プレフィックスをかなりうまく一致させることができるはずです。

分析している情報の種類について説明していないので、相違を定量化しましょう。このアルゴリズムの目的のために、発散を距離関数として特徴付けることができます。かなり高いハミング距離が必要です。n グラム間のハミング距離がたとえば 1 の場合、上記のアイデアは機能しません。しかし、n-1 の場合、上記のアルゴリズムははるかに簡単になります。

私のアルゴリズムを改善するために、いくつかの可能性を連続的に排除するアルゴリズムを構築しましょう。

Shannon Entropyを呼び出して、特定の n-gram の情報を定義できます。検索文字列を取得し、最初の m 文字に基づいてプレフィックスを連続して作成します。m プレフィックスのエントロピーが「十分に高い」場合は、後で使用します。

p を検索文字列の m プレフィックスとして定義します
1 GB 文字列を検索し、p に一致するオフセットの配列を作成します。
m-prefix を拡張して、m-prefix よりも高い k-prefix のエントロピー k > m である k-prefix にします。
上で定義した要素のオフセット配列を保持して、k プレフィックス文字列と一致するようにします。一致しない要素を破棄します。
検索文字列全体が満たされるまで 4 に進みます。

ある意味では、これはハフマンエンコーディングを逆にするようなものです。

score 0 · Accepted Answer

パターンがかなりランダムである場合は、文字列のnプレフィックスの位置を事前に計算できます。

nプレフィックスのすべてのオプションを調べる代わりに、1GBの文字列で実際のオプションを使用するだけです。これらのオプションは1Gig未満になります。メモリに収まる大きさのプレフィックスを使用してください。チェックする16GBのRAMはありませんが、3または2を試さない場合でも、プレフィックス4は機能します（少なくともメモリ効率の高いデータ構造では）。

ランダムな1GBの文字列とランダムな1KBのパターンの場合、3バイトのプレフィックスを使用するとプレフィックスごとに数十の場所を取得する必要がありますが、4バイトのプレフィックスは平均0または1を取得するため、ルックアップは高速である必要があります。

事前計算場所

def find_all(pattern, string):
  cur_loc = 0
  while True:
     next_loc = string.find(pattern, cur_loc)
     if next_loc < 0: return
     yield next_loc
     cur_loc = next_loc+1

big_string = ...
CHUNK_SIZE = 1024
PREFIX_SIZE = 4
precomputed_indices = {}
for i in xrange(len(big_string)-CHUNK_SIZE):
  prefix = big_string[i:i+PREFIX_SIZE]
  if prefix not in precomputed_indices:
    precomputed_indices[prefix] = tuple(find_all(prefix, big_string))

パターンを調べる

def find_pattern(pattern):
  prefix = pattern[:PREFIX_SIZE]
  # optimization - big prefixes will result in many misses
  if prefix not in precomputed_indices:
    return -1
  for loc in precomputed_indices[prefix]:
    if big_string[loc:loc+CHUNK_SIZE] == pattern:
        return loc
  return -1

score 0 · Accepted Answer

十分な RAM (またはディスク/スワップさえも) が利用可能な場合に、このことをインデックス化する可能な方法を誰かがほのめかしました。

元の Gig 文字列の各文字から拡張された 1K ブロックに対して単純な 32 ビット CRC を実行したとします。これにより、データの先頭からのバイトオフセットごとに 4 バイトのチェックサムデータが生成されます。

これだけでも、検索速度がわずかに向上する可能性があります。各 1K 検索ターゲットのチェックサムは、各 CRC に対してチェックできます...各衝突が真の一致をテストしました。それでも、通常の線形検索よりも数桁高速であるはずです。

これは明らかに、CRC アレイ用に 4 GB の RAM を消費します (さらに、元のデータ用の元の Gig と、環境とプログラムのオーバーヘッドが少し増えます)。

16GB まである場合は、チェックサムを並べ替えて、それぞれが見つかったオフセットのリストを保存できます。これはインデックス付き検索になります (ターゲット検索ごとに平均約 16 プローブ ... 最悪の場合は約 32 または 33 (そこにあるフェンスポストの可能性があります)。

16BG ファイルインデックスは線形チェックサム検索よりも優れたパフォーマンスを提供する可能性があり、ほぼ確実に線形生検索よりも優れています (ファイルシステム/ストレージが非常に遅い場合を除きます)。

(追加): この戦略は、同じ 1 ギガバイトのデータ BLOB に対して多くの検索を行う必要があると説明した場合にのみ有益であることを明確にする必要があります。

インデックスを構築するためにスレッド化されたアプローチを使用する場合があります (インデックスを読み取り、複数のスレッドでチェックサムを実行する場合)。インデックス作成を個別のプロセスまたはノードのクラスターにオフロードすることもできます (特に、ファイルベースのインデックス --- 上記の ~16GB オプションを使用する場合)。単純な 32 ビット CRC を使用すると、リーダースレッドがデータを取得できる限りの速さでチェックサム/インデックス作成を実行できる可能性があります (ただし、1K のデータごとに 1024 個のチェックサムについて話しているため、そうではない可能性があります)。

実際に検索を実行するために C で Python モジュールをコーディングすることにより、パフォーマンスをさらに向上させることができます... および/またはチェックサム/インデックス作成を実行する可能性があります。

このような C 拡張機能の開発とテストには、明らかに別のトレードオフが伴います。これは、再利用性がゼロに近いように思えます。

score 0 · Accepted Answer

効率的だが複雑な方法の 1 つは、Burrows-Wheeler 変換を使用したフルテキストインデックス作成です。これには、ソーステキストに対して BWT を実行し、その上で小さなインデックスを使用して、入力パターンに一致するテキスト内の部分文字列をすばやく見つけることが含まれます。

このアルゴリズムの時間計算量は、照合する文字列の長さでおよそ O(n) であり、入力文字列の長さとは関係ありません! さらに、インデックスのサイズは入力データよりもそれほど大きくなく、圧縮によってソーステキストのサイズよりも小さくすることさえできます。

score 0 · Accepted Answer

無限のメモリを使用すると、1 GB ファイル内の位置とともに 1k 文字列ごとにハッシュできます。

メモリが無限にない場合は、検索時に使用するメモリページの数によって制限されます。

score 0 · Accepted Answer

文字列のメソッドが Python の (正規表現) モジュールによって提供されるメソッドfind()よりも高速であるかどうかは、はっきりとはわかりませんが、調べる方法は 1 つしかありません。search()re

文字列を検索するだけの場合、必要なのは次のとおりです。

import re
def findit(1_gb_string):
    yield re.search(1_kb_pattern, 1_gb_string)

ただし、本当に最初の一致のみが必要な場合finditer()は、イテレータを返すを使用した方がよい場合があります。このような大規模な操作では、実際にはよりよい場合があります。

score 0 · Accepted Answer

http://www.youtube.com/watch?v=V5hZoJ6uK-s あなたにとって最も価値のあるものになります。動的プログラミングに関する MIT の講義です。

python - Pythonでパターンの最初の出現を1GB以上のデータ文字列で検索する最速の方法

10 に答える 10

Related

Reference