# HG changeset patch # User Masataka Kohagura # Date 1447752065 -32400 # Node ID f9293af3d474eb532c9e1952707f77a83ec2e083 # Parent e8fd8c7d22c2d9d0ee1c0ca761f709d91f1e0ea2 add 1117.html diff -r e8fd8c7d22c2 -r f9293af3d474 2015/1113.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/2015/1113.html Tue Nov 17 18:21:05 2015 +0900 @@ -0,0 +1,270 @@ + + + + + seminar + + + + + + + + + + + + + + + + + + + + + + + +
+ +
+ + + + + + + + +
+

Cerium 上での正規表現の実装

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

研究目的

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

現在していること

+

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

+
    +
  • まずは parser tree から 決定性オートマトンへの変換
    • +
  • プログラム実行時に正規表現を入力すると、決定性オートマトンのリスト構造を返す
    • +
  • concatenation は実装した
    • +
  • '|'、'*' は書いている途中
    • +
+

+
+ + + + + + +
+

どのようなリスト構造か

+ 
+    
+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 e8fd8c7d22c2 -r f9293af3d474 2015/1117.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/2015/1117.html Tue Nov 17 18:21:05 2015 +0900 @@ -0,0 +1,270 @@ + + + + + seminar + + + + + + + + + + + + + + + + + + + + + + + +
+ +
+ + + + + + + + +
+

Cerium 上での正規表現の実装

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

研究目的

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

現在していること

+

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

+
    +
  • まずは parser tree から 決定性オートマトンへの変換
    • +
  • プログラム実行時に正規表現を入力すると、決定性オートマトンのリスト構造を返す
    • +
  • concatenation は実装した
    • +
  • '|'、'*' は書いている途中
    • +
+

+
+ + + + + + +
+

どのようなリスト構造か

+ 
+    
+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 の遷移先(アドレス)を格納している
    • +
    • +
+
+ + + + + + + + +
+ +