Mercurial > hg > Members > masakoha > seminar

<!DOCTYPE html>
<html>
<head>
  <meta http-equiv="content-type" content="text/html;charset=utf-8">
  <title>seminar</title>

<!--
   Notes on CSS media types used:

   1) projection -> slideshow mode (display one slide at-a-time; hide all others)
   2) screen     -> outline mode (display all slides-at-once on screen)
   3) print      -> print (and print preview)

   Note: toggle between projection/screen (that is, slideshow/outline) mode using t-key

   Questions, comments?
   - send them along to the mailinglist/forum online @ http://groups.google.com/group/webslideshow
-->

<!-- styles  -->
<style media="screen,projection">

html,
body,
.presentation { margin: 0; padding: 0; }

.slide { display: none;
         position: absolute;
         top: 0; left: 0;
         margin: 0;
         border: none;
         padding: 2% 4% 0% 4%;         /* css note: order is => top right bottom left  */
         -moz-box-sizing: border-box;
         -webkit-box-sizing: border-box;
         box-sizing: border-box;
         width: 100%; height: 100%;    /* css note: lets use border-box; no need to add padding+border to get to 100% */
         overflow-x: hidden; overflow-y: auto;
         z-index: 2;
       }

.slide.current { display: block; }  /* only display current slide in projection mode */

.slide .stepcurrent { color: black; }
.slide .step        { color: silver; } /* or hide next steps e.g. .step { visibility: hidden; } */

.slide {
/*
  background-image: -webkit-linear-gradient(top, blue, aqua, blue, aqua);
  background-image: -moz-linear-gradient(top, blue, aqua, blue, aqua);
*/
}
</style>

<style media="screen">
.slide             { border-top: 1px solid #888; }
.slide:first-child { border: none;  }
</style>

<style media="print">
.slide    { page-break-inside: avoid; }
.slide h1 { page-break-after:  avoid; }
.slide ul { page-break-inside: avoid; }
</style>


<!-- add js lib (jquery) -->
<script src="js/jquery-1.7.min.js"></script>

<!-- S6 JS -->
<script src="js/jquery.slideshow.js"></script>
<script src="js/jquery.slideshow.counter.js"></script>
<script src="js/jquery.slideshow.controls.js"></script>
<script>
  $(document).ready( function() {
    Slideshow.init();

    // Example 2: Start Off in Outline Mode
    // Slideshow.init( { mode: 'outline' } );

    // Example 3: Use Custom Transition
    // Slideshow.transition = transitionScrollUp;
    // Slideshow.init();

    // Example 4: Start Off in Autoplay Mode with Custom Transition
    // Slideshow.transition = transitionScrollUp;
    // Slideshow.init( { mode: 'autoplay' } );
  } );
</script>

</head>
<body>

<div class="presentation">

  <div class='slide cover'>
  <table width="90%" height="90%" border="0" align="center">
  <tr>
  <td><div align="center">
      <h1>Cerium 上での正規表現の実装</h1>
      </div>
  </td>
  </tr>
      <tr>
      <td><div align="right">
          <name>Masataka Kohagura 17th, November , 2015</name>
      </div></td>
      </tr>
  </tr>
  </table>
  </div>

  <div id="cover">
    <h1>研究目的</h1>
    正規表現はオートマトンに変換することができ、 そしてオートマトンの受理の問題は Class NC と呼ばれる問題でもある。<br>
    この問題は計算機の台数が多ければ多いほど高速化できるという特徴を持ち、並列化に向いている問題といえる。<br>
    コンピュータの動作やゲームの動作などの多くの問題はオートマトンの受理問題に落としこむことができるので、この問題を解決すれば様々な問題に対応できるようになる。<br>
    本研究では正規表現の問題を並列処理で実装し、速く処理できるようにする。
        </ul>
  </div>

  <div id="cover">
    <h1>これまで実装しているところ</h1>
    <ul>
      <li>与えられたから正規表現から正規表現の parser tree に変換することはできている。</li>
    </ul>
    <h1>現在していること</h1>
    <p>正規表現の parser tree から subset constraction に変換するプログラムを書いている途中</p>
    <ul>
      <li>まずは parser tree から 決定性オートマトンへの変換</li>
      <li>parser tree を入力すると、リスト構造で構成された決定性オートマトンを返す</li>
      <li>concatenation は実装した </li>
      <li>'|'、'*' は書いている途中</li>
    </ul>
    <p></p>
  </div>

<!--
  <div id="cover">
    <h1>正規表現で生成された二分木を表示</h1>
    <pre>
    <code>
% ./regexParser -regex "test"

            t
        +
            s
    +
        e
 +
    t

% ./regexParser -regex "a*bc"

        c
    +
        b
 +
    *
        a
    </code>
    </pre>
  </div>
  -->


<!--
  <div id="cover">
    <h1>問題点</h1>
    <p>正規表現 a*b の tree 構造(本当はこうなってほしい)</p>

    <object data="images/vector/aastabtrue.svg" type="image/svg+xml"></object><br>
    <p>正規表現 a*b の tree 構造(現状)</p>
    <object data="images/vector/aastabfalse.svg" type="image/svg+xml"></object><br>
  </div>
-->

  <div id="cover">
    <h1>どのようなリスト構造か</h1>
    <pre>
    <code>
typedef struct bitVector {
    int arrayNum;
    unsigned long *bitContainer;
}BitVector,*BitVectorPtr;

typedef struct bitVectorList {
    bitVectorList *self;
    BitVectorPtr bi;
    bitVectorList* initBvl;
    bitVectorList* next[256];
}BitVectorList, *BitVectorListPtr;
    </code>
    </pre>
    <ul>
      <li>BitVectorPtr-&gt;bitContainer に状態を格納する。 </li>
      <li>BitVectorListPtr-&gt;next[c] は 'c' という文字が入力されたときの BitVectorListPtr の遷移先(アドレス)を格納している </li>
      <li> </li>
    </ul>
  </div>

  <div id="cover">
    <h1>図解</h1>
    <p>正規表現の parser tree を決定性オートマトンに変換する</p>
    <p>例) 正規表現 "(a|b)c"</p>
        <ul>
            <object data="images/vector/automaton.svg" width="20%" type="image/svg+xml"></object><br>
        </ul>
    <p>この決定性オートマトンをリスト構造で表現し出力する</p>
        <ul>
            <object data="images/vector/BitVectorList.svg" width="40%" type="image/svg+xml"></object><br>
        </ul>
  </div>

  <div id="cover">
    <h1>'|' が含まれた parser tree をうまく決定性オートマトンに変換できていない問題</h1>
    <p>例) 正規表現 "(a|b)c"</p>
        <ul>
            <object data="images/vector/automaton.svg" width="20%" type="image/svg+xml"></object><br>
        </ul>
    <p> 状態 0100 から 0001 に遷移先がなくなっている</p>
        <ul>
            <object data="images/vector/BitVectorListMiss.svg" width="20%" type="image/svg+xml"></object><br>
        </ul>
  </div>

