ようじょのおえかきちょう

ふぇぇ お医者さんにペン持ったらダメっていわれた〜〜

言語処理100本ノック2015 をRubyでやる【第6章】

programming nlp

コードは GitHub に上げています。この記事では省略した長い出力も output/ ディレクトリに置いてます。

github.com

今回は第 6 章「英語テキストの処理」です。やっと折り返しですね！

英語のテキスト（nlp.txt）に対して，以下の処理を実行せよ．

50. 文区切り

(. or ; or : or ? or !) → 空白文字 → 英大文字というパターンを文の区切りと見なし，入力された文書を1行1文の形式で出力せよ．

解答

# 50.rb

require 'active_record'

File.open('nlp.txt') do |lines|
  lines.each do |line|
    sentences = line.scan(/[A-Z].+?[.;:?!](?=(?:\s[A-Z])|\n)/)
    if sentences.present?
      sentences.each do |sentence|
        puts sentence.rstrip
      end
    else
      line.scan(/^(.+?)\n$/) do |chars|
        puts chars
      end
  end
end

問題文に示されたルールの正規表現だと Natural language processing history などの見出しが拾えないので、別で拾ってあげます（/^(.+?)\n$/）。

出力（一部省略）

Natural language processing
From Wikipedia, the free encyclopedia
Natural language processing (NLP) is a field of computer science, artificial intelligence, and linguistics concerned with the interactions between computers and human (natural) languages.
As such, NLP is related to the area of humani-computer interaction.
Many challenges in NLP involve natural language understanding, that is, enabling computers to derive meaning from human or natural language input, and others involve natural language generation.
History
The history of NLP generally starts in the 1950s, although work can be found from earlier periods.
In 1950, Alan Turing published an article titled "Computing Machinery and Intelligence" which proposed what is now called the Turing test as a criterion of intelligence.
The Georgetown experiment in 1954 involved fully automatic translation of more than sixty Russian sentences into English.
The authors claimed that within three or five years, machine translation would be a solved problem.
...

51. 単語の切り出し

空白を単語の区切りとみなし，50の出力を入力として受け取り，1行1単語の形式で出力せよ．ただし，文の終端では空行を出力せよ．

解答

require './util'

File.open('50.txt') do |sentences|
  sentences.each do |sentence|
    puts sentence.split
    puts
  end
end

sentence の終わりで puts します。

出力（一部省略）

Natural
language
processing

From
Wikipedia,
the
free
encyclopedia

Natural
...

52. ステミング

51の出力を入力として受け取り，Porterのステミングアルゴリズムを適用し，単語と語幹をタブ区切り形式で出力せよ． Pythonでは，Porterのステミングアルゴリズムの実装としてstemmingモジュールを利用するとよい．

解答

require 'active_record'
require 'lingua/stemmer'

stemmer = Lingua::Stemmer.new(language: 'en')

File.open('51.txt') do |words|
  words.each do |word|
    target = word.chomp
    if target.present?
      puts "#{target}\t#{stemmer.stem(target)}"
    else
      puts
    end
  end
end

ruby-stemmer という gem を使いました。たしか Python で stemming を使ってやった人と結果を合わせたら一緒だったと思います。空行なら word.chomp が空文字になるので、このときは空行を出力しました。

github.com

出力（一部省略）

Natural  Natur
language    languag
processing  process

From    From
Wikipedia,  Wikipedia,
the the
free    free
encyclopedia    encyclopedia

Natural Natur
...

53. Tokenization

Stanford Core NLPを用い，入力テキストの解析結果をXML形式で得よ．また，このXMLファイルを読み込み，入力テキストを1行1単語の形式で出力せよ．

解答

./corenlp.sh -annotators tokenize,ssplit,pos,lemma,parse,ner,dcoref, --file nlp.txt

後の問題を見ると、単語・レンマ・品詞・参照表現・代表参照表現・係り受け解析の結果が必要なようです。参照表現を得るのは dcoref ですが、依存関係の表を見ると他の annotator も必要でした。

Annotator dependencies | Stanford CoreNLP

# util.rb

require 'rexml/document'

def xml_elements(filename: 'nlp.txt.xml')
  doc = REXML::Document.new(File.new(filename))
  doc.elements
end

def sentence_tokens
  xml_elements.each('root/document/sentences/sentence') do |sentence|
    sentence.elements.each('tokens/token') do |token|
      block_given? ? yield(sentence, token) : token
    end
  end
end

class REXML::Element
  alias_method :to_text, :text
  remove_method :text

  %w(type idx).each do |attribute_name|
    define_method attribute_name do
      self.attributes[attribute_name]
    end
  end

  %w(id).each do |attribute_name|
    define_method attribute_name do
      self.attributes[attribute_name].to_i
    end
  end

  %w(sentence start end).each do |element_name|
    define_method element_name do
      self.elements[element_name].to_text.to_i
    end
  end

  %w(word lemma POS NER text governor dependent).each do |element_name|
    define_method element_name do
      self.elements[element_name].to_text
    end
  end
end

XML は REXML を使って読むことにしました。sentence を開いて token を 1 つずつ見て……という作業はよく出てくるので sentence_tokens にまとめました。

また、id や word といった attributes や elements はよく参照する割に書く量が多いのでメソッドを作りました。text という element があるのですが、メソッドを作る際に REXML::Element#text と名前が被ってしまうので、to_text というエイリアスメソッドを作って元々の text を削除しました。

# 53.rb

require './util'

sentence_tokens do |_, token|
  puts token.word
end

出力（一部省略）

