{"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00086140","sets":["1164:2592:6670:6899"]},"path":["6899"],"owner":"11","recid":"86140","title":["疎な接尾辞木構築のWord RAM上の高速化"],"pubdate":{"attribute_name":"公開日","attribute_value":"2012-10-26"},"_buckets":{"deposit":"6411dec4-e135-4feb-99ce-2b75832b4790"},"_deposit":{"id":"86140","pid":{"type":"depid","value":"86140","revision_id":0},"owners":[11],"status":"published","created_by":11},"item_title":"疎な接尾辞木構築のWord RAM上の高速化","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"疎な接尾辞木構築のWord RAM上の高速化"},{"subitem_title":"Faster Sparse Suffix Tree Construction on Word RAM","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2012-10-26","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"北海道大学工学部"},{"subitem_text_value":"株式会社調和技研"},{"subitem_text_value":"北海道大学大学院情報科学研究科"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Hokkaido University, Fac. Eng.","subitem_text_language":"en"},{"subitem_text_value":"Chowa Giken Co.","subitem_text_language":"en"},{"subitem_text_value":"Hokkaido University, IST.","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/86140/files/IPSJ-AL12142009.pdf"},"date":[{"dateType":"Available","dateValue":"2014-10-26"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL12142009.pdf","filesize":[{"value":"247.9 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"10fe6fea-20dc-4813-9fe8-fb53c5b7f71b","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2012 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"高木, 拓也"},{"creatorName":"上村, 卓史"},{"creatorName":"有村, 博紀"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Takuya, Takagi","creatorNameLang":"en"},{"creatorName":"Takashi, Uemura","creatorNameLang":"en"},{"creatorName":"Hiroki, Arimura","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN1009593X","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"長さ N のテキストの K ≤ N 個の索引点に対する接尾辞木を疎接尾辞木 (sparse suffix tree) といい， O(K) 語の領域しか使用しないため，さまざまな応用に用いられている．上村と有村 (Proc. CPM2011, LNCS 6661, 2011) は，長さ N ビットのハフマン圧縮テキストが入力として与えられたとき，その疎接尾辞木を O(σ) 前処理時間と O(K+σ) 語の領域を用いて，オンライン構築するアルゴリズムを与えている．本稿では，ビット並列計算と簡潔トライ構造からなる詰め込み文字列 (packed string) 技法を用いて，長さ O(N) ビットのハフマン圧縮テキストに対して，疎接尾辞木を O(σ) 前処理時間と O(K+σ) 語の領域を用いて， O(⌈N/w⌉√w+K√w) 時間でオンライン構築するアルゴリズムを与える．ここに， w は計算機のレジスタ長 (ビット) であり， σ は符号中の符号語長さの総和である．これは，疎接尾辞木のオンライン構築で初めて， O(N) 時間より少ない計算時間を達成したアルゴリズムである．提案手法は， K≦O(N/√w) のときに従来手法より高速である．また，一般の有限接頭符号上や，単語アルファベット上の符号化テキストに対しても拡張可能である．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"We present an efficient algorithm on Word RAM for constructing a sparse suffix tree on an encoded text over a regular prefix-code in O(⌈N/w⌉ √w+K√w) time using O(σ)preprocessing and O(K + σ) word space, where N is the length of the text in base letters, K is the length of the text in code words, σ is the size of a base alphabet Σ, σ is the total size of a code alphabet on Σ, and w is a bit-length of a register of Word RAM.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"8","bibliographic_titles":[{"bibliographic_title":"研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2012-10-26","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"9","bibliographicVolumeNumber":"2012-AL-142"}]},"relation_version_is_last":true,"weko_creator_id":"11"},"id":86140,"updated":"2025-01-21T17:48:35.707535+00:00","links":{},"created":"2025-01-18T23:37:33.792800+00:00"}