3

巨大なテキストファイルの文字列バッファがあります。文字列バッファ内の特定の単語/フレーズを検索する必要があります。それを行うための効率的な方法は何ですか？

再モジュール一致を使用してみました。しかし、私は巨大なテキストコーパスを持っているので、それを検索する必要があります。これにはかなりの時間がかかります。

単語とフレーズの辞書が与えられます。

各ファイルを繰り返し処理し、それを文字列に読み込み、辞書内のすべての単語とフレーズを検索し、キーが見つかった場合は辞書内のカウントをインクリメントします。

私たちが考えた小さな最適化の1つは、最大単語数のフレーズ/単語の辞書を最小に並べ替えることでした。次に、文字列バッファからの各単語の開始位置を比較し、単語のリストを比較します。1つのフレーズが見つかった場合、他のフレーズは検索されません（最も長いフレーズと一致したため、これが必要です）

誰かが文字列バッファで単語ごとに移動する方法を提案できますか？（文字列バッファを単語ごとに反復します）？

また、これで実行できる他の最適化はありますか？ 

data = str(file_content)
for j in dictionary_entity.keys():
    cnt = data.count(j+" ")
    if cnt != -1:
        dictionary_entity[j] = dictionary_entity[j] + cnt
f.close()
4

8 に答える 8

7

ファイルの内容（私の場合はProject Gutenbergのオズの魔法使い）を単語ごとに繰り返す、3つの異なる方法：

from __future__ import with_statement
import time
import re
from cStringIO import StringIO

def word_iter_std(filename):
    start = time.time()
    with open(filename) as f:
        for line in f:
            for word in line.split():
                yield word
    print 'iter_std took %0.6f seconds' % (time.time() - start)

def word_iter_re(filename):
    start = time.time()
    with open(filename) as f:
        txt = f.read()
    for word in re.finditer('\w+', txt):
        yield word
    print 'iter_re took %0.6f seconds' % (time.time() - start)

def word_iter_stringio(filename):
    start = time.time()
    with open(filename) as f:
        io = StringIO(f.read())
    for line in io:
        for word in line.split():
            yield word
    print 'iter_io took %0.6f seconds' % (time.time() - start)

woo = '/tmp/woo.txt'

for word in word_iter_std(woo): pass
for word in word_iter_re(woo): pass
for word in word_iter_stringio(woo): pass

その結果：

% python /tmp/junk.py
iter_std took 0.016321 seconds
iter_re took 0.028345 seconds
iter_io took 0.016230 seconds
于 2010-05-04T21:56:40.330 に答える
1

これは、トライが本当に役立つような問題のように聞こえます。おそらく、パトリシア/基数トライのようなある種の圧縮トライを使用する必要があります。トライで探している単語/フレーズの辞書全体に収まる限り、これにより時間の複雑さが大幅に軽減されます。それがどのように機能するかは、単語の先頭を取り、最も長い一致が見つかるまでトライを下降し、そのノードのカウンターをインクリメントすることです。これは、部分的な一致がうまくいかない場合は、トライを上る必要があることを意味する場合があります。次に、次の単語の先頭に進み、もう一度やり直します。トライの利点は、トライを検索するたびに辞書全体を検索することです（各検索には、約O（m）が必要です。ここで、mは辞書内の単語/フレーズの平均の長さです）。

辞書全体を1つのトライに収めることができない場合は、辞書をいくつかの試行に分割し（たとえば、alで始まるすべての単語/フレーズに対して1つ、mzに対して1つ）、それぞれのコーパス全体をスイープすることができます。トライ。

于 2010-05-04T21:06:43.243 に答える
0

NaturalLanguageToolkitの検討を検討しましたか。これには、テキストコーパスを操作するための多くの優れた関数が含まれており、dictのように（キーを持っている）およびlistのように（スライスを持って）動作するクールなFreqDistクラスもあります。

于 2010-05-05T00:37:39.547 に答える
0

モジュールがそれを速く行うことができない場合re、あなたはそれをそれ以上速くすることを強く迫られるでしょう。どちらの方法でも、ファイル全体を読み取る必要があります。正規表現を修正することを検討してください（提供できますか？）。たぶん、あなたが成し遂げようとしていることについての背景もあるでしょう。

于 2010-05-04T20:14:00.393 に答える
0

逆に試してみることができます...テキストコーパスを2,000,000回（単語ごとに1回）処理する代わりに、1回だけ処理します。コーパス内のすべての単語について、ハッシュテーブルなどをインクリメントして、その単語の数を格納します。擬似コードの簡単な例：

word_counts = new hash<string,int>
for each word in corpus:
  if exists(word_counts[word]):
    word_counts[word]++
  else:
    word_counts[word] = 1

単語の完全なリストを使用して事前にword_countsを初期化することで、速度を上げることができる場合があります。これには、ifステートメントは必要ありません...わからない。

于 2010-05-04T20:19:52.013 に答える
0

xyldが言ったように、正規表現とおそらくコードも投稿すると役立つとは思いますが、reモジュールの速度に勝るものはないと思います。追加できるのは、最適化する前にプロファイリングを試すことだけです。ほとんどの処理がどこに行くのかを見ると、かなり驚かれるかもしれません。私はホットショットを使用してコードのプロファイルを作成し、非常に満足しています。ここhttp://onlamp.com/pub/a/python/2005/12/15/profiling.htmlでPythonプロファイリングの良い紹介を見つけることができます。

于 2010-05-04T20:21:42.340 に答える
0

使用reのパフォーマンスが十分でない場合は、を使用しているfindall()か、一致するものを1つずつ手動で検索している可能性があります。イテレータを使用すると、高速になる可能性があります。

>>> for i in re.finditer(r'\w+', 'Hello, this is a sentence.'):
...     print i.group(0)
...     
Hello
this
is
a
sentence
于 2010-05-04T20:23:11.510 に答える
0 
#!/usr/bin/env python
import re

s = ''
for i in xrange(0, 100000):
    s = s + 'Hello, this is a sentence. '
    if i == 50000:
        s = s + " my phrase "

s = s + 'AARRGH'

print len(s)

itr = re.compile(r'(my phrase)|(\w+)').finditer(s)
for w in itr:
    if w.group(0) == 'AARRGH':
        print 'Found AARRGH'
    elif w.group(0) == "my phrase":
        print 'Found "my phrase"'

これを実行すると、

$ time python itrword.py
2700017
Found "my phrase"
Found AARRGH

real    0m0.616s
user    0m0.573s
sys     0m0.033s

ただし、正規表現に明示的に追加された各「フレーズ」は、パフォーマンスに悪影響を及ぼします。私の大まかな測定では、上記は「\ w +」を使用する場合よりも50％遅くなります。

于 2010-05-04T21:16:03.730 に答える