6

Byte Pair Encodingアルゴリズムには、スペースで区切られた文字列をバイグラムに変更する置換ステップがあります。

strつまり、次のようなタプルのリストが与えられた場合:

[('t', 'h', 'i', 's', '\ue000'), ('c', 'o', 'r', 'p', 'u', 's', '\ue000'), ('i', 'n', '\ue000'), ('t', 'x', 't', 'f', 'i', 'l', 'e', '\ue000'), ('t', 'h', 'e', '\ue000'), ('s', 'e', 'n', 't', 'e', 'n', 'c', 'e', '\ue000'), ('b', 'a', 'r', '\ue000'), ('a', 'n', 'd', '\ue000'), ('i', 's', '\ue000'), ('f', 'o', 'o', '\ue000'), ('f', 'i', 'r', 's', 't', '\ue000'), ('a', '\ue000'), ('.', '\ue000')]

そして文字列タプル:('i', 's')

すべてのタプルキーを反復処理して に置き換えるようにリストを処理するにはどうすればよい('i', 's')です('is')か? 、つまり、出力Counterは次のようになります。

[('t', 'h', 'is', '\ue000'), ('c', 'o', 'r', 'p', 'u', 's', '\ue000'), ('i', 'n', '\ue000'), ('t', 'x', 't', 'f', 'i', 'l', 'e', '\ue000'), ('t', 'h', 'e', '\ue000'), ('s', 'e', 'n', 't', 'e', 'n', 'c', 'e', '\ue000'), ('b', 'a', 'r', '\ue000'), ('a', 'n', 'd', '\ue000'), ('is', '\ue000'), ('f', 'o', 'o', '\ue000'), ('f', 'i', 'r', 's', 't', '\ue000'), ('a', '\ue000'), ('.', '\ue000')]

私はこれを試しました：

>>> cin
[('t', 'h', 'i', 's', '\ue000'), ('c', 'o', 'r', 'p', 'u', 's', '\ue000'), ('i', 'n', '\ue000'), ('t', 'x', 't', 'f', 'i', 'l', 'e', '\ue000'), ('t', 'h', 'e', '\ue000'), ('s', 'e', 'n', 't', 'e', 'n', 'c', 'e', '\ue000'), ('b', 'a', 'r', '\ue000'), ('a', 'n', 'd', '\ue000'), ('i', 's', '\ue000'), ('f', 'o', 'o', '\ue000'), ('f', 'i', 'r', 's', 't', '\ue000'), ('a', '\ue000'), ('.', '\ue000')]
>>> [tuple(' '.join(i).replace(' '.join(qtuple), ''.join(qtuple)).split()) for i in cin]
[('t', 'h', 'is', '\ue000'), ('c', 'o', 'r', 'p', 'u', 's', '\ue000'), ('i', 'n', '\ue000'), ('t', 'x', 't', 'f', 'i', 'l', 'e', '\ue000'), ('t', 'h', 'e', '\ue000'), ('s', 'e', 'n', 't', 'e', 'n', 'c', 'e', '\ue000'), ('b', 'a', 'r', '\ue000'), ('a', 'n', 'd', '\ue000'), ('is', '\ue000'), ('f', 'o', 'o', '\ue000'), ('f', 'i', 'r', 's', 't', '\ue000'), ('a', '\ue000'), ('.', '\ue000')]

しかし、各単語をループしてから文字列に変更して置換し、再度分割してからタプルにキャストするよりも効率的な方法はありますか?

正規表現の置換はより高速でしょうか? 文字列を扱わずにタプルのリストを操作する方法はありますか?

これを試してみましたが、文字列をに置き換えることstr.replaceは問題ではないようです。それは実際にバイグラムを数えて抽出しています:

import io
from collections import Counter

import time

infile = 'big.txt' # comes from norvig.com/big.txt

n = 2
with io.open(infile, 'r', encoding='utf8') as fin:
    text = fin.read().lower().replace(u' ', u"\uE000")
    for j in range(1,6400):
        unused_char = unichr(ord(u'\uE001') + j)

        start = time.time()
        char_bigrams = zip(*[text[i:] for i in range(n)])
        bigram_time = time.time() - start

        start = time.time()
        most_freq_bigram = Counter(filter(lambda x: u"\uE000" not in x and '\n' not in x, char_bigrams)).most_common(1)[0][0]
        max_time = time.time() - start

        start = time.time()
        text = text.replace(''.join(most_freq_bigram), unused_char)
        replace_time = time.time() - start
        print j, ''.join(most_freq_bigram), most_freq_bigram, bigram_time, max_time, replace_time
    print text

これは、norvig.com/big.txtでテストされています

[アウト]：

