libsent/src/util/ptree.c

パトリシア検索木を用いた名前検索：データ型が int の場合 [詳細]

#include <sent/stddefs.h>
#include <sent/ptree.h>

ptree.cのインクルード依存関係図

ソースコードを見る。

関数
int	testbit (char *str, int bitplace)
int	where_the_bit_differ (char *str1, char *str2)
static PATNODE *	new_node ()
PATNODE *	make_ptree (char **words, int *data, int wordsnum, int bitplace)
void	disp_ptree (PATNODE *node, int level)
static int	testbit_local (int bitplace)
static int	ptree_search_data_r (PATNODE *node)
int	ptree_search_data (char *str, PATNODE *node)
PATNODE *	ptree_make_root_node (int data)
static void	ptree_add_entry_at (char *str, int bitloc, int data, PATNODE **parentlink)
void	ptree_add_entry (char *str, int data, char *matchstr, PATNODE **rootnode)
void	free_ptree (PATNODE *node)
変数
static char *	tmp_str
	Local work area: current string we are searching for
static int	maxbitplace
	Local work area: Maximum bit length of tmp_str

---

説明

パトリシア検索木を用いた名前検索：データ型が int の場合

作者:

Akinobu LEE

日付:

Thu Feb 17 15:34:39 2005

Revision

1.3

ptree.c で定義されています。

---

関数

int testbit	(	char *	str,
		int	bitplace
	)

String bit test function.

引数:

	str	[in] key string
	bitplace	[in] bit location to test

戻り値:

the content of tested bit in tmp_str, either 0 or 1.

ptree.c の 36 行で定義されています。

参照元 aptree_add_entry_at()・make_ptree()・ptree_add_entry_at()・where_the_bit_differ().

int where_the_bit_differ	(	char *	str1,
		char *	str2
	)

Find in which bit the two strings differ, starting from the head.

引数:

	str1	[in] string 1
	str2	[in] string 2

戻り値:

the bit location in which the string differs.

ptree.c の 61 行で定義されています。

参照元 aptree_add_entry()・ptree_add_entry().

static PATNODE* new_node

(

)

[static]

Allocate a new node.

戻り値:

pointer to the new node.

ptree.c の 82 行で定義されています。

PATNODE* make_ptree	(	char **	words,
		int *	data,
		int	wordsnum,
		int	bitplace
	)

Make a patricia tree for given string arrays. Recursively called by descending the scan bit.

引数:

	words	[in] list of word strings
	data	[in] integer value corresponding to each string in words
	wordsnum	[in] number of above
	bitplace	[in] current scan bit.

戻り値:

pointer to the root node index.

ptree.c の 105 行で定義されています。

参照元 make_ptree()・ngram_make_lookup_tree().

void disp_ptree	(	PATNODE *	node,
		int	level
	)

Output a tree structure in text for debug, traversing pre-order

引数:

	node	[in] root index node
	level	[in] current tree depth

ptree.c の 168 行で定義されています。

static int testbit_local

(

int

bitplace

)

[static]

Local bit test function for search.

引数:

bitplace

[in] bit place to test.

戻り値:

the content of tested bit in tmp_str, either 0 or 1.

ptree.c の 200 行で定義されています。

static int ptree_search_data_r

(

PATNODE *

node

)

[static]

Recursive function to search the data in the tree

引数:

node

[in] current node.

戻り値:

the found integer value.

ptree.c の 224 行で定義されています。

参照元 ptree_search_data().

int ptree_search_data	(	char *	str,
		PATNODE *	node
	)

Search for the data whose key string matches the given string.

引数:

	str	[in] search key string
	node	[in] root node of index tree

戻り値:

the exactly found integer value, or the nearest one.

ptree.c の 246 行で定義されています。

参照元 ngram_lookup_word()・set_unigram().

PATNODE* ptree_make_root_node

(

int

data

)

Make a root node of a index tree.

引数:

data

[in] the first data

戻り値:

the newly allocated root node.

ptree.c の 268 行で定義されています。

参照元 ptree_add_entry()・set_unigram().

static void ptree_add_entry_at	(	char *	str,
		int	bitloc,
		int	data,
		PATNODE **	parentlink
	)			[static]

Insert a new node to the existing index tree.

引数:

	str	[in] new key string
	bitloc	[in] bit branch to which this node will be added
	data	[in] new data integer value
	parentlink	[i/o] the parent node to which this node will be added

ptree.c の 286 行で定義されています。

参照元 ptree_add_entry().

void ptree_add_entry	(	char *	str,
		int	data,
		char *	matchstr,
		PATNODE **	rootnode
	)

Insert a new node to the index tree.

引数:

	str	[in] new key string
	data	[in] new data integer value
	matchstr	[in] the most matching data already exist in the index tree, as obtained by aptree_search_data()
	rootnode	[i/o] pointer to root index node

ptree.c の 326 行で定義されています。

参照元 set_unigram().

void free_ptree

(

PATNODE *

node

)

Free all the sub nodes from specified node.

引数:

node

[in] current node.

ptree.c の 345 行で定義されています。

参照元 free_ptree()・ngram_info_free().

---