| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2007-05-31 13:00 ［招待講演］文字列の圧縮とパターンの照合・発見 ○竹田正幸（九大）  AI2007-5 |
|
| 抄録 | （和） | 圧縮パターン照合とは，圧縮された文字列データに対して，伸張せずに文字列パターン照合を行う技術である．通常，圧縮パターン照合は，通常の非圧縮データ上のパターン照合に比べ，多くの計算時間を要する．このため，圧縮パターン照合の研究は，伸張後にパターン照合技術を適用するナイーヴな手法より高速なアルゴリズムの開発を第１の目標としていた．これに対し，講演者らは，この常識を覆し，圧縮手法によっては，非圧縮データ上のパターン照合よりも高速に照合を行えることを示した．すなわち，文字列データ圧縮を，パターン照合高速化の手段として位置づけたのである．本講演では，圧縮率や圧縮・伸張に要する計算量といった従来の観点ではなく，圧縮パターン照合の観点から既存の圧縮法を概観するとともに，パターン照合高速化に適した新たな圧縮手法について，パターン発見に関する研究とも絡めながら述べる． |
| （英） | The compressed pattern matching (CPM, in short) problem is, given a compressed string data, to perform a string pattern matching task without decompressing it. Usually CPM requires much more time compared to ordinary pattern matching over uncompressed string data, and therefore most of the studies on the CPM problem aim to develop a CPM algorithm which runs faster than a naive method of decompression followed by a simple search. Our research group showed that some of the CPM algorithms over compressed data in some compressed format could run faster than ordinary pattern matching algorithms over uncompressed data. Namely, string data compression can be a good means of accelerating the string pattern matching task. In this talk we give an overview of existing compression methods from a viewpoint of CPM, not from the tradional viewpoints of compression ratios and time and space complexities of compression/decompression. Then we describe a recent development of new compression scheme suitable for speedup-by-compression. |
|
| キーワード | （和） | 文字列データ圧縮 / 文字列パターン照合 / 文字列パターン発見 / 圧縮パターン照合 / / / / |
| （英） | string data compression / string pattern matching / string pattern discovery / compressed pattern matching / / / / | |
| 文献情報 | 信学技報, vol. 107, no. 78, AI2007-5, pp. 25-25, 2007年5月. | |
| 資料番号 | AI2007-5 | |
| 発行日 | 2007-05-24 (AI) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | AI2007-5 |
|
| 研究会情報 | |
| 研究会 | AI |
| 開催期間 | 2007-05-31 - 2007-05-31 |
| 開催地（和） | 機械振興会館 |
| 開催地（英） | Kikai-Shinko-Kaikan Bldg. |
| テーマ（和） | 「自動化：推論，発見，学習，データマイニング」および一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | AI |
| 会議コード | 2007-05-AI |
| 本文の言語 | 日本語 |
| タイトル（和） | 文字列の圧縮とパターンの照合・発見 |
| サブタイトル（和） | |
| タイトル（英） | String data compression, pattern matching, and pattern discovery |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 文字列データ圧縮 / string data compression |
| キーワード(2)（和/英） | 文字列パターン照合 / string pattern matching |
| キーワード(3)（和/英） | 文字列パターン発見 / string pattern discovery |
| キーワード(4)（和/英） | 圧縮パターン照合 / compressed pattern matching |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 竹田 正幸 / Masayuki Takeda / タケダ マサユキ |
| 第1著者 所属（和/英） | 九州大学 (略称： 九大) Kyushu Univeristy (略称： Kyushu Univ.) |
| 第2著者 氏名（和/英/ヨミ） | / / |
| 第2著者 所属（和/英） | (略称： ) (略称： ) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2007-05-31 13:00:00 |
| 発表時間 | 50分 |
| 申込先研究会 | AI |
| 資料番号 | AI2007-5 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | no.78 |
| ページ範囲 | p.25 |
| ページ数 | 1 |
| 発行日 | 2007-05-24 (AI) |
[研究会発表申込システムのトップページに戻る]