{"id":40146,"updated":"2025-01-22T12:34:16.127565+00:00","links":{},"created":"2025-01-18T23:07:19.761926+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00040146","sets":["1164:3500:3510:3514"]},"path":["3514"],"owner":"1","recid":"40146","title":["遷移先節点集合を導入したトライ構造における更新手法の実現"],"pubdate":{"attribute_name":"公開日","attribute_value":"2006-03-22"},"_buckets":{"deposit":"a5e91378-3cbb-4be8-bb6d-97d87a17441f"},"_deposit":{"id":"40146","pid":{"type":"depid","value":"40146","revision_id":0},"owners":[1],"status":"published","created_by":1},"item_title":"遷移先節点集合を導入したトライ構造における更新手法の実現","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"遷移先節点集合を導入したトライ構造における更新手法の実現"},{"subitem_title":"Implementation of Updation Techniques for the Trie Structure Based on the Set of Terminal Node","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2006-03-22","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":"Osaka Kyoiku University","subitem_text_language":"en"},{"subitem_text_value":"Osaka Kyoiku University","subitem_text_language":"en"},{"subitem_text_value":"Osaka Kyoiku University","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/40146/files/IPSJ-FI06082001.pdf"},"date":[{"dateType":"Available","dateValue":"2008-03-22"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-FI06082001.pdf","filesize":[{"value":"342.0 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":"39"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"6b064bc8-f87f-4d8b-8af3-f677f4302c2d","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2006 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":"Yasumasa, NAKAMURA","creatorNameLang":"en"},{"creatorName":"Yu, NOMURA","creatorNameLang":"en"},{"creatorName":"Hisatoshi, MOCHIZUKI","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN10114171","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":"自然言語処理システムを中心に広く用いられているトライ法のデータ構造として、2つの1次元配列を用いたダブル配列法がある。ダブル配列法は高速性とコンパクト法をあわせもつ有効なデータ構造であるが、動的検索法に比べ更新処理が高速であるとはいえない。そのため現在では、未使用要素を双方向リストとして連結する手法が知られているが、遷移先節点探索の計算回数を抑制する手法ではない。そこで本論文では、更新処理を高速化するため、ダブル配列法に遷移情報を格納する1次元配列を新たに用いた手法を提案する。キー集合20万語に対する実験を行った結果、提案手法は双方向リストを用いた手法より、追加処理は約2.4倍、削除処理は約2.1倍高速となった。","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"A trie is used widely, such as dictionary information construction of natural language processing system. As a data structure of trie, there is the double-array structure which Aoe and others proposed. A double-array structure is an efficient data structure combining fast access with compactness. However, the updating processing is not faster than other dynamic retrieval methods. Then, although the technique of connecting empty elements as doubly list is known now, it is not the technique of controlling the complexity of terminal node search. In this paper, we presents a fast insertion and deletion algorithms by connecting empty elements as doubly list and reduction algorithm of deletion time. From the simulation results for 200 thousands keys, it turned out that the presented method for insertion is about 2.4 times faster than the doubly list method, and deletion is about 2.1 times faster than the doubly list method. ","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"6","bibliographic_titles":[{"bibliographic_title":"情報処理学会研究報告情報学基礎（FI）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2006-03-22","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"33(2006-FI-082)","bibliographicVolumeNumber":"2006"}]},"relation_version_is_last":true,"weko_creator_id":"1"}}