部分文字列増幅法による共通パターン発見アルゴリズム

• Item type: Trans(1)
• 公開日: 2005-01-15
• タイトル: 部分文字列増幅法による共通パターン発見アルゴリズム
• タイトル / 言語: en
• タイトル: A Pattern Discovery Algorithm by Substring Amplification
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: オリジナル論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 九州大学情報基盤センター 九州大学附属図書館
• 著者所属: 九州大学大学院システム情報科学府
• 著者所属: 九州大学情報基盤センター
• 著者所属(英): en
• 著者所属(英): Computing and Communications Center Kyushu University,Presently with Kyushu University Library
• 著者所属(英): en
• 著者所属(英): Department of Informatics Kyushu University
• 著者所属(英): en
• 著者所属(英): Computing and Communications Center Kyushu University
• 著者名: 池田, 大輔; 山田, 泰寛; 廣川, 佐千男
• 著者名(英): Daisuke, Ikeda; Yasuhiro, Yamada; Sachio, Hirokawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，複数の文字列に共通な部分を見つける問題を考察する．まず，この問題をパターンから生成された文字列の集合が与えられたときに，そのパターンの定数部分を見つける問題（テンプレート発見問題）として定式化する．パターンとは定数と変数からなる文字列で，パターンが生成する語は変数を定数文字列で置きかえて得られる．置きかえに用いられる文字列中の部分文字列の頻度分布はベキ分布に従うことを仮定し，高確率でテンプレート発見を解くアルゴリズムを構築する．共通部分の発見問題の1 つである最長の共通部分列を探す問題はNP 完全であることが知られているが，問題の再定式化，部分文字列の集合による定数部分の表現方法，部分文字列の頻度と総出現数から共通部分を発見する手法により，テンプレート発見問題は高確率でO(n) 時間で解けることを示す．ここで，n は入力文字列の長さの和である．さらに，このアルゴリズムがノイズに対し頑健であることと，複数のテンプレートが混在する場合でも有効であることを，Web 上の実データに適用することで実証する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we consider to find common parts among given strings. We define this problem as the template discovery problem which is, given a set of strings generated by some pattern, to find constant parts of the pattern. A pattern is a string over constant and variable symbols, and generates strings by replacing variables into constant strings. We assume that the frequency of replaced constant strings follows a power-law distribution, and construct an algorithm which solves the problem with high probability. Although the longest common subsequence problem, which is one of the famous common part discovery problems, is well-known to be NP-complete, we show that the template discovery problem can be solved in O(n) with high probability, where n is the total length of input strings. This complexity is achieved due to the following our contributions: reformulation of the problem, using a set of substrings to express a template, and using string frequency and all occurrences to find substrings common to input trings. Moreover, using data on the Web, we show noise robustness and effectiveness for the case that input strings are generated by different patterns.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464803
• 書誌情報: 情報処理学会論文誌数理モデル化と応用（TOM）; 巻 46, 号 SIG2(TOM11), p. 56-66, 発行日 2005-01-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7780
• 出版者 / 言語: ja
• 出版者: 情報処理学会