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

北野坂備忘録

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

言語処理100本ノック 2015年版 (46~49)

5章後編に突入。

46. 動詞の格フレーム情報の抽出

45のプログラムを改変し,述語と格パターンに続けて項(述語に係っている文節そのもの)をタブ区切り形式で出力せよ.45の仕様に加えて,以下の仕様を満たすようにせよ.

項は述語に係っている文節の単語列とする(末尾の助詞を取り除く必要はない)
述語に係る文節が複数あるときは,助詞と同一の基準・順序でスペース区切りで並べる

「吾輩はここで始めて人間というものを見た」という例文(neko.txt.cabochaの8文目)を考える. この文は「始める」と「見る」の2つの動詞を含み,「始める」に係る文節は「ここで」,「見る」に係る文節は「吾輩は」と「ものを」と解析された場合は,次のような出力になるはずである.

始める で ここで
見る は を 吾輩は ものを

 文節から助詞を削り出していたのでカンタンに終わったが、後から手戻りが生じた。
 「助詞と同一の基準・順序で」となっているが、後半の設問を見ると辞書順ではなく助詞を辞書順にしたものと並びが一致している。
 このため、助詞と単語列を一つのリストにして、助詞を基準に並べ替えなければならない。

#!/usr/bin/env python

import codecs
import re
import copy

morphlist=[]
srcslist=[]
printstring = ""

class Chunk(object):
  def __init__(self,line):
    l = re.split(" ",line)
    self.dst = l[2]
    self.dst = int(self.dst[:-1])
    l[1] = int(l[1]) #文節番号をint化
    self.srcs =[]
    self.morphs = []
    for x in srcslist:
      if (x[0] == l[1]):
        self.srcs.append(x[1])
    srcslist.append([self.dst,l[1]]) #srcslistに追加

  def morphsin(self,morphlist):
    self.morphs = morphlist

  def existparticle(self):
    for x in self.morphs:
      if x.pos == '助詞':
        return x.base

  def existverb(self):
    for x in self.morphs:
      if x.pos == '動詞':
        return x.base

  def pdelsymbol(self):
    printx = ""
    for x in self.morphs:
      if x.pos != '記号':
        if x.surface != '一':
          printx = printx + x.surface
    if printx:
      return printx, self.dst

class Morph(object):
  def __init__(self,line):
    l = re.sub(r"\t",",",line)
    l = re.split(",",l)
    self.surface = l[0]
    self.base = l[7]
    self.pos = l[1]
    self.pos1 = l[2]

fin = codecs.open('neko.txt.cabocha', 'r', 'utf_8')
string = []
src = []

if __name__ == "__main__":
  n=0 
  for line in fin:
#    if n==100000:
    if n==50:
      break
    if re.search("EOS",line):
      if string:
        string[-1].morphsin(morphlist)
        morphlist = []
        src.append(string.copy()) #stringを追加
        string = []
        srcslist=[]
      continue
    if re.search(r'^\*',line):
      if string:
        string[-1].morphsin(morphlist)
        morphlist = []
      c = Chunk(line)
      string.append(copy.copy(c)) #Chunkを追加
      n = n + 1
      continue
    b = Morph(line)
    morphlist.append(copy.copy(b))

  for stringx in src:
    for chunkx in stringx:
      if chunkx.existverb():
        l = chunkx.pdelsymbol()
        printstring = chunkx.existverb() + "\t"
        particlelist = []
        particlestring = []
        printx = ""
        for cx in chunkx.srcs: #chunkx.srcsを入手
          if stringx[cx].existparticle():
            l = stringx[cx].pdelsymbol()
            #助詞と項をparticlelistに保存
            particlelist.append((stringx[cx].existparticle(),l[0]))
        if len(particlelist)>=1:
          #助詞を基準にしてソート
          particlelist = sorted(particlelist, key=lambda x: x[0])

          for x in particlelist: #格パターン
            printx = printx + x[0] + " "
          printstring = printstring + printx + "\t"
          printx = ""

          for x in particlelist: #項
            printx = printx + x[1] + " "
          printstring = printstring + printx
       
          print(printstring)
          printx = ""
          particlelist = []
          particlestring = []