1 th (u't', u'h') 0.896255016327 3.28389787674 0.0253069400787
2 e (u'\ue002', u'e') 1.47053217888 3.16544914246 0.0280749797821
3 in (u'i', u'n') 1.13404297829 3.10529899597 0.0245559215546
4 an (u'a', u'n') 1.20013689995 3.63801002502 0.0242891311646
5 er (u'e', u'r') 1.41387891769 3.13376092911 0.0237591266632
6 on (u'o', u'n') 1.22826981544 3.06997895241 0.0227301120758
7 re (u'r', u'e') 1.21916294098 2.97599196434 0.0238041877747
8 at (u'a', u't') 1.14608097076 2.97988891602 0.0226521492004
9 en (u'e', u'n') 1.20747494698 2.88649988174 0.019054889679
10 ed (u'e', u'd') 1.16296696663 2.8995718956 0.0198271274567
11 is (u'i', u's') 1.17692494392 3.02292394638 0.0228500366211
12 d (u'\ue005', u'd') 1.13779211044 2.85169506073 0.0229239463806

私はすでにscikit-learnCountVectorizer を試しましたが、 を使用するほど高速ではないようです。Python での Fast/Optimize N-gram implementations をzip参照してください。

また、ステップでそれらfilterの操作がないCounterと、さらに時間がかかりました。Counter 操作は反復ごとに 3 秒かかります =(

この操作を他にどのように最適化できますか?

Counter(filter(lambda x: u"\uE000" not in x and '\n' not in x, char_bigrams)).most_common(1)[0][0]
4

3 に答える 3

4

文字列タプルを長さ 2 に保つ場合は、次のように reduce を使用できます。

def cons_2(word_list, t):
    j = ''.join(t)
    f = lambda acc, e: acc[:-1] + (j,) if (acc[-1] == t[0] and e == t[1]) else acc + (e,)
    return [reduce(f, i[1:], (i[0],)) for i in word_list]

print cons_2(cin, ('i', 's'))

置換は行われず、fすべての要素iに適用されます。値cinは変更されず、代わりに新しい配列が作成されて返されます。

詳細：

  • reducefすべての配列要素に適用されi、アキュムレータに値を返しますacc。
  • 削減のパラメータ:
    • f: 適用する関数。
    • i[1:]: 最初の要素を除くすべての要素で反復する配列。
    • (i[0],): アキュムレータの初期値。入力タプルの最初の値を持つタプルiです。
  • f:lambdaアキュムレータaccと現在の要素eを入力とする関数です。
    • アキュムレータの最後の要素が文字列タプルの最初の要素eと等しく、現在の要素が文字列タプルの 2 番目の要素と等しい場合は、タプルを返します。acc[-1] + (j,)それ以外の場合は、通常の連結を続行しますacc + (e,)。

文字列タプル > 2 の場合、考え方は同じですが、タプルの長さを管理する必要がありlます。

def cons_n(word_list, t):
    l = len(t)
    j = ''.join(t)
    f = lambda acc, e: acc[:-l] + (j, e,) if acc[-l:] == t or acc[:l] == t else acc + (e,)
    return [reduce(f, i[l:], (i[:l])) for i in word_list]

print cons_n(cin, ('i', 's'))

これは、長さ n の文字列タプルで機能するはずです。

詳細：

  • 上記と同じプロセスですが、l: reduceを使用fすると残りの要素に適用されi[l:]、アキュムレータの初期値は最初のl要素:を持つタプルになります(i[:l])。
  • l文字列 tuple と等しい要素を後方および前方にチェックし、ttrue の場合はタプルを追加します。acc[:-l] + (j, e,)そうでない場合は、通常の連結を続行しますacc + (e,)。

これは機能的なアプローチであり、データは変更されずに生成されるため、複数のプロセスを同時に実行しても安全です (理論的には、私は Python インタープリターの専門家ではありません)。

上記のコードが関数型プログラミングに慣れていない人にとって奇妙すぎる場合、これは別のアプローチです。

def cons_n_iter(tuple_list, tuple_seq):
     jnt = ''.join(tuple_seq)
     lnt = len(tuple_seq)
     res = []
     for word in tuple_list:
         acc = (word[:lnt])
         for letter in word[lnt:]:
             if acc[-lnt:] == tuple_seq or acc[:lnt] == tuple_seq:
                 acc = acc[:-lnt] + (jnt, letter,)
             else:
                 acc += (letter,)
         res += (acc,)
     return res

print cons_n_iter(cin, ('i', 's'))

ロジックは機能的アプローチと同じで、アキュムレータを同じように使用します。この場合、res上記の例ではアキュムレータを処理していたため、アキュムレータは明示的ですreduce。

于 2016-11-01T19:14:52.620 に答える
3

これはあなたが必要とするものですか？re を使用します。

import re,ast
cin = [('t','h',"i",'s', '\ue000'), ('c', 'i', 's', 'p')]
cin = re.sub(r"i'[,\s]+'s", r"is",str(cin))
cin = ast.literal_eval(cin)
于 2016-10-31T20:18:00.380 に答える