けんつの煽られ駆動開発記

何か作るときは大抵誰かに煽られた時です。

Scalaのラムダ式と高階関数周りを整理してみる

はじめに

Scalaをああだこうだ使っているけど、いまいちココらへんが理解できていないので
なんとなくまとめて整理してみる。

参考にした記事達

qiita.com
d.hatena.ne.jp

これがいつもダントツでわかりやすくお世話になっています。
関数 · Scala研修テキスト


ラムダ式

上の参考サイトを元に値を引数で一つ受け取って、それに1加算して返す関数を考える。
通常の書き方で書くと次のようになる。

def inc(x: Int): Int = x + 1

inc(1) // return => 2

これをラムダで書き換えてみる。

すると次のようになる。

val inc: Int => Int = x => x + 1
inc(1) // return => 2

ただこちらは関数型でない言語を使ったことがない人には直感で理解がしにくいと思う。
上記のコードを次の用にするとわかりやすいかもしれない。

val inc: (Int => Int) = (x :Int) => x + 1

(Int => Int)が変数incの型であり、Int型の引数をとりInt型の戻り値を返すという意味になっている
(Int => Double)ならInt型の引数をとり、Double型の戻り値を返すという意味合いになる。
引数を2つとり、それらを加算して返す関数は次のように書ける。

val plus: ((Int,Int) => Int) = (x: Int, y: Int) => x + y

変数の型(今回ならInt => Int)を省略することができて、その場合は次のようになる。

val inc = (x: Int) => x + 1

この場合だと引数を二個以上もつ関数もラムダで書きやすい。
上記と同様に引数を2つ受け取り、それを加算する関数を書くと次のようになる。

val plus = (x: Int, y: Int) => x + y
plus(5,6) // return => 11

ここまで書いた右辺のことをラムダ式という。

無名関数

ラムダ式は名前のない関数、つまり無名関数として定義でき
無名関数は変数に束縛されていると言える。

高階関数

一言で言うなら、関数を引数にとる関数のことで次のように書ける。
ラムダ式のことがわかっていればさほど難しい話ではない。

def calc(plus: (Int,Int) => Int, minus: Int) = plus(2,3) - minus
val plus_func: (Int, Int) => Int = (x, y) => x + y

calc(plus_func, 5) //return => 0

引数だけでなく、戻り値として関数を返すこともできるのが高階関数である。

def add(x: Int): (Int => Int) = (y : Int) => x + y
add(2)(3) // return => 5

この様な高階関数はあまり意識しなくても使っていることが多く
よく使う場面ではScalaのコレクションにおいて、mapやforeach,filterなどのメソッドを使うときである

(1 to 100).filter(x => x % 2 == 0)

カリー化

カリー化とは(Int, Int) => Intのように複数の引数をとるラムダにおいて Int => Int => Intのように引数を分割し、
ひとつ引数を取ったあとに、その引数をメソッドチェインのようにチェインさせて書く方法のことを指す。

関数型言語ではよく使われており、Haskellでは複数の引数をとると自動でカリー化されるらしい。

さっきのplus関数で例を挙げてみる。

先に書いたカリー化していない場合は

val plus: (Int, Int) => Int = (x: Int, y: Int) => x + y

となるが

これをカリー化すると次のようになる

val plus: Int => Int => Int = (x: Int) => (y: Int) => x + y
plus(2)(3) // return => 5

これが使えるとなにが嬉しいかというと、filterなどの高階関数を扱うあれこれにおいて
片方の値を定数にして、もう片方を動的に処理した場合などに非常に便利になる。

val myFilter: Int => Int => Boolean = (x: Int) => (y: Int) => x < y 
(1 to 100).filter(myFilter(50))
res10: scala.collection.immutable.IndexedSeq[Int] = Vector(51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100)

最速のEchoサーバーを目指して、LinuxKernelモジュールを作っていく part2

はじめに

前回はカーネルモジュールで出力をやるところまでやった。
rabbitfoot141.hatenablog.com
今回は、気合でカーネルスレッドを扱えるようにする。

実装

EchoサーバではTCPを使用する、それをスレッドでああだこうだして複数接続を可能にしたい。

