1

非常に大きなテキスト ファイルを指定すると、ファイル内で 1 回だけ出現するすべての単語を削除したいと考えています。簡単で効率的な方法はありますか？

よろしくお願いします、

4

3 に答える 3

8

ファイルに対して 2 つのパスを実行する必要があります。

パス 1:

  • 単語をキーとして使用し、それらの出現を値として使用して辞書を作成します (つまり、単語を読むたびに、辞書の値に 1 を追加します)。
  • 次に、リストを前処理して、値が 1 より大きいすべてのキーを削除します。これが「ブラックリスト」になります。

パス 2:

  • ファイルをもう一度読み、ブラックリストに一致する単語をすべて削除します。

ランタイム：

  • 両方のパスでファイルを読み取る線形時間。
  • 各単語を辞書に追加するのに O(1) かかり、パス 1 でその値をインクリメントします。
  • 辞書をブラックリストに前処理するには O(n) かかります。
  • パス 2 のブラックリスト検索には O(1) かかります。

O(n) の複雑さ

于 2012-10-17T20:33:29.553 に答える
2

ファイルを 2 回通過する必要があります。ただし、まれな単語が本当にまれな場合は、2 番目のパスでファイルの大きなセクションのトークン化をスキップできます。最初に、ファイルを単語ごとにパススルーし、1 回出現した単語の検出位置、または 2 回出現した単語のプレースホルダー値を含む辞書を作成します。

MULTI_WORD = -1
word_locations = {}

for pos, word in tokenize(input_file):
    if word not in word_locations:
        word_locations[word] = pos
    else:
        word_locations[word] = MULTI_WORD

次に、編集が必要な位置を除外し、残りの部分を単純にコピーできます。

edit_points = [(pos, len(word)) for word, pos in word_locations.iteritems()
                                if pos != MULTI_WORD]

start_pos = 0
for end_pos, edit_length in edit_points:
    input_file.seek(start_pos)
    output_file.write(input_file.read(end_pos - start_pos))
    start_pos = end_pos + edit_length
input_file.seek(start_pos)
output_file.write(input_file.read())

メモリのオーバーヘッドを節約するためのブロックごとのコピー手順や、エディット ポイントがない場合の特別なケースなど、さらにいくつかの最適化が必要になる場合があります。

于 2012-10-17T21:03:34.610 に答える
0

参照する特定のコードがなければ知ることは困難ですが、開始するのに適した場所は Python 用の Natural Language Toolkit です。

于 2012-10-17T20:28:24.667 に答える