libsent/src/util/ptree.c

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

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

ソースコードを見る。

関数

int testbit (char *str, int slen, int bitplace)
 String bit test function.
int testbit_max (char *str, int bitplace, int maxbitplace)
 Local bit test function for search.
int where_the_bit_differ (char *str1, char *str2)
 Find in which bit the two strings differ, starting from the head.
static PATNODE * new_node ()
 Allocate a new node.
PATNODE * make_ptree (char **words, int *data, int wordsnum, int bitplace)
 Make a patricia tree for given string arrays.
void disp_ptree (PATNODE *node, int level)
 Output a tree structure in text for debug, traversing pre-order
static int ptree_search_data_r (PATNODE *node, char *str, int maxbitplace)
 Recursive function to search the data in the tree
int ptree_search_data (char *str, PATNODE *node)
 Search for the data whose key string matches the given string.
static int ptree_replace_data_r (PATNODE *node, char *str, int val, int maxbitplace)
 Recursive function to replace the data in the tree
int ptree_replace_data (char *str, int val, PATNODE *node)
 Search for the data whose key string matches the given string, and replace its value.
PATNODE * ptree_make_root_node (int data)
 Make a root node of a index tree.
static void ptree_add_entry_at (char *str, int slen, int bitloc, int data, PATNODE **parentlink)
 Insert a new node to the existing index tree.
void ptree_add_entry (char *str, int data, char *matchstr, PATNODE **rootnode)
 Insert a new node to the index tree.
void free_ptree (PATNODE *node)
 Free all the sub nodes from specified node.

変数

static unsigned char mbit [] = {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01}

説明

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

作者:
Akinobu LEE
日付:
Thu Feb 17 15:34:39 2005
Revision
1.4

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

関数

int testbit ( char *  str,
int  slen,
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 の 40 行で定義されています。

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

int testbit_max ( char *  str,
int  bitplace,
int  maxbitplace 
)

Local bit test function for search.

引数:
str [in] key string
bitplace [in] bit place to test.
maxbitplace [in] maximum number of bitplace
戻り値:
the content of tested bit in tmp_str, either 0 or 1.

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

参照元 aptree_remove_entry_r()・aptree_search_data_r()・ptree_replace_data_r()・ptree_search_data_r().

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 の 73 行で定義されています。

参照元 aptree_add_entry()・ptree_add_entry().

static PATNODE* new_node (  )  [static]

Allocate a new node.

戻り値:
pointer to the new node.

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

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 の 119 行で定義されています。

参照元 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 の 182 行で定義されています。

static int ptree_search_data_r ( PATNODE *  node,
char *  str,
int  maxbitplace 
) [static]

Recursive function to search the data in the tree

引数:
node [in] current node.
str [in] key string
maxbitplace [in] maximum number of bitplace
戻り値:
the found integer value.

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

参照元 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 の 234 行で定義されています。

参照元 ngram_lookup_word()・set_unigram().

static int ptree_replace_data_r ( PATNODE *  node,
char *  str,
int  val,
int  maxbitplace 
) [static]

Recursive function to replace the data in the tree

引数:
node [in] current node.
str [in] key string
val [in] new value
maxbitplace [in] maximum number of bitplace
戻り値:
the found integer value.

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

参照元 ptree_replace_data().

int ptree_replace_data ( char *  str,
int  val,
PATNODE *  node 
)

Search for the data whose key string matches the given string, and replace its value.

引数:
str [in] search key string
val [in] value
node [in] root node of index tree
戻り値:
the exactly found integer value, or the nearest one.

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

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 の 300 行で定義されています。

参照元 ptree_add_entry()・set_unigram().

static void ptree_add_entry_at ( char *  str,
int  slen,
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 の 318 行で定義されています。

参照元 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 の 358 行で定義されています。

参照元 set_unigram().

void free_ptree ( PATNODE *  node  ) 

Free all the sub nodes from specified node.

引数:
node [in] current node.

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

参照元 free_ptree()・ngram_info_free().

Juliusに対してThu Jul 23 12:17:08 2009に生成されました。  doxygen 1.5.1