Natural
language
processing
From
Wikipedia
,
the
free
encyclopedia
Natural
...

54. 品詞タグ付け

Stanford Core NLPの解析結果XMLを読み込み，単語，レンマ，品詞をタブ区切り形式で出力せよ．

解答

require './util'

sentence_tokens do |_, token|
  puts [
    token.word,
    token.lemma,
    token.POS
  ].join("\t")
end

出力（一部省略）

Natural  natural JJ
language    language    NN
processing  processing  NN
From    from    IN
Wikipedia   Wikipedia   NNP
,   ,   ,
the the DT
free    free    JJ
encyclopedia    encyclopedia    NN
Natural natural JJ
...

55. 固有表現抽出

入力文中の人名をすべて抜き出せ．

解答

require './util'

sentence_tokens do |_, token|
  puts token.word if token.NER == 'PERSON'
end

NER は Named Entity Recognition の略で、意味は「固有表現認識」です。

出力

Alan
Turing
Joseph
Weizenbaum
MARGIE
Schank
Wilensky
Meehan
Lehnert
Carbonell
Lehnert
Racter
Jabberwacky
Moore

56. 共参照解析

Stanford Core NLPの共参照解析の結果に基づき，文中の参照表現（mention）を代表参照表現（representative mention）に置換せよ．ただし，置換するときは，「代表参照表現（参照表現）」のように，元の参照表現が分かるように配慮せよ．

解答

# util.rb

...

class Mention
  attr_accessor :start, :endd, :text, :representative_text

  def initialize(start, endd, text, representative_text)
    @start = start
    @endd = endd
    @text = text
    @representative_text = representative_text
  end
end

それぞれの参照表現について、開始位置、終了位置、参照表現テキスト、代表参照表現テキストを持っておきます。

# 56.rb

require './util'

# 文ごとの参照表現
sentence_mentions = []

xml_elements.each('root/document/coreference/coreference') do |coreference|
  representative = coreference.elements['mention[@representative="true"]']
  representative_text = representative.text

  coreference.elements.each('mention[not(@representative)]') do |mention|
    sentence = mention.sentence
    start = mention.start
    endd = mention.end - 1
    text = mention.text
    sentence_mentions[sentence] ||= []
    sentence_mentions[sentence] << Mention.new(start, endd, text, representative_text)
  end
end

endds = []
outputs = []

sentence_tokens do |sentence, token|
  mentions = sentence_mentions[sentence.id]
               &.select { |mention| mention.start == token.id }
               &.sort_by { |mention| -mention.endd }

  output = ''

  mentions&.each do |mention|
    endds << mention.endd
    output += "[#{mention.representative_text}("
  end

  output += token.word

  endds.count(token.id).times { output += ')]' }
  endds.delete(token.id)

  outputs << output
end

puts outputs.join(' ')

end は予約語なので変数名は endd にしています。

代表参照表現は入れ子になる場合もあるので [代表参照表現(参照表現)] のように置換することにしました。入れ子になった代表参照表現の終了位置が同じ場合に正しい数だけカッコを閉じるため、endds に終了位置情報を追加していき、参照表現を出力し終わったら endds に含まれた現在の token の id の数だけ閉じカッコを出力します。

出力（一部省略、表示用に適宜改行を追加）

...
However , [the systems(systems based on [hand-written rules(hand-written rules)])] can only be 
made more accurate by increasing the complexity of [the rules([the rules(the rules)] , which is a 
much more difficult task)] . In particular , there is a limit to the complexity of systems based on 
hand-crafted rules , beyond which the systems become more and more unmanageable . However , 
creating more data to input to [Systems based on machine-learning algorithms(machine-learning systems)] 
...

57. 係り受け解析

Stanford Core NLPの係り受け解析の結果（collapsed-dependencies）を有向グラフとして可視化せよ．可視化には，係り受け木をDOT言語に変換し，Graphvizを用いるとよい．また，Pythonから有向グラフを直接的に可視化するには，pydotを使うとよい．

解答

require 'gviz'
require './util'

# 1文目
sentence = xml_elements['root/document/sentences/sentence']

Graph do
  sentence.elements.each('dependencies[@type="collapsed-dependencies"]/dep') do |dep|
    unless dep.type == 'punct'
      governor_id = dep.elements['governor'].idx.to_id
      dependent_id = dep.elements['dependent'].idx.to_id
      route governor_id => dependent_id
      node governor_id, label: dep.governor
      node dependent_id, label: dep.dependent
    end
  end

  save('57', :png)
end

前々回の 44. 係り受け木の可視化 と同じです。type が collapsed-dependencies になっている dependencies の dep を順番に見て、主要部 => 従属部 の形でグラフを書いていきます。

yamasy1549.hateblo.jp

出力

f:id:yamasy1549:20180421223639p:plain

58. タプルの抽出

Stanford Core NLPの係り受け解析の結果（collapsed-dependencies）に基づき，「主語 述語 目的語」の組をタブ区切り形式で出力せよ．ただし，主語，述語，目的語の定義は以下を参考にせよ．

  • 述語: nsubj関係とdobj関係の子（dependant）を持つ単語
  • 主語: 述語からnsubj関係にある子（dependent）
  • 目的語: 述語からdobj関係にある子（dependent）

解答

# util.rb

...
class Dependant
  attr_accessor :governor, :dependent, :governor_idx, :dependent_idx

  def initialize(governor, dependent, governor_idx, dependent_idx)
    @governor = governor
    @dependent = dependent
    @governor_idx = governor_idx
    @dependent_idx = dependent_idx
  end
