圧縮文字列における最長共通部分文字列および回文を求める多項式時間アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
直線的プログラム(Straight line program, SLP)は単元集合を生成する文脈自由文法の部分クラスとみなすことができ,そこで生成される文字列の長さは,変数の個数nに対して指数的に長くなりうる.そのため,SLPによって圧縮表現された文字列に対してnの多項式時間で効率よく処理を行うには,陽に展開することなく処理を行うことが必要不可欠となる.本研究では,SLPとして表現された2つの文字列の最長共通部分文字列の長さを求める問題をO(n^4log n)時間,O(n^4)領域で解くアルゴリズムを示す.またSLPとして表現された文字列に含まれるすべての回文を検出する問題に対して,O(n^4)時間,O(n^2)領域で解くアルゴリズムを示す.
- 社団法人電子情報通信学会の論文
- 2008-03-03
著者
-
橋本 和夫
東北大学大学院情報科学研究科
-
橋本 和夫
国際電信電話株式会社研究所
-
橋本 和夫
株式会社kddi研究所
-
橋本 和夫
Kddi米国研究所
-
中村 智将
東北大学大学院情報科学研究科
-
松原 渉
東北大学大学院情報科学研究科
-
稲永 俊介
九州大学大学院システム情報科学研究院
-
石野 明
東北大学大学院情報科学研究科
-
篠原 歩
東北大学大学院情報科学研究科
-
石野 明
グーグル株式会社
-
橋本 和夫
Kdd
-
橋本 和夫
知識情報処理グループ・リーダ
-
橋本 和夫
東北大学大学院 情報科学研究科
-
稲永 俊介
九州大学 大学院システム情報科学研究院
関連論文
- タイミングを考慮したリンク解析によるWebトラッキングサイト検知とそのブラックリスト生成
- 構文規則に基づく技術論文からの比較情報抽出に関する検討
- 屋外無線LANを用いた多人数リアルタイム運動計測システムに関する実証実験報告(ユビキタス/ブロードバンドネットワークの品質とメディア品質、品質評価モデル、信頼性とセキュリティ、コンテンツ、インセンティブ、一般)
- サ変名詞を含む複合名詞のアスペクト演算に関する一考察
- PHMIPv6によるハンドオフ管理の性能向上に関する研究(モバイルネットワーク,有線/無線シームレスネットワーク,ネットワーク制御,無線通信一般)
- 網管理エキスパートシステムのためのSNMP通信スタブ生成ツールの設計
- 協調フィルタリングにおける評価値予測アルゴリズムを応用した検索式拡張手法
- D-15-25 類似検索技術を応用した学術論文情報配信システム
- 特別寄稿 第13回電波功労賞を受賞して 2.4GHz帯高速無線アクセス網の開発、実用化 (第13回電波功労賞)
- 誤認識訂正のための繰返し音声検出手法
- 学習分野別の共起語情報を用いた学習情報の検索手法の検討
- 文書自動分類手法を用いた有害情報フィルタリングソフトの開発
- 非適合プロファイルを利用した文書フィルタリング手法
- B-7-41 無線アクセスを用いた教育用ネットワークの構築(5) : 伝送劣化検出と周波数切替手法の検討
- B-7-40 無線アクセスを用いた教育用ネットワークの構築(4) : トラヒック収集装置の構成
- B-7-39 無線アクセスを用いた教育用ネットワークの構築(3) : IP ネットワークの構成と機能
- B-7-38 無線アクセスを用いた教育用ネットワークの構築(2) : CFO-SSシステムを用いた教育用無線IPネットワークの構築
- B-7-37 無線アクセスを用いた教育用ネットワークの構築(1) : 全体概略
- モバイルコミュニケーション環境においてマルチソースストリーミングを実現するためのハンドオフ方式の提案(フォトニックネットワークシステム,光ルーティング,ブロードバンドアプリケーション,一般)
- DNS監視による異常クライアントの検知(オーバーレイネットワーク,VPN,DDoS,ネットワークセキュリティ,P2P通信,ネットワークソフトウェア,一般)
- モバイルコミュニケーション環境においてマルチソースストリーミングを実現するためのハンドオフ方式の提案(モバイルネットワーク,トラヒック,ポストIPネットワーキング,プロトコル・ネットワーク制御,ネットワーク予測・解析,一般)
- SSL/TLSで暗号化されたWeb通信に対する侵入検知システム(セキュリティ/危機管理,新しいパラダイムの中での分散システム/インターネット運用・管理)
- B-7-15 大規模DNSサーバのための異常検知方式の提案(B-7. 情報ネットワーク,一般セッション)
- 圧縮文字列における最長共通部分文字列および回文を求める多項式時間アルゴリズム
- VANET環境における協調衝突回避システムの改善(無線,オーバーレイネットワーク,VPN,DDoS,ネットワークセキュリティ,P2P通信,ネットワークソフトウェア,一般)
- モバイルネットワークにおけるマルチソースストリーミング方式の提案(TCP,配信サービス,オーバーレイネットワーク,VPN,DDoS,ネットワークセキュリティ,P2P通信,ネットワークソフトウェア,一般)
- ページ閲覧時間を考慮したWebログマイニング手法の提案
- ページ閲覧時間を考慮したWebログマイニング手法の提案 (「Web Intelligence」および一般発表)
- 優先度を考慮したルータ主導型TCP輻輳制御方式の提案(デモ,ポスターセッション,VPN, NAT,ネットワークセキュリティ,DDoS, P2P及び一般)
- ハンドオフを考慮したRTP/RTCP通信におけるレート制御手法(VPN, NAT,ネットワークセキュリティ,DDoS, P2P及び一般)
- 分散型フィードバックによる階層型Mobile IPv6の負荷分散方式(VPN, NAT,ネットワークセキュリティ,DDoS, P2P及び一般)
- 確率的時間論理に基づくフォールトモデルを用いた診断方法
- アラーム伝播のモデル化についての検討
- AICを用いた因果関係抽出手法の性能評価
- 2項分布モデルを用いた実時間疎通劣化検出手法の評価
- テキスト検索のための相関ルールの発見
- 因果関係発見手法の性能評価実験
- 因果関係発見手法の検討
- 半導体歩留り解析へのデータマイニング適用手法の提案
- 実時間疎通劣化検出方式のための2項分布モデル更新手法
- 大量文書向けのクラスタリング手法の評価
- ベイジアンクラスタリング用類似値評価関数の高速化の検討
- 類似ドキュメントの発見手法の検討
- C言語プログラム検査ツールの実装と適用結果
- BS-4-2 プライバシーを考慮した分散認証法の提案(BS-4.ユビキタスネットワークにおけるネットワークセキュリティ,シンポジウムセッション)
- A-7-2 ユビキタス環境での安全なプライバシー情報の交換についての検討(A-7.情報セキュリティ,一般セッション)
- 擬似学習集合の生成による決定木の再構成手法と学習特性
- 実時間エキスパートシステム
- スタック型忘却随伴メモリメンテナンスシステムの動特性について
- テキスト検索のための相関ルールの発見
- 人の暮らしと自然のICTに基づいた共生へ向けて-「Kurihara」グリーンプロジェクト-
- 人の暮らしと自然のICTに基づいた共生へ向けて-「Kurihara」グリーンプロジェクト-
- 知識の更新と忘却機構に関する検討
- 人の暮らしと自然のICTに基づいた共生へ向けて-「Kurihara」グリーンプロジェクト-
- 事例に基づく定性的知識から定量的知識への変換手法の検討
- 知識ベースの保守支援機能に関する検討
- ガバナ間の共起関係学習のための基礎実験
- E-023 テキストマイニングを用いたサッカー勝敗分析記事からの評判分析(E分野:自然言語・音声・音楽,一般論文)
- L-036 分散認証基盤を活用したプライベート情報交換アーキテクチャの提案(L分野:ネットワーク・セキュリティ,一般論文)
- F-048 系列ルールマイニングにおいて時間差を考慮する確信度の提案(人工知能・ゲーム,一般論文)
- 履歴診断エキスパートシステムのための状態推定方式の提案
- シミュレーテッドアニーリングを用いた定量的知識から定性的知識への写像関数最適化手法の評価
- シミュレーテッドアニーリシグを用いた定量的知識から定性的知識への写像関数の最適化
- 実時間網管理への定性的診断知識の適用手法
- G-020 ベイジアンネットワークを用いた生活習慣分析(G分野:生体情報科学,一般論文)
- 2ZL-3 項目応管理論に基づく健康診査における質問項目分析(バイオインフォマティクスと医療,学生セッション,コンピュータと人間社会,情報処理学会創立50周年記念)
- 5W-2 構文規則に基づく特許文書からの比較情報抽出に関する検討(言語情報抽出,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- 3W-2 アンサンブル学習におけるHoeffding Treeを用いた動的な分類器統合法(学習(2),学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- E-006 技術論文からの比較情報抽出(自然言語・音声・音楽,一般論文)
- RF-005 数値データストリームからの決定木導出(人工知能・ゲーム,査読付き論文)
- RA-002 オリエンテーリングにおける最適経路導出問題のための走行時間予測モデル(モデル・アルゴリズム・プログラミング,査読付き論文)
- 漢字仮名変換を用いた仮名漢字変換率評価
- 漢字仮名変換を用いた仮名漢字変換率評価 : 大規模テキストを対象とした仮名漢字変換評価システムの構成と性能評価
- アスペクト遷移モデルの提案
- 属性集合が可変な場合における決定木学習方式
- パケット通信網利用者支援エキスパ-トシステム
- 深い知識利用局面において必要とされるユーザインタフェースについて
- 決定木の符号長計算方式の検討
- リアルタイムプランニングにおける応答時間特性の解析手法
- 適応型リアルタイムプランニングを用いた状態依存型ダイナミックルーティングに関する検討
- 大量文書向けのクラスタリング手法の評価
- 時区間論理に関する一検討(4)
- 時区間論理に関する一検討(3)
- 時区間論理に関する一検討(2)
- 栗原グリーンプロジェクト - 環境負荷低減型のまちづくりを目指したICTシステムの構想 -
- 栗原グリーンプロジェクト - 広域分散地域におけるエネルギー管理システム -
- 栗原グリーンプロジェクト - グリーン指向管理情報ベース(G-MIB) -
- 栗原グリーンプロジェクト - スマートフォンを用いたパークアンドライド支援システム -
- 栗原グリーンプロジェクト - 環境負荷低減のための生活支援システム -
- Socio-familiar Personalized Serviceの提案とその応用 : 次世代ユビキタスサービスを実現するネットワークソフトウェアへ向けて(ネットワークソフトウェア技術とその応用論文)
- 移動経路を共有するソーシャルネットワークサービスの構想
- 位置情報を用いた拡張現実アプリケーションの開発
- 個人情報を活用した人にやさしいサービスの実現方法に関する検討
- パーベイシブ環境におけるサービスの個人化とその応用
- 半導体歩留り解析に回帰木分析を適用するための仮説検証手法の提案
- 1-5 インターネットコンテンツの配信・管理技術(1.情報爆発時代における通信の果たす役割とその未来像,情報爆発時代に向けた新たな通信技術-限界打破への挑戦-)
- 利用者が所有する個人情報を活用したサービス横断的個人化方式の提案(ポストIPネットワーキング,新世代ネットワーク,ネットワークモデル,インターネットトラヒック,TCP/IP,マルチメディア通信,ネットワーク管理,リソース管理,プライベートネットワーク,NW安全性及び一般)
- 半導体歩留り解析のための回帰木に基づく仮説検証手法の提案
- 能動学習における決定境界の安定性の検討(学習法,統計推理,データベース,一般)
- M-012 放射線量を可視化するスマートフォンアプリケーション「シーベルト」の開発(実環境センシング,M分野:ビキタス・モバイルコンピューティング)