# HG changeset patch # User Masataka Kohagura # Date 1448593144 -32400 # Node ID b796a4f4c33255cee2e3b09e2eef0c38b5e039b0 # Parent 123b1f3a08336ad2dbba7f2be25e5b7a3b20727e add somefiles diff -r 123b1f3a0833 -r b796a4f4c332 2015/1124.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/2015/1124.html Fri Nov 27 11:59:04 2015 +0900 @@ -0,0 +1,291 @@ + + + + + seminar + + + + + + + + + + + + + + + + + + + + + + + +
+ +
+ + + + + + + + +
+

Cerium 上での正規表現の実装

+
+
+ Masataka Kohagura 4th, August , 2015 +
+
+ +
+

研究目的

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

今日までにしたこと

+
    +
  • とりあえず動くところまではプログラムを直した(若干バグが)
    • +
+

+
+ +
+

現在していること

+

正規表現の parser tree から subset constraction に変換するプログラムを書いている途中

+
    +
  • Parser Tree のノードに word や CharClass を挿れる(今は一文字のみ)
    • +
+

CharClass を Binary Tree で表現する

+
    +
  • 正規表現の Parser Tree のノードに Character Class (例 : [a-z])が含まれている場合、Character Class を二分木で表現する
    • +
+
+
+ +
+

Character Class が正規表現内に複数含まれる場合

+

複数の Character Class の範囲が重複する場合

+
    +
  • Character Class Tree を Merge する
    • +
+ +
+
+
+ + + + + + +
+

どのようなリスト構造か

+ 
+    
+typedef struct bitVector {
+    int arrayNum;
+    unsigned long *bitContainer;
+}BitVector,*BitVectorPtr;
+
+typedef struct bitVectorList {
+    bitVectorList *self;
+    BitVectorPtr bi;
+    bitVectorList* initBvl;
+    bitVectorList* next[256];
+}BitVectorList, *BitVectorListPtr;
+    
+
+
    +
  • BitVectorPtr->bitContainer に状態を格納する。
    • +
  • BitVectorListPtr->next[c] は 'c' という文字が入力されたときの BitVectorListPtr の遷移先(アドレス)を格納している
    • +
    • +
+ +
+ + + + + + + + +
+ + diff -r 123b1f3a0833 -r b796a4f4c332 2015/1127.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/2015/1127.html Fri Nov 27 11:59:04 2015 +0900 @@ -0,0 +1,280 @@ + + + + + seminar + + + + + + + + + + + + + + + + + + + + + + + +
+ +
+ + + + + + + + +
+

Cerium 上での正規表現の実装

+
+
+ Masataka Kohagura +
+
+ +
+

研究目的

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

今日までにしたこと

+
    +
  • とりあえず動くところまではプログラムを直した(若干バグが)
    • +
+
    +
  • 正規表現木のノード内に一文字のアルファベットだけしか入らなかったが、単語をいれれるようにした
    • +
+

+
+ +
+

実装すること

+

正規表現の parser tree から subset constraction に変換するプログラムを書く

+
    +
  • Parser Tree のノードに word や CharClass を挿れる(今は一文字のみ)
    • +
+

CharClass を Binary Tree で表現する

+
    +
  • 正規表現に Character Class (例 : [a-z])が含まれている場合、Character Class を二分木で表現する
    • +
+
+
+ +
+

Character Class が正規表現内に複数含まれる場合

+

複数の Character Class の範囲が重複する場合

+
    +
  • Character Class Tree を Merge し再構築する
    • +
+ +
+
+
+ +
+

直しているところ

+
    +
  • '|' が複数含まれていると正しく正規表現木が構築されない
    • +
  • '()'や'*'直後の単語の先頭文字が Node に含まれない
    • + 
    +    
+%  ./regexParser -regex "(ac|b|aa)*ac"
+regex : (ac|b|aa)*ac
+---Print Node----
+        c(6)
+    +(7)
+        *(5)
+                aa(3)
+            |(4)
+                b(2)
+ |(8)
+    ac(1)
+-----------------
+    
+
    +
+
    +
+
+ +
+

どのようなリスト構造か

+ 
+    
+typedef struct bitVector {
+    int arrayNum;
+    unsigned long *bitContainer;
+}BitVector,*BitVectorPtr;
+
+typedef struct bitVectorList {
+    bitVectorList *self;
+    BitVectorPtr bi;
+    bitVectorList* initBvl;
+    bitVectorList* next[256];
+}BitVectorList, *BitVectorListPtr;
+    
+
+
    +
  • BitVectorPtr->bitContainer に状態を格納する。
    • +
  • BitVectorListPtr->next[c] は 'c' という文字が入力されたときの BitVectorListPtr の遷移先(アドレス)を格納している
    • +
    • +
+ +
+ + + + + + + + +
+ + diff -r 123b1f3a0833 -r b796a4f4c332 2015/images/omni/subsetConstraction.graffle Binary file 2015/images/omni/subsetConstraction.graffle has changed diff -r 123b1f3a0833 -r b796a4f4c332 2015/images/vector/CharClassTree0.pdf Binary file 2015/images/vector/CharClassTree0.pdf has changed diff -r 123b1f3a0833 -r b796a4f4c332 2015/images/vector/CharClassTree0.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/2015/images/vector/CharClassTree0.svg Fri Nov 27 11:59:04 2015 +0900 @@ -0,0 +1,367 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff -r 123b1f3a0833 -r b796a4f4c332 2015/images/vector/CharClassTree1.pdf Binary file 2015/images/vector/CharClassTree1.pdf has changed diff -r 123b1f3a0833 -r b796a4f4c332 2015/images/vector/CharClassTree1.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/2015/images/vector/CharClassTree1.svg Fri Nov 27 11:59:04 2015 +0900 @@ -0,0 +1,467 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff -r 123b1f3a0833 -r b796a4f4c332 2015/images/vector/CharClassTreeMerge.pdf Binary file 2015/images/vector/CharClassTreeMerge.pdf has changed diff -r 123b1f3a0833 -r b796a4f4c332 2015/images/vector/CharClassTreeMerge.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/2015/images/vector/CharClassTreeMerge.svg Fri Nov 27 11:59:04 2015 +0900 @@ -0,0 +1,690 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +