Swiftで作る！マルコフ連鎖を使った文章ジェネレーター

マルコフ連鎖とは、現在の状況から確率的に次の状態が決まる「マルコフ過程」の中でも、その変わりうる状態の数が有限のもののことを指します。端的にいうと「確率の連鎖」といった感じです。

マルコフ連鎖を使うと、まるで人間が書いたようなリアルな文章なのに意味が通じない、という面白い文章を生成できます。

今回は、マルコフ連鎖の文章ジェネレーターを、Swiftを使って実装する方法とそのアルゴリズムをご紹介します。ちなみに、本記事では英語の文章を扱います。

＞＞今回使うコードをまとめたものはこちら

マルコフ連鎖を用いた文章ジェネレーターとは

オートマトン（状態機械）という言葉を聞いたことがありますか？ トリガーとなるイベントを受け取ると、現在の状態に応じたアクションを行い、次の状態へ遷移するシステムをいいます。

マルコフ連鎖はオートマトンの一種で、それぞれの遷移（状態の変化）に起こり得る確率が関連づけられます。

一度始まると、始点から終点に行き着くまで、それぞれの確率に沿って遷移を繰り返します。

これがよく応用されるのが、文章生成システムです。文章を入力すると、ひとつの単語を1ユニットとして、単語から単語へと遷移する確率を分析します。そしてその確率に沿って遷移を行い、ランダムな文章を生成します。

生成される文章は意味が通じないことが多いですが、たまに面白い文章が出来上がることもあります。

表記方法

連鎖内のノードは、Wordクラスのインスタンスとして扱われます。クラス内には、単語を保存するStringと、他の単語へのリンクがあります。

リンクを保存するデータ構造はいくつかあります。

最良と思えるアプローチは、Wordインスタンスとそれが現れた回数を保存することでしょう。そして、0からトータルセット数の間でランダムな数字を生成し、リンクに到達するまでイテレートします。しかしこの方法では時間がかかります。

別のデータ構造としては、インスタンスの発生回数を列に保存し、ランダムに生成した数字を元にバイナリサーチする方法が挙げられます。実装は少し難しいですが早く動作します。

ここで紹介するのは、空間計算量の効率を完全に無視した、でも動作が早くて割と簡単に実装できる方法です。

それぞれのWordにサブシークエントのWordを列として保存します。そしてインスタンスが発生するたびに、Wordのコピーを列に追加していきます。あとは、列からランダムなエレメントを選ぶだけで発生確率に合った出力になります。

Wordクラスの例がこちらです。

class Word {
   let str: String?
   var links: [Word] = []
   init(str: String?) {
      self.str = str
   }
   func randomNext() -> Word{
      let index = arc4random_uniform(UInt32(links.count))
      return links[ Int(index)]
   }
}

気をつけて欲しいのは、links列が多くの循環参照を作り出してしまい、メモリーリークに繋がってしまう可能性があることです。それを回避するために列を手動で解放する必要があります。

この解放を行うのが、Chainクラスです。

class Chain {
   var words: [String?: Word]  [ : ]

deinit内でlinks列を解放します。

   deinit {
      for word in wods.values {
         word.links = [ ]
      }
   }

このステップを含めないとメモリーリークが発生してしまいます。

それぞれのwordsを追加するには、String列を受け取るaddメソッドを使います。

   func add(_ words: [String]) {

wordsがない場合はリターンしましょう。

      if words.isEmpty { return }

次に、連続するwordsをペアごとにイテレートします。たとえば、”Help, I’m being oppressed”という入力なら、（”Help”, “I’m”）、（”I’m”, “being”）、（”being”, “oppressed”）という風にです。

そして実装する際は、文章の始まりと終わりを示す「nil」を使います。つまり、（nil, “Help”）、（”Help”, “I’m”）、（”I’m”, “being”）、（”being”, “oppressed”）、（”opressed”, nil）となります。

nilを使うためには、StringではなくString?を使います。

      let words = words as [String?]

次に、nilを最初と最後に繋げるためにふたつの列を作ります。

      let wordPairs = zip([nil]  + words, words + [nil])
        for (first, second) in wordPairs {

それぞれのwordsを繋げるためのヘルパー関数を使って、Wordオブジェクトをフェッチします。

         let firstWord = word(first)
         let secondWord = word(second)

あとはsecondWordをfirstWordに付け足すだけです。

         firstWord.links.append(secondWord)
      }
   }

ヘルパー関数は、words辞書から存在するwordをフェッチします。もしインスタンスが辞書に存在しない場合は、words辞書にインスタンスを追加します。

