正規表現型とその効率的な包含関係判定とその応用

• Item type: Trans(1)
• 公開日: 2023-08-28
• タイトル: 正規表現型とその効率的な包含関係判定とその応用
• タイトル / 言語: en
• タイトル: Efficient Inclusion Determination of Regular Expressions for String and Its Applications
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [発表概要, Unrefereed Presentatin Abstract]
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 筑波大学情報学群情報メディア創成学類
• 著者所属: 筑波大学図書館情報メディア系
• 著者所属(英): en
• 著者所属(英): The College of Media Arts, Science and Technology, University of Tsukuba College of Media Arts, Science and Technology, School of Informatics, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): Faculty of Library, Information and Media Science, University of Tsukuba
• 著者名: 大渕, 雄生; 中井, 央
• 著者名(英): Yuki, Obuchi; Hisashi, Nakai
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 多くのプログラミング言語は文字列型を備えている．文字列は内容によって意味に種類がある．一般的には，この種類をプログラミング言語ではチェックすることはなく，そのチェックはコードを記述するプログラマに委ねられている．このことは，たとえばURLを引数として渡すはずであるところにIDを渡してしまうなどのバグを引き起こしたり，代入する変数の間違いによって機密データ文字列が公開データに含まれてしまったりするなどのセキュリティ上の問題を実際に発生させている．本発表ではこのような文字列に対して正規表現自体を一種の「型」と見なして制約をつけることで，より安全かつ堅牢なプログラムの構築を可能にする．また，本発表ではこの正規表現型の包含関係によって，静的型付け言語の継承関係を模倣し，関数オーバロードや静的キャストなどの機能を実装している．正規表現型の包含関係判定の問題は今までXMLスキーマ表現のタイプチェックにおいて応用されてきた．しかし，今回のようにテキスト表現に用いる場合はXMLスキーマ表現の包含関係に用いられてきたアルゴリズムでは計算量において問題がある．XMLスキーマ用のアルゴリズムは，使用されるアルファベット数に比例した時間がかかるため，テキスト表現にそのまま用いてしまうとUnicodeのような大きな文字セット用いることができない．このため本発表ではDFA圧縮の技術を用いてこれを実現するアルゴリズムを提案し，ナイーブなアルゴリズムに対して数十万倍の効率化を行っている．提案した正規表現型の具体的な導入手法と効果を示すために，キャストに関する構文や型チェックのための構文をBashに導入した．これにより，導入された言語での記述例と効果の提示を行った．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Many programming languages have a String type. String type can have different types contents. Such as URLs, Version Numbers or Passwords. In general, programming languages do not check contents of String and let programmers to check thier code. This causes bugs, such as showing an ID when a URL should be displayed, or security problems, such as sensitive data strings being included in public data due to a variable mix-up. This research proposed to think the regular expression itself as a kind of “Type” for strings and imposes restrictions on it, thereby making it possible to construct more secure and robust programs. In addition, this study implements functions such as overloading and static casting by imitating the inheritance relation of statically typed languages by the inclusion relation of this regular expression type. The problem of determining the inclusion relation of regular expression types has been applied to type checking of XML schema. However, the algorithm used for XML schema has a problem in terms of computational complexity when used for String. The algorithm for XML Schema takes time in linear to the number of alphabets. Therefore, it is not possible to use a large character set such as Unicode if it is used for String representation. For, this presentation proposes an algorithm that using DFA compression technology, which is several hundred thousand times more efficient than naive algorithms. In order to show the concrete introduction and effectiveness of the proposed “Regular Expression Type”, a new syntax for casting and a syntax for type checking were/are? introduced into Shell (Bash). This provided an example introducing “Regular Expression Type” to an existing language.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 16, 号 3, p. 30-30, 発行日 2023-08-28
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会