はじめに

ScalaMatsuri 2016で「ScalaとSparkによる日本語テキストマイニング」を聞いて面白そうだったので、まずは日本語形態素解析エンジンkuromojiを触ってみることにしました。
といっても形態素解析するだけなら、ただ単にkuromojiを呼びだすだけなので、もうちょっと賢そうなことをしたいなぁと思っていたところ、「kuromoji.js使って構文解析した」という記事を読みました。
確率自由文脈文法による構文解析……これは何だか凄そうです！

自由文脈文法って何だか聞き覚えあるなと思っていたら、そうそうプログラミング言語でも親しみのあるBNF（バッカス・ナウア記法）で記述できる文法のことでした。まぁ単純な置換ルールによる再帰的な文法のことですね。その置換ルールに確率を付けたのが確率自由文脈文法、と。
「文脈自由文法の話」というスライドがとても分かりやすかったです。

構文解析結果

今回は構文木の推定だけ行って、学習はしていません。
元記事と同じ構文木が得られたので、たぶん合っていると思います。

S 0.2 (8.00e-04)
|
+- 名詞句 1.0 (1.00e-01)
|  |
|  +- 名詞 1.0 (1.00e-01)
|  |  |
|  |  +- 形容詞 0.1 (1.00e-01)
|  |  |  |
|  |  |  +- 名詞 - 隣
|  |  |  |
|  |  |  `- 助詞 - の
|  |  |
|  |  `- 名詞 - 客
|  |
|  `- 助詞 - は
|
`- 動詞 0.5 (4.00e-02)
   |
   +- 名詞 1.0 (8.00e-02)
   |  |
   |  +- 形容詞 0.4 (8.00e-02)
   |  |  |
   |  |  +- 副詞 - よく
   |  |  |
   |  |  `- 形容詞 0.2 (2.00e-01)
   |  |     |
   |  |     +- 名詞 - 柿
   |  |     |
   |  |     `- 動詞 - 食う
   |  |
   |  `- 名詞 - 客
   |
   `- 助動詞 - だ

実装

とりあえず置換ルールのクラスを定義します。

case class Rule(left: String, right1: String, right2: String, prob: Double)

構文木の各ノードは、置換ルールもしくは形態素、そして部分木の確率を持っていれば良さそうです。

case class PcfgNode(label: Either[Rule, Token], prob: Double)

構文木の型は、scalazのTreeを利用してTree[PcfgNode]とします。

あとは構文木を推定する関数です。元記事で使われているCYK法と内側外側アルゴリズム……はちゃんと勉強したほうが良さそうなので……とりあえずシンプルな再帰関数で実装してみます。
いちおう計算効率にも配慮して、メモ化してみました。といってもscalazのMemoを噛ませているだけです。scalaz便利。

def calcPcfgTree: ((Seq[Token], Seq[Rule], String)) => Option[Tree[PcfgNode]] =
  Memo.mutableHashMapMemo { case (inputs: Seq[Token], rules: Seq[Rule], target: String) =>
    inputs.size match {
      case 0 =>
        None
      case 1 =>
        if (inputs.head.getPartOfSpeechLevel1 == target) {
          Some(PcfgNode(Right(inputs.head), 1.0).leaf)
        } else {
          None
        }
      case size =>
        val trees =
          for {
            rule <- rules if rule.left == target
            i <- Range(1, size)
            child1 <- calcPcfgTree(inputs.take(i), rules, rule.right1)
            child2 <- calcPcfgTree(inputs.takeRight(size - i), rules, rule.right2)
          } yield {
            val rootProb = rule.prob * child1.rootLabel.prob * child2.rootLabel.prob
            PcfgNode(Left(rule), rootProb).node(child1, child2)
          }
        trees.reduceOption(Ordering.by((_: Tree[PcfgNode]).rootLabel.prob).max)
    }
  }

やりたい気持ちをそのままコードに落とせた気がします。
Scalaのfor文は、複雑なデータ変換もネストを深くせずに書けるのでいいですね。

