今回もCodeKataをKotlinでやっていきたいと思います。
「そもそもCodeKataって何？」と言う方は"CodeKataをKotlinでやってみた 〜Karate Chop編〜"をご参照ください。
トライしてみる
今回の課題は21あるKataのうち14つ目に当たる"Tom Swift Under the Milkwood"です。
Trigram analysis is very simple. Look at each set of three adjacent words in a document. Use the first two words of the set as a key, and remember the fact that the third word followed that key. Once you’ve finished, you know the list of individual words that can follow each two word sequence in the document. For example, given the input:
I wish I may I wish I might
You might generate:
"I wish" => ["I", "I"]
"wish I" => ["may", "might"]
"may I" => ["wish"]
"I may" => ["I"]
This says that the words “I wish” are twice followed by the word “I”, the words “wish I” are followed once by “may” and once by “might” and so on.
To generate new text from this analysis, choose an arbitrary word pair as a starting point. Use these to look up a random next word (using the table above) and append this new word to the text so far. This now gives you a new word pair at the end of the text, so look up a potential next word based on these. Add this to the list, and so on.....
つまり、Victor Appletonさんの小説"Tom Swift and His Airship"を対象にtrigramアルゴリズムを適用することで、「オリジナルのなんちゃってTom Swift文体を生成してみよう!」というのが今回の課題となります。
trigramアルゴリズムとは
trigramとは、任意の文字列が3文字だけ続いた文字列のことである。
任意の文書や文字列などにおける任意のn文字の連続は、n-gramと呼ばれる。この内、1文字続きのものはunigram、2文字続きのものはbigram、3文字続きのものはtrigram、と特に呼ばれ、4文字以上のものは、単に4-gram、5-gramと表現されることが多い。
（引用：weblio辞書-trigram）
CodeKataの課題説明にもtrigramについての説明がありますが、要するに「ある文章において、特定の二単語の後に出現することのある単語を次の単語に設定する」というアルゴリズムです。実際にCodeKataで参照されていた例を用いて確認してみます。
I wish I may I wish I might
例えば、"I wish"という2単語が与えられた際、上記文章において"I wish"の後に続く可能性がある単語は"I"のみなので、trigramを1回適用すると結果は"I wish I"となります。この結果に再度trigramを適用する場合には、最後の2単語"wish I"を見ることで次に続く単語"may/might"を確認することができるので、結果は"I wish I may"/"I wish I might"となります。
実装
class Trigram(sentence: String) {
// storing sentence passed as argument as List
private var sentenceList: List<String> = sentence.split(" ")
// storing word relationship as Map i.e. {I wish=[I, I], wish I=[may, might], I may=[I], may I=[wish]}
// above map is saying "the two words 'wish I' is followed by the words 'may, might' in the sentence"
private val wordMap: Map<String, List<String>> = generateWordMap()
// sentence generated with trigram algorithm
private var generatedSentence: MutableList<String> = getFirstTwoWords()
/**
* generate wordMap which stores word relationship
*/
private fun generateWordMap(): Map<String, List<String>> =
sentenceList.dropLast(2)
.mapIndexed { index, it -> listOf(it, sentenceList[index + 1], sentenceList[index + 2]) }
.groupBy ({ "${it[0]} ${it[1]}" }, {it[2]})
/**
* execute trigram algorithm repeatedly until sentence size reaches "length"
*/
fun execute(length: Int) {
while (generatedSentence.size < length) {
try {
// when the nextWord has valid word option to be followed,
// pick that word and add that word to "generatedSentence"
val nextWord = getNextWord(getLastTwoWords())
generatedSentence.add(nextWord)
} catch (e: IllegalArgumentException) {
// when the nextWord doesn't have valid word option to be followed,
// rollback "generatedSentence" to one step before and undo one count
generatedSentence.removeLast()
continue
}
}
// print the result of trigram algorithm processing
println(generatedSentence.joinToString(" "))
}
/**
* randomly get first two words which will be origin of trigram algorithm
*/
private fun getFirstTwoWords(): MutableList<String> {
val startIndex = (0 until sentenceList.lastIndex).random()
return sentenceList.slice(startIndex..startIndex + 1).toMutableList()
}
/**
* get last two words of "generatedSentence" to pick a next word following
*/
private fun getLastTwoWords(): String =
"${generatedSentence[generatedSentence.lastIndex - 1]} ${generatedSentence[generatedSentence.lastIndex]}"
/**
* get a next word by referring last two words passed as argument "key"
*/
private fun getNextWord(key: String): String {
val wordOption = wordMap.getByKey(key)
val randomIndex = (0..wordOption.lastIndex).random()
return wordOption.elementAt(randomIndex)
}
companion object {
/**
* get value by key assuring return type is "List<String>", not "List<String>?"
*/
private fun Map<String, List<String>>.getByKey(key: String): List<String> {
return this[key] ?: throw IllegalArgumentException("invalid item passed: $key")
}
}
}
trigramの対象とする文章をTrigramインスタンス生成の際に引数として渡してもらい、そのインスタンスに対してexecuteメソッドを呼んでもらうことでアルゴリズムを適用します。
sentenceListは対象となる文章をリストにしたもの（例えば[I, wish, I, may, I, wish, I, might]）、wordMapは単語の対応関係をMapとして保持するもの（例えば{I wish=[I, I], wish I=[may, might], I may=[I], may I=[wish]}）、generatedSentenceはtrigramアルゴリズム適用で生成された文章となりますが、インスタンス生成時にgetFirstTwoWordsメソッドで対象文章内からランダムに起点となる連続する2単語を設定するようにしています。
executeメソッドでは引数としてInt型を渡すことで生成される文章の単語長を指定できます。例えば、trigram.execute(10)とすると生成文章の単語数が10単語になるまでtrigramアルゴリズムの適用を繰り返します。
executeメソッド内ではwhileを使ってアルゴリズムの連続適用を実装してみました。try節では生成文章の終端2単語を参照し、元文章でその2単語に連続している箇所が存在する単語を生成文章に加えています。もし連続する単語の候補が複数ある場合には、ランダムでどちらかの単語を設定するようにしてみました。
catch節では終端2単語に連続する単語が元文章で存在しないケースをハンドルしています。例えば、冒頭で取り上げた文章"I wish I may I wish I might"はもし終端2単語に"I might"が設定されてしまうと次に設定する単語の候補が存在しません。このような場合には、"might"を生成文章から削除し、再度削除後の終端2文字を参照することでアルゴリズムの際適用を行うようにしています。
テストケース整備
それではテストケースを整備してアルゴリズムが意図通り動作しているか確認してみます。テストケースは2つ用意していて、1つ目はブログ内でも例として取り上げられていた文章、2つ目は実際の"Tom Swift and His Airship"の文章を対象としてtrigramアルゴリズムを適用しています。
class TomSwiftTest {
@Test
fun testTrigram1() {
val trigram = Trigram("I wish I may I wish I might")
trigram.execute(10)
}
@Test
fun testTrigram2() {
val story = File("resources/TomSwift.txt").readText()
val trigram = Trigram(story)
trigram.execute(1000)
}
}
最初の2文字をランダムにしているので毎回生成文章は異なりますが、例えばそれぞれ下記のように出力されます。
// by testTrigram1
I may I wish I may I wish I might
// by testTrigram2
"Hello!" exclaimed our hero. As Tomturned the corner on which the gang
of bad men. These included Ferguson Appleson, Anson Morse, Wilson Featherton,
alias Simpson, Jake Burke, alias HappyHarry, who sometimes masqueraded as
a strongman, now," observed Mr. Damon."Don't hold that view, I beg of you.
Bless my spark-plug, but ......
Victor Appletonさんの文体に慣れ親しんでいないため個人では判断ができませんが、小説の文体的な雰囲気を持った文章を生成できているように見えます。ひとまずこれで成功としたいと思います。
まとめ
前回の[CodeKataをKotlinでやってみた 〜Counting Code Lines編〜]
(https://qiita.com/Takuyaaaa/items/cb9143fbcb9e0b2a7822)に続き、今回もこれまでと比較すると難易度が高めだと思いました。
実装の改善点として、現状ではもしexecuteのcatch節でロールバックが行われた際に単語の候補が一つしか存在しない場合、最初にランダムに設定される2単語に続く単語の候補が存在しない場合の考慮が漏れているといった点があるなと思っています。
お読みいただきまして、ありがとうございました！
関連記事一覧
- CodeKataをKotlinでやってみた 〜Karate Chop編〜
- CodeKataをKotlinでやってみた 〜Data Munging編〜
- [CodeKataをKotlinでやってみた 〜Bloom Filters編〜]
(https://qiita.com/Takuyaaaa/items/eaa3848bce3bccdd946f) - [CodeKataをKotlinでやってみた 〜Anagrams編〜]
(https://qiita.com/Takuyaaaa/items/df06e24e6f2c7f8ced35) - [CodeKataをKotlinでやってみた 〜Checkout編〜]
(https://qiita.com/Takuyaaaa/items/0a4b82e30c977444c0bc) - [CodeKataをKotlinでやってみた 〜Sorting it Out編〜]
(https://qiita.com/Takuyaaaa/items/b5210c53bff3ff5f0512) - [CodeKataをKotlinでやってみた 〜Counting Code Lines編〜]
(https://qiita.com/Takuyaaaa/items/cb9143fbcb9e0b2a7822) - [CodeKataをKotlinでやってみた 〜Tom Swift Under the Milkwood編〜]
(https://qiita.com/Takuyaaaa/items/feccf69d2b9d95196a72) - [CodeKataをKotlinでやってみた 〜Transitive Dependencies編〜]
(https://qiita.com/Takuyaaaa/items/9b43473b8feffe1ce9f7) - [CodeKataをKotlinでやってみた 〜Word Chains編〜]
(https://qiita.com/Takuyaaaa/items/2539338252ad7e19ba18) - [CodeKataをKotlinでやってみた 〜Simple Lists編〜]
(https://qiita.com/Takuyaaaa/items/36ef73522bfe8d054448)