その目的のために今回は頑張ってカーネルスレッドを実装する。

kernel moduleでカーネルスレッド


参考にしたのはまつもとりーさんの次の記事。
hb.matsumoto-r.jp

linux/kthread.hとlinux/sched.hいうヘッダーファイルにある関数を使う。

kthread.hがカーネルスレッドに関するあれこれで、sched.hがカーネルで扱うプロセスやそれを扱うtask_structという構造体を使うためにある。

それでは早速コードを晒す。

#include <linux/kthread.h>
#include <linux/sched.h>

struct task_struct *task;

static int kthread_cb(void *arg){

    printk("[%s] running as kthread\n", task->comm);

    while(!kthread_should_stop()){
        schedule();
    }

    return 0;

}

グローバル変数としてtask_structを宣言している。
これにプロセスとして起動したいあれこれを代入して使う。

kthread_cb関数ではカーネルスレッドとしての動かしたい処理を書いている。

それを次のモジュール本体のコードで次のように使う。

static int fastecho_init_module(void){

        printk("Fastest Echo Server Start!!");

        //make kernel thread
        task = kthread_create(kthread_cb, NULL, "lrf141:fastecho");
        
        printk("[%s] wake up as kthread\n", task->comm);

        //launch task
        wake_up_process(task);
        
        return 0;
}

static void fastecho_cleanup_module(void){

        printk("Fastest Echo Server is unloaded!");
        printk("[%s] stop kthread\n", task->comm);
        kthread_stop(task);

}

まず前のコードで宣言したtask_structにkthread_create関数の戻り値を代入する
これでスレッドが使える様になるので、printkの次でwake_up_process関数を呼び出し、プロセスとして起動する

rmmod時にはそれを止める処理を書いている。


これを前回のモジュール本体に組み込んで次のようにする。

$ make
$ sudo insmod fastecho.ko
$ ps auwx | grep "\[lrf141:faste
cho\]"
root     30557 98.3  0.0      0     0 ?        R    16:49   0:05 [lrf141:fast
echo]
$ dmesg
[176532.823327] Fastest Echo Server Start!!
[176532.826178] [lrf141:fastecho] wake up as kthread
[176532.827453] [lrf141:fastecho] running as kthread
[176586.304842] Fastest Echo Server is unloaded![lrf141:fastecho] stop kthrea
d
$ sudo rmmod fastecho.ko

おわりに

まつもとりーさんの記事のおかげでなんとかカーネルスレッドを動かすことはできたので
次はネットワークの部分を実装していきたい。

最速のEchoサーバーを目指して、LinuxKernelモジュールを作っていく part1

はじめに

これから諸事情でLinux Kernel moduleとして動作する最速(?)のEchoサーバを作ることになったので
Echoサーバを作る過程をまとめていく。
今回はとりあえず、環境構築からKernel moduleで「Hello,World」的なことをするまでをやる

開発環境構築

参考にしたのは次の2つ
前者では主に、開発環境の面を、後者でコード周りを参考にした。

カーネルモジュール作成によるlinuxカーネル開発入門 - 第一回 hello world - Qiita
Linux kernel module の作成 - Qiita


VM的なのを使いたいなら特に前者を、そうでなくてよくてバグを踏んだ瞬間OSが死んでいいなら後者で十分だと思う。
これがメインではないので関連記事を参照して欲しい。

カーネルモジュールの作成

とりあえずCで開発するのでMakefileを作る
今までこういったものまともに書いたことないので今のところはふたつ目の参考記事のものをパクる。


KERNEL_DIR = /lib/modules/$(shell uname -r)/build
BUILD_DIR := $(shell pwd)
VERBOSE   := 0

obj-m := fastecho.o
fastecho-objs := fastecho_module.o


all:
	make -C $(KERNEL_DIR) SUBDIRS=$(BUILD_DIR) KBUILD_VERBOSE=$(VERBOSE) modules

clean:
	rm -f *.o *.ko *.mod.c *.symvers *.order .fastecho*
	rm -fr .tmp_versions

次に、カーネルモジュール本体のコードを書く

#include<linux/module.h>
#include<linux/kernel.h>

