| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2008-03-10 15:15 圧縮文字列における最長共通部分文字列および回文を求める多項式時間アルゴリズム ○松原 渉（東北大）・稲永俊介（九大）・石野 明・篠原 歩・中村智将・橋本和夫（東北大）  COMP2007-63 |
|
| 抄録 | （和） | 直線的プログラム(Straight line program, SLP)は単元集合を生成する文脈自由 文法の部分クラスとみなすことができ，そこで生成される文字列の長さは，変数 の個数$n$に対して指数的に長くなりうる． そのため，SLPによって圧縮表現された文字列に対して$n$の多項式時間で効率よ く処理を行うには，陽に展開することなく処理を行うことが必要不可欠となる． 本研究では，SLPとして表現された2つの文字列の最長共通部分文字列の長さを求める問題を$O(n^4 \log n)$時間，$O(n^4)$領域で解くアルゴリズムを示す． またSLPとして表現された文字列に含まれるすべての回文を検出する問題に対して，$O(n^4)$時間，$O(n^2)$領域で解くアルゴリズムを示す． |
| （英） | \emph{Straight line programs} (\emph{SLPs}) is one of the most powerful and general compression schemes. An SLP is a context-free grammar which generates only one string. In order to process SLP efficiently (in polynomial time with respect to the compressed size) decompression is never feasible. This paper studies two problems on compressed strings described in terms of SLPs. One is to compute the length of the longest common substring of two given SLP-compressed strings, and the other is to compute all palindromes of a given SLP-compressed string. We show efficient algorithms that solve these problems in $O(n^4 \log n)$ time with $O(n^3)$ space, and in $O(n^4)$ time with $O(n^2)$ space, respectively, where $n$ is the size of the input SLP-compressed strings. |
|
| キーワード | （和） | 圧縮 / 文字列処理 / 直線的プログラム / 回文 / 最長共通部分文字列 / / / |
| （英） | compression / string processing / straight line program / palindrome / longest common substring / / / | |
| 文献情報 | 信学技報, vol. 107, no. 537, COMP2007-63, pp. 55-62, 2008年3月. | |
| 資料番号 | COMP2007-63 | |
| 発行日 | 2008-03-03 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2007-63 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2008-03-10 - 2008-03-10 |
| 開催地（和） | 日本アイ・ビー・エム（株）大和事業所 |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2008-03-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | 圧縮文字列における最長共通部分文字列および回文を求める多項式時間アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Polynomial time algorithms for computing longest common substring and all palindromes from compressed strings |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 圧縮 / compression |
| キーワード(2)（和/英） | 文字列処理 / string processing |
| キーワード(3)（和/英） | 直線的プログラム / straight line program |
| キーワード(4)（和/英） | 回文 / palindrome |
| キーワード(5)（和/英） | 最長共通部分文字列 / longest common substring |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 松原 渉 / Wataru Matsubara / マツバラ ワタル |
| 第1著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 稲永 俊介 / Shunsuke Inenaga / イネナガ シュンスケ |
| 第2著者 所属（和/英） | 九州大学 (略称： 九大) Kyushu University (略称： Kyushu Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 石野 明 / Akira Ishino / イシノ アキラ |
| 第3著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 篠原 歩 / Ayumi Shinohara / シノハラ アユミ |
| 第4著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 第5著者 氏名（和/英/ヨミ） | 中村 智将 / Tomoyuki Nakamura / ナカムラ トモユキ |
| 第5著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 第6著者 氏名（和/英/ヨミ） | 橋本 和夫 / Kazuo Hashimoto / ハシモト カズオ |
| 第6著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2008-03-10 15:15:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2007-63 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | no.537 |
| ページ範囲 | pp.55-62 |
| ページ数 | 8 |
| 発行日 | 2008-03-03 (COMP) |
[研究会発表申込システムのトップページに戻る]