バイトペアの操作方法バイグラムのカウントと置換をPythonで効率的にエンコードするには？

Question

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-learn CountVectorizerで実験してきたと私はいないようでしたzipを使用するのと同じくらい速くなるように、Fast/Optimize N-gram implementations in python

また、除外するの手順で操作を実行すると、さらに時間がかかりました。 ？？カウンタ動作を反復ごとに3秒を取っている=（

他にどのようにこの操作を最適化することができ

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

Answer 1

あなたは長さ2に、あなたの文字列のタプルを続ける場合は、このように減らす使用することができます

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の値が代わりに新しい変更されていないされていません配列が作成され、返されます。

詳細：

• reduceは、各配列要素iためfを適用し、アキュムレータaccに値を返します。削減の
• パラメータ：
  • f：機能が適用されます。
  • i[1:]：最初の要素以外のすべての要素を反復処理する配列。
  • (i[0],)：アキュムレータの初期値。入力タプルの最初の値がiのタプルです。
• f：アキュムレータの最後の要素は、文字列のタプルの最初の要素と現在の要素に等しい場合
  • ：アキュムレータaccとを入力として、現在の要素eとlambda関数であります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を使用して：減らす要素の残りの部分にfを適用i[l:]とアキュムレータの初期値は、最初l要素を持つタプルで：(i[:l])。
• 文字列タプルtに等しいl要素を前後にチェックし、trueの場合はタプルを追加します。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')) 

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

Answer 2

は、これはあなたが再使用して必要なものです

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) 

Answer 3

あなたの元のコード：

[tuple(' '.join(i).replace(' '.join(qtuple), ''.join(qtuple)).split()) for i in cin] 

それは

を何が起こっているか確認するために簡単ですので、私はそれを拡張します

result = [] 
qtuple = ("i", "s") 
for i in cin: 
    f = " ".join(qtuple) 
    r = "".join(qtuple) 
    word = ' '.join(i) 
    word = word.replace(f, r) 
    word = word.split() 
    word = tuple(word) 
    result.append(word) 
print(result) 

ループ外に移動できるものを探します。 私たちは、おそらく他の誰かがre.replace対str.replaceの比較的効率に話すことができる代わりに、各単語

find = " ".join(qtuple) 
replacement = "".join(qtuple) 
result = [] 
# this will join and split each word once 
for i in cin: 
    word = " ".join(i) 
    # if you had multiple replacements to do, they should be in an inner loop here 
    word = word.replace(find, replacement) 
    result.append(tuple(word.split(" "))) 
print(result) 

のためにそれらを計算するの置き換えを事前に計算することができます。個人的には、読みやすさのために単純な置換がそれを行うなら、私は正規表現を避ける傾向があります。

さらに効率の向上は、入力のデータ構造を変更することで実現できます。置換シンボルが1文字の場合、タプルのリストの代わりに文字列を使用して、ループ内の結合を避けることができます。

result = [] 
replacements = [("\ue000", "X"), ("is", "Z")] 
s = "".join(["".join(t) for t in cin]) 
for f, r in replacements: 
    s = s.replace(f,r) 
print(s) 

# output: thZXcorpusXinXtxtfileXtheXsentenceXbarXandXZXfooXfirstXaX.X 

私は、選択されたデータ構造がなぜ好都合なのかを説明するために、いくつかの要件を追加する必要があると思います。効率的な観点から、またバイトペアエンコーディングアルゴリズムの文脈では、文字列は私にとってもっと意味があります。