<!--
  <div id="cover">
    <pre>
    <code>
NodePtr string() {
    char c = *ptr;
    NodePtr n = NULL;
    if (isLiteral(c)) {
        n = createNode(0,literal(),string());
    } else {
        n = createNode(0,0,0);
    }
    return n;
}
    </code>
    </pre>
    <p>string なのか literal なのか判断しないで createNode をしてる</p>
  </div>
-->


<!--
  <div id="cover">
    <h1>今週のしたこと</h1>
    例題 : ab(ab)+
        <ul>
            <object data="images/vector/abab.svg" type="image/svg+xml"></object><br>
        </ul>
        テキストが abab の途中で分割される場合を考える
        <ul>
            <object data="images/vector/ababautomata.svg" type="image/svg+xml"></object><br>
        </ul>
        分割されたファイルの1コ前の終わりが状態(3)の場合で、分割されたファイルの先頭が b の場合状態(4)に遷移して受理される。(正規表現にマッチする)
        <ul>
            <object data="images/vector/ababtable.svg" type="image/svg+xml"></object><br>
        </ul>
        <ul>
            <object data="images/vector/bitvectorTable.svg" type="image/svg+xml"></object><br>
        </ul>
  </div>
-->

<!--
  <div id="cover">
    <h1>prog</h1>
    <ul>
    <li>

    </li>

    <pre>
    <code>
typedef struct SDL_AudioSpec {
    int freq;          /** DSP frequency samples per second */
    Uint16 format;     /** Audio data format */
    Uint8  channels;   /** Number of channels: 1 mono, 2 stereo */
    Uint8  silence;    /** Audio buffer silence value (calculated) */
    Uint16 samples;    /** Audio buffer size in samples (power of 2) */
    Uint16 padding;    /** Necessary for some compile environments */
    Uint32 size;       /** Audio buffer size in bytes (calculated) */
    void (SDLCALL *callback)(void *userdata, Uint8 *stream, int len);
    void  *userdata;
} SDL_AudioSpec;
    </code>
    </pre>
    <img src="./images/sqrWave.png" width="50%" height="">
    </ul>
  </div>

-->

</div> <!-- presentation -->
</body>
</html>
author	Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date	Fri, 27 Nov 2015 11:59:04 +0900
parents	0d280684e31f
children