基数木
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/03/23 05:48 UTC 版)
基数木（英: Radix tree）またはパトリシア木（英: Patricia tree）とは、文字列集合を格納するトライ木に基づく特殊化された集合データ構造である。パトリシアトライ（英: Patricia trie）とも。通常のトライ木に比較すると、基数木の辺は単一の文字ではなく文字の並びでラベル付けされる。それは、文字列でもよいし、整数やIPアドレスなどを表すビット列でもよい。辞書式順序を適用できるオブジェクトの並びなら何でもラベルとして使用できる。基数木と言った場合、整数を格納する木構造のみを指すことが多く、パトリシア木といった場合は特に格納するデータを限定しないが、基本的に構造や動作原理は同じである。
| |||||||||||||||||||||||||||||||||||||||||||||||||||
- ^ Practical Algorithm to Retrieve Information Coded in Alphanumeric
- ^ Askitis, Nikolas; Sinha, Ranjan (2007年), “HAT-trie: A Cache-conscious Trie-based Data Structure for Strings”, Proceedings of the 30th Australasian Conference on Computer science 62: pp. 97-105, ISBN 1-920-68243-0
[続きの解説]
- 基数木のページへのリンク