MODULE_DESCRIPTION("The fastest echo server in kernel module");
MODULE_AUTHOR("lrf141");
MODULE_LICENSE("MIT");


static int fastecho_init_module(void){
  
  printk("Fastest Echo Server!!");

  return 0;
}


static void fastecho_cleanup_module(void){

  printk("Fastest Echo Server is unloaded!");

}

module_init(fastecho_init_module);
module_exit(fastecho_cleanup_module);

カーネルモジュールを書く上で、一行目のlinux/module.hは必ず必要となる。
include文の次に来る、大文字のあれこれはそれぞれモジュールの情報で
上から、そのモジュールの説明文、作者、ライセンスとなっている。

そのあとにはモジュールとして呼び出す関数が2つあるが、その両方で使用しているprintkはstdio.hを使った時のprintfのような機能がある。

末尾二行にあるmodule_init()関数ではカーネルモジュールがロードされた際に引数で渡した関数を呼び出す。
引数として渡す関数はintを返り値としている。

module_exit()関数では、カーネルモジュールがアンロードされた時に引数の関数を実行する。

ソースコードがかけたらとりあえずmakeする。


そのあとこれらモジュールの情報は次のようにすると見れる。

$ modinfo fastecho.ko
filename:       /home/lrf141/cProject/fastest_echo/fastecho.ko
license:        MIT
author:         lrf141
description:    The fastest echo server in kernel module
srcversion:     B5F9EFB5EC209D9B991796D
depends:        
vermagic:       4.4.0-98-generic SMP mod_unload modversions 

モジュールをロードするときは次のようにする

$ sudo insmod fastecho.ko

モジュールをアンロードするときはこれ。

$ sudo rmmod fastecho.ko

ただこれではprintkで出力された文字列が見れない。
ということでここまで終わった段階でdmesgコマンドでカーネルのバッファ出力内容をみる
ただ見るだけでは見づらいのでgrepも組み合わせる。

$ dmesg | grep "Fast"
[46074.578777] Fastest Echo Server!!
[46079.485027] Fastest Echo Server is unloaded!

するとprintkした内容が見えている。

最後に

今回は簡単なモジュールの制作をやったので次回はこれにネットワークの機能を突っ込みたい

Hadoopを使ってみた

はじめに

インフラに興味をもってから、その中でも特に分散システムや分散並列処理に興味を持ったので有名な分散処理フレームワークであるHadoopを使ってみる。

今回は以下の記事を参考にして自分のUbuntu 16.04上で動かす。

Apache Hadoop 2.5.0 セットアップ手順 その1 – ローカル実行からシングルノードクラスター起動まで – hrendoh's tech memo

Hadoopのインストール

Hadoop ver 2.7以降のものはJava7の環境下で動く。 Linuxを使ってる人でJavaScalaを使ったことがある人ならわかると思うがJavaの実行環境と言ってもOpenJDKとOracle JDK/JREの2つが存在する。 しかし、Hadoopはこの両方をサポートしているため、いずれかがインストールされていればいい。

詳しくは以下のHadoop wikiに書いてある。

HadoopJavaVersions - Hadoop Wiki

次はJDK/JRE以外で必要なものをインストールする。 公式ドキュメントにはssh,rsyncが必要と書いているがこれらはUbuntuにデフォルトで入っているため省略。

いよいよ、Hadoop本体をインストールする。 今回は次のリンクからhadoop-2.8.2をダウンロードした。

Index of /software/apache/hadoop/common

それらのファイルを展開したら/etc/profileに次のコードを末尾に追加する

export PATH=/<展開したディレクトリ>/hadoop-2.5.0/bin:$PATH

その次に展開したディレクトリ内の/etc/hadoop/hadoop-env.shにJAVA_HOMEのパスを通す。

それが完了したなら、コマンドを実行する。