結果

生れる	で 	どこで 
つく	か が 	生れたか 見当が 
泣く	で 	所で 
する	だけ 	事だけは 
始める	で 	ここで 
見る	は を 	吾輩は ものを 
捕える	を 	我々を 
煮る	て 	捕えて 
食う	て 	煮て 
(略)
47. 機能動詞構文のマイニング

動詞のヲ格にサ変接続名詞が入っている場合のみに着目したい.46のプログラムを以下の仕様を満たすように改変せよ.

「サ変接続名詞+を(助詞)」で構成される文節が動詞に係る場合のみを対象とする
述語は「サ変接続名詞+を+動詞の基本形」とし,文節中に複数の動詞があるときは,最左の動詞を用いる
述語に係る助詞(文節)が複数あるときは,すべての助詞をスペース区切りで辞書順に並べる
述語に係る文節が複数ある場合は,すべての項をスペース区切りで並べる(助詞の並び順と揃えよ)

例えば「別段くるにも及ばんさと、主人は手紙に返事をする。」という文から,以下の出力が得られるはずである.

返事をする と に は 及ばんさと 手紙に 主人は

このプログラムの出力をファイルに保存し,以下の事項をUNIXコマンドを用いて確認せよ.

コーパス中で頻出する述語(サ変接続名詞+を+動詞)
コーパス中で頻出する述語と助詞パターン

今まではChunk内で事なきを得ていたが、今回からはChunkが分かれる。つまりメソッド化できない。
まず、サ変接続名詞を取得する。これはメソッド化できる。
次に、「サ変接続名詞+を+動詞」を取り出す。
上記の例であれば「する」には「及ばさんと」「主人は」「手紙に」「返事を」がかかっている。
この中で「サ変接続名詞+を」の「返事を」だけを特別扱いするわけである。

#!/usr/bin/env python

import codecs
import re
import copy

morphlist=[]
srcslist=[]
printstring = ""

class Chunk(object):
  def __init__(self,line):
    l = re.split(" ",line)
    self.dst = l[2]
    self.dst = int(self.dst[:-1])
    l[1] = int(l[1]) #文節番号をint化
    self.srcs =[]
    self.morphs = []
    for x in srcslist:
      if (x[0] == l[1]):
        self.srcs.append(x[1])
    srcslist.append([self.dst,l[1]]) #srcslistに追加

  def morphsin(self,morphlist):
    self.morphs = morphlist

  def existsahennoun(self):
    for x in self.morphs:
      if x.pos1 == 'サ変接続':
        return x.surface

  def existparticle(self):
    for x in self.morphs:
      if x.pos == '助詞':
        return x.base

  def existparticlewo(self):
    for x in self.morphs:
      if x.pos == '助詞' and x.base =='を':
        return x.base

  def existverb(self):
    for x in self.morphs:
      if x.pos == '動詞':
        return x.base

  def pdelsymbol(self):
    printx = ""
    for x in self.morphs:
      if x.pos != '記号':
        if x.surface != '一':
          printx = printx + x.surface
    if printx:
      return printx, self.dst

class Morph(object):
  def __init__(self,line):
    l = re.sub(r"\t",",",line)
    l = re.split(",",l)
    self.surface = l[0]
    self.base = l[7]
    self.pos = l[1]
    self.pos1 = l[2]

fin = codecs.open('neko.txt.cabocha', 'r', 'utf_8')
string = []
src = []

if __name__ == "__main__":
  n=0 
  for line in fin:
#    if n==100000:
    if n==1000:
      break
    if re.search("EOS",line):
      if string:
        string[-1].morphsin(morphlist)
        morphlist = []
        src.append(string.copy()) #stringを追加
        string = []
        srcslist=[]
      continue
    if re.search(r'^\*',line):
      if string:
        string[-1].morphsin(morphlist)
        morphlist = []
      c = Chunk(line)
      string.append(copy.copy(c)) #Chunkを追加
      n = n + 1
      continue
    b = Morph(line)
    morphlist.append(copy.copy(b))
  for stringx in src:
    for chunkx in stringx:
      if chunkx.existverb():
        l = chunkx.pdelsymbol()
        printstring = chunkx.existverb() + "\t"
        particlelist = []
        particlestring = []
        printx = ""
        wostring = ""
        for cx in chunkx.srcs: #chunkx.srcsを入手
          if stringx[cx].existparticle(): #助詞が存在する場合
            #かつ、woの場合だけ特別扱いする
            if stringx[cx].existparticlewo() and stringx[cx].existsahennoun():
              l = stringx[cx].pdelsymbol()
              wostring = stringx[cx].existsahennoun() + "を" #サ変+をを出力
            else:
              l = stringx[cx].pdelsymbol()
              particlestring.append(l[0]) 
              particlelist.append((stringx[cx].existparticle(),l[0]))

        if len(wostring)>=1 and len(particlelist)>=1:
          particlelist = sorted(particlelist, key=lambda x: x[0])

          for x in particlelist:
            printx = printx + x[0] + " "
          printstring = printstring + printx + "\t"
          printx = ""

          for x in particlelist:
            printx = printx + x[1] + " "
          printstring = printstring + printx
          printx = ""

          printstring = wostring + printstring

          print(printstring)
          printx = ""
          particlelist = []
          particlestring = []
          wostring = ""

コーパス中で頻出する述語(サ変接続名詞+を+動詞)を取り出すには cut を使用して、

cut -f1 47.txt | sort | uniq -c | sort -nr

     27 返事をする
     19 挨拶をする
     11 話をする
      8 質問をする
      7 喧嘩をする
      6 真似をする
      5 昼寝をする
      5 相談をする
      5 邪魔をする
      5 質問をかける
      5 辞儀をする
(略)

タブで区切ってあるので次も手がかからない。このためのタブ指示であろう。
コーパス中で頻出する述語と助詞パターン

cut -f1,2 47.txt | sort | uniq -c | sort -nr

      5 返事をする      と
      4 挨拶をする      から
      3 返事をする      と は
      3 喧嘩をする      と
      3 挨拶をする      と
(略)

48. 名詞から根へのパスの抽出

文中のすべての名詞を含む文節に対し,その文節から構文木の根に至るパスを抽出せよ. ただし,構文木上のパスは以下の仕様を満たすものとする.

各文節は(表層形の)形態素列で表現する
パスの開始文節から終了文節に至るまで,各文節の表現を"->"で連結する

「吾輩はここで始めて人間というものを見た」という文(neko.txt.cabochaの8文目)から,次のような出力が得られるはずである.

吾輩は -> 見た
ここで -> 始めて -> 人間という -> ものを -> 見た
人間という -> ものを -> 見た
ものを -> 見た

43に近い処理である。構文木の根というのがハッキリしないが、便宜上係り先番号が-1の文節を根とする。
まずは名詞を含む文節を抽出する。
内容的に再帰を用いる。今回は根まで探索する rootdetect再帰関数 を導入する。

#!/usr/bin/env python

import codecs
import re
import copy
import sys

morphlist=[]
srcslist=[]
printstring = ""

class Chunk(object):
  def __init__(self,line):
    l = re.split(" ",line)
    self.dst = l[2]
    self.dst = int(self.dst[:-1])
    l[1] = int(l[1]) #文節番号をint化
    self.srcs =[]
    for x in srcslist:
      if (x[0] == l[1]):
        self.srcs.append(x[1])
    srcslist.append([self.dst,l[1]]) #srcslistに追加

  def morphsin(self,morphlist):
    self.morphs = morphlist

  def pdelsymbol(self):
    printx = ""
    for x in self.morphs:
      if x.pos != '記号':
        if x.surface != '一':
          printx = printx + x.surface
    if printx:
      return printx, self.dst #文面と係先を返す

  def existnoun(self):
    for x in self.morphs:
      if x.pos == '名詞':
        return x.pos

  def existverb(self):
    for x in self.morphs:
      if x.pos == '動詞':
        return x.pos