あとは構文木をprintすればお終いです。
ノードのshow関数を実装すれば、あとはscalazが木っぽく整形してくれます。

implicit val showPcfgNode = Show.show { node: PcfgNode =>
  node.label match {
    case Left(rule) => f"${rule.left} ${rule.prob} (${node.prob}%.2e)"
    case Right(token) => f"${token.getPartOfSpeechLevel1} - ${token.getBaseForm}"
  }
}

for (r <- result) println(r.drawTree)

今後の課題

自然言語処理なにそれおいしいの状態でも、なんちゃって構文解析はできることが分かりました。敷居思ったより高くない？
いずれ適当な文章をスクレイピングして、適当な自然言語処理をして、適当にドヤ顔することを夢見つつ、まずは何かしらの教科書読みます。たぶん……。

全コード

src/main/scala/Main.scala

import com.atilika.kuromoji.ipadic.{Token, Tokenizer}

import scala.collection.JavaConverters._
import scalaz.Scalaz.ToTreeOps
import scalaz.{Memo, Show, Tree}

case class Rule(left: String, right1: String, right2: String, prob: Double)

case class PcfgNode(label: Either[Rule, Token], prob: Double)

object Main extends App {
  val rules = Seq(
    Rule("S", "名詞句", "形容詞", 0.5),
    Rule("S", "名詞句", "名詞", 0.3),
    Rule("S", "名詞句", "動詞", 0.2),
    Rule("名詞", "形容詞", "名詞", 1),
    Rule("名詞句", "名詞", "助詞", 1),
    Rule("形容詞", "名詞", "助詞", 0.1),
    Rule("形容詞", "名詞", "動詞", 0.2),
    Rule("形容詞", "副詞", "形容詞", 0.4),
    Rule("形容詞", "副詞", "形容詞", 0.3),
    Rule("動詞", "副詞", "動詞句", 0.5),
    Rule("動詞", "名詞", "助動詞", 0.5)
  )

  val tokenizer = new Tokenizer()
  val tokens = tokenizer.tokenize("隣の客はよく柿食う客だ").asScala.toVector
  val result = calcPcfgTree(tokens, rules, "S")

  implicit val showPcfgNode = Show.show { node: PcfgNode =>
    node.label match {
      case Left(rule) => f"${rule.left} ${rule.prob} (${node.prob}%.2e)"
      case Right(token) => f"${token.getPartOfSpeechLevel1} - ${token.getBaseForm}"
    }
  }

  for (r <- result) println(r.drawTree)

  def calcPcfgTree: ((Seq[Token], Seq[Rule], String)) => Option[Tree[PcfgNode]] =
    Memo.mutableHashMapMemo { case (inputs: Seq[Token], rules: Seq[Rule], target: String) =>
      inputs.size match {
        case 0 =>
          None
        case 1 =>
          if (inputs.head.getPartOfSpeechLevel1 == target) {
            Some(PcfgNode(Right(inputs.head), 1.0).leaf)
          } else {
            None
          }
        case size =>
          val trees =
            for {
              rule <- rules if rule.left == target
              i <- Range(1, size)
              child1 <- calcPcfgTree(inputs.take(i), rules, rule.right1)
              child2 <- calcPcfgTree(inputs.takeRight(size - i), rules, rule.right2)
            } yield {
              val rootProb = rule.prob * child1.rootLabel.prob * child2.rootLabel.prob
              PcfgNode(Left(rule), rootProb).node(child1, child2)
            }
          trees.reduceOption(Ordering.by((_: Tree[PcfgNode]).rootLabel.prob).max)
      }
    }
}

build.sbt

name := "pcfg"
version := "0.0.0"
scalaVersion := "2.11.7"

libraryDependencies ++= Seq(
  "com.atilika.kuromoji" % "kuromoji-ipadic" % "0.9.0",
  "org.scalaz" %% "scalaz-core" % "7.2.1"
)

project/build.properties

sbt.version=0.13.11

メモ化再帰で始める構文解析

はじめに

構文解析結果

実装

今後の課題

全コード