2

1 つの大きなテキスト (~4GB) の場合、~100 万のフレーズを検索し、それらを補完的なフレーズに置き換える必要があります。生のテキストと置換の両方が簡単にメモリに収まります。単純な解決策は、1 回の交換に約 1 分かかるため、完了するまでに文字通り何年もかかります。

単純な解決策:

for search, replace in replacements.iteritems():
    text = text.replace(search, replace)

使用する正規表現方法re.subは x10 遅いです。

for search, replace in replacements.iteritems():
    text = re.sub(search, replace, text)

いずれにせよ、これはボイヤー・ムーア弦、またはアホ・コラシックを使用するのに最適な場所のようです。ただし、これらのメソッドは一般に実装されているため、文字列の検索のみに機能し、文字列の置換には機能しません。

または、これをすばやく実行できるツール (Python 以外) も歓迎します。

ありがとう！

4

4 に答える 4

1

Wikipedia の全文に対して ~100,000 回の検索と置換操作を実行する必要がある、このユースケースもありました。sed、awk、またはを使用すると、perl何年もかかります。検索と置換を行う Aho-Corasick の実装を見つけることができなかったので、独自にfsedを作成しました。このツールはたまたま Python で作成されています (したがって、必要に応じてコードをハッキングできます) が、sed.

次の方法で取得できます。

pip install fsed
于 2015-12-18T13:20:59.103 に答える
1

Python以外でsedは、通常、この種の目的で使用されます。

たとえば (ここから取得)、ファイル sue.txt で「醜い」という単語を「美しい」に置き換えるには、次のようにします。

sed -i 's/ugly/beautiful/g' /home/bruno/old-friends/sue.txt

コードのプロファイリングを投稿していません。時期尚早の最適化を行う前に、いくつかのタイミングを試す必要があります。4 GB のファイル内のテキストの検索と置換は、計算負荷の高い操作です。

ALTERNATIVE 質問: 私はこれを行う必要がありますか? -

以下では、Wikipedia コーパス全体の検索と置換を 10 ミリ秒未満で行う方法について説明します。これは素晴らしいデザインとは思えないため、警鐘を鳴らしています。明らかな理由がない限り、データのサブセットがロード/表示されているため、表示および/またはロードに使用するコードを変更して、検索と置換を行う必要があります。4GB のデータ全体に対して多くの操作を行う可能性は低いため、検索と置換の操作は実際に作業しているものに限定してください。さらに、作業中のファイルの大きさがわからないため、タイミングは依然として非常に不正確です。

最後に、次の点に注意してください。

高速化は、数百万の sed 呼び出しを連鎖させずにアルゴリズムである必要があります

しかし、あなたが扱っているデータは「単一の大きなテキスト（〜4GB）」であると指摘したので、その意味を正しく理解していれば、変更は必要ありません。

更新： 以下では、〜4KBのファイル（私は推測しています）で操作を行うには90秒かかることを示しています。これは私には非常に奇妙に思えます.sed操作は通常、それに近い場所にはかかりません. ファイルが実際に 4MB の場合 (期待しています)、評価に 24 時間かかるはずです (理想的ではありませんが、おそらく許容できるでしょうか?)。

于 2013-09-05T20:49:31.043 に答える
0

それらは通常、文字列を検索するためだけに実装され、文字列を置換することはありません

完璧です。まさにあなたが必要としているものです。4G テキストで効果のないアルゴリズムを使用して検索するだけでも十分に悪いですが、いくつかの置換を行うことはおそらくさらに悪いことです...ソース テキストとターゲット テキストのサイズの違いによって生じる拡大/縮小のためのスペースを確保するために、ギガバイトのテキストを移動する必要がある可能性があります.

場所を見つけて、部品を交換部品と結合するだけです。

したがって、ばかげた例えは になります"_".join( "a b c".split(" ") )が、もちろん、このようにコピーを作成したくはありませんsplit。

注: Python でこれを行う理由はありますか?

于 2013-09-05T20:52:30.570 に答える