TOP > 研究報告検索 > 文字列の方程式を解く

文字列の方程式を解く

研究報告コード R070000116
整理番号 R070000116
掲載日 2008年4月11日
研究者
  • 篠原 歩
研究者所属機関
  • 九州大学大学院システム情報科学研究院
研究機関
  • 九州大学大学院システム情報科学研究院
報告名称 文字列の方程式を解く
報告概要 インターネットの発展を背景として膨大なデータが蓄積されているが、特にXMLフォーマットの導入は、あらゆる情報を計算機と人間の双方に可読な文字列として表現することによって協調的な知的生産性を高めようとするものであり、大量のテキストデータを効率よく処理するための技術はますます重要になっている。パターン照合をはじめとした文字列処理に関する研究は、これまでも深く研究されてきたが、そこで用いられる手法は文字列としての性質を巧みに利用して文字列処理に特化されたものであり、他方で膨大な研究の蓄積がなされている数値演算とはほとんど無関係である。テキストデータの分類や、大量のテキストデータに潜む規則の発見など、知的な文字列処理を行うための操作の大部分は計算量的に困難な問題を内包しており、これらを現実的な時間で近似していくためには、「文字列」に対する新しい視点が必要であると考える。本研究は、文字列として与えられる情報を、そのまま離散的な値としてではなく、連続的な数値としてとらえるための枠組みを開発し、その上でさまざまな文字列操作を数値演算として実装できるようにするための基礎理論の構築を目的としている。
画像

※ 画像をクリックすると拡大します。

R070000116_01SUM.gif
研究分野
  • 解析学