   func word(_ str: String?) -> Word {
      if let word = words[str] {
         return word
      } else {
         let word = Word(str:str)
         words[str] = word
         return word
      }
   }

そして、ここからはランダムな文章を生成します。

   func generate() -> [String] {

wordsをひとつひとつ生成して、resultに保存します。

      var result: [String] = []

無限ループを使い文章を生成します。終了するコンディションは、ループ内で定義します。

      while true {

Wordインスタンスを、resultの最後に追加します。

         let currentWord = word(result.last)

次のwordsをランダムに選択します。

         let nextWord = currentWord.rancomNext()

終了するコンディションですが、もしリンクされたwordsが文章の最後ならループ終了、そうでない場合はresultに追加します。

         if let str = nextWord.str {
            result.append(str)
         } else {
            break
         }
      }

そして完成した文章をリターンします。

      return result
   }
}

wordsの型としてString?を使っていますが、OptionalはHashableに対応していません。これを解決するためのエクステンションコードがこちらになります。

extension Optional: Hashable where Wrapped: Hashable {
   public var hasValue: Int {
      switch self {
         case let wrapped?: return wrapped.hashValue
         case .none: return 42
      }
   }
}

文章の入力

マルコフ連鎖は、実際に使ってみることに面白さがあります。

そこで、筆者自身のブログからRSSフィード形式で文章を引用することにしました。

let feedURL = URL(string: "https://www.mikeash.com/pyblog/rss.py?mode=fulltext")!

RSSはXMLの一種なので、XMLDocumentを使って文章を読み込みます。

let xmlDocument = try! XMLDocument(contentsOf: feedURL, options: [ ])

ブログの本文は、XMLファイルのitemノードにある、descriptionの中にあります。XPathを使ってこれを抽出します。

let descriptionNodes = try! xmlDocument.nodes(forXPath: "//item/description")

抽出したいのは文章のみなので、nilはスキップします。

let descriptionHTMLs = descriptionNodes.compactMap({ $0.stringValue})

本文だけを抽出するために、NSAttributedStringを使ってHTMLのマークアップを分離します。

let descriptionStrings = descriptionHTMLs.map({
   NSAttributedString(html: $0.data(using: .utf8)!, options: [:], documentAttributes: nil)!.string
})

ここで、全文を細かいstringに分ける関数を見てみましょう。このプログラムでは、文章がString列に保存されます。なので、wordSequences関数でString列の列をリターンします。

func wordSequences(in str: String) -> [[String]] {

そしてresultを保存します。

   var result: [[String]] = [ ]

Stringを一文ごとに分けるのは簡単ではありません。たとえば「Mr. Jock, TV quiz Ph.D., bags few lynx.」は一文ですが、ピリオドは4つあります。

句読点を正しく理解するために使うのがNSStringです。strで文章の数を数えて、Foundationで句読点を解析して文章ごとに分けます。

   str.enumerateSUbstrings(in: str.startIndex..., options: .bySentences, { substring, substringRabge, enclosingRange, stop in

文章を単語に分けるときも同じような問題が起こります。そしてNSStringで単語の数を数えることはできません。そこで、ここではスペースを基準として単語を数えることにしました。

句読点を含む単語は完全に分離できないというデメリットはありますが、一方でアウトプットがより自然な文章になるというメリットがあります。

改行文字もここで切り離します。

      let words = substring!.split(separator: " ").map({
         $0.trimmingCharacters(in: CharacterSet.newlines)
      })

そして分けられた文章をresultに追加します。

      result.append(words)
   })
   return result
}

さて、ここでメインコードに戻ります。stringを文章と単語に分ける関数がある今、マルコフ連鎖を実装する時が来ました。まずは空のChainオブジェクトを作ります。

let chain = Chain()

そして関数を使いstringを文章と単語に分け、Chainに追加します。

for str in descriptionStrings {
   for sentence in wordSequences(in: str) {
      chain.add(sentence)
   }
}

あとはランダムな文章を生成するだけです。generate関数で単語を選択して、スペースを間に挟んでつなげていきます。

うまい文ができるかは運次第なので、アウトプットは複数生成します。

