ダブル配列法によるトライ検索の実現法

• Item type: SIG Technical Reports(1)
• 公開日: 1991-09-19
• タイトル: ダブル配列法によるトライ検索の実現法
• タイトル / 言語: en
• タイトル: IMPLEMENTATION OF TRIE SEARCH STRATEGIES BY DOUBLE - ARRAY STRUCTURES
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 徳島大学工学部
• 著者所属: 徳島大学工学部
• 著者所属(英): en
• 著者所属(英): The University of Tokushima
• 著者所属(英): en
• 著者所属(英): The University of Tokushima
• 著者名: 青江, 順一; 森本, 勝士
• 著者名(英): Jun-Ichi, Aoe; Katushi, Morimoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 自然言語処理の辞書検索手法として有効利用されているトライ法を効率的にインプリメントするためのデータ構造として，二つの1次元配列を使用するダブル配列法を提案する．また，自然言語処理の辞書は，予め基本的キー集合を構築しておき，後に使用者がキーを適宜追加して拡充させる場合が一般的であるので，本手法はこの条件を満足する場合（準静的検索法）を満足するものである．本手法では，トライにおいて分岐なしに終端のノードまで連続する遷移列をダブル配列とは別のデータ構造TAILにストリングとして格納し，このダブル配列とTAILを使ったトライ法のの検索，追加，削除アルゴリズムを提案する．キーの長さをk; ダブル配列上で冗長に定義される状態番号数をm; 入力記号の種類をeとするとき，検索，削除，追加の最悪の計算時間がそれ0（），0（），0（・e+e^）となることを示す．また，千個以上のキー集合に対する種々の実験結果から，このmはダブル配列に定義されるべき全状態数に対して，1パーセント以下の小さな値となることが分かった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: An efficient trie search algorithm is presented in this paper by introducing a new internal array structure, called a double-array, that combines the fast access of a matrix form with the compactness of a list form. Each arc of the trie can be computed from the double-array in O(1) time; that is to say, the worst-case time complexity for retrieving a key becomes O(k) for the length k of that key. The double-array is modified to make the size compact while maintaining fast access and algorithms for retrieval, insertion and deletion are presented. Suppose that the size of the double-array is n + m, n being the number of nodes of the trie, e being the number of input symbols, and m being the number of redundant nodes on the double-array. Then it is theoretically proved that the worstcase times of deletion and insertion are proportional to O(m) and O(me+e^2) respectively, independent of n. From the experimental results of building the double-array incrementally for various sets of keys, it is shown that m has an extremely small value, ranging from 0.17 to 1.13.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10115061
• 書誌情報: 情報処理学会研究報告自然言語処理（NL）; 巻 1991, 号 80(1991-NL-085), p. 9-16, 発行日 1991-09-19
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会