非明示的表現に対するアルゴリズムの開発

隐式表示算法的开发

• 批准号: 16092220
• 负责人: 篠原 歩
• 金额: $ 9.22万
• 依托单位: Tohoku University (2005-2007)Kyushu University (2004)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas
• 财政年份: 2004
• 资助国家: 日本
• 起止时间: 2004 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-16092220/
• 关键词: 最大共通部分文字列; 回文構造; 文字列圧縮; フィボナッチ文字列; アルゴリズム; 文字列照合; XML; 索引構造; 文字列処理; データ圧縮; 非明示的表現; 文字列照合アルゴリズム; データ構造; パターン照合; パターン発見; 最長共通部分列; ビット並列化; 文法圧縮

本研究は,非明示的に表現されたオブジェクトに対するアルゴリズムの開発とその計算量の解析を行うことを目的し,また同時に,効率のよいアルゴリズムの開発に適した非明示的な表現法を文字列やグラフなどの離散構造を対象として研究を展開してきた.具体的には,直線的プログラムとして圧縮表現された文字列を対象として,繰り返し構造や共通部分を検出する問題に取り組んだ.直線的プログラムは,文字列の連結を基本命令とした代入式の列であり,種々の文法圧縮,辞書式圧縮を抽象化したものである.もしもこの直線的プログラムからもとの文字列を陽に展開してしまうと,その長さは指数的に長くなりうるため,決して多項式時間で処理を行うことができない.我々は文字列に内在する組み合わせ構造や周期に着目することにより,圧縮文字列に含まれる回文構造の検出や,最大共通部分文字列の計算を多項式時間で行うアルゴリズムを開発した.また,漸化式として表される文字列の性質を調べた.隣接2項の漸化式で表されるフィボナッチ文字列を一般化し,隣接n項の漸化式でn-ボナッチ文字列を定義した.本研究では,任意のn≧2に対して,無限n-ボナッチ文字列における第k項目の有限n-ボナッチ文字列の最大連続出現数はk→∞のとき2+1/(φ(n)-1)に収束することを証明した.ここに,φ(n)はn-ボナッチ定数であり,特にφ(2)=(1+√<5>)/2は黄金比として知られている.さらに,nを増加させると,最大連続数はちょうど3に近づくことを示した.

This study aims to analyze the computational quantities of the unexplicit expression, the literal expression, the discrete structure and the open structure of the efficiency. Specific to the straight line, the compression expression, the text column, the image, the structure, the common part, the problem, the group. Straight line of text links basic commands substitution columns grammatical compression lexicographical compression abstract. The length of the index is the length of the line, and the polynomial time is the processing line. In the case of a character string, the structure of the group is combined with the structure of the period, and the structure of the reduced character string is combined with the structure of the palindrome, and the calculation of the maximum common part of the character string is performed in polynomial time. The nature of the text string is adjusted. Generalization of adjacent 2-term progressive expression, definition of adjacent n-term progressive expression. In this paper, we prove that the maximum number of consecutive occurrences of an arbitrary n ≥ 2 pairs of infinite n-ここに,φ(n)はn-ボナッチ定数であり,特にφ(2)=(1+√<5>)/2は黄金比として知られている. In the evening,n is increased, and the maximum number of consecutive lines is increased.

项目成果

XML文書フィルタリングのための軽量な高速化技法

XML文档过滤的轻量级加速技术

• 发表时间: 2007
• 期刊: 第18回データ工学ワークショップ(DEWS2007)
• 作者: 御手洗 秀一;他2名
• 通讯作者: 他2名

Fully Incremental LCS Computation

全增量LCS计算

• 发表时间: 2005
• 期刊: Lecture Notes in Computer Science(Proc.the 15th International Symposium on Fundamentals of Computation Theory) 3623
• 作者: Yusuke Ishida;他3名
• 通讯作者: 他3名

Improving Time and Space Complexity for Compressed Pattern Matching

提高压缩模式匹配的时间和空间复杂度

• 发表时间: 2006
• 期刊: Proc.17^<th> International Symposium on Algorithms and Computation
• 作者: Shirou Maruyama;他2名
• 通讯作者: 他2名

Approximate Point Set Pattern Matching on Sequences and Planes

序列和平面上的近似点集模式匹配

• 发表时间: 2004
• 期刊: Proceeding of the 15th Annual Symposium on Combinatorial Pattern Matching(CPM 2004) LNCS 3109
• 作者: 大崎 純;西脇眞二;Heikki Hyyro et al.;Ayumi Shinohara;Shunsuke Inenaga et al.;Tomoaki Suga et al.
• 通讯作者: Tomoaki Suga et al.

On Bit-Parallel Processing of Multi-byte Text

多字节文本的位并行处理

• DOI: 10.1007/978-3-540-31871-2_25
• 发表时间: 2004
• 作者: Heikki Hyyrö;Jun Takaba;A. Shinohara;M. Takeda
• 通讯作者: M. Takeda