end
...

nsubj 関係または dobj 関係の子を Dependant クラスのインスタンスとして持つことにします。

# 58.rb

require './util'

xml_elements.each('root/document/sentences/sentence') do |sentence|
  nsubj_list = []
  dobj_list = []

  sentence.elements.each('dependencies[@type="collapsed-dependencies"]/dep') do |dep|
    type = dep.type

    if type == 'nsubj' || type == 'dobj'
      governor = dep.governor
      dependent = dep.dependent
      governor_idx = dep.elements['governor'].idx.to_i
      dependent_idx = dep.elements['dependent'].idx.to_i
      eval("#{type}_list") << Dependant.new(governor, dependent, governor_idx, dependent_idx)
    end
  end

  governor_idx = nsubj_list.map(&:governor_idx) & dobj_list.map(&:governor_idx)
  governor_idx.each do |idx|
    nsubj = nsubj_list.select { |dep| dep.governor_idx == idx }
    dobj = dobj_list.select { |dep| dep.governor_idx == idx }

    subjects   = nsubj.map(&:dependent).uniq # 主語
    predicates = nsubj.map(&:governor).uniq  # 述語
    objects    = dobj.map(&:dependent).uniq  # 目的語
    puts subjects.product(predicates, objects).map{ |*word| word.join("\t")}
  end
end

最初に nsubj_list と dobj_list を作っておきます。nsubj は主格で述語に係る名詞句、dobjは目的格で述語に係る名詞句、の意味らしいです（日本語 Universal Dependencies の試案 [PDF]）。nsubj_list と dobj_list に共通する governor_idx を持つ dep が、主語や述語や目的語となります。

出力

understanding    enabling    computers
others  involve generation
Turing  published   article
experiment  involved    translation
ELIZA   provided    interaction
patient exceeded    base
ELIZA   provide response
which   structured  information
underpinnings   discouraged sort
that    underlies   approach
Some    produced    systems
which   make    decisions
systems rely    which
that    contains    errors
implementations involved    coding
algorithms  take    set
Some    produced    systems
which   make    decisions
models  have    advantage
they    express certainty
Systems have    advantages
Automatic   make    use
that    make    decisions

59. S式の解析

Stanford Core NLPの句構造解析の結果（S式）を読み込み，文中のすべての名詞句（NP）を表示せよ．入れ子になっている名詞句もすべて表示すること．

解答

# util.rb

...
class Object
  def is_pair?
    self.is_a?(Array) && self.first.is_a?(String) && self.last.is_a?(String)
  end
end

[String, String] となる配列を pair と呼ぶことにします。これは S 式のひとつの単位で、最小の句です。

# 89.rb

require './util'

def parse(s_expr)
  read(tokenize(s_expr))
end

def tokenize(s_expr)
  s_expr.gsub(/[()]/, ' \0 ').split
end

def read(tokens)
  token = tokens.shift
  if token == '('
    l = []
    l << read(tokens) until tokens[0] == ')'
    tokens.shift
    l
  else
    token
  end
end

def output_words(expr)
  if expr.is_pair?
    expr.last
  else
    expr[1..-1].map { |e| output_words(e) }.join(' ')
  end
end

def evaluate(expr, pos: 'NP')
  if expr.first == pos
    puts output_words(expr)
  end
  expr[1..-1].each { |e| evaluate(e) } unless expr.is_pair?
end

xml_elements.each('root/document/sentences/sentence/parse') do |parse|
  parse.to_text
    .yield_self { |text| parse(text) }
    .yield_self { |text| evaluate(text) }
end

