圧縮テキスト上での<i>q</i>-gram非重複頻度の効率的な計算とその応用

• Item type: SIG Technical Reports(1)
• 公開日: 2011-02-28
• タイトル: 圧縮テキスト上での<i>q</i>-gram非重複頻度の効率的な計算とその応用
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Department of Informatics
• 著者所属: Department of Electrical Engineering and Computer Science
• 著者所属: Department of Informatics
• 著者所属: Graduate School of Information Science and Electrical Engineering Kyushu University
• 著者所属: Department of Informatics
• 著者所属(英): en
• 著者所属(英): Department of Informatics
• 著者所属(英): en
• 著者所属(英): Department of Electrical Engineering and Computer Science
• 著者所属(英): en
• 著者所属(英): Department of Informatics
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Electrical Engineering Kyushu University
• 著者所属(英): en
• 著者所属(英): Department of Informatics
• 著者名: Keisuke, Goto; Nami, Fukui; Hideo, Bannai; Shunsuke, Ikenaga; Masayuki, Takeda
• 著者名(英): Keisuke, Goto; Nami, Fukui; Hideo, Bannai; Shunsuke, Ikenaga; Masayuki, Takeda
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: In many problems concerning text data, length-q substrings, or q-grams, can represent important characteristics of the data. Determining the frequencies of all q-grams contained in the data is an important problem with many applications. In this paper, we consider the problem of calculating the non-overlapping frequencies of all q-grams in a text represented as a straight line program (SLP). We show that the problem can be solved in O(q2n) time, where n is the size of the SLP. We also show an interesting application of the algorithm, which converts an arbitrary SLP to an SLP that is constructed based on frequency information.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In many problems concerning text data, length-q substrings, or q-grams, can represent important characteristics of the data. Determining the frequencies of all q-grams contained in the data is an important problem with many applications. In this paper, we consider the problem of calculating the non-overlapping frequencies of all q-grams in a text represented as a straight line program (SLP). We show that the problem can be solved in O(q2n) time, where n is the size of the SLP. We also show an interesting application of the algorithm, which converts an arbitrary SLP to an SLP that is constructed based on frequency information.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2011-AL-134, 号 11, p. 1-7, 発行日 2011-02-28
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会