for _ in 0 ..< 200 {
   print("\”” + chain.generate().jointed(separator: “ “) + “\””)
}

実際にマルコフ連鎖で文章を生成してみた

これが実際に生成された文章です。

• “We’re ready to be small, weak references in New York City.”
• “It thus makes no values?”
• “Simple JSON tasks, it’s wasteful if you can be.”
• “Another problem, but it would make things more programming-related mystery goo.”
• “The escalating delays after excessive focus on Friday, September 29th.”
• “You may not set.”
• “Declare conformance to use = Self.init() to detect the requested values.”
• “The tagged pointer is inlined at this nature; even hundreds of software and writing out at 64 bits wide.”
• “We’re ready to express that it works by reader ideas, so the decoding methods for great while, it’s inaccessible to 0xa4, which takes care of increasing addresses as the timing.”
• “APIs which is mostly a one-sided use it yourself?”
• “There’s no surprise.”
• “I wasn’t sure why I’ve been called ‘zero-cost’ in control both take serious effort to miss instead of ARC and games.”
• “For now, we can look at the filesystem.”
• “The intent is intended as reader-writer locks.”
• “For example, we can use of the code?”
• “Swift’s generics can all fields of Swift programming, with them is no parameters are static subscript, these instantiate self = cluster.reduce(0, +) / Double(cluster.count)”
• “However, the common case, you to the left-hand side tables.”

意味が通じない文章が大半ですが、たくさんトライすることで面白い文章が生成されるかもしれません。

最後に

さまざまな分野に応用されているマルコフ連鎖ですが、文章生成では時に面白いものが生み出されることがあります。

このコードから学べることは、方向が曖昧な循環参照、NSStringを使った文章の切り離し、そして異なる型での順応です。

この機会に、是非ともマルコフ連鎖を使って面白い文章生成にチャレンジしてみてください！

ちなみに今回のコードをまとめたものがこちらになります。

class Word {
   let str: String?
   var links: [Word] = []
   init(str: String?) {
      self.str = str
   }
   func randomNext() -> Word{
      let index = arc4random_uniform(UInt32(links.count))
      return links[ Int(index)]
   }
}

class Chain {
   var words: [String?: Word]  [ : ]
   deinit {
      for word in wods.values {
         word.links = [ ]
      }
   }
   func add(_ words: [String]) {
      if words.isEmpty { return }
      let words = words as [String?]
      let wordPairs = zip([nil]  + words, words + [nil])
      for (first, second) in wordPairs {
         let firstWord = word(first)
         let secondWord = word(second)
         firstWord.links.append(secondWord)
      }
   }
   func word(_ str: String?) -> Word {
      if let word = words[str] {
         return word
      } else {
         let word = Word(str:str)
         words[str] = word
         return word
      }
   }
   func generate() -> [String] {
      var result: [String] = []
      while true {
         let currentWord = word(result.last)
         let nextWord = currentWord.rancomNext()
         if let str = nextWord.str {
            result.append(str)
         } else {
            break
         }
      }
      return result
   }
}

extension Optional: Hashable where Wrapped: Hashable {
   public var hasValue: Int {
      switch self {
         case let wrapped?: return wrapped.hashValue
         case .none: return 42
      }
   }
}

let feedURL = URL(string: "https://www.mikeash.com/pyblog/rss.py?mode=fulltext")!
let xmlDocument = try! XMLDocument(contentsOf: feedURL, options: [ ])
let descriptionNodes = try! xmlDocument.nodes(forXPath: "//item/description")
let descriptionHTMLs = descriptionNodes.compactMap({ $0.stringValue})
let descriptionStrings = descriptionHTMLs.map({
   NSAttributedString(html: $0.data(using: .utf8)!, options: [:], documentAttributes: nil)!.string
})

func wordSequences(in str: String) -> [[String]] {
   var result: [[String]] = [ ]
   str.enumerateSUbstrings(in: str.startIndex..., options: .bySentences, { substring, substringRabge, enclosingRange, stop in
      let words = substring!.split(separator: " ").map({
         $0.trimmingCharacters(in: CharacterSet.newlines)
      })
      result.append(words)
   })
   return result
}

let chain = Chain()

for str in sedcriptionStrings {
   for sentence in wordSequences(in: str) {
      chain.add(sentence)
   }
}

for _ in 0 ..< 200 {
   print("\”” + chain.generate().jointed(separator: “ “) + “\””)
}