プレフィックスツリーとC ++の実装



Prefix Tree C Implementation



記事のディレクトリ

プレフィックスツリー

1トライツリーとは何ですか?

トライツリー、つまり単語検索ツリーとも呼ばれるプレフィックスツリーは、ハッシュツリーの変形であるツリー構造です。一般的なアプリケーションは、(文字列だけでなく)多数の文字列をカウントおよびソートするために使用されるため、テキスト単語の頻度統計のために検索エンジンシステムでよく使用されます。

トライツリー 本旨 文字列を使用して、時間のスペースです 共通のプレフィックス クエリ時間のオーバーヘッドを減らして効率を上げるため。その 利点 はい:不要な文字列の比較を最小限に抑えます。クエリの効率はハッシュテーブルよりも高くなります。



それは3つあります 基本的な性質

  1. ルートノードには文字が含まれず、ルートノードを除く各ノードには1文字しか含まれません。
  2. ルートノードからノードまで、パスを通過する文字が接続されます。これは、ノードに対応する文字列です。
  3. 各ノードのすべての子には、異なる文字が含まれています。

2ツリーの構築とクエリ

例に従って、トライツリーの構造を説明します。
トピック :長さが10以下の100,000語の場合、各単語が出現したかどうかを判断し、出現した場合は最初の出現位置を指定します。
思想 :すべての単語の単語シーケンス全体をトラバースすると、時間計算量は次のようになります。O(n 2)O(n ^ 2)単語シーケンスの長さは100,000であり、明らかにそのような時間計算量は高すぎます。しかし、100,000語を考慮すると、文字列の繰り返しが必要であり、この問題の最も適切な解決策は、プレフィックスツリーであるトライツリーです。プレフィックスツリーの形式は何ですか?
abc、abd、bcd、efg、hiiを想定して、次の単語を表すツリー構造を構築します。



画像

ただし、プレフィックスツリーを作成すると、同じプレフィックスを持つ単語をすばやくトラバースできるようになります。現在、マルチフォークツリーのルートノードからリーフノードへの各パスは単語です。単語b、abcd 2単語、またはそのような方法を黒くする方法を追加すると、短い文字が格納されているかどうかを区別できません。この問題を解決するために、たとえば、ノードに情報を記録できます。単語が文字の後に終わる場合は、その時点です。end+ 1がノードに記録されるため、接頭辞で終わる単語がいくつかあることがわかります。変更後の構造は次のとおりです。

画像

これが私たちがはっきりと見ることができるものです。左端のパスには、abcという単語とabcdという単語があります。新たに追加された情報によると、すべての文字列に含まれる文字列の数を知ることができます。ここで別の問題が発生した場合、すべての文字列の前に文字列がいくつあるか知りたいのですが、文字列をトラバースする必要がありますか?パスの背後にあるノードは、すべての端を合計します。簡単にするために、ノードにさらに多くの情報、各ノードが交差した回数を格納できます。つまり、マルチフォークツリーを作成するときに、特定の文字列に含まれるすべての文字列の数を記録します。プレフィックス、それが交差した回数はこの値です。調整された構造は次のとおりです。注:C ++の実装では、グラフ内のすべてのSが1ずつインクリメントされ、単語自体の前にそれ自体が付けられます。

画像

元のトピックに戻ると、ノードの情報に基づいて単語を取得すると(End> 0)、このような構造が現れる可能性がありますが、満たされていないという要件があります。つまり、この単語がある場合、どのように元のリストの単語を返しますか?場所はどこですか?上で紹介したマルチフォークツリー構造の紹介によると、この問題も非常に簡単に解決できると思います。ノードには、より多くの情報を格納できます。非終了文字End = 0の場合、他の情報を格納する必要はありません。 End> 0の場合、この時点で情報が再度保存され、100000語の語彙における単語の位置がマークされます。クエリマルチフォークツリーを構築すると、位置情報を直接返すことができます。



3トライツリーアプリケーション

この記事の概要で説明した問題は、Trieツリーを使用して解決できることに加えて、Trieツリーは次の問題も解決できます(この記事から抜粋: 大規模なデータ処理の面接の質問とビットマップの詳細な説明 正直なところ、著者の要約はかなり完全ですが、それは常に厄介な感じがします... Tucaoは間違っています、私は反映しています...):

  • 3、1Gサイズのファイルがあり、各行はワードであり、ワードのサイズは16バイトを超えず、メモリ制限サイズは1Mです。頻度が最も高い上位100語を返します。
  • 9、1,000万の文字列、一部は重複しています。重複する文字列を残さずに、すべての重複を削除する必要があります。どのように設計および実装しますか?
  • 10、テキストファイル、約10,000行、1行に1単語、最も頻繁に出現する単語のトップ10を数えるように求められました。アイデアを与え、時間計算量分析を行ってください。
  • 13.人気のあるクエリを探す:検索エンジンは、ログファイルを介して各検索でユーザーが使用したすべての検索文字列を記録します。各クエリ文字列の長さは1〜255バイトです。現在1,000万件のレコードがあるとすると、これらのクエリ文字列の繰り返し読み取りは、合計が1,000万件であるにもかかわらず比較的高くなりますが、重複が削除された場合、300万件以下になります。クエリ文字列の再現性が高いほど、クエリ文字列のユーザー数が多くなり、人気が高まります。最も人気のある10個のクエリ文字列を数えてください。必要なメモリは1Gを超えることはできません。
    (1)この問題を解決するためのあなたの考えを説明してください
    (2)主な処理フロー、アルゴリズム、およびアルゴリズムの複雑さを教えてください。

4 C ++はTrieツリーを実装し、いくつかの文字列の問題を解決します

1つの文字列型配列arr1、別の文字列型配列arr2。

  • arr1に表示されるarr2の文字列は何ですか?印刷してください
  • arr1で文字列プレフィックスとして表示されるarr2の文字列は何ですか?印刷してください
  • arr1で文字列プレフィックスとして表示されるarr2の文字列は何ですか? arr2で最も多く出現するプレフィックスを印刷してください。

結果を下図に示します。

画像#include #include #include using namespace std const int MaxBranchNum = 26/ / can be extended class TrieNode{ public: string word int path //How many times has the character been crossed to count the number of strings prefixed with the string? int End //String ending with this character TrieNode* nexts[MaxBranchNum] TrieNode() { word = '' path = 0 End = 0 memset(nexts,NULL,sizeof(TrieNode*) * MaxBranchNum) } } class TrieTree{ private: TrieNode *root public: TrieTree() ~TrieTree() / / Insert string str void insert(string str) / / Query the string str has appeared, and returned as a prefix several times int search(string str) / / Delete the string str void Delete(string str) void destory(TrieNode* root) / / Print all the nodes in the tree void printAll() / / Print the word prefixed with str void printPre(string str) / / Output all words rooted in root in lexicographic order void Print(TrieNode* root) / / Returns the number of words prefixed by str int prefixNumbers(string str) } TrieTree::TrieTree() { root = new TrieNode() } TrieTree::~TrieTree() { destory(root) } void TrieTree::destory(TrieNode* root) { if(root == nullptr) return for(int i=0i<MaxBranchNumi++) { destory(root->nexts[i]) } delete root root = nullptr } void TrieTree::insert(string str) { if(str == '') return char buf[str.size()] strcpy(buf, str.c_str()) TrieNode* node = root int index = 0 for(int i=0 i<strlen(buf) i++) { index = buf[i] - 'a' if(node->nexts[index] == nullptr) { node->nexts[index] = new TrieNode() } node = node->nexts[index] node->path++/ / There is a path across this node } node->End++ node->word = str } int TrieTree::search(string str) { if(str == '') return 0 char buf[str.size()] strcpy(buf, str.c_str()) TrieNode* node = root int index = 0 for(int i=0i<strlen(buf)i++) { index = buf[i] - 'a' if(node->nexts[index] == nullptr) { return 0 } node = node->nexts[index] } if(node != nullptr) { return node->End }else { return 0 } } void TrieTree::Delete(string str) { if(str == '') return char buf[str.size()] strcpy(buf, str.c_str()) TrieNode* node = root TrieNode* tmp int index = 0 for(int i = 0 i<str.size()i++) { index = buf[i] - 'a' tmp = node->nexts[index] if(--node->nexts[index]->path == 0) { delete node->nexts[index] } node = tmp } node->End-- } int TrieTree::prefixNumbers(string str) { if(str == '') return 0 char buf[str.size()] strcpy(buf, str.c_str()) TrieNode* node = root int index = 0 for(int i=0i<strlen(buf)i++) { index = buf[i] - 'a' if(node->nexts[index] == nullptr) { return 0 } node = node->nexts[index] } return node->path } void TrieTree::printPre(string str) { if(str == '') return char buf[str.size()] strcpy(buf, str.c_str()) TrieNode* node = root int index = 0 for(int i=0i<strlen(buf)i++) { index = buf[i] - 'a' if(node->nexts[index] == nullptr) { return } node = node->nexts[index] } Print(node) } void TrieTree::Print(TrieNode* node) { if(node == nullptr) return if(node->word != '') { cout<<node->word<<' '<<node->path<<endl } for(int i = 0i<MaxBranchNumi++) { Print(node->nexts[i]) } } void TrieTree::printAll() { Print(root) } int main() { cout << 'Hello world!' << endl TrieTree trie string str = 'li' cout<<trie.search(str)<<endl trie.insert(str) cout<<trie.search(str)<<endl trie.Delete(str) cout<<trie.search(str)<<endl trie.insert(str) cout<<trie.search(str)<<endl trie.insert(str) cout<<trie.search(str)<<endl trie.Delete('li') cout<<trie.search(str)<<endl trie.Delete('li') cout<<trie.search(str)<<endl trie.insert('lia') trie.insert('lic') trie.insert('liab') trie.insert('liad') trie.Delete('lia') cout<<trie.search('lia')<<endl cout<<trie.prefixNumbers('lia')<<endl return 0 }