非巡回正規表現に対する効率的なパターン照合
スポンサーリンク
概要
- 論文の詳細を見る
正規表現は,アルファべットΣの文字と,結合"・"と選択"|"だけから構成されるとき,非巡回正規表現(acyclic regular expression)と呼ばれる.本稿では,非巡回正規表現のクラスに対して,長さmと深さdをもつ非巡回正規表現と長さnをもつ入力テキストを入力として受け取り,O(md)の前処理時間とO(md/w)領域を用いて,O(nmd/w)時間で正規表現照合問題を解く効率よいアルゴリズムを与える.このために,正規表現と等価な非決定性有限オートマトン(NFA)の状態遷移計算をビット演算と加減算を用いて模倣する分配集積演算と呼ぶビット並列計算手法を開発し,WuとManberらのSHIFT-AND手法(CACM 35(10), 1992)を,非巡回正規表現パターンに拡張している.本結果は,定数深さの非巡回正規表現に対して,O(m/w)領域を達成しつつ,一般の正規表現照合に対するBilleのアルゴリズム(ICALP, 2006)のよりも時間計算量が小さい.
- 2010-05-12
著者
-
有村 博紀
北海道大学大学院情報科学研究科
-
湊 真一
北海道大学大学院情報科学研究科
-
湊 真一
函館五稜郭病院
-
湊 真一
Ntt光ネットワークシステム研究所
-
金田 悠作
北海道大学大学院情報科学研究科
-
湊 真一
Ntt 未来ねっと研
-
湊 真一
北海道大学大学院情報科学研究科:科学技術振興機構erato湊離散構造処理系プロジェクト
-
有村 博紀
北海道大学
-
湊 真一
北海道大学大学院情報科学研究科・科学技術振興機構erato湊離散構造処理系プロジェクト・ /科学技術振興機構erato湊離散構造処理系プロジェクト・北海道大学大学院情報科学研究科
-
Minato Shin-ichi
Graduate School Of Information Science And Technology Hokkaido University
-
湊 真一
北海道大学大学院情報科学研究科:科学技術振興機構
-
湊 真一
Ntt光ネットワーク研究所
-
湊 真一
北海道大学 大学院情報科学研究科
関連論文
- BDD上の命題化計算に基づくEMアルゴリズム
- 木の最適ラベリング問題とその進化系統樹への応用
- 接尾辞木を用いた圧縮尺度計算による効率よいスパムポスト検出手法(ポスターセッション,iDBフォーラム2008(招待講演・ポスター英語ディスカッション))
- 極小出現を用いた頻出多部エピソードの効率のよい発見アルゴリズム (特集 「知見の創出を目指した情報技術」および一般)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム (コンピュータシステム)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム (VLSI設計技術)
- 数値データからの意外な回帰結合ルールの発見
- XQUBE:具体例と演示からのXQuery問合せ構築のための視覚言語(セッション6c:問合せ処理・インデクシング)
- Flexcastによる段階的導入に優れたマルチキャストシステムの設計と実装(ネットワーク・並列分散システムソフトウェア, システム開発論文)
- Flexcastに基づくマルチキャストシステムの開発とその方式設計について(映像通信,コンテンツ配信ネットワーク,マルチキャスト,一般)
- An EM algorithm for inferring geographic transmission probability tables from a large phylogenetic tree (特集 「ベイジアン・ネットワーク」および一般)
- D-4-18 高速ストリーム処理のための文字列パターン照合手法とそのFPGA設計(D-4. データ工学,一般セッション)
- D-1-7 並列ビット分配にもとづいた効率的な正規表現照合アルゴリズム(D-1.コンピュテーション,一般セッション)
- 非巡回正規表現に対する効率的なパターン照合
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- 頻出順序木パターンを見つけるオンラインアルゴリズム (計算機科学基礎理論の新展開)
- 滑走窓や忘却の概念を用いたオンライン型半構造データマイニングアルゴリズム
- 滑走窓や忘却の概念を用いたオンライン型半構造データマイニングアルゴリズム
- 半構造データマイニングのための部分構造パターンの効率的探索
- D-1-6 動的刈り込み接尾辞木を用いた圧縮尺度計算によるスパム検出(D-1. コンピュテーション,一般セッション)
- ウェブ閲覧における効率的なキーワード抽出とその利用
- 4ZK-7 ブラウジング支援のための一覧性の高いキーワードリストの抽出(情報爆発時代におけるテキストデータ処理,学生セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- プロパティ接尾辞木のオフライン線形時間構築アルゴリズム(構造化文書・XML,データ工学論文)
- D-020 プロパティ接尾辞木 : メタデータ付き系列データのための効率よい索引構造(D分野:データベース)
- プロパティ付き接尾辞木の効率よいオフライン構築について
- LA_002 単語幅を制約した接尾辞木の効率のよい構築アルゴリズム(A分野:モデル・アルゴリズム・プログラミング)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 効率良い正規表現照合のための並列ビット分配にもとついたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- WWWからの情報抽出 : Webラッパーの自動構築(WWW上の情報の知的アクセスのためのテキスト処理)
- テキストマイニングにおける最適パターン発見
- テキストマイニングにおける最適パターン発見(データ・テキストマイニング)
- ウェブデータマイニング(「データマイニング特集号」)
- HTMLからのテキストの自動切り出しアルゴリズムと実装
- 分散記憶型並列計算機における大規模接尾辞配列の構築法
- テキストマイニングを用いたウェブデータからのキーワード獲得
- 分散記憶型並列計算機における大規模接尾辞配列の構築法
- HTMLからのテキストの自動切り出しアルゴリズムと実装
- テキストデータからの高速データマイニング : 探索的文書ブラウジングとウェブデータへの応用(発見科学)
- 細菌検査データからの頻出二部エピソードの抽出 (特集 「諸分野の連携による知識発見」および一般)
- 1.「知識創出学」とは?(北の国から明日のICTに架ける橋,知の創出を支える次世代IT基盤技術-北海道大学グローバルCOEプログラムと北海道内情報通信系研究グループの活動-)
- 2.情報系異分野共同研究プロジェクト(北の国から明日のICTに架ける橋,知の創出を支える次世代IT基盤技術-北海道大学グローバルCOEプログラムと北海道内情報通信系研究グループの活動-)
- 極小出現区間を用いたエピソードマイニングの高速化(データベース・アルゴリズム)
- 極小出現区間を用いたエピソードマイニングの高速化(データベース・アルゴリズム)
- ラベル付きグラフからのウォークの多項式時間学習
- 塩基およびアミノ酸配列における共変異集合を列挙する高速アルゴリズム
- D-019 ビット並列手法に基づく大規模連続ストリームパターン照合(D分野:データベース)
- データインテンシブコンピューティング : その2 頻出アイテム集合発見アルゴリズム(知能コンピューティングとその周辺〔第2回〕)
- 生物配列の局所マルチプルアラインメントの計算困難性
- 大規模幾何データからの高速な極大部分グラフ発見 (特集 「ウェブマイニング」および一般)
- TANE--学習を用いた柔軟な情報抽出ウェブブラウザ (特集 「ウェブマイニング」および一般)
- D_045 大規模文字列ソートのための適応的なデータ分割アルゴリズム(D分野:データベース)
- ゼロサプレス型二分決定グラフを用いたトランザクションデータベースの効率的解析手法(データマイニング,データ工学論文)
- Efficient Discovery of Maximal Two-Dimensional Patterns with Don't-Cares(extended abstract) (テーマ:特集「ウェブデータの知的処理」および一般)
- 深さ優先探索に基づく変数制限つき極大モチーフの高速マイニング (テーマ:「データマイニングと統計数理」および一般)
- ワイルドカードを許した極大モチーフの列挙アルゴリズム
- 大規模データストリームのためのマイニング技術の動向(データ工学論文)
- A Catalog for Prediction-Preserving Reducibility with Membership Queries on Formal Languages (New Developments of Theory of Computation and Algorithms)
- E-007 構文グラフ集合を用いたKey Semanticsマイニング(E.自然言語・文書・ゲーム)
- 大規模木構造データからの頻出無順序木パターン発見アルゴリズム (計算機科学基礎理論の新展開)
- 半構造データマイニングにおけるパターン発見技法
- 大規模木構造データからの頻出部分構造パターン発見アルゴリズム(文字列アルゴリズム)
- 高速な無順序木パターン発見アルゴリズム (人工知能基礎論研究会(第54回)特集「医療及び化学情報マイニング」および一般)
- 半構造データからの効率よい無順序木パターン発見手法(インターネット環境でのデータ工学とディペンダビィリティ及び一般)
- 半構造データからの効率よい無順序木パターン発見手法(インターネット環境でのデータ工学とディペンダビィリティ及び一般)
- 半構造データからの効率よい無順序木パターン発見手法
- 大規模木構造データからの高速な部分構造発見(「21世紀の知識情報科学に向けて」,及び一般)
- 2部クリークを用いたclosed item setの効率的な列挙(「21世紀の知識情報科学に向けて」,及び一般)
- データストリーム処理のための効率良いXPath問合せ機構(セッション4A : 時空間データ・ストリーム)
- データストリーム処理のための効率良いXPath問合せ機構(時空間データ・ストリーム)(「夏のデータベースワークショップ(DBWS2003)」一般)
- テキストマイニング:ウェブデータからの知識発見を目指して (特集 情報論的学習理論--機械学習のさまざまな形)
- データマイニング : ウェブデータからの知識発見を目指して
- TK-7-1 知の創出を支える次世代IT基盤拠点(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- TK-7-1 知の創出を支える次世代IT基盤拠点(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- TK-7-1 知の創出を支える次世代IT基盤拠点(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- TK-7-1 知の創出を支える次世代IT基盤拠点(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- TK-7-1 知の創出を支える次世代IT基盤拠点(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- D-4-2 オンラインXMLストリーム処理のための効率良い木正規表現パターン照合アルゴリズム(D-4.データ工学,一般セッション)
- 位置情報付き個人コンテンツ分類のための線形HMMを用いたイベントクラスタリング(機械学習応用,テキスト・Webマイニング,一般)
- タグとキーワードの関係を利用したテキストマイニング (人工知能基礎論研究会(第46回) 知識ベースシステム研究会(第54回) 合同研究会 テーマ:「アクティブマイニング」および一般)
- タグとキーワードの関係を利用したテキストマイニング (人工知能基礎論研究会(第46回) 知識ベースシステム研究会(第54回) 合同研究会 テーマ:「アクティブマイニング」および一般)
- 1. データストリームのためのマイニング技術(最新!データマイニング手法)
- 分類階層を考慮したパタン照合アルゴリズム (特集 オントロジー)
- テキストマイニング基盤技術(「テキストマイニング」)
- 木の変換規則の例からの学習 (小特集 「発見科学」及び一般演題)
- 飽和集合列挙アルゴリズムを用いた大規模データベースからのルール発見手法 (特集 計算推論--モデリング・数理・アルゴリズム)
- 大規模系列データから代表的な頻出エピソードを発見するための効率よいアルゴリズム (特集「人工知能における論理の新たな展開」)
- 飽和系列パターンの多項式時間列挙アルゴリズム
- 飽和系列パターンの多項式時間列挙アルゴリズム
- 計算学習理論における学習(機械学習,それが人に及ばざる理由)
- TD-1-7 ウェブデータからの高速テキストマイニング
- Webマイニング(「テキストマイニング」)
- 木に含まれる限定サイズ部分木の列挙 (コンピュテーション)
- 系列二分決定グラフを操作するための豊富な演算体系の構築 (Theoretical Foundations of Computing)
- 長大な拡張文字列パターンに対する大規模文字列照合の高速化
- 疎な接尾辞木構築のWord RAM上の高速化
- 超辺の縮約を許した非巡回部分超グラフの効率よい列挙
- 非対称で個体差がある関係データ分析のための機会調整型無限関係モデル(ベイズ統計モデル,統計推理,データベース,一般)