部分文字列増幅法による共通パターン発見アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,複数の文字列に共通な部分を見つける問題を考察する.まず,この問題をパターンから生成された文字列の集合が与えられたときに,そのパターンの定数部分を見つける問題(テンプレート発見問題)として定式化する.パターンとは定数と変数からなる文字列で,パターンが生成する語は変数を定数文字列で置きかえて得られる.置きかえに用いられる文字列中の部分文字列の頻度分布はベキ分布に従うことを仮定し,高確率でテンプレート発見を解くアルゴリズムを構築する.共通部分の発見問題の1つである最長の共通部分列を探す問題はNP完全であることが知られているが,問題の再定式化,部分文字列の集合による定数部分の表現方法,部分文字列の頻度と総出現数から共通部分を発見する手法により,テンプレート発見問題は高確率で0(n)時間で解けることを示す.ここで,nは入力文字列の長さの和である.さらに,このアルゴリズムがノイズに対し頑健であることと,複数のテンプレートが混在する場合でも有効であることを,Web上の実データに適用することで実証する.
- 2005-01-15
著者
-
山田 泰寛
九州大学ユーザーサイエンス機構
-
池田 大輔
九州大学大学院システム情報科学研究院
-
廣川 佐千男
九州大学情報基盤研究開発センター
-
廣川 左千男
九州大学情報基盤研究開発センター
-
池田 大輔
九州大学情報基盤センター
-
山田 泰寛
九州大学大学院システム情報科学府
-
池田 大輔
九州大学システム情報
-
池田 大輔
九州大学システム情報科学研究院
関連論文
- 〈「ディジタル図書館」ワークショップ第38回 発表論文〉スモールサイエンスのための e-Science リポジトリの要求分析
- 概念束によるヒヤリハット報告書の分析システム (言語理解とコミュニケーション・第1回集合知シンポジウム--言語処理が紡ぎ出す未来)
- 外部連携サービスによる機関リポジトリの潜在需要の解析
- Ｗｅｂシラバス統合による教育情報ライブラリ構築
- キーワード連動広告でのキーワード発見手法の提案(夏のデータベースワークショップ2007(データ工学,一般))
- キーワード連動広告でのキーワード発見手法の提案(メタデータ,夏のデータベースワークショップ2007(データ工学,一般))
- 接尾辞木を用いた圧縮尺度計算による効率よいスパムポスト検出手法(ポスターセッション,iDBフォーラム2008(招待講演・ポスター英語ディスカッション))
- プレーリストからの曲目やアーティストの相互関連抽出
- SNS(Social Networking Service)における信頼と図書館における応用(第33回ディジタル図書館ワークショップの論文)
- ＜発表論文＞SNS (Social Networking Service) における信頼と図書館における応用 （「ディジタル図書館」ワークショップ 第33回）
- WebDBにおける出力レコードのメタデータ自動抽出(セッション2:Web応用)
- D_040 WebDBをコンポーネントとするセマンティック・メタ検索の提案(D分野:データベース)
- マッシュアップを簡単に実現するメタCGIとそのアーキテクチャ(セッション2:Web応用)
- FFTを用いた繰り返しパターン発見手法の提案(セッション5B : パターン抽出)
- Webシラバス情報収集エージェントの試作(ソフトウェアエージェントとその応用論文)
- 3次元分散共有仮想空間を媒介とする3次元マルチメディアデータの交換・流通環境
- 統合検索システムDAISEnでの検索サイトフォーム分析(セッション9B : 情報統合)
- 統合検索システムDAISEnでの検索サイトフォーム分析(情報統合)(「夏のデータベースワークショップ(DBWS2003)」一般)
- ウェブデータウエアハウスと協働する業務報告書オーサリングシステム
- 新個人認証システムPersonal IDが変える図書館の個人情報管理 : 個人情報やプライバシーに配慮した一歩先行く図書館サービスとは
- D-012 XDES : 多様な構造と流動的変化に対応できるデータエントリーシステムの構築(D分野:データベース)
- 部分文字列の数え上げによるブログスパムの検出(マイニングとフィルタリング)
- 部分文字列の数え上げによるブログスパムの検出(マイニングとフィルタリング)
- 英和辞典を用いた単語階層構造の動的構築
- マッシュアップを簡単に実現するメタCGIとそのアーキテクチャ(セッション2:Web応用)
- 英和辞典を用いた単語階層構造の動的構築 (「Web Intelligence」および一般発表)
- 平成18年度における研究開発 電子図書館システムの研究開発
- WebDBのQuery Formにおけるメタデータ自動抽出
- Web上の高等教育用コンテンツの自動収集と抽出--シラバスの自動抽出
- 学会講演データにおける著者やキーワードの関連分析システム (テーマ:特集「ウェブデータの知的処理」および一般)
- プレーリストからの曲目やアーティストの相互関連抽出
- 文書群からの概念グラフの構成(検索とキーワード・概念抽出)
- 文書群からの概念グラフの構成(検索とキーワード・概念抽出)
- Web データベースにおける入力フォーム情報の自動抽出
- 文書群の局所性と大域性の差を利用したキーワード粒度評価(重要語抽出・検索・文書分類)
- 文書群の局所性と大域性の差を利用したキーワード粒度評価(重要語抽出・検索・文書分類)
- 教員データに対する多面的検索システム(eラーニング2, 夏のデータベースワークショップDBWS2005)
- 教員データに対する多面的検索システム(eラーニング2, 夏のデータベースワークショップ2005)
- ウェブデータウエアハウスと協働する業務報告書オーサリングシステム
- ウェブデータウエアハウスと協働する業務報告書オーサリングシステム
- 概念束によるヒヤリハット報告書の分析システム(第1回集合知シンポジウム〜言語処理が紡ぎ出す未来〜)
- 不一致を許す文字列照合のためのFFTを用いた確率的アルゴリズムの精度評価
- 2K1 大学評価の報告書作成支援システムと大学情報のデータウェアハウスについて((課題研究2)ICTを活用した教育支援環境,教育の原点に光を当てる〜乱流の中の本流を見出す〜)
- WebDBにおける出力レコードのメタデータ自動抽出(セッション2:Web応用)
- 単語の出現頻度に着目した病院評判情報の分析(抽出(1))
- 単語の出現頻度に着目した病院評判情報の分析(抽出(1))
- Webデータベースにおける入力フォーム情報の自動抽出(セッション4: メタデータとWebデータベース応用)
- Webデータベースにおける入力フォーム情報の自動抽出(セッション4: メタデータとWebデータベース応用)
- 短期・中期移動平均線を用いた株価の解析
- 教員データにおける高頻度語(語の統計量とその応用)
- 教員連想検索システム(セッション2:文書変換・表示)
- 部分文字列増幅法による共通パターン発見アルゴリズム
- 交代数を用いた多言語Webテキストからの共通部分特定とラッパーの生成法(データマイニング)
- D-039 検索サイトにおける入力項目と検索結果のフィールド名の対応調査(D.データベース)
- テンプレート発見問題の定式化と部分文字列増幅法を用いたアルゴリズム(文字列アルゴリズム)
- 部分文字列増幅法による共通パタン発見アルゴリズム(パターン認識)
- 半構造化文書に対する木構造と文字列を組合せたラッパーの自動生成法(コーパス構築)(セマンティックウェブと自然言語処理その他一般)
- 文字列の頻度分布による共通パタン発見(パタン発見)(セマンティックウェブと自然言語処理その他一般)
- 文字列の頻度分布による共通パタン発見
- 九州大学自己点検・評価関連情報システム(セッション2:XML応用システム)
- Web上の多言語テキストデータからのラッパー自動生成
- SoftPathを用いた同系統単語抽出方式
- N-32 自動収集したWebシラバスデータの分析と考察(教育支援システム(2),N.教育・人文科学)
- D-6 専門検索サイトの動的統合による次世代検索システムDAISENにおける検索サイトエディタの開発(Web検索(1),D.データベース)
- n-gram交代数を用いた半構造化データの不要部分削除
- n-gram交代数を用いた半構造化データの不要部分削除
- Webグラフの構造解析 (「Webシステムにおける情報獲得支援技術」)
- 3次元分散共有仮想空間を媒介とする3次元マルチメディアデータの交換・流通環境
- 検索サイトの統合システム
- 初等幾何推論の多面的表示方式
- ZKネットワーク雑記帳
- $\lambda_C$計算と$\lambda_P$計算との対応(計算理論とその応用)
- D-1-6 動的刈り込み接尾辞木を用いた圧縮尺度計算によるスパム検出(D-1. コンピュテーション,一般セッション)
- 文書群からの概念グラフの構成
- 観光イベントについての「といえば検索」の提案(「コミュニティ上での知識の共有・再利用」及び一般)
- D-037 形式概念を用いた倒産情報の分析システム(D分野:データベース,一般論文)
- 背表紙画像を用いたネットワーク透過な仮想書架
- ＜発表論文＞研究支援ツールとしての機関リポジトリにおけるバージョン管理機能 （「ディジタル図書館」ワークショップ 第33回）
- ユビキタス図書館 ： 偏在する図書館サービス
- 電子図書館と利用者のプライバシー ： 履歴・個人情報の保護と利用の両立を目指して
- Ｗｅｂサービスを用いた読書録サービスの設計と実装
- 単純な部分文字列照合によるＷｅｂからの書誌情報の抽出
- 仮想書架における背表紙画像生成の自動化
- 高性能ＲＦＩＤリーダ付き書架の性能評価と新たな図書館サービスの提案
- ＜発表論文＞ＲＦＩＤ技術を用いた図書館自動化への期待 （「ディジタル図書館」ワークショップ第26回）
- RFID技術を用いた図書館自動化への期待
- WWWからの情報抽出 : Webラッパーの自動構築(WWW上の情報の知的アクセスのためのテキスト処理)
- ウェブデータマイニング(「データマイニング特集号」)
- 部分文字列の頻度分布に基づいた同一テンプレートを持つWebページの自動収集(Webマイニング)(テーマ:「Webマイニングによる情報活動と自然言語処理」その他一般)
- 部分文字列の頻度分布に基づいた同一テンプレートを持つWebページの自動収集(Webマイニング)(テーマ:「Webマイニングによる情報活用と自然言語処理」その他一般)
- 部分文字列の頻度分布に基づいた同一テンプレートを持つWebページの自動収集
- 学会講演データの多面的解析システム (テーマ:特集「ウェブデータの知的処理」および一般)
- 高性能RFIDリーダ付き書架の性能評価と新たな図書館サービスの提案
- 電子図書館の歴史と九大附属図書館の取り組み
- リポジトリのアクセスログ解析
- 複雑な知識モデルを利用した人間の学習プロセスシミュレーションの検討
- クロス集計による文献ファセット検索システムの提案
- The Computational Complexity of Hereditary Elementary Formal Systems
- 手掛り語に着目した倒産情報の分析手法の提案(応用,自然言語処理)
- 手掛り語に着目した倒産情報の分析手法の提案(応用,自然言語処理)