関連発表論文 (1) Shunsuke Inenaga, Masayuki Takeda, Ayumi Shinohara, Hiromasa Hoshino, and Setsuo Arikawa, "The Minimum DAWG for All Suffixes of a String and its Applications", Proc. 13th Ann. Symp. on Combinatorial Pattern Matching (CPM2002), Lecture Notes in Computer Science 2373, pp. 153-167, Springer-Verlag, July 2002.
(2) Kensnke Baba, Ayumi Shinohara, Masaynki Takeda, Shunsnke Inenaga, and Setsuo Arikawa , "A Note on Randomized Algorithm for String Matching with Mismatches", Proc. The Prague Stringology Conference '02 (PSC'02), pp. 9-17, Czech Technical University, September 2002.
(3) Shunsnke Inenaga, Ayumi Shinohara, Masayuki Takeda, and Setsuo Ankawa, "Compact Directed Acyclic Word Graphs for a Sliding Window", Proc. 9th International Symposium on String Proceseing and Information Retrieval (SPIRE2002) , Lecture Notes in Computer Science 2476, pp. 310-824, Springer-Verlag, September 2002.
(4) Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Hideo Bannai, and Setsuo Arikawa, "Space-Economical Construction of Index Structures for All Suffixes of a String", Proc. 27th Inter. Symp. on Mathematical Foundation of Computer Seience (MFCS2002), Lecture Notes in Computer Science 2420, pp. 341-352, Springer-Verlag, August 2002.
(5) Shunsuke Inenaga, Ayumi Shinohara, "Bidirectional Construction of Suffix Trees" Prague Stringology Conference 2002 (PSC'02) pp.75-87, September 2002.
(6) Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, Masayuki Takeda, and Setsuo Arikawa, "Discovering Best Variable-Length- Don't-Care Patterns", Proc. 5th International Conference on Discovery Science (DS2002), Lecture Notes in Computer Scienee 2534, pp. 86-97, Springer-Verlag, November 2002.
(7) Satoru Miyamoto, Shunsuke Inenaga, Masayuki Takeda, and Ayumi Shinohara, "Ternary Directed Acyclic Word Graphs", Proc. Eighth International Conference on Implementation and Application of Automata (CIAA2003) , Lecture Notes in Computer Science 2759, pp. 120-130, Springer-Verlag, July 2003.
(8) Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, and Masayuki Takeda, "Inferring Strings from Graphs and Arrays", Proc. 28th International Symposium on Mathematical Foundations of Computer Science (MFCS2003), Lecture Notes in Computer Science 2747, pp. 208-217, Springer-Verlag, August 2003.
(9) Kensnke Baba, Satoshi Tsuruta, Ayumi Shinohara, and Masayuki Takeda "On the Length of the Minimum Solution of Word Equations in One Variable", Proc. 28th International Symposium on Mathematical Foundations of Computer Science (MFCS2003), Lecture Notes in Computer Science 2747, pp. 189-197, Springer-Verlag, August 2003.
(10) Tetsuya Nakatoh, Kensuke Baba, Daisnke Ikeda, Yasuhiro Yamada, and Sachio Hirokawa "An Efficient Mapping for Scores of String Matching" Proc. Prague Stringology Conference '03 (PSC '03), pp. 127-136, Czech Technical University, 2003.
(11) Shunsuke Inenaga, Takashi Funamoto, Masayuki Takeda, and Ayumi Shinohara, "Linear-Time Off-Line Text Compression by Longest-First Substitution", Proc. 10th International Symposium on String Processing and Information Retrieval (SPlRE 2003), Lecture Notes in Computer Science 2857, pp. 137-152, Springer-Verlag, October 2003.
(12) Zdenek Tronicek and Ayumi Shinohara, "The Size of Subsequence Automaton", Proc. 10th International Symposium on String Processing and Information Retrieval (SPIRE 2003), Lecture Notes in Computer Science 2857, pp, 304-310, Springer-Verlag, October 2003.
(13) Kensuke Baba, Yoshihito Tanaka, Tetsuya Nakatoh, and Ayumi Shinohara "A Generalization of FFT Algorithms for String Matchingi", Proc. International Symposium on Information Science and Electrical Engineering 2003, pp. 191-194, November 2003.
(14) Heikki Hyyroe, Kimmo Fredriksson, Gonzalo Navarro, "Increased Bit-Parallelism for Approximate String Matching" Proc. The Third International Workshop on Experimental and Efficient Algorithms (WEA2004), Lecture Notes in Computer Science 3059, Springer-Verlag, May, 2004.
(15) Heikki Hyyroe, Ayumi Shinohara "Bit-Parallel LCS-length Computation Revisited" Proc. 15th Australasian Workshop on Combinatorial Algorithms (AWOCA2004), July, 2004.
(16) Hideo Bannai, Heikki Hyyroe, Ayumi Shinohara, Masayuki Takeda, Kenta Nakai, Satoru Miyano "Finding Optimal Pairs of Patterns" Proc. 12th International Conference on Intelligent Systems for Molecular Biology /3rd European Conference on Computational Biology (ISMB/ECCB2004), July, 2004
(17) Heikki Hyyroe, "A note on bit-parallel alignment computation" Proc. Prague Stringology Conference '04 (PSC'04), pp.79-87, August, 2004.
(18) Hideo Bannai, Heikhi Hyyroe, Ayumi Shinohara, Masayuki Takeda, Kenta Nakai, Satoru Miyano "Finding Optimal Pairs of Patterns" Proc. 4th Workshop on Algorithms in Bioinformatics (WABI2004), pp. 450-462, September, 2004.
(19) Shunsuke Inenaga, Hideo Bannai, Heikki Hyyroe, Ayumi Shinohara, Masayuki Takeda, Kenta Nakai, Satoru Miyano "Finding Optimal Pairs of Cooperative and Competing Patterns with Bounded Distance" Proc. The 7th International Conference on Discovery Science (DS2004), pp.32-46, October, 2004.
(20) Heikki Hyyroe, "An Improvement and an Extension on the Hybrid Index for Approximate String Matching" Proc. The Eleventh Symposium on String Processing and Information Retrieval (SPIRE2004), pp.208-209, October, 2004.
(21) Heikki Hyyro, Jun Takaba, Ayumi Shinohara, Masayuki Takeda "On Bit-Parallel Processing of Multi-byte Strings" Proc. The first Asia Information Retrieval Symposium (AlRS2004), October, 2004.
(22) Shunsuke Inenaga, Ayumi Shinohara and Masayuki Takeda. "An efficient pattern matching algorithm on a subclass of context free grammars", Proc. Eighth International Conference on Developments in Language Theory (DLT04), Lecture Notes in Computer Science 3340, pp. 225-236, Springer-Verlag, December, 2004.
(23) Heikld Hyyroe, Yoan Pinzon and Ayumi Shinohara. "Fast Bit-Vector Algorithms for Approximate String Matching under Indel-Distance" Proc. The 31st Annual Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2005), Lecture Notes in Computer Science, Springer-Verlag, January, 2005.
(24) Kensuke Baba, Ayumi Shinohara, Masayuki Takeda, Shunsuke Inenaga, and Setsuo Arikawa "A Note on Randomized Algorithm for String Matching with Mismatches", Nordic Journal of Computing, Vol. 10, pp. 2-10, 2003.
(25) 馬場謙介、篠原歩、竹田正幸、稲永俊介、有川節夫 "近似文字列照合のための確率アルゴリズム"、LAシンポジウム,2002.
(26) 中藤哲也、馬場謙介、池田大輔、山田泰寛、廣川佐千男、篠原歩 "近似文字列照合のための決定性アルゴリズム" 第14回データ工学ワークショップ,2003.
(27) 中藤哲也,馬場隊介"近似文字列照合のための効率的なアルゴリズム"日本データベース学会Letters,vol.2 (1),pp.87-90,日本データベース学会,2003.
研究制度
  • 戦略的創造研究推進事業 さきがけタイプ(旧若手個人研究推進事業を含む)/強調と制御
研究報告資料
  • 篠原 歩. 文字列の方程式を解く. さきがけライブ2004 「強調と制御」領域 研究報告会講演要旨集 インタラクションとコミュニケーション ~主観の客観科学を目指して~ (研究期間2001-2004), 2005. p.32 - 38.

PAGE TOP