| 講演名 | 1995/5/12 文字列パターン照合のための損失のあるデータ圧縮 深町 修一, 下薗 真一, 有村 博紀, 篠原 武, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | もとのアルファベットからより小さなサイズkのアルファベットへの写像は,k-indexingと呼ばれ,損失のある圧縮符号とみなすことができる.損失のある符号を用いて圧縮されたテキスト上での文字列パターン照合は,圧縮率が高くなるために高速化が期待できるが,誤検出の可能性がある.2^n-indexingを用いると,nビットの固定長符号で,長さlのパターンの誤検出の期待値がほぼ<1/2>^ |
| 抄録(英) | A mapping, called k-indexing, from an alphabet to a smaller alphabet of size k is considered as a lossy text compression for speeding up string pattern matching. An approximation algorithm to find a k-indexing that minimizes false detection is presented. Using optimized 2^n-indexing, texts can be compressed in fixed length code of n (bit/char) and the expectation of false detection for patterns of length l is roughly <1/2>^ |
| キーワード(和) | 情報検索 / データ圧縮 / 文字列パターン照合 / 近似アルゴリズム |
| キーワード(英) | information retrieval / data compression / string pattern matching / approximation |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | NLC |
|---|---|
| 開催期間 | 1995/5/12(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Natural Language Understanding and Models of Communication (NLC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 文字列パターン照合のための損失のあるデータ圧縮 |
| サブタイトル（和） | |
| タイトル（英） | Lossy Text Compression for String Pattern Matching |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 情報検索 / information retrieval |
| キーワード(2)（和/英） | データ圧縮 / data compression |
| キーワード(3)（和/英） | 文字列パターン照合 / string pattern matching |
| キーワード(4)（和/英） | 近似アルゴリズム / approximation |
| 第 1 著者 氏名（和/英） | 深町 修一 / Shuichi Fukamachi |
| 第 1 著者 所属（和/英） | 九州工業大学情報工学部知能情報工学科 Department of Artificial Intelligence Kyushu Institute of Technology |
| 第 2 著者 氏名（和/英） | 下薗 真一 / Shinichi Shimozono |
| 第 2 著者 所属（和/英） | 九州工業大学情報工学部制御システム工学科 Department of Control Engineering and Science Kyushu Institute of Technology |
| 第 3 著者 氏名（和/英） | 有村 博紀 / Hiroki Arimura |
| 第 3 著者 所属（和/英） | 九州工業大学情報工学部知能情報工学科 Department of Artificial Intelligence Kyushu Institute of Technology |
| 第 4 著者 氏名（和/英） | 篠原 武 / Takeshi Shinohara |
| 第 4 著者 所属（和/英） | 九州工業大学情報工学部知能情報工学科 Department of Artificial Intelligence Kyushu Institute of Technology |
| 発表年月日 | 1995/5/12 |
| 資料番号 | |
| 巻番号（vol） | vol.95 |
| 号番号（no） | 29 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |