nlib
nn::nlib::succinct::Trie クラスfinal

LOUDSを利用したTrieの実装です。 [詳解]

#include "nn/nlib/succinct/Trie.h"

公開型

typedef bool(* MatchCallback) (const char *first, const char *last, uint32_t nodeid, void *user_obj)
 ユーザー定義のコールバック関数です。 [詳解]
 

公開メンバ関数

void Match (const char *cstr, MatchCallback callback, void *user_obj) noexcept
 文字列を検査してTrieに登録されている文字列を検出します。 [詳解]
 
void Match (const char *cstr, MatchCallback callback) noexcept
 上記関数の引数省略版で、nullptrを引数として渡します。
 
void Match (const void *data, size_t n, MatchCallback callback, void *user_obj) noexcept
 データを走査して検出対象のパターンを検出します。 [詳解]
 
void Match (const void *data, size_t n, MatchCallback callback) noexcept
 上記関数の引数省略版で、nullptrを引数として渡します。
 
void MatchBackward (const void *data, size_t n, MatchCallback callback, void *user_obj) noexcept
 データを後ろ向きに走査して検出対象のパターンを検出します。 [詳解]
 
void MatchBackward (const void *data, size_t n, MatchCallback callback) noexcept
 上記関数の引数省略版で、nullptrを引数として渡します。
 
errno_t GetCommonPrefixWords (const void *prefix, size_t n, ReallocCstringVec *vec) noexcept
 共通のプレフィックスを持つデータを辞書順にリストアップします。 [詳解]
 
std::pair< errno_t, Nlist< uint32_t > > GetCommonPrefixWords (const void *prefix, size_t n) noexcept
 共通のプレフィックスを持つデータのnodeidのリストを返します。 [詳解]
 
size_t MemSize () const noexcept
 このクラスが明示的に確保するメモリ量を返します。 [詳解]
 
コンストラクタ、デストラクタ、及び初期化
constexpr Trie () noexcept
 デフォルトコンストラクタです。実行後Init()による初期化を必要とします。
 
 ~Trie () noexcept
 デストラクタです。
 
Trieassign (Trie &rhs, move_tag)
 ムーブ代入演算子に相当します。
 
 Trie (Trie &rhs, move_tag)
 ムーブコンストラクタに相当します。
 
 Trie (Trie &&rhs)
 ムーブコンストラクタです。
 
Trieoperator= (Trie &&rhs)
 ムーブ代入演算子です。
 
bool Init () noexcept
 オブジェクトを初期化します。成功した場合はtrueを返します。
 
void Reset () noexcept
 このオブジェクトをデフォルトコンストラクタの実行直後の状態にリセットします。
 
インポートとエクスポート
bool Export (BinaryWriter *w) const noexcept
 オブジェクトを(ファイルに)書き出します。 [詳解]
 
bool Import (BinaryReader *r) noexcept
 書き出されたオブジェクトを読み出します。 [詳解]
 

詳解

LOUDSを利用したTrieの実装です。

説明
コンパクトなデータサイズでTrieを利用することができます。 TrieBuilderで作成するか、Import()メソッドでインポートして利用します。
以下のコードでは、aaaa-zzzzまで26^4パターンの文字列をTrieに登録していますが、770KBytesほどしか消費しません。 なお、文字列をそのまま並べた場合、1.8MBytesほど消費することになります。
TrieBuilder builder;
builder.Init();
auto loop = [&](std::function<bool(const char*)> func) {
char buf[5];
buf[4] = '\0';
for (char ch0 = 'a'; ch0 <= 'z'; ++ch0) {
buf[0] = ch0;
for (char ch1 = 'a'; ch1 <= 'z'; ++ch1) {
buf[1] = ch1;
for (char ch2 = 'a'; ch2 <= 'z'; ++ch2) {
buf[2] = ch2;
for (char ch3 = 'a'; ch3 <= 'z'; ++ch3) {
buf[3] = ch3;
if (!func(buf)) return false;
}
}
}
}
return true;
};
bool result = loop([&](const char* str) { return builder.AddWord(str); });
SUCCEED_IF(result);
auto trie = builder.Build2();
nlib_printf("The size of the words([a-z][a-z][a-z][a-z]): %d bytes\n", 4 * 26 * 26 * 26 * 26);
nlib_printf("The size of the trie for them: %" PRIuS " bytes\n", trie->MemSize());
result = loop([&](const char* str) {
int val = 0;
trie->Match(str, [](const char* first, const char* last, uint32_t nodeid, void* user_obj) {
NLIB_UNUSED(nodeid);
NLIB_UNUSED(first);
NLIB_UNUSED(last);
*reinterpret_cast<int*>(user_obj) = 1;
// nlib_printf("%s\n", std::string(first, last).c_str());
return true;
},
&val);
return val == 1;
});
SUCCEED_IF(result);
/*
Output:
The size of the words([a-z][a-z][a-z][a-z]): 1827904 bytes
The size of the trie for them: 785007 bytes
aaaa
....
zzzz
*/

Trie.h36 行目に定義があります。

型定義メンバ詳解

◆ MatchCallback

nn::nlib::succinct::Trie::MatchCallback

ユーザー定義のコールバック関数です。

引数
[in]first検出語の先頭(後ろ向きサーチの場合は最後尾)を指すポインタ
[in]last検出語の直後(後ろ向きサーチの場合は直前)を指すポインタ
[in]nodeid検出した語のID(連続値ではない)
[in,out]user_objユーザー指定オブジェクトへのポインタ
戻り値
trueの場合は引き続き解析を続ける。falseの場合は処理を打ち切り
説明
文字列(パターン)を検出した場合に呼び出されます。 ユーザーはそれに対応した処理を記述します。

