最長重複文字列問題 を scala をつかって解いてみる

先日 買った WEB+DB vol.67 の 「関数プログラミング」の中の記事
記事の中では Haskell を使って問題を解いているのですが、
scala の勉強の為 同じ問題を scala を使って考えてみました。

まだ scala のお作法 わかってないので ドキュメント見ながらの結果オーライになってます。。。

今回の 最長重複文字列問題だけの部分だけでなく 特集全体で 関数プログラミングの考え方の記事として
非常に興味深い記事となっています。

WEB+DB PRESS Vol.67

最長重複文字列問題

最も長く重複している部分文字列を探しだす問題らしい。
もともとは『珠玉のプログラミング』にある文字列の問題。

例えば 今回の題材の場合 mississippi という文字列があった場合、
この文字列の中で 重複している最大の 部分文字列としては issi という文字列になります。

これを以下のような手順で解いていきます。

1. 接尾辞リストを作る
2. ソートする
3. 隣合う要素を組にする
4. 組となっている２つの文字列の共通部分の長さを求める
5. 共通部分が一番長い要素を取り出す
6. 共通部分のみを残す

これらを scala つかって同じように作って行きたいと思います。

接尾辞リストを作る

今回の問題を解く 鍵となる 接尾辞リストの作成ですが、scala でも tails を使って作成出来そうです。
tails の結果は Iterator型なので toList にて結果を List 型にしました。

val moji = "mississippi"
moji.tails.toList

この方法がいいのかはわかりませんが

scala> moji.tails.toList
res0: List[String] = List(mississippi, ississippi, ssissippi, sissippi, issippi, ssippi, sippi, ippi, ppi, pi, i, "")

こういう 接尾辞リストとしたかったので こうやってみました。

ソートする

リスト型は sorted メソッドを持っているのでこれを使ってソートします。

moji.tails.toList.sorted

scala> moji.tails.toList.sorted
res1: List[String] = List( "", i, ippi, issippi, ississippi, mississippi, pi, ppi, sippi, sissippi, ssippi, ssissippi)

隣合う要素を組にする

隣り合う組通しを ペアにします。
これは 記事と同じように makepair というペアを作る関数を作ってみます。
ここは 定番の zip を使っています。

def makepair(list1:List[String]) = list1.zip(list1.tail)

scala> makepair(res1)
res2: List[(String, String)] = List( ( "",i), (i,ippi), (ippi,issippi), (issippi,ississippi), (ississippi,mississippi), (mississippi,pi), (pi,ppi), (ppi,sippi), (sippi,sissippi), (sissippi,ssippi), (ssippi,ssissippi))

組となっている２つの文字列の共通部分の長さを求める

組となっている２つの文字列の共通部分を求めるのに、comlen という関数をつくってみます。
この関数は (文字,文字) というタプルを引数として、受け取る関数で 文字列の共通部分の長さを返します。
scala でどうやるのが効率的か思いつかなかったので、記事の Haskell と同じような方法でやってみました。 toList メソッドで List 型に変換して 二つのリストを zip で処理し その後 takeWhile をつかって タプルの 一番目の値と二番目が同じものを選びリストにし その配列の長さを length メソッドをつかって求めます。

ここは 正直この方法がscala としていいのかわかりません。
ほかの簡単な方法も思いつかなかったので 記事と同じようにリストとして扱って
共通部分の長さを求めてみました。
これより scala なりの別のよい方法があるのかもしれません。

def comlen(t:(String,String)):Int = {
	 t._1.toList.zip(t._2.toList).takeWhile{tp => (tp._1 == tp._2)}.length
}

共通部分が一番長い要素を取り出す

こちらも chooseMax 関数を作って実行します。
この 関数は (文字,文字) のタプルのリストを引数としてとり、その中から 共通部分の長さの一番大きなものを取り出します。
こちらは maxBy をつかって タプルの一番目の要素の一番大きなものを抽出しております。

def chooseMax(plist:List[(String,String)]) = {
	  plist.map{t => (comlen(t),t._1)}.maxBy(_._1)
}

共通部分のみを残す

共通部分のみを取り出す 関数 extract も用意します。
こちらも タプルを引数として受け取り 二番目の文字から一番目の数字の数だけ取り出します。
この処理には take をつかっております。
List1.take(3) だと List1から3つの要素と取り出すことになります。

scala> "hogehoge".take(3)
res3: String = hog

こんな風なかんじ

def extract(t1:(Int, String)):String = {t1._2.take(t1._1)}

まとめ ソース

// 最長重複文字列 を 抽出する
// maxcomstr.scala
 
val moji = "mississippi"
println(moji)

// 隣合う要素を組にする関数
def makepair(list1:List[String]) = list1.zip(list1.tail)

// 組となっている２つの文字列の共通部分の長さを求める関数
def comlen(t:(String,String)):Int = {
	 t._1.toList.zip(t._2.toList).takeWhile{tp => (tp._1 == tp._2)}.length
}

// 共通部分が一番長い要素を取り出す関数
def chooseMax(plist:List[(String,String)]) = {
	  plist.map{t => (comlen(t),t._1)}.maxBy(_._1)
	}

// 共通部分のみ抽出する関数
def extract(t1:(Int, String)):String = {t1._2.take(t1._1)}

// moji.tails.toList.sorted にて 
// 接尾辞リストを作ってソートした結果を関数に渡し結果を出力
println("Max common Strings : " + extract(chooseMax(makepair(moji.tails.toList.sorted))))

実行結果

% scala maxcomstr.scala
mississippi
Max common Strings : issi