読者です 読者をやめる 読者になる 読者になる

北野坂備忘録

主にインストールやプログラミングのメモを載せています。

言語処理100本ノック 2015年版 (83,84)

83. 単語/文脈の頻度の計測

82の出力を利用し,以下の出現分布,および定数を求めよ.

f(t,c): 単語tと文脈語cの共起回数
f(t,∗): 単語tの出現回数
f(∗,c): 文脈語cの出現回数
N: 単語と文脈語のペアの総出現回数

単語tと文脈語cの共起回数は、ソートをすればいけます。
cat 82.txt | sort -k 1,2 |uniq -c|sort -nr
が、とんでもない量なのでまともにやっても歯が立ちません。

>wc -l 82.txt
67960353 82.txt

6千8百万行もあります。
しかたがないので各項の一文字目を使ってインデックス化します。今回は小文字化していないので[a-zA-Z][a-zA-Z]になると思いましたが、ハイフンや英語以外のアルファベットが入っているためもっと多くなります。この後の問題も考えて、範囲は[a-zA-Z][a-zA-Z]とします。

#!/usr/bin/env python

import codecs
import re
import collections

fin = codecs.open('82.txt', 'r', 'utf_8')
wordlist = []
lowercase = [chr(i) for i in range(97,97+26)]
uppercase = [chr(i) for i in range(65,65+26)]
wcase = lowercase + uppercase

if __name__ == "__main__":
  n = 0
  for line in fin:
    wordlist =re.split("\t",line[:-1])
    if wordlist[1] == "":
      continue
    if wordlist[0][0] in wcase and wordlist[1][0] in wcase:
      filename = "dir83/" + wordlist[0][0] + wordlist[1][0] + ".txt"
      fout = codecs.open(filename, 'a', 'utf_8')
      fout.writelines(line)
      print(n)
      n += 1

ここで何をしているかというと、以下のようなファイルマトリックスを作成しているのです。

aa ab ac ad ..
ba bb bc bd ..
ca cb cc cd ..
da db dc dd ..
.. .. .. .. ..

このファイル一つ一つに対して処理を行い、その出現分布を合計することで、最終的な出現分布が求まります。
ただし、今回の設問では例示としてaaのファイルだけを処理していきます。

処理としては、この分割したファイルを一つ一つソートしていきます
cat aa.txt | sort -k 1,2 |uniq -c|sort -nr > aalc.txt
sed -i 's/^\s*//g' aalc.txt
最終的に足し合わせれば f(t,c) の出現分布がカウントできます。

33211 a and
33075 and       a
25776 and       and
22067 as        a
22050 a as
13364 a a
12681 and       as
12643 as        as
12603 as        and
(略)

 同様にaa.txt 内の 単語tの出現回数 を見てみると、
cut -f 1 aa.txt | sort -k 1 |uniq -c|sort -nr > aatc.txt
sed -i 's/^\s*//g' aatc.txt

165640 and
120554 a
72606 as
35499 an
29216 at
24755 are
18052 also
8829 all
8001 after
(略)

文脈語の出現分布は
cut -f 2 aa.txt | sort -k 1 |uniq -c|sort -nr > aacc.txt
sed -i 's/^\s*//g' aacc.txt

165311 and
120131 a
72645 as
35581 an
29237 at
24915 are
18267 also
8875 all
7913 after
(略)

 となりました。
 Nはaa.txtの行数、今回は701279になります。

84. 単語文脈行列の作成

83の出力を利用し,単語文脈行列Xを作成せよ.ただし,行列Xの各要素X_tcは次のように定義する.

f(t,c)≥10ならば,X_tc=PPMI(t,c)=max{log( (N×f(t,c)) / (f(t,∗)×f(∗,c) ) ),0}
f(t,c)<10ならば,X_tc=0

ここで,PPMI(t,c)はPositive Pointwise Mutual Information(正の相互情報量)と呼ばれる統計量である.なお,行列Xの行数・列数は数百万オーダとなり,行列のすべての要素を主記憶上に載せることは無理なので注意すること.幸い,行列Xのほとんどの要素は0になるので,非0の要素だけを書き出せばよい.

※後日一部修正しました。
kenichia.hatenablog.com

f(t,c)の出現回数が9以下であればX_tcは0となります。f(t,c)が10以上のものだけ相手にします。
 aalc.txtは65713行存在しますが、が、出現回数が10を越えるものは5584行しかありません。
 aalc.txtから出現数が10以上のものだけを残したaalc10.txtを作成します。

#!/usr/bin/env python

import codecs
import re
import collections
import math

flc10 = codecs.open('aalc10.txt', 'r', 'utf_8')
ftc = codecs.open('aatc.txt', 'r', 'utf_8')
fcc = codecs.open('aacc.txt', 'r', 'utf_8')
wordlist = []
tdic = collections.defaultdict(int)
cdic = collections.defaultdict(int)

N = 701279

if __name__ == "__main__":

  for line in ftc:
    string =re.split(" ",line[:-1])  
    tdic[string[1]]=int(string[0])

  for line in fcc:
    string =re.split(" ",line[:-1])  
    cdic[string[1]]=int(string[0])

  for line in flc10:
    string =re.split(" ",line[:-1])  
    wordlist =re.split("\t",string[1])   
    Xtc = math.log( ( N * int(string[0]) ) / ( tdic[wordlist[0]] * cdic[wordlist[1]] ) )
    if Xtc < 0:
       Xtc = 0
    print(string[1],"\t",Xtc)

 単語と文脈語の辞書を作成し、値を入れてから単語文脈行列を計算しています。

結果
a       and      0.15586062343634052 
and     a        0.15328394801522166 
and     and      0
as      a        0.573358713548542 
a       as       0.5685360627457968
(略)
a       accord   0.2792034844520285
a       accomplishment   0.5370325937541283
a       accompaniment    0.3998314722406432
a       accessed         0
a       absorbed         0