Trie.h42 行目に定義があります。

関数詳解

◆ Export()

nn::nlib::succinct::Trie::Export ( BinaryWriter w) const
noexcept

オブジェクトを(ファイルに)書き出します。

引数
[in]w書き出し用オブジェクト
戻り値
成功した場合はtrue
説明
書きだしたデータはImport()関数で読みだして復元することができます。 また、データは常にリトルエンディアンで書き出されます。

◆ GetCommonPrefixWords() [1/2]

nn::nlib::succinct::Trie::GetCommonPrefixWords ( const void *  prefix,
size_t  n,
ReallocCstringVec vec 
)
noexcept

共通のプレフィックスを持つデータを辞書順にリストアップします。

引数
[in]prefixプレフィックスへのポインタ
[in]nプレフィックスの長さ
[out]vecprefix をプレフィックスとして持つ文字列が格納されるベクタ
戻り値
0ならば成功

◆ GetCommonPrefixWords() [2/2]

nn::nlib::succinct::Trie::GetCommonPrefixWords ( const void *  prefix,
size_t  n 
)
noexcept

共通のプレフィックスを持つデータのnodeidのリストを返します。

引数
[in]prefixプレフィックスへのポインタ
[in]nプレフィックスの長さ
戻り値
エラー値とnodeidのリストのペア
説明
nodeidMatchCallbackの引数に渡される整数です。
以下のようなコードでsuffix trieを構築して利用する応用が存在します。
// text from https://en.wikipedia.org/wiki/Trie
const char* str = R"(In computer science, a trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is a kind of search tree - an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are not necessarily associated with every node. Rather, values tend only to be associated with leaves, and with some inner nodes that correspond to keys of interest. For the space-optimized presentation of prefix tree, see compact prefix tree.)";
const size_t len = nlib_strlen(str);
TrieBuilder builder;
SUCCEED_IF(builder.Init());
// construct the suffix trie for 'str'
for (size_t i = 0; i < len - 1; ++i) {
SUCCEED_IF(builder.AddWord(str + i));
}
auto trie = builder.Build2();
// map nodeid -> pos in 'str'
std::map<uint32_t, size_t> nodeid_to_pos;
struct UserObj {
std::map<uint32_t, size_t>* nodeid_to_pos;
size_t i;
} uobj;
uobj.nodeid_to_pos = &nodeid_to_pos;
for (size_t i = 0; i < len - 1; ++i) {
uobj.i = i;
trie->Match(str + i, [](const char*, const char*, uint32_t nodeid, void* user_obj) {
UserObj* u = reinterpret_cast<UserObj*>(user_obj);
(*u->nodeid_to_pos)[nodeid] = u->i;
return true;
}, &uobj);
}
// list the occurences of the specified pattern
auto list_up = [&](const char* pat) {
nlib_printf("---- %s ----\n", pat);
size_t l = nlib_strlen(pat);
auto result = trie->GetCommonPrefixWords(pat, l);
if (result.first != 0) return;
for (auto& nodeid : result.second) {
size_t pos = nodeid_to_pos[nodeid];
size_t first = pos >= 10 ? pos - 10 : 0;
size_t last = pos + 10 + l < len ? pos + 10 + l : len;
nlib_printf("%s\n", std::string(str + first, str + last).c_str());
}
};
list_up("tree");
list_up("of");
/*
Output:
---- tree ----
or prefix tree (as they
of search tree - an orde
d digital tree and somet
n ordered tree data stru
on in the tree defines t
mes radix tree or prefix
de in the tree stores th
ry search tree, no node
of prefix tree, see comp
ct prefix tree.
---- of ----
scendants of a node ha
d to keys of interest.
sentation of prefix tr
is a kind of search tr
on prefix of the strin
*/

◆ Import()

nn::nlib::succinct::Trie::Import ( BinaryReader r)
noexcept

書き出されたオブジェクトを読み出します。

引数
[in]r読み出し用オブジェクト
戻り値
インポートが成功した場合はtrue

◆ Match() [1/2]

nn::nlib::succinct::Trie::Match ( const char *  cstr,
MatchCallback  callback,
void *  user_obj 
)
inlinenoexcept

文字列を検査してTrieに登録されている文字列を検出します。

引数
[in]cstrヌル終端する文字列
[in]callback語が検出された場合に呼び出されるコールバック関数
[in,out]user_objユーザー指定オブジェクトへのポインタ

Trie.h44 行目に定義があります。

◆ Match() [2/2]

nn::nlib::succinct::Trie::Match ( const void *  data,
size_t  n,
MatchCallback  callback,
void *  user_obj 
)
noexcept

データを走査して検出対象のパターンを検出します。

引数
[in]data検査対象のデータの先頭へのポインタ
[in]nデータサイズ
[in]callbackパターンが検出された場合に呼び出されるコールバック関数
[in,out]user_objユーザー指定オブジェクトへのポインタ

◆ MatchBackward()

nn::nlib::succinct::Trie::MatchBackward ( const void *  data,
size_t  n,
MatchCallback  callback,
void *  user_obj 
)
noexcept

データを後ろ向きに走査して検出対象のパターンを検出します。

引数
[in]data検査対象のデータの最後尾へのポインタ
[in]nデータサイズ
[in]callbackパターンが検出された場合に呼び出されるコールバック関数
[in,out]user_objユーザー指定オブジェクトへのポインタ

◆ MemSize()

nn::nlib::succinct::Trie::MemSize ( ) const
noexcept

このクラスが明示的に確保するメモリ量を返します。

戻り値
バイト数
説明
実際にシステムが確保するメモリ量はアライメントやヒープの管理領域の関係上この関数の返り値より大きい可能性があります。

このクラス詳解は次のファイルから抽出されました: