分詞|確率最大中国語分詞python実現

サマリ
確率最大分詞は分詞のアルゴリズムの一つであり,文中のすべての候補語を選択することによってそれらの累積確率を計算し,異なる語の組合せの中で累積確率が最大の組合せを最終的な分詞結果として選択する.ここではpythonを用いて実装する.
アルゴリズムの説明
まず、累計確率をどのように計算するかを説明します.もし分詞を待つ文が「対外経済技術協力と交流が絶えず拡大している」としたら、候補語には「対」「対外」「外」「経済」などがあるかもしれない.各語の積算確率は、その元の確率に積算確率が最も大きい左隣語を乗じる確率、すなわちP’(wi)=P(wi)*P(wi-1)に等しく、文の始まりである単語に対しては彼自身の確率である.
例えば、P’(対)=P(対),P’(対外)=P(対外)である.P’(外)=P(外)*P(対),P’(経済)=P(経済)*max{P’(外),P’(外)}と同様である.
具体的なアルゴリズムは以下の通りである.

まず、文を左から右の順にすべての候補語w 1,w 2,...,wnを取り出す必要がある.

各候補語の確率値を計算し、その左隣語を記録する.

は次に、各候補語の累積確率を計算し、累積確率が最も大きい候補語は最適な左隣語である.

wnが文の末尾語であり、累積確率P’(wn)が最大である場合、wnは文の終点語である.

はwnから始まり、左から右の順に、各語の最適な左隣語、すなわち文の分詞結果を順次出力する.

文が長い場合、文の分割方式が多いため、確率を計算する回数と消費されるメモリ空間が大きくなるため、動的計画方式を使用してこのアルゴリズムを記述します.
リストdp[i]を使用してsentence[0,i](pythonではsentence[0:i+1]、ここでは説明を容易にするために)のすべての分割の最大確率を表し、root[]はdp[i]が最大となる語の開始座標を記録する.ワードを使うtailは末尾語または現在語の下付き文字を表し、root[word_tail]はその語の開始下付き文字を表す.
詳細例の説明
候補語を検索する最大長maxを設定します.len=4、初期化dp[]、root[]の長さは文の長さで、各項目は0です.sentence=「対外経済技術協力と交流が拡大している」.

word=「対」で、辞書の「対」を探す確率は0.003388である.

dp[0]=0.003388はsentence[0,0]の現在の最大確率を表し、root[0]=0はsentence[0]の語の開始を0とする.

word=「対外」で、辞書の中の「対」を探す確率は7.5 e-05である.

dp[1]=7.5 e-05で、sentence[0,1]の現在の最大確率を表す.root[1]=0で、「対外」を表す最初の下に0と表記されている.すなわち、「対外」の場合、累計確率が最も大きい語である.

「対外経」、「対外経済」は辞書にないので、スキップした.

word=‘外’,確率は0.00025であり,その積算確率P’(外)=P(外)*P’(対)=0.00025*dp[0]を計算し,dp[1],すなわちP’(外)より大きいか否かを判断し,もしそうであればdp[1]を置き換えroot[1]を1に変更する.ここでは小さいので、置き換えたり、スキップしたりしません.

以降はこれを類推し,root[]で記録された下付き記号により尾語から最も確率の高い左隣語を探す.

文が長すぎると、確率を最後まで乗算するとオーバーフローの問題を引き起こす可能性が高いので、確率を自然対数P(W)*=-lnP(W)=Σ[−lnP(wi)]すると,最大値を求める問題が最小値を求める問題になる.辞書を取得するときに自然対数を取り、累積確率を計算するときに加算に変更するだけです.
インプリメンテーションコード
まず辞書の読み込み

#    -    
def get_dict(path):
    pro_dict = {}
    with open(path, 'r') as r:
        lines = r.readlines()
        for line in lines:
            sub = line.split(',')
            #            
            #               
            pro_dict[sub[0]] = -math.log(float(sub[2].strip('
')[:-1]) / 100)
    return pro_dict


max_len = 4 

ぶんごアルゴリズム

def max_pro(sentence):
    pro_dict = get_dict('WordFrequency.txt')
    dp = [999] * len(sentence)  # dp[i]  sentence[0: i+1]     
    root = [0] * len(sentence)  # root[i]  sentence[i]       
    for i in range(len(sentence)):
        for j in range(i, i+max_len):
            if j < len(sentence):
                word = sentence[i: j+1]
                # print(word)
                if word in pro_dict.keys():
                    temp_pro = pro_dict[word]
                    print(word, temp_pro)
                    if i > 0:
                        temp_pro += dp[i-1]
                    if temp_pro < dp[j]:
                        dp[j] = temp_pro
                        root[j] = i
            else:
                break
    #     
    result = []
    word_tail = len(sentence) - 1
    while word_tail >= 0:
        result.append(sentence[root[word_tail]: word_tail + 1])
        word_tail = root[word_tail] - 1
    result.reverse()
    return dp, root, result

主関数、分詞の具体的な時間をテストして、辞書をロードするのに必要な時間を含みます

if __name__ == '__main__':
    start = time.time()
    dp, root, result = max_pro('               。')
    # print(dp)
    # print(root)
    print(result)
    end = time.time()
    print("running time: " + str(end - start) + "s")