class Morph(object):
  def __init__(self,line):
    l = re.sub(r"\t",",",line)
    l = re.split(",",l)
    self.surface = l[0]
    self.base = l[7]
    self.pos = l[1]
    self.pos1 = l[2]

fin = codecs.open('neko.txt.cabocha', 'r', 'utf_8')
string = []
src = []

def rootdetect(stringx,n): #再帰関数
  printstring = ""
  z1 = stringx[n].pdelsymbol() #係り先の文面と係り先を入手
  z2 = stringx[z1[1]].pdelsymbol()
  if z1[1] != -1:
    print(" -> ",z2[0],end="")
    rootdetect(stringx,z1[1])
  
if __name__ == "__main__":
  param = sys.argv 
  n=0 
  for line in fin:
#    if n==100000:
    if n==100:
      break
    if re.search("EOS",line):
      if string:
        string[-1].morphsin(morphlist)
        morphlist = []
        src.append(string.copy()) #stringを追加
        string = []
        srcslist=[]
      continue
    if re.search(r'^\*',line):
      if string:
        string[-1].morphsin(morphlist)
        morphlist = []
      c = Chunk(line)
      string.append(copy.copy(c)) #Chunkを追加
      n = n + 1
      continue
    b = Morph(line)
    morphlist.append(copy.copy(b))

  if len(param)>1:
    stringn = int(param[1])
  else:
    stringn = 1

  stringx = src[stringn]
  for chunkx in stringx:
      if chunkx.dst != -1: #根であれば無視
        z1 = chunkx.pdelsymbol() #文面と係り先を入手
        if z1: #z1が存在すれば
          printstring = z1[0] + " -> "
          z2 = stringx[z1[1]].pdelsymbol() #係り先の文面と係り先を入手
          printstring = printstring + z2[0] 
          if chunkx.existnoun() and stringx[z1[1]]: #名詞を含む文節と係り先が存在すれば
            print(printstring,end="")
            #再帰関数
            rootdetect(stringx,z1[1])
            print("")
            printstring = ""

結果は同じなので省略。

49. 名詞間の係り受けパスの抽出

