# HG changeset patch
# User Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
# Date 1284356453 -32400
# Node ID f5fb37614d52a967f2bc754da784f4a6144ff618
# Parent  df4ce962e5ce9e2d1f5cf7667ae9eb7ac7b236bd
add utf-8 description

diff -r df4ce962e5ce -r f5fb37614d52 presen/index.html
--- a/presen/index.html	Mon Sep 13 12:18:26 2010 +0900
+++ b/presen/index.html	Mon Sep 13 14:40:53 2010 +0900
@@ -55,7 +55,8 @@
         <ul>
           <li>正規表現は, パターンマッチによるテキストの検索等に利用されている.</li>
           <li>シンプルで保守性に優れ, かつ性能の高い正規表現マッチャを実装したい. </li><br/>
-          <li class="incremental">プログラムの開発は, 生産性の高い言語によって行われることが開発者にとって望ましい.</li><span class="incremental"></span>
+          <li class="incremental">プログラムの開発は, 生産性の高い言語によって行われることが開発者にとって望ましい.</li>
+          <li class="incremental">開発効率 or 実行効率 ?</li><span class="incremental"></span>
         </ul>
       </div>
       <!-- PAGE -->
@@ -75,7 +76,8 @@
           <p>ex: "<blue>(A|B)*C</blue>" -> "A"または"B", の0回以上の繰り返し直後に"C"<span class="incremental">: "C","ABC","ABBBBC"</span></p>
           <li>GNU grep などのテキスト検索ツール等で利用されている.</li>
           <br/><br/>
-          <li class="incremental">正規表現は(NFAを経て)等価なDFA(決定性有限オートマトン)に変換可能.</li><span class="incremental"></span>
+          <li class="incremental">正規表現は(NFAを経て)等価なDFA(決定性有限オートマトン)に変換可能.</li>
+          <li class="incremental">主張: DFAは直接コードで表現できる.</li><span class="incremental"></span>
         </ul>
       </div>
       <!-- PAGE -->
@@ -219,6 +221,7 @@
             <tr><th><strong>LLVM-IR (LLVM)</strong></th><td>0.044s</td><td>0.08s</td><td>0.47s</td></td>
           </table>
           <li>LLVMによるコンパイルが, GCCによるコンパイルに比べ10倍程高速な結果がでた.</li>
+          <li class="incremental">主張: コンパイル速度はあまり重要でない.</li>
         </ul>
       </div>
       <!-- PAGE -->
@@ -228,7 +231,7 @@
           <li>コンパイルされたプログラムの実行速度</li>
           <ul>
             <li>C/CbC/LLVM-IRをコンパイルしたプログラムの実行速度に, あまり差がでなかった.</li>
-            <li class="incremental">3つの生成系は, 生成する言語が違うが, 生成するコードの処理内容は同じ.</li>
+            <li>3つの生成系は, 生成する言語が違うが, 生成するコードの処理内容は同じ.</li>
           </ul>
           <li class="incremental">生成されたコードは, 関数呼び出しとswitch文によるシンプルなプログラムなので, 最適化によって性能の等しいネイティブコードが生成されたためと思われる.</li>
           <li class="incremental">CbCでは, 関数呼び出しより軽量な状態遷移である継続を用いて実装しているため, コンパイラの最適化に依らず性能の高いコードが保証されている -> 生成コードとして最適.</li>
@@ -248,6 +251,7 @@
             <tr><th><blue>simple-regex</blue></th><td>: 単純な正規表現</td></tr>
             <tr><th><blue>complex-regex</blue></th><td>: 複雑な正規表現</td></tr>
             </table>
+            <p class="incremental">"複雑さ" = 変換されたDFAの状態数/遷移規則の多さ.</p>
           </li>
           <!--
           <li>実験環境.</li><br/>
@@ -292,7 +296,6 @@
             パターン　: "<blue style='font-size: 70%;'>(Python|Perl|Pascall|Prolog|PHP|Ruby|Haskell|Lisp|Scheme)</blue>" - <a href="pix/complex-regex.png" target="blank">図</a><br/>
             マッチ行数: 3439028行
           </li>
-          <li class="incremental">"複雑さ" = 変換されたDFAの状態数/遷移規則の多さ.</li>
         </ul>
       </div>
       <!-- PAGE -->
@@ -341,6 +344,30 @@
             <li>同様のパターンで何度もマッチングを行うプログラムと相性が良い.</li>
             <li class="incremental">スパムフィルタの単語検索など.</li>
           </ul>
+          <strong class="incremental">ご清聴ありがとうございました.</strong>
+        </ul>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+        <h1>付録: UTF-8</h1>
+        <ul>
+          <li>Unicodeの符号化形式 -> マルチバイト文字に対応.</li>
+          <li>符号単位は8bit.</li>
+          <li>ASCIIとの互換性を持っている.</li>
+          <li>プログラムでのバイト操作が非常に容易な, 素晴らしい符号化形式.</li>
+          <ul>
+            <li>文字の先頭1ByteでByteが分かる</li>
+            <li>先頭Byteと中間Byteは先頭2bitで判別可能.</li>
+          </ul>
+        </ul>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+        <h1>正規表現: UTF-8</h1>
+        <ul>
+          <li>入力の最小単位として, Unicode文字単位でNFA,DFAを構築すれば良い.</li>
+          <img src="pix/utf-dfa.png" stye="height: 11em;"/>
+          <li class="incremental">GNU grep 2.5.X では, DFAの遷移毎に入力文字に対して mbrtowc() を用いてwchar型への変換を行っている -> ボトルネック (90%以上)</li>
         </ul>
       </div>
     </div>