短縮記述された文字列上での多項式時間照合アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
直線的プログラムによって短縮記述された文字列についての照合問題を考察する.通常,このようにして表される文字列の真の長さは,その記述長nに対して指数的に長い.この問題に対して我々は,文献[6]において,O(n^7)時間照合アルゴリズムを与えた.本稿では,これを改良し,O(n^4log n)時間アルゴリズムを実現する.
- 一般社団法人情報処理学会の論文
- 1995-07-28
著者
-
篠原 歩
九州大学理学部基礎情報学研究施設
-
Karpinski Marek
Institute Of Informatics Warsaw University
-
篠原 歩
九大 大学院システム情報科学研究院
-
Rytter Wojciech
Department of Computer Science, University of Bonn
-
Rytter Wojciech
Department Of Computer Science University Of Bonn
関連論文
- 九州大学における一般情報処理教育支援システムについて
- 質問学習における学習可能性の統一的特徴づけ
- Learning pattern languages using queries
- Learnability of Subsequence Languages
- 順序付き二分法定グラフの学習可能性
- 反駁PAC学習可能性
- 並列知識獲得システムBONSAI Garden
- 薬剤取り違え防止のための医薬品名類似性指標 (特集 「医療及び化学情報マイニング」および一般)
- 1変数文字列方程式の最小解の長さの上限
- 圧縮されたテキスト上のパターン照合 : データ圧縮とパターン照合の新展開
- 断片パターンマッチングの計算量的困難性と近似アルゴリズムについて
- 平衡直線的プログラムに対するパターン照合アルゴリズム
- 2G-2 圧縮テキストに対する文字列照合のための統一的枠組み
- 2G-1 データ圧縮による文字列照合の高速化
- BONSAI : 決定木とインデックス化による文字列からの機械発見システム
- 無矛盾最小OBDD問題の近似困難性について
- ゲノムデータベース(5)配列データからの知識発見
- LZW圧縮テキストに対する高速文字列照合アルゴリズム
- コンピュ-タの推論による知識発見の支援(情報) (ゲノムサイエンス--生命の全体像の解明をめざして) -- (第1部 日本におけるヒト・ゲノム研究の最前線)
- 短縮記述された文字列上での多項式時間照合アルゴリズム
- ALT '94報告
- ゲノム情報における機械学習の計算量 : 理論と実際 (「人工知能技術における計算量」)
- 学習アルゴリズムによるアミノ酸のインデックス化とタンパク質データからの知識獲得実験
- PAC 学習 : 確率的で近似的に正しい学習 (計算的学習理論とその応用)