tokenize では ((( みたいにカッコが連続しているので、間に空白を入れて split しやすくしています。read では token を 1 つずつ見ていって、( から ) までを l という変数に入れてやって再帰します。

pair は [品詞名, 単語] の形になり、入れ子になると [品詞名1, [品詞名2, 単語]] のようになります。output_words では、一番外側の品詞（品詞名1）が 'NP' なら、内側に向かって単語部分を順番に取り出しています。

yield_self は Ruby 2.5 から新しく入ったメソッドで、一度使ってみたかったので使いました。yield_self を使わず書くと以下のようになりますが、使ったほうが「つながってる、一連の処理」感が出て良いのかなと思います。

parsed = parse(parse.text)
evaluate(parsed)

出力（一部省略）

Natural language processing
Wikipedia
the free encyclopedia Natural language processing -LRB- NLP -RRB-
the free encyclopedia Natural language processing
NLP
a field of computer science , artificial intelligence , and linguistics concerned with the interactions between computers and human -LRB- natural -RRB- languages
a field of computer science
a field
computer science
artificial intelligence
...

もっと良い書き方あるよ〜などあれば issue とかで教えてもらえるとうれしいです！

github.com

言語処理100本ノック2015 をRubyでやる【第5章 後半】

programming nlp

コードは GitHub に上げています。この記事では省略した長い出力も output/ ディレクトリに置いてます。

github.com

今回は第 5 章「係り受け解析」です。長いので前半と後半に分けます。

夏目漱石の小説『吾輩は猫である』の文章（neko.txt）をCaboChaを使って係り受け解析し，その結果をneko.txt.cabochaというファイルに保存せよ．このファイルを用いて，以下の問に対応するプログラムを実装せよ．

45. 動詞の格パターンの抽出

今回用いている文章をコーパスと見なし，日本語の述語が取りうる格を調査したい． 動詞を述語，動詞に係っている文節の助詞を格と考え，述語と格をタブ区切り形式で出力せよ． ただし，出力は以下の仕様を満たすようにせよ．

  • 動詞を含む文節において，最左の動詞の基本形を述語とする
  • 述語に係る助詞を格とする
  • 述語に係る助詞（文節）が複数あるときは，すべての助詞をスペース区切りで辞書順に並べる

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

始める で

見る は を

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

  • コーパス中で頻出する述語と格パターンの組み合わせ
  • 「する」「見る」「与える」という動詞の格パターン（コーパス中で出現頻度の高い順に並べよ）

解答

# util.rb

class Chunk
  ...
  # 最左にある特定の品詞
  def first_morph(pos)
    self.morphs.find { |morph| morph.pos == pos }
  end
  ...

該当 chunk に登場する最左（一番最初）の特定の品詞を取り出します。

require './util'

dependencies.each do |sentence|
  sentence.each do |chunk|
    verb = chunk.first_morph("動詞")
    if verb
      predicate = verb.base
      particles = chunk.srcs.map { |src| sentence[src].first_morph("助詞")&.base }.compact

      puts [predicate, particles.sort.join(' ')].join("\t") if particles.present?
    end
  end
end

動詞を述語（predicate）として、それに係っている形態素（chunk の srcs から見ていけばわかる）の中から最左の助詞であるものを格（particles）として取り出します。最左の助詞が無い（nil）場合もあるので「ぼっち演算子」&. を使っています。nil&.base のせいで map は nil を含んだ配列を返すので、compact して nil を取り除きます。

出力（一部省略）

生れる    で
つく  か が
泣く  で
する  だけ て
始める   で
見る  は を
聞く  で
捕える   を
煮る  て
食う  て
...

解答

頻出する述語と格パターンの組み合わせを見るには、回数付きで uniq して sort すれば良さそうです。

sort 45.txt | uniq -c | sort -r

「する」「見る」「与える」が左側に来る時の右側の助詞（格）を、上と同じように表示します。

sed -nE "s/^する   (.*)/\1/p" 45.txt | sort | uniq -c | sort -r
sed -nE "s/^見る  (.*)/\1/p" 45.txt | sort | uniq -c | sort -r
sed -nE "s/^与える   (.*)/\1/p" 45.txt | sort | uniq -c | sort -r

出力（一部省略）

# 頻出する述語と格パターンの組み合わせ

    584 云う  と
    443 する  を
    256 思う  と
    207 なる  に
    199 ある  が
    188 する  に
    179 見る  て
    134 する  と
    117 する  が
    110 する  に を
    ...
# 「する」が左側に来る時の右側の助詞（格）

    443 を
    188 に
    134 と
    117 が
    110 に を
    102 て を
     88 て
     61 は
     60 が を
     51 で を
    ...

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

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

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

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

始める で ここで

見る は を 吾輩は ものを

解答

require './util'

dependencies.each do |sentence|
  sentence.each do |chunk|
    verb = chunk.first_morph("動詞")
    if verb
      predicate = verb.base
      particles = chunk.srcs.map { |src| sentence[src].first_morph("助詞")&.base }.compact
      chunks = chunk.srcs.map { |src| sentence[src].surfaces if sentence[src].first_morph("助詞") }.compact
      particles, chunks = particles.zip(chunks).sort do |a, b|
        # 同じ格なら文節でもソート
        (a.first <=> b.first).nonzero? || (a.last <=> b.last)
      end.transpose

      puts [predicate, particles.join(' '), chunks.join(' ')].join("\t") if particles.present?
    end
  end
end

前問のプログラムに chunks を考慮した処理を追加します。述語に係っている chunk に助詞が含まれる（格パターンが存在する）なら、その chunk 全ての単語列（ここでは surfaces）を書き出します。

ソート部分は他の人と出力を揃えるためにやりました。比較対象の変数たちは次のように [格, 単語] の形になっています。

a
#=> ["か", "生れたか"]

b
#=> ["が", "見当が"]

a.first <=> b.first
#=> -1

(a.first <=> b.first).nonzero? || (a.last <=> b.last) より 1 つ目の条件式で true が返るので、格が違えば格でソートされます。もし格が同じだった場合はこれが false になるので 2 つ目の条件式が評価され、単語のほうでソートされます。zip してるので最後に行と列を入れ替えるため transpose しておしまいです。

出力（一部省略）

生れる    で どこで
つく  か が 生れたか 見当が
泣く  で 所で
する  だけ て  いた事だけは 泣いて
始める   で ここで
見る  は を 吾輩は ものを
聞く  で あとで
捕える   を 我々を
煮る  て 捕えて
食う  て 煮て
...

47. 機能動詞構文のマイニング

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

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

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

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

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

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

解答

# util.rb

class Chunk
  ...
  # サ変接続名詞 + を（助詞）
  def sahen_wo
    self.morphs.each.with_index do |morph, i|
      next_morph = self.morphs[i+1]
      if next_morph.present? && next_morph.pos == '助詞' && next_morph.surface == 'を' \
         && morph.pos == '名詞' && morph.pos1 == 'サ変接続'
        return morph.surface + 'を'
      else
        return ''
      end
    end
  end

  def has_sahen_wo?
    self.sahen_wo.present?
  end

サ変接続名詞 + を の組み合わせを見つけます。sahen_wo を持つ chunk を見たい時があるので、has_sahen_wo? も作りました（でも結局 has_sahen_wo? してからもう一回 sahen_wo してるので 2 回同じ処理してて良くなさそう）。

# 47.rb

require './util'

dependencies.each do |sentence|
  sentence.each do |chunk|
    next unless chunk.has_sahen_wo? && chunk.depends?
    dst = sentence[chunk.dst]
    verb = dst.first_morph("動詞")

    next unless verb
    # 述語（〜を〜）
    predicate = chunk.sahen_wo + verb.base

    src_pairs = []
    dst.srcs.each do |src|
      # 自分自身に係るものであれば除く
      next if sentence[src] == chunk
      src_chunk = sentence[src]
      src_particle = src_chunk.first_morph("助詞")&.surface
      src_pairs << [src_chunk.surfaces, src_particle] if src_chunk && src_particle
    end

    surfaces, particles = src_pairs.sort_by{ |_, particle| particle }.transpose
    puts [predicate, particles.join(' '), surfaces.join(' ')].join("\t") if particles.present?
  end
end

["彼が", "昼寝を", "する", "ときは", "必ず", "その", "背中に", "乗る"] という sentence（chunk の配列）を例に説明します。

ソースコード 説明
chunk.has_sahen_wo? && chunk.depends? 該当する chunk として ["昼寝", "を"] を Morph に持つ chunk が引っかかる
dst = sentence[chunk.dst] 該当 chunk の係り先 chunk は する
verb = dst.first_morph("動詞") 係り先 chunk の最左の動詞は する
predicate = chunk.sahen_wo + verb.base 述語 昼寝をする
src_chunk = sentence[src] 係り元 chunk として ["彼", "が"] を Morph に持つ chunk が引っかかる
src_particle = src_chunk.first_morph("助詞")&.surface 係り元 chunk に含まれる最左の助詞 "が"
src_chunk && src_particle src_particle が nil になることもあるので、ここで係り元 chunk と助詞の対応を確認する

あとは対応の保証された src_pairs を助詞でソートして出力します。

出力（一部省略）

決心をする  と こうと
返報をする んで  偸んで
昼寝をする が 彼が
迫害を加える  て 追い廻して
投書をする て へ やって ほととぎすへ
話をする    に 時に
昼寝をする て 出て
欠伸をする から て て  なったから して 押し出して
報道をする に 耳に
御馳走を食う  と 見ると
...

解答

述語（サ変接続名詞 + を + 動詞）は 1 列目にあるので cut -f 1 で切り出します。

cut -f 1 ../../output/47.txt | uniq -c | sort -r

述語と助詞は 1, 2 列目です。

cut -f 1,2 ../../output/47.txt | uniq -c | sort -r

出力（一部省略）

# 頻出する述語

      3 返事をする
      3 相談をする
      2 結婚を申し込む
      2 宙返りをする
      2 返事をする
      2 返事をする
      2 返事をする
      2 質問をする
      2 講釈をする
      2 行水を使う
      ...
# 頻出する述語と助詞

      2 安心を得る が
      1 ストライキをしでかす  から て
      1 御馳走を食わせる    から に に
      1 ストライキを起す    が て に
      1 相談を持ちかける    に は
      1 いたずらを始める    て と
      1 降参を申し込む   かい て ながら は
      1 御馳走をあるく   って て
      1 仕事を片付ける   から へ
      1 北面を取り囲む   て として に は
      ...

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

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

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

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

吾輩は -> 見た

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

人間という -> ものを -> 見た

ものを -> 見た

解答

# util.rb

class Chunk
  ...
  def path_to_root(sentence)
    self.depends? ? [self] + sentence[self.dst].path_to_root(sentence) : [self]
  end
end

構文木の根までのパスを配列で返します。ぐるぐる再帰です。

# 48.rb

require './util'

dependencies.each do |sentence|
  sentence.each do |chunk|
    if chunk.depends? && chunk.has_pos?("名詞")
      path = chunk.path_to_root(sentence).map(&:surfaces)
      puts path.join(" -> ") unless path[-1].blank?
    end
  end
end

path の最後が ？ など記号のときにどう扱っていいか分からなかったので、飛ばすことにしました（path[-1] が空文字になるときは出力しない）。

出力（一部省略）

吾輩は -> 猫である
名前は -> 無い
どこで -> 生れたか -> つかぬ
見当が -> つかぬ
何でも -> 薄暗い -> 所で -> 泣いて -> 記憶している
所で -> 泣いて -> 記憶している
ニャーニャー -> 泣いて -> 記憶している
いた事だけは -> 記憶している
吾輩は -> 見た
ここで -> 始めて -> 人間という -> ものを -> 見た
...

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

文中のすべての名詞句のペアを結ぶ最短係り受けパスを抽出せよ．ただし，名詞句ペアの文節番号がiとj（i<j）のとき，係り受けパスは以下の仕様を満たすものとする．

  • 問題48と同様に，パスは開始文節から終了文節に至るまでの各文節の表現（表層形の形態素列）を"->"で連結して表現する
  • 文節iとjに含まれる名詞句はそれぞれ，XとYに置換する

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

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

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

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

Xは | Yという -> ものを | 見た

Xは | Yを | 見た

Xで -> 始めて -> Y

Xで -> 始めて -> 人間という -> Y

Xという -> Y

解答

require './util'

dependencies.each do |sentence|
  noun_pairs = sentence.select { |chunk| chunk.has_pos?("名詞") }.combination(2)

  noun_pairs.each do |i, j|
    noun_i = i.first_morph("名詞")
    noun_j = j.first_morph("名詞")
    surface_i = noun_i.surface
    surface_j = noun_j.surface
    noun_i.surface = "X"
    noun_j.surface = "Y"

    path_i = i.path_to_root(sentence)
    path_j = j.path_to_root(sentence)
    if path_i.include?(j)
      # 文節iから構文木の根に至る経路上に文節jが存在する場合
      puts path_i[0...path_i.index(j)].map(&:surfaces).push("Y").join(" -> ")
    else
      # 文節iと文節jから構文木の根に至る経路上で共通の文節kで交わる場合
      k = (path_i & path_j).first
      output_paths = [
        path_i[0...path_i.index(k)].map(&:surfaces).join(" -> "),
        path_j[0...path_j.index(k)].map(&:surfaces).join(" -> "),
        k.surfaces
      ]
      puts output_paths.join(" | ")
    end

    noun_i.surface = surface_i
    noun_j.surface = surface_j
  end
end

combination(2) で名詞を含む chunk（名詞句）のペアを作り、それぞれの名詞を一旦 X Y に置き換えます（後で戻すので別の変数に隠しておきます）。

経路上に文節 j が存在する場合は j までのパスを表示しますが、素直に path_i[0..path_i.index(j)].map(&:surfaces) と書くと Xで -> 始めて -> Yという みたいに、出力例と一致しないので、Y を含む分節は Y だけを出力してやる必要がありました。「文節 j」だったら Yという まで出力してやってもいいと思うのですが、日本語の説明と出力例が違ってややこしいですね……。ということで、j の 1 つ手前まで + Y、すなわち path_i[0...path_i.index(j)].map(&:surfaces).push("Y") で期待した出力になります。

経路上で共通の文節 k で交わる場合はそのまま実装すればよいです。path_i と path_j は順番に並んでいるので、共通集合（集合に順番の概念はありませんが、ここでは配列になって返ってくるので順番が保たれます）の最初の要素 (path_i & path_j).first が k です。あとは path_i と path_j についてそれぞれ k の手前まで出力、続いて k を出力すれば良いです。

出力（一部省略）

Xは -> Yである
Xで -> 生れたか | Yが | つかぬ
Xでも -> 薄暗い -> Yで
Xでも -> 薄暗い -> 所で | Y | 泣いて
Xでも -> 薄暗い -> 所で -> 泣いて | Yだけは | 記憶している
Xでも -> 薄暗い -> 所で -> 泣いて -> Yしている
Xで | Y | 泣いて
Xで -> 泣いて | Yだけは | 記憶している
Xで -> 泣いて -> Yしている
X -> 泣いて | Yだけは | 記憶している
...

もっと良い書き方あるよ〜などあれば issue とかで教えてもらえるとうれしいです！

github.com

言語処理100本ノック2015 をRubyでやる【第5章 前半】

programming nlp

昨日 4/18 に第 10 章の問題 99 までなんとか終えることができました。ブログ更新のほうサボってたので、これから解説をがんばります。

コードは GitHub に上げています。この記事では省略した長い出力も output/ ディレクトリに置いてます。

github.com

今回は第 5 章「係り受け解析」です。長いので前半と後半に分けます。

夏目漱石の小説『吾輩は猫である』の文章（neko.txt）をCaboChaを使って係り受け解析し，その結果をneko.txt.cabochaというファイルに保存せよ．このファイルを用いて，以下の問に対応するプログラムを実装せよ．

40. 係り受け解析結果の読み込み（形態素）

形態素を表すクラスMorphを実装せよ．このクラスは表層形（surface），基本形（base），品詞（pos），品詞細分類1（pos1）をメンバ変数に持つこととする．さらに，CaboChaの解析結果（neko.txt.cabocha）を読み込み，各文をMorphオブジェクトのリストとして表現し，3文目の形態素列を表示せよ．

解答

係り受け解析の結果を用いるので、-I0 -O4 オプションが必要です。cabocha -f1 -I0 -O4 neko.txt で出力された nako.txt.cabocha はこんな感じです。ここでは、EOS がきたら文章が終わるとみなします。

...

* 0 2D 0/0 -0.764522
　 記号,空白,*,*,*,*,　,　,　
* 1 2D 0/1 -0.764522
吾輩  名詞,代名詞,一般,*,*,*,吾輩,ワガハイ,ワガハイ
は 助詞,係助詞,*,*,*,*,は,ハ,ワ
* 2 -1D 0/2 0.000000
猫 名詞,一般,*,*,*,*,猫,ネコ,ネコ
で 助動詞,*,*,*,特殊・ダ,連用形,だ,デ,デ
ある  助動詞,*,*,*,五段・ラ行アル,基本形,ある,アル,アル
。 記号,句点,*,*,*,*,。,。,。
EOS
* 0 2D 0/1 -1.911675
名前  名詞,一般,*,*,*,*,名前,ナマエ,ナマエ
は 助詞,係助詞,*,*,*,*,は,ハ,ワ
* 1 2D 0/0 -1.911675
まだ  副詞,助詞類接続,*,*,*,*,まだ,マダ,マダ
* 2 -1D 0/0 0.000000
無い  形容詞,自立,*,*,形容詞・アウオ段,基本形,無い,ナイ,ナイ
。 記号,句点,*,*,*,*,。,。,。
EOS
EOS

...

* 1 2D 0/1 -0.764522 といった行の意味は以下のとおりです。

項目 項目名 備考
* 文節の開始位置を示す
1 文節番号 0始まり
2D 係り先文節番号 係り先が同定されなければ -1
0/1 主辞/機能語フィールド 主辞が 0 番目の形態素（吾輩）、機能語が 1 番目の形態素（は）
今後廃止される可能性あり
-0.764522 係り関係のスコア 係りやすさの度合い
信じていい値かどうかは微妙 
# util.rb

require 'active_record'

class Morph
  attr_accessor :surface, :base, :pos, :pos1

  def initialize(surface, base, pos, pos1)
    @surface = surface
    @base = base
    @pos = pos
    @pos1 = pos1
  end
end

class Chunk
  attr_accessor :morphs, :dst, :srcs

  def initialize(morphs: [], dst: -1, srcs: [])
    @morphs = morphs
    @dst = dst
    @srcs = srcs
  end

  # どこかの文節に係っているか
  def depends?
    self.dst != -1
  end
end

# 係り受け解析結果
def dependencies(filename: 'neko.txt.cabocha')
  sentence_list = []

  File.open(filename) do |lines|
    sentence = []
    chunk = Chunk.new

    lines.each do |line|
      # 文節のはじめ
      line.scan(/\*\s\d+\s(?<dst>-?\d+)D/) do |(dst)|
        sentence << chunk if chunk.morphs.present?
        chunk = Chunk.new(dst: dst.to_i)
      end

      # 形態素
      line.scan(/(?<surface>.+?)\t(?<pos>.+?),(?<pos1>.+?)(?:,.+?){4},(?<base>.+?)(?:,|$)/) do |surface, pos, pos1, base|
        chunk.morphs << Morph.new(surface, base, pos, pos1)
      end

      # 文のおわり
      if line == "EOS\n" && chunk.morphs.present?
        sentence << chunk
        sentence.each.with_index do |chunk, i|
          sentence[chunk.dst].srcs << i if chunk.depends?
        end
        sentence_list << sentence
        sentence = []
        chunk = Chunk.new
      end
    end
  end

  sentence_list
end

以降の問題で使うので util.rb にまとめて書いておきます。問題 40 は 41 と合わせて解いたので、各文は Morph オブジェクトのリストでなく Chunk オブジェクトのリストになっています（どうしても Morph オブジェクトのリストにしたければ Chunk オブジェクトを開いて @morphs を取り出せば良い）。

入力ファイルを 1 行ずつ読んで、形態素行の場合は正規表現 /(?<surface>.+?)\t(?<pos>.+?),(?<pos1>.+?)(?:,.+?){4},(?<base>.+?)(?:,|$)/ で surface pos pos1 base を取得します。わかりやすさのために正規表現内で名前をつけていますが、ブロック内の変数としてこれらを拾う |surface, pos, po1, base| と対応しているわけではなく、ここは |hoge, fuga, piyo, bar| とかでも正規表現内の () の順番で拾って変数に代入してくれます。Morph オブジェクトの外からクラス変数を Read / Write したいので attr_accessor を使っています。

dependencies は sentence（文） > chunk（文節） > morph（形態素） という階層でオブジェクトが収められた配列です。以下の出力例は、sentence は文節を 3 つ持ち、1 つ目の文節は形態素を 2 つ持つことを示します。

sentence = dependencies[2]

sentence
# => [#<Chunk:0x00007fd76c9f1d48
  @dst=2,
  @morphs=
   [#<Morph:0x00007fd76c9f1ac8 @base="名前", @pos="名詞", @pos1="一般", @surface="名前">,
    #<Morph:0x00007fd76c9f18e8 @base="は", @pos="助詞", @pos1="係助詞", @surface="は">],
  @srcs=[]>,
 #<Chunk:0x00007fd76c9f1780
  @dst=2,
  @morphs=[#<Morph:0x00007fd76c9f1500 @base="まだ", @pos="副詞", @pos1="助詞類接続", @surface="まだ">],
  @srcs=[]>,
 #<Chunk:0x00007fd76c9f13c0
  @dst=-1,
  @morphs=
   [#<Morph:0x00007fd76c9f1168 @base="無い", @pos="形容詞", @pos1="自立", @surface="無い">,
    #<Morph:0x00007fd76c9f0fb0 @base="。", @pos="記号", @pos1="句点", @surface="。">],
  @srcs=[0, 1]>]

上で説明したような処理を施した dependencies から 3 文目を取り出して、全ての Chunk が持つ Morph を表示します。

# 40.rb

require './util'

# 3文目 : "名前はまだ無い。"
sentence = dependencies[2]

sentence.each do |chunk|
  chunk.morphs.each do |morph|
    puts "surface: #{morph.surface}, base: #{morph.base}, pos: #{morph.pos}, pos1: #{morph.pos1}"
  end
end

出力

surface: 名前, base: 名前, pos: 名詞, pos1: 一般
surface: は, base: は, pos: 助詞, pos1: 係助詞
surface: まだ, base: まだ, pos: 副詞, pos1: 助詞類接続
surface: 無い, base: 無い, pos: 形容詞, pos1: 自立
surface: 。, base: 。, pos: 記号, pos1: 句点

41. 係り受け解析結果の読み込み（文節・係り受け）

40に加えて，文節を表すクラスChunkを実装せよ．このクラスは形態素（Morphオブジェクト）のリスト（morphs），係り先文節インデックス番号（dst），係り元文節インデックス番号のリスト（srcs）をメンバ変数に持つこととする．さらに，入力テキストのCaboChaの解析結果を読み込み，１文をChunkオブジェクトのリストとして表現し，8文目の文節の文字列と係り先を表示せよ．第5章の残りの問題では，ここで作ったプログラムを活用せよ．

解答

# util.rb

...

class Chunk
  ...
  # surfaceをまとめて文字列で返す
  def surfaces(symbol: false)
    surfaces = symbol ? self.morphs : self.morphs.reject { |morph| morph.pos == '記号' }
    surfaces.map { |morph| morph.surface }.join
  end
end

...

def  dependencies(filename: 'neko.txt.cabocha')
      ...
      # 文のおわり
      if line == "EOS\n" && chunk.morphs.present?
        sentence << chunk
        sentence.each.with_index do |chunk, i|
          sentence[chunk.dst].srcs << i if chunk.depends?
        end
        sentence_list << sentence
        sentence = []
        chunk = Chunk.new
      end
      ...
end

以降の問題で記号を省いて surface を出力することがあるので、記号のあるなしをオプションで指定できるようにしました。問題 41 では記号を含んだまま出力します。

dependencies の中で sentence を開いてひとつずつ chunk を見ていきます。chunk がどこかに係っていれば、係り先の chunk の src に番号（sentence のうち何番目の形態素であるか）をメモします。

# 41.rb

require './util'

# 8文目 : "この書生というのは時々我々を捕えて煮て食うという話である。"
sentence = dependencies[7]

sentence.each do |chunk|
  puts "morphs: #{chunk.surfaces(symbol: true)}, dst: #{chunk.dst}, srcs: #{chunk.srcs.to_s}"
end

出力

morphs: この, dst: 1, srcs: []
morphs: 書生というのは, dst: 7, srcs: [0]
morphs: 時々, dst: 4, srcs: []
morphs: 我々を, dst: 4, srcs: []
morphs: 捕えて, dst: 5, srcs: [2, 3]
morphs: 煮て, dst: 6, srcs: [4]
morphs: 食うという, dst: 7, srcs: [5]
morphs: 話である, dst: -1, srcs: [1, 6]

42. 係り元と係り先の文節の表示

係り元の文節と係り先の文節のテキストをタブ区切り形式ですべて抽出せよ．ただし，句読点などの記号は出力しないようにせよ．

解答

require './util'

dependencies.each do |sentence|
  sentence.each do |chunk|
    if chunk.depends? && chunk.surfaces.present? && sentence[chunk.dst].surfaces.present?
      puts [chunk.surfaces, sentence[chunk.dst].surfaces].join("\t")
    end
  end
end

条件は

  • 係り先が存在する
  • 係り元 chunk が記号のみではない
  • 係り先 chunk も記号のみではない

です。記号は出力しないとのことなので、前問で定義した chunk.surfaces を使って記号を省きます。

出力（一部省略）

吾輩は    猫である
名前は   無い
まだ  無い
どこで   生れたか
生れたか    つかぬ
とんと   つかぬ
見当が   つかぬ
何でも   薄暗い
薄暗い   所で
じめじめした  所で
...

43. 名詞を含む文節が動詞を含む文節に係るものを抽出

名詞を含む文節が，動詞を含む文節に係るとき，これらをタブ区切り形式で抽出せよ．ただし，句読点などの記号は出力しないようにせよ．

解答

# util.rb

class Chunk
  ...
  # 特定の品詞を含むか
  def has_pos?(pos)
    self.morphs.map(&:pos).include?(pos)
  end
  ...
end

# 43.rb

require './util'

dependencies.each do |sentence|
  sentence.each do |chunk|
    if chunk.depends? && chunk.surfaces.present? && sentence[chunk.dst].surfaces.present? \
      && chunk.has_pos?("名詞") && sentence[chunk.dst].has_pos?("動詞")
      puts [chunk.surfaces, sentence[chunk.dst].surfaces].join("\t")
    end
  end
end

前問の条件に加えて、

  • 係り元 chunk に名詞を含む
  • 係り先 chunk に動詞を含む

場合を考慮します。

出力（一部省略）

どこで    生れたか
見当が   つかぬ
所で  泣いて
ニャーニャー  泣いて
いた事だけは  記憶している
吾輩は   見た
ここで   始めて
ものを   見た
あとで   聞くと
我々を   捕えて
...

44. 係り受け木の可視化

与えられた文の係り受け木を有向グラフとして可視化せよ．可視化には，係り受け木をDOT言語に変換し，Graphvizを用いるとよい．また，Pythonから有向グラフを直接的に可視化するには，pydotを使うとよい．

解答

require 'gviz'
require './util'

# 4文目 : "どこで生れたかとんと見当がつかぬ"
sentence = dependencies[3]

Graph do
  sentence.each do |chunk|
    if chunk.depends?
      route chunk.surfaces.to_id => sentence[chunk.dst].surfaces.to_id
      node chunk.surfaces.to_id, label: chunk.surfaces
      node sentence[chunk.dst].surfaces.to_id, label: sentence[chunk.dst].surfaces
    end
  end

  save("44", :png)
end

Python なら pydot がおすすめされていますが、今回はRuby ということで、DOT言語を吐いてグラフを書ける Gviz を使いました。

github.com

route 係り元 => 係り先 というように全てのパターンを書き出していきます。使い方を見ると 単語.to_sym した形で（route :hoge => :fuga みたいに）書かれていたのですが、日本語の Symbol では動いてくれなかったので、オブジェクト id を指定することにしました。ただ、そのままだとオブジェクト id が表示されるので label として表示したい日本語の単語を教えてやります。

対象となる文章は特に指定されていないので、適当に 4 文目を使ってみました。あんまり長い文章だとごちゃごちゃして見にくかったです。

出力

f:id:yamasy1549:20180419221240p:plain

構文木の可視化が面白かったので、けいおんの「ごはんはおかず」の歌詞でやってみました。楽しいね。

もっと良い書き方あるよ〜などあれば issue とかで教えてもらえるとうれしいです！

github.com