$ hadoop
Usage: hadoop [--config confdir] [COMMAND | CLASSNAME]
  CLASSNAME            run the class named CLASSNAME
 or
  where COMMAND is one of:
  fs                   run a generic filesystem user client
  version              print the version
  jar <jar>            run a jar file
                       note: please use "yarn jar" to launch
                             YARN applications, not this command.
  checknative [-a|-h]  check native hadoop and compression libraries availability
  distcp <srcurl> <desturl> copy file or directories recursively
  archive -archiveName NAME -p <parent path> <src>* <dest> create a hadoop archive
  classpath            prints the class path needed to get the
                       Hadoop jar and the required libraries
  credential           interact with credential providers
  daemonlog            get/set the log level for each daemon
  trace                view and modify Hadoop tracing settings

Most commands print help when invoked w/o parameters.

このあと参考にした記事ではスタンドアロンモードで起動して動作確認しているがそれは省略。

擬似分散モード

通常はいくつかのサーバなどにあれこれを分散させて処理を行うがそれが難しい場合もあるので今回は擬似分散モードという HDFSデーモンやDataNode、yarnなどを全て同一のサーバ上で実行するモードを使う。

設定ファイルの編集

etc/hadoopディレクトリに設定ファイルが存在する。

まずはcore-site.xmlに次を追加

<configuration>
    <property>
        <name>fs.defaultFS</name>
        <value>hdfs://localhost:9000</value>
    </property>
</configuration>

次にhdfs-site.xmlにプロパティdfs.replicationを1にセットしたproperty要素を追加。

<configuration>
    <property>
        <name>dfs.replication</name>
        <value>1</value>
    </property>
</configuration>

これが終わったなら次の段階に移行する

hdfs(hadoop distributed file system)をフォーマット

初回はデーモンを起動する前にファイルシステムのフォーマットが必要になる。

$ hdfs namenode -format

hdfsデーモンの起動

hdfsのデーモンを起動するにはhadoopを展開したディレクトリ直下のsbin/start-dfs.shを実行する。

実行後にjpsコマンドを叩いて、NameNodeとDataNodeがあれば正常に動作している。

$ cd hadoop-2.8.2
$ sbin/start-dfs.sh
$ jps
15538 SecondaryNameNode
15301 DataNode
24793 Jps
15182 NameNode

Webインターフェースの確認

50070番ポートの通信をファイヤーウォールの設定から許可するとlocalhost:50070でwebインターフェースが起動していることが確認できる。

MapReduceを実行する

MapReduceで使うディレクトリをHDFS(Hadoop Distributed File System)上に作成する

$ hadoop fs -mkdir /user
$ hadoop fs -mkdir /user/<username>

この時のusernameは現在自分の使用しているアカウント名と同一にするといい。

次に、ディレクトリ内に格納されている既存のサンプルを動作させる。

$ hadoop jar share/hadoop/mapreduce/hadoop-mapreduce-examples-2.8.2.jar pi 10 10000
.....
Estimated value of Pi is 3.14120000000000000000

今回はHDFS上で円周率を求めるサンプルがあったのでそれを実行した。 調べてみるとWordCountなどもあるらしい。

おわりに

今回はHadoopをインストールし、HDFS上でサンプルを動かすところまでやった。 ただし、HDFS上で実行したためジョブがローカル実行されている。 次回はそれを分散実行するためのyarnについて触れていこうと思う。

Twitter APIのScalaラッパーを作っている話

はじめに

夏休み、特にすることがなかったのとTwitter4Jに憧れてScalaでTwitter4SというTwitter APIのラッパーを作り始めた。
初めは標準ライブラリだけでごり押すつもりが色々ありいくつかライブラリを使用しているがある程度出来た為、概要をまとめる。

ただまだまだ作りこまないといけないため、今後の更新によってはこのブログの記事は当てにならなくなる。
Github上で管理してるものが全てであり、どのように動作するかはソースコードが物語っている。

Github

このライブラリは次のレポジトリで公開されている。

github.com

また、github pagesでこれらのjarファイルを公開しているため次をbuild.sbtに追加すると自分のプロジェクトで使用できるようになる。

resolvers += "Maven Repo on github" at "https://lrf141.github.io/Twitter4S/"

libraryDependencies ++= Seq(
     "Twitter4S" % "twitter4s_2.12" % "1.0.0"
)

主要なクラスやオブジェクトに関するドキュメントを次のリンクで公開しているので何かあればそちらも参照して欲しい。

https://lrf141.github.io/Twitter4S/