文中のすべての名詞句のペアを結ぶ最短係り受けパスを抽出せよ.ただし,名詞句ペアの文節番号がiとj(i"で連結して表現する
文節iとjに含まれる名詞句はそれぞれ,XとYに置換する

また,係り受けパスの形状は,以下の2通りが考えられる.

文節iから構文木の根に至る経路上に文節jが存在する場合: 文節iから文節jのパスを表示
上記以外で,文節iと文節jから構文木の根に至る経路上で共通の文節kkで交わる場合: 文節iから文節kに至る直前のパスと文節jから文節kに至る直前までのパス,文節kの内容を"|"で連結して表示

例えば,「吾輩はここで始めて人間というものを見た。」という文(neko.txt.cabochaの8文目)から,次のような出力が得られるはずである.

Xは | Yで -> 始めて -> 人間という -> ものを | 見た
Xは | Yという -> ものを | 見た
Xは | Yを | 見た
Xで -> 始めて -> Y
Xで -> 始めて -> 人間という -> Y
Xという -> Y

 この問題が何をしたいのか分からない場合、44の係り受け木の可視化を使って有向グラフを出力して眺めると良い。
 文の中に二つ以上の名詞句がある場合、その経路を全て探索せよというものである。
・根に至る経路上にいるのであれば|を使わない形
・根に至る経路上にいないのであれば|を使って表現しろ
 ということである。

 まずは名詞句のセットを構築したほうが早いかな?
[3,4,5]というセットの場合、
[3,4]
[3,5]
[4,5]
 のセットを調べることになる。

方針としては、
1.名詞句のセットを構築する。
2.異なる2つの名詞句を総当たりでリスト化する。
3.根に至る経路上にいるかいないか判定する。
4.経路上にいるかいないかで表現を変えて出力する。
という、非常にウォーターフォール的な手法を用いる。

XやYの処理も地味にやっかい。pdelsymbolxというメソッドを導入。

経路上に存在している時は、
1.最初の名詞句をX化して表示
2.次で終われば Y だけ表示
3.終わらなければ再帰関数に移行。
設問の文面的には経路上にあるときなぜ「Yを」などではなく「Y」だけになるのか判然としないのだが、例に合わせた。

経路上に存在しないときがやっかいで、
1.文節iから根まで探索して文節番号をリスト化。
2.文節jから根まで探索して文節番号をリスト化。
3.初めて重なる文節をkとする。
4.文節iから文節kの直前まで -> 表記 して |で終了
5.文節jから文節kの直前まで -> 表記 して |で終了
6.文節kを表示
という手間がかかる。

#!/usr/bin/env python

import codecs
import re
import copy
import sys

morphlist=[]
srcslist=[]
printstring = ""

class Chunk(object):
  def __init__(self,line):
    l = re.split(" ",line)
    self.dst = l[2]
    self.dst = int(self.dst[:-1])
    l[1] = int(l[1]) #文節番号をint化
    self.srcs =[]
    for x in srcslist:
      if (x[0] == l[1]):
        self.srcs.append(x[1])
    srcslist.append([self.dst,l[1]]) #srcslistに追加

  def morphsin(self,morphlist):
    self.morphs = morphlist

  def pdelsymbol(self):
    printx = ""
    for x in self.morphs:
      if x.pos != '記号':
        if x.surface != '一':
          printx = printx + x.surface
    if printx:
      return printx, self.dst #文面と係り先を返す

  def pdelsymbolx(self,X): #名詞をXやYに変更するメソッド
    printx = ""
    existX = 0
    for x in self.morphs:
      if x.pos != '記号':
        if x.surface != '一':
          if x.pos == '名詞' and existX == 0:
            printx = printx + X
            existX = 1
          #名詞形態素が連続したときの処理
          elif x.pos == '名詞' and existX == 1: 
            existX = 1
          else: 
            printx = printx + x.surface
    existX = 0
    if printx:
      return printx, self.dst #文面と係り先を返す

  def existnoun(self):
    for x in self.morphs:
      if x.pos == '名詞':
        return x.pos

class Morph(object):
  def __init__(self,line):
    l = re.sub(r"\t",",",line)
    l = re.split(",",l)
    self.surface = l[0]
    self.base = l[7]
    self.pos = l[1]
    self.pos1 = l[2]

fin = codecs.open('neko.txt.cabocha', 'r', 'utf_8')
string = []
src = []

def rootdetect(stringx,n):
  printstring = ""
  z1 = stringx[n].pdelsymbol() #係り先の文面と係り先を入手
  z2 = stringx[z1[1]].pdelsymbol()
  if z1[1] != -1:
    print(" -> ",z2[0],end="")
    rootdetect(stringx,z1[1])

def jdetect(stringx,firstnoun_n,lastnoun_n): #文節jが存在するか探索
  detect = 0
  z1 = stringx[firstnoun_n].pdelsymbol() 
  z2 = stringx[z1[1]].pdelsymbol()
  if z1[1] == lastnoun_n:
    detect = 1
    return detect
  if z1[1] != -1:
    detect = jdetect(stringx,z1[1],lastnoun_n)
    if detect == 1:
      return detect
    if z2[1] == -1:
      detect = 0
      return detect

def rootcheck(nountoelist,stringx,noun_n): #根までの文節番号のリストを作成
  nountoelist.append(noun_n)
  z1 = stringx[noun_n].pdelsymbol() 
  if z1[1] == -1:
    return
  else:
    rootcheck(nountoelist,stringx,z1[1])
  return nountoelist

def itojpath(stringx,firstnoun_n,lastnoun_n): #iからjまでのパスを表示
  z1 = stringx[firstnoun_n].pdelsymbolx("X") 
  if z1[1] == lastnoun_n:
    print("Y")
    return
  else:
    z2 = stringx[z1[1]].pdelsymbol() 
    print(z2[0],"-> ",end="")
    itojpath(stringx,z1[1],lastnoun_n)

if __name__ == "__main__":
  param = sys.argv 
  n=0 
  for line in fin:
#    if n==100000:
    if n==100:
      break
    if re.search("EOS",line):
      if string:
        string[-1].morphsin(morphlist)
        morphlist = []
        src.append(string.copy()) #stringを追加
        string = []
        srcslist=[]
      continue
    if re.search(r'^\*',line):
      if string:
        string[-1].morphsin(morphlist)
        morphlist = []
      c = Chunk(line)
      string.append(copy.copy(c)) #Chunkを追加
      n = n + 1
      continue
    b = Morph(line)
    morphlist.append(copy.copy(b))

  if len(param)>1: #引数処理
    stringn = int(param[1])
  else:
    stringn = 1
  stringx = src[stringn]

  nounlist = [] #名詞句のリストを作成
  n = 0
  for chunkx in stringx:
    if chunkx.existnoun():
      nounlist.append(n)
    n = n + 1

  nounset = [] #名詞句のリストから総当たりリストを作成
  n=0
  m=1
  while n < len(nounlist) -1 :
    while m < len(nounlist):
      nounset.append([nounlist[n],nounlist[m]])
      m = m + 1
    n = n + 1
    m = n + 1

  n = 0
  while n < len(nounset): #総当たりリストから経路判定をする
    firstnoun_n = nounset[n][0]
    lastnoun_n = nounset[n][1]
    firstnoun = stringx[firstnoun_n].pdelsymbolx("X")
    lastnoun = stringx[lastnoun_n].pdelsymbolx("Y")
    detect = jdetect(stringx,firstnoun_n,lastnoun_n)

    if detect == 1: #経路有り処理
      z1 = stringx[firstnoun_n].pdelsymbolx("X") 
      printstring = z1[0] + " -> "
      print(printstring,end="")
      itojpath(stringx,firstnoun_n,lastnoun_n)

    elif detect == 0: #経路無し処理
      #文節iから文節kに至る直前のパス
      #文節jから文節kに至る直前までのパス
      #文節k を取得
      nountoelist =[]
      firstnounlist = rootcheck(nountoelist,stringx,firstnoun_n)
      nountoelist =[]
      lastnounlist = rootcheck(nountoelist,stringx,lastnoun_n)
      k = set(firstnounlist).intersection(lastnounlist)
      i = set(firstnounlist).difference(k)
      j = set(lastnounlist).difference(k)

      xn = 0 #文節iからkまでのパスを表示
      for x in i:
        if xn == 0: 
          l = stringx[x].pdelsymbolx("X")
          print(l[0],end="")
          xn = xn + 1
        else:
          l = stringx[x].pdelsymbol()
          print(" ->",l[0],end="")
      print(" | ",end="")

      xn = 0 #文節jからkまでのパスを表示
      for x in j:
        if xn == 0: 
          l = stringx[x].pdelsymbolx("Y")
          print(l[0],end="")
          xn = xn + 1
        else:
          l = stringx[x].pdelsymbol()
          print(" ->",l[0],end="")
      print(" | ",end="")

      for x in k: #文節kはパスではない
        l = stringx[x].pdelsymbol()
        print(l[0])
          
    n = n + 1    

結果は同じなので省略。
長くなったなあ。もっと綺麗な手法あるんだろうなあ。