著者

竹田 正純

出版者

駒澤大学

雑誌

論集 (ISSN:03899837)

巻号頁・発行日

vol.32, pp.21-22, 1990-09

著者

稲永 俊介 船本 崇 竹田 正幸 篠原 歩

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.103, no.622, pp.29-36, 2004-01-22

---

文字列の文法に基づく圧縮とは,与えられたテキストを生成する文法を構築することによってデータのサイズを縮小する圧縮法である.この中で長さ優先置換法とは,テキスト中の部分文字列のうち,重複なく複数回現れている最長のものを生成規則として別の一文字に置換していくものである.本論文では,文字列に対する索引構造の一つである接尾辞木に対して極めて技巧的な構造の更新を行うことにより,この長さ優先置換を線形時間で行うアルゴリズムを提案する.

著者

成澤 和志 稲永 俊介 坂内 英夫 竹田 正幸

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.107, no.24, pp.63-70, 2007-04-19

被引用文献数

1

---

本論文では,Blumerらによって提案された同値関係による同値類を計算する問題を考える.Blumerらはコンパクト有向無閉路文字列グラフ(CDAWG)と呼ばれる索引構造を定義するために同値類を利用した.同値類は本質的に等しく出現する冗長な部分文字列を集めた集合であるため,テキスト解析において有用である.本論文では,接尾辞配列を用いて同値類を計算するアルゴリズムを提案する.提案アルゴリズムでは,接尾辞木および接尾辞リンク木の巡回を模倣するため接尾辞配列の他に2つの補助配列を使用するが,これら以外のデータ構造を必要としない.このアルゴリズムは入力文字列に対して,線形時間および線形領域で動作する.本論文では,提案アルゴリズムと接尾辞木およびコンパクト有向無閉路文字列を用いたアルゴリズムとの計算時間・計算領域を計算機実験によって比較する.

著者

竹田 正幸 福田 智子 南里 一郎

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会ソサイエティ大会講演論文集

巻号頁・発行日

vol.2001, 2001-08-29