ソースコード概要

ドキュメントで公開してるソースファイルとは別にnet,utilパッケージが存在する
ディレクトリ構成は次の通り。

├── src
│   ├── main
│   │   └── scala
│   │       └── twitter4s
│   │           ├── APIKeys.scala
│   │           ├── HomeTimeLine.scala
│   │           ├── SearchBase.scala
│   │           ├── Status.scala
│   │           ├── StatusBase.scala
│   │           ├── TimeLineBase.scala
│   │           ├── TimeLineUser.scala
│   │           ├── Tweet.scala
│   │           ├── Tweets.scala
│   │           ├── Twitter.scala
│   │           ├── TwitterFactory.scala
│   │           ├── TwitterImpl.scala
│   │           ├── UserArray.scala
│   │           ├── UserStatus.scala
│   │           ├── UserTimeLine.scala
│   │           ├── net
│   │           │   ├── HttpRequest.scala
│   │           │   ├── HttpResponse.scala
│   │           │   └── oauth
│   │           │       └── OAuthRequest.scala
│   │           └── util
│   │               └── JsonDecoder.scala

net package

このパッケージではhttp requestやOAuthに関するクラスを管理している。
OAuthRequest.scalaOAuth認証に必要なパラメータや署名などを生成できる。
Twitter APIを利用するにあたってOAuthはver 1.0に準拠している。
それらを利用してHttpRequest.scalaでPOST/GETに関する機能を実装している。


ここでのBase64変換にapache commons codecを利用している。

util package

このパッケージではこのプロジェクトで使用するネットワークや本体に関係ないクラスを管理している。
この記事公開時点ではJsonDecoder.scalaという中身が非常に行儀悪いクラスのみである。

このクラスではStringの値として受け取ったjsonを解析しcase classのメンバに代入することを主としている。
jsonの解析にcirceというscala製のライブラリを使用している。

src/main/scala直下 twitter4s package

ここではtwitter apiを利用するための色々なクラスやオブジェクト、トレイトが存在する。
主にjsonを解析した際、データの受け皿となるcase classだが、リクエストに必要なメソッドを含むトレイトやそれを実際に実装しているTwitterImpl.scalaなどがメインになっている。

必要な機能は***Base.scalaという名前でトレイトとして存在しそれらはTwitter.scalaのトレイトにミックスインされている。
このライブラリを使用する際にはそれらを実装したTwitterImplのメソッドを呼び出している。

またそのクラスを継承したTwitterFactoryクラスがありライブラリユーザはこれからインスタンスを受け取り各種メソッドを呼び出す仕組みになっている。
このクラスはシングルトンである。

加えてcase classをjson解析で多用しているため解析によって受け取った値は好きなように使用することが出来る。

使用方法

最初に書いたようにbuild.sbtもしくはBuild.scala内にresolversとlibraryDependenciesを追加してもらえるとすぐに使用できる。
具体的な使用方法については公開しているレポジトリのREADME.mdを参照して欲しい。

プルリクについて

プルリクについては、たまに「英語でないとダメ」という意見も見受けられるがこのレポジトリに関しては日本語でのプルリクも受け付けている。
公開されているソースコードをみて、「このコードクソだな」などある場合は積極的にプルリクを送って欲しい。

形態素解析とngram、マルコフ連鎖を用いてもののけ姫風の文章を生成する。

形態素解析とngram,マルコフ連鎖を組み合わせる

前回紹介した記事では

rabbitfoot141.hatenablog.com

ngramをいくつかの文字で分割するタイプにしたが今回は形態素解析を用いていくつかの形態素で分割し、マルコフ連鎖を使って文章を生成する。

今回の概要

形態素解析は今回はライブラリを用いて行う。
言語はScalaで書くので「kuromoji」を用いる。

ビルドツールにsbtを用いているのでbuild.sbtに次を追加。

resolvers += "Atilika Open Source repository" at "http://www.atilika.org/nexus/content/repositories/atilika"
libraryDependencies ++= Seq(
  "org.atilika.kuromoji" % "kuromoji" % "0.7.7"
)

前回は夏目漱石の「こころ」を対象データにしたが今回はもののけ姫のサンでいこうと思う。
このサイトから借りた。
lovegundam.dtiblog.com

形態素解析を行う

今回はkuromojiという日本語の形態素解析器を使うので上記の依存関係などを記述しておく必要がある。

形態素解析が何かはウィキペディア等を参照してほしい。
ライブラリを使うと簡単なので今回はコードのみ紹介する。

import org.atilika.kuromoji.{Tokenizer,Token}
import collection.JavaConversions._
import scala.collection.mutable.{Map,ArrayBuffer}
import scala.io.{Source,BufferedSource}

object NgramMorph{

  private [this] val tokenizer = Tokenizer.builder.mode(Tokenizer.Mode.NORMAL).build
  private [this] val n:Int = 1

  def main(args:Array[String]):Unit = {

    val sourceLine:Iterator[String] = Source.fromResource("san_tmp.dat").getLines
    
    for(line <- sourceLine){
      val tokens = tokenizer.tokenize(line)
      tokens.foreach{ t => 
        val token:Token = t.asInstanceOf[Token]
        println(s"${token.getSurfaceForm}")
      }
    }
  }
}

マルコフ連鎖を用いて会話文を自動生成する

ここではngramとマルコフ連鎖を用いる。
今回はn = 1とする。

import org.atilika.kuromoji.{Tokenizer,Token}
import collection.JavaConversions._
import scala.collection.mutable.{Map,ArrayBuffer}
import scala.io.{Source,BufferedSource}
import java.util.Random


object NgramMorph{

  private [this] val tokenizer = Tokenizer.builder.mode(Tokenizer.Mode.NORMAL).build
  private [this] val n:Int = 1

  def main(args:Array[String]):Unit = {

    val sourceLine:Iterator[String] = Source.fromResource("san_tmp.dat").getLines
   
   
   val ngramMap:Map[String,ArrayBuffer[String]] = Map[String,ArrayBuffer[String]]()
   
    
    //一行ずつ形態素解析をしてngramで分割
    for(line <- sourceLine){
      val tokens = tokenizer.tokenize(line)

      var nowSurface:String = tokens.head.asInstanceOf[Token].getSurfaceForm

      if( !ngramMap.contains(nowSurface) )
        ngramMap += (nowSurface -> ArrayBuffer.empty[String])

      tokens.tail.foreach{ t => 
        val token:Token = t.asInstanceOf[Token]
        var tmpSurface:String = token.getSurfaceForm
        var ngramArray:ArrayBuffer[String] = ngramMap(nowSurface)
        
        ngramArray += tmpSurface

        ngramMap.update(nowSurface,ngramArray)
        if(!ngramMap.contains(tmpSurface))
          ngramMap += (tmpSurface -> ArrayBuffer.empty[String])
        nowSurface = tmpSurface
      }
    }


    //マルコフ連鎖を使って会話文生成
    val rnd:Random = new Random
    var result_str:String = ngramMap.keys.toList(rnd.nextInt(ngramMap.size))

    var tmp_str:String = result_str
    while(!result_str.contains("。")){
      var next_wordArray:ArrayBuffer[String] = ngramMap(tmp_str)
      tmp_str = next_wordArray(rnd.nextInt(next_wordArray.size))
      result_str += tmp_str
    }

    println(result_str)

  }
}

このプログラムを10回動かして得た出力結果は次の通り

きかないもの…。
動きはじめた。
知らせてもここはシシ神さまがおかしいの礼を言いな。
だろう。
においで木をシシ神にこのことも人間のか。
味方だよ。
アシタカ、人間くさい。
味方だ。
けがれるだけだから…。
がんばって。

今回はもののけ姫のサンのセリフを対象に会話文生成を行ったが、前回使用した夏目漱石のこころに比べると圧倒的に量が少ないので微妙な結果になってしまったが形態素解析を用いたので意味不明な文は格段に減少した。

ちなみに前回使った夏目漱石のこころを同様に試すと次のようになった

姿を引いたの驚いたけれども横文字のさせる勇気に、私のです。
捌けた。
邯鄲という意味を読み出しました。
盛り潰そう。
邪魔をできるだけ切り詰めたの様子が一面に、気の外れた室で、因循らしく見える動作はよほど経っていなん。
済まなくなります。
使用さが少しもそれが帰った軽薄に書く事まで書いたと私に、お母さん一週間のようにはすぐ引き受けたので私はいよいよまた、私に向ってもらった。
会いにしてなお目立ちます。
鈍って見に吹き払った。
曇りが、こっそりこの世にもう熱心に気が付くはずが、彼の中に裹まれて植え付けられてくれさえ頼りに取った。

n = 3あたりでやるとうまくいくかもしれない。

n-gramとマルコフ連鎖の理論と実装、もちろんScalaを使って。

対話システムを作りたかった

対話システムという名の対話botを作っているがいきなり深層学習はハードルが高すぎたから人工無能から始めることにした。

この記事の流れ

今回の記事は次のように進んでいく。

と、まぁほとんどがアルゴリズム的な話になりそう。

n-gramとは

n-gramとは形態素解析のように辞書を使って文章を品詞分解していくのではなく「文字単位で文章を分割していく」手法のこと。
なので、形態素解析のように辞書を必要とするわけではない。

またn-gramのnが何を指すかというとn文字で分割するという意味である。


1-gramは1文字ずつ分割する。
2-gramは2文字ずつ分割する。
3-gramは3文字ずつ分割する。

みたいに。

実際には次のように分割していく。

文章:今日は雨のようだ。
条件:n = 2とする

分割:
今日
日は
は雨
雨の
のよ
よう
うだ
だ。

ただここで問題なのがnが小さすぎるとその自然言語にもよるが不適切な結果を生むことに成る。

文章:東京都庁
条件:n = 2

分割:
東京
京都
都庁

n-gramを使って文字列分割を行うと本来想定している最適解とは異なる場合がある。
今回で言えば、「東京都庁」という意味を持つのに本来の意味とかけ離れた「京都」が出てしまうなど。

そこで日本語の文章を分割するときはn=3を想定するっぽい。
簡単故にこれを実際の会話で使う文章生成に使うと割と精度が下がる。

n-gramのサンプル

今回は、「青空文庫」さんから夏目漱石の「こころ」をお借りしました。
事前にutf-8にしてあれこれ邪魔な記述を抜かして使用します。

これに対してn = 3の時のn-gram、つまりtri-gramで分割しました。

ソースコードは次の通り。

import scala.io.Source
import scala.io.BufferedSource
import scala.collection.mutable.Map

object Ngram{

  //3文字ずつ分割していく
  private [this] val n:Int = 3

    
  def main(args:Array[String]):Unit = {
      
      //文字列とその出現頻度を格納
      var ngramMap:Map[String,Int] = Map[String,Int]()
      

      //ファイルを読み込む
      val source = Source.fromFile("kokoro.dat","utf-8")

      //1行ずつ読み込む
      val lines:Iterator[String] = source.getLines

      //ngramで分割し格納
      for(line <- lines){

        var tmp_line:String = line

        while(tmp_line.length >= this.n){
          
          var subString:String = tmp_line.take(this.n)

          //切り出した文字列が今までに出てないなら追加
          //出現しているなら出現回数の更新
          if(!ngramMap.contains(subString)){
            ngramMap += (subString -> 1)
          }else{
            var count:Int = ngramMap(subString) + 1
            ngramMap.update(subString, count)
          }
          
          //先頭文字の除去
          tmp_line = tmp_line.tail
        }

      }

      val result_key:Iterable[String] = ngramMap.keys
      for(key <- result_key){
        println(s"${key} ${ngramMap(key)}")
      }
            
  }

}


これをコンパイルして次のように実行する。

$ scala Ngram | sort -r -nk2 | head

そうすると、よく使われる部分文字列ベスト10が切り出せた。

部分文字列 出現回数
した。 1464
ました 1026
った。 856
です。 789
のです 776
かった 593
たので 562
なかっ 470
ってい 397
奥さん 386

語尾とか接続詞的なあれこれは頻度高いのわかるが「奥さん」…。

マルコフ連鎖とは

マルコフ連鎖とは、ある事象がその直近の事象のみに影響を受けて確率的に変化するという考えかた。
これにはマルコフ性という、次に起こる事象が過去に起きた事象の影響を受けないという性質がなければならない。

