Japanese subtitles

← 03xpsps-01 Fsm Optimization Solution

dummy description

Get Embed Code
3 Languages

Showing Revision 1 created 10/23/2014 by Udacity.

  1. この問題は少し難しいので
    2つ星レベルに分類します
  2. ここでは有限状態機械を最適化していきます
  3. 図のような有限状態機械があったとします
  4. ステート1には受理状態が1つあり
    他にもいくつかステートがあります
  5. 図をよく見て考えてください
  6. bの道を通ってステート2に進めば
    受理状態には行けません
  7. ステート2、ステート3またはステート4から
    ステート1に行く道はなく
  8. この道を行く文字列はどれも失敗に終わります
  9. この状態機械はステート1以外を
    含まないのと同じです
  10. ならばもっとシンプルにしましょう
  11. でも何のためにですか?
  12. Webブラウザを作るために
    多くの正規表現を使ってきました
  13. 正規表現は有限状態機械として表され
    そして処理されます
  14. つまりブラウザの高速化に
    有限状態機械の小型化は必須なのです
  15. ではコードを書いていきます
  16. この有限状態機械の定義を基に考えましょう
  17. まず実行に関係しないステートを識別し
  18. それらを死状態として定義から取り除きます
  19. ただし最適化前に使われていた言語をそのまま保ち
  20. まったく同じ文字列と一致するようにしたまま
    取り除く必要があります
  21. どのように進めるか計画を立てましょう
  22. これが計画です
  23. ステップ1では生状態と死状態を探します
  24. 生状態を探しそれ以外は死んでいると推測します
  25. 具体的な方法はこうです
  26. まずは辞書を反復しすべてのステートを探します
  27. そしてそれぞれのステートに
    nfsmacceptsを実行します
  28. これはレッスン1の宿題に出てきました
  29. 有限状態機械の定義として
  30. 開始ステートと受理状態
    そして遷移の辞書を受け取り
  31. あるステートから受理状態に
    たどりつけるかどうかを見るプロシージャでした
  32. nfsmacceptsに図の定義とステート3を与えると
  33. ステート1には行けず
    つまりどの受理状態にも行けません
  34. ステート1を与えると成功します
  35. これを生と死の定義として
  36. 生状態と死状態を見分けていきます 楽しいですね
  37. ステップ2では死状態を持たない
    新しい有限状態機械を作ります
  38. 賢くきれいな定義を作るために
    注意すべきことがあります
  39. 死状態につながる遷移は含めません
  40. すべての死状態を取り除き
  41. 生状態へとつながらないステートも
    取り除いていきます
  42. 詳細を確認しましょう
  43. 各エッジのステートと辞書のエントリを見ます
  44. 今のステートが死状態なら
    新しい有限状態機械にコピーしません
  45. そうでなければ元の有限状態機械にあった
    すべての行き先を見て
  46. 生状態のものをすべてコピーする準備をします
  47. 生状態がない場合は
    そのエッジを取り除きコピーはしません
  48. 図にあるすべてのステートで
    そのプロセスを繰り返したら
  49. それに基づき受理状態のリストを更新します
  50. 死んでいる受理状態は必要ありません
  51. 解答を見てみましょう
  52. まずレッスン1の宿題からnfsmacceptsのコードを
  53. そっくりそのままコピーしました
    何も変えていません
  54. 次は有限状態機械のトリミングです
  55. 先ほど説明したようにすべてのステートを探します
  56. コピーが存在することもあります
  57. 少しトリミングに時間がかかるかもしれませんが
  58. 実行にかかる時間が節約できれば問題ありません
  59. 各ステートが生きているかどうかは
    nfsmacceptsを実行すれば分かります
  60. もし生きていたら生状態のリストに加えます
  61. では新しいエッジの辞書を作成しましょう
  62. もし古い辞書のエッジの遷移元に生状態があれば
  63. それを基に更新していきます
  64. 新しい行き先を計算し
    死んでいる行き先を取り除くわけです
  65. 古いエッジの行き先が生きていたら
    リストに追加します
  66. しかし新しい有限状態機械に
    新しいエッジを設定するのは
  67. 行き先が空でない場合のみです
  68. どこにも行き着かず失敗するエッジはいりません
  69. エッジが存在しない場合は失敗すると推測します
  70. 最後に受理状態を生きているものだけとする
    更新を加えてください
  71. そして新しいエッジと新しい受理状態の
    タプルを返します
  72. これで完了です
  73. 見てください Trueと出ています
  74. Trueは真です
  75. いいですね すばらしいです