もっと言えば、マルコフ性を備えた確率過程のことをマルコフ過程といい、その中でも状態空間が連続ではなく離散的である場合を特にマルコフ連鎖という。

身近な例を上げるなら、すごろくや人生ゲームといったものが一種のマルコフ連鎖の例と言える。

今回はこれを自然言語処理、特にn-gramで分割したものに対して適用する。

n-gramマルコフ連鎖を使った文章生成

本来は確率を使ってどうこうするけど、Scalaでそれをやってしまうと処理速度的に心配なので次に出てくる文字列をひたすら追加しそこからランダムで選択することにした。

それが次のコード

import scala.io.{Source,BufferedSource}
import scala.collection.mutable.{Map,ArrayBuffer}
import scala.util.Random

object Markov{

  //tri-gramを想定
  private [this] val n:Int = 3

  def main(args:Array[String]):Unit = {

    //ngramの分割結果と次に続く文字列を格納する
    var ngramMap:Map[String,ArrayBuffer[String]] 
      = Map[String,ArrayBuffer[String]]()

    //ファイルから一行ずつ読み込む
    val source:BufferedSource = Source.fromFile("kokoro.dat","utf-8")
    val lines:Iterator[String] = source.getLines


    //ngramで分割
    for(line <- lines){

      var tmp_line:String = line
      var split_str:String = tmp_line.take(this.n)

      //先頭文字列だけ独立して追加
      if(!ngramMap.contains(tmp_line.take(this.n)))
         ngramMap += ( split_str -> ArrayBuffer.empty[String] )

      tmp_line = tmp_line.tail

      while(tmp_line.length >= this.n){
        
        var ngramArray:ArrayBuffer[String] = ngramMap(split_str)
        ngramArray += tmp_line.take(this.n)
        ngramMap.update(split_str,ngramArray)
        
        if( !ngramMap.contains(tmp_line.take(this.n)) )
          ngramMap += (tmp_line.take(this.n) -> ArrayBuffer.empty[String])

        split_str = tmp_line.take(this.n)
        tmp_line = tmp_line.tail
      }
    }


    //先頭文字列選択を行う
    val rnd:Random = new Random
    var result_str:String = ngramMap.keys.toList(rnd.nextInt(ngramMap.size)) 

    var tmp_str:String = result_str
    while(!result_str.contains("。")){
      var next_wordArray:ArrayBuffer[String] = ngramMap(tmp_str)
      tmp_str = next_wordArray(rnd.nextInt(next_wordArray.size))
      result_str += tmp_str.last
    }


    println(result_str)

  }
}

これを実行することによって得たいくつかの文章は次の通り
ひどい文もできていたので比較的ましなものを選択した。

叔父だの叔母だの、その性質としてよかった。
耳に異様な調子をもっと底の方に沈んだ心を大事そうに聞いた。
端書を受けない事はできないかと疑ってみました。
かも彼らは、退屈のために箒で背中を向けた。
今東京へ出て来たといって褒めるのですから、私には分りませんでした。
生と異なる点を明白に述べなければ純白でなくっちゃなるまですでに妻を迎えたらしい。
父に万事をやっ付けて離さない悠長な田舎にありませんでした。
思うかと、奥さんをどうしてもいいました
酸にも聞こえる試しはまるで頼りにするのは定めていた私が、それは迷惑そうな顔をちょっと顔だけ向け直して来て、いつの間にか暮れて春になりました。
まだ起きているのであった。

ngramだと単語が意味を持たないので、計算コストは低いけど出来上がる文が時折変な文になってしまう。
マルコフ連鎖を採用しているのも原因の一つであるけど。


対話botへの応用

これをどう対話botに応用するかといえば、今回はngramとマルコフ連鎖を使ったわけだがそれを例にするなら
ngramで分割する対象データをtwitterfacebookといった比較的人が会話で使う構造をしているものにするといったことが考えられる。
文章生成に関してはこのままマルコフ連鎖で生成できる。

自分が発話した内容に関してもngramを用いてどんどんデータを追加していくとなおさら面白いかもしれない。