辞書ツリーとぼかし検索
3796 ワード
辞書ツリーは文字列を格納するツリー構造で、次のような場面があると仮定して、文字列の山を与えて、ある文字列をプレフィックスとする文字列の個数を求めさせます.
例えばabcd、abceをあげて、abcをプレフィックスとする文字列の個数を求めます.
コードは以下の通りです
以下のコードは他のブログから出ていますが、ノードの削除コードが不完全で、修正済みです.
例えばabcd、abceをあげて、abcをプレフィックスとする文字列の個数を求めます.
コードは以下の通りです
#include
#include
using namespace std;
typedef struct _Node
{
int count;
struct _Node * pNodeArr[26];
_Node()
{
count=0;
memset(pNodeArr,NULL,sizeof(struct _Node *)*26);
}
}Node,*PNode;
PNode pRoot;
void InsertTree(string str)
{
if(pRoot==NULL)
{
pRoot=new Node();
}
int i=0;
PNode pTmp=pRoot;
while(ipNodeArr[index]==NULL)
{
pTmp->pNodeArr[index]=new Node();
}
pTmp=pTmp->pNodeArr[index];
pTmp->count++;
i++;
}
}
int FindStrNumber(string str)
{
int i=0;
PNode pTmp=pRoot;
while(ipNodeArr[index]==NULL)
{
// , -1
return -1;
}
pTmp=pTmp->pNodeArr[index];
i++;
}
return pTmp->count;
}
int main()
{
pRoot=NULL;
string str;
cin>>str;
InsertTree(str);
cin>>str;
InsertTree(str);
cin>>str;
InsertTree(str);
cin>>str;
cout<
以上は辞書の木の一例です.検索エンジンの応用において、私たちはよくスマートプロンプトやあいまいな検索の例に出会います.例えば、あなたがリンゴを入力すると、検索ボックスにリンゴに関するすべての高周波語彙が並べられます.これも辞書ツリーを使って実現できます.以下のコードは他のブログから出ていますが、ノードの削除コードが不完全で、修正済みです.
#include
#include
#include
using namespace std;
typedef struct _Node
{
bool bEnd;
struct _Node * pNodeArr[256];
_Node()
{
bEnd=false;
memset(pNodeArr,NULL,sizeof(struct _Node *)*256);
}
}Node,*PNode;
class Trie
{
public:
Trie();
~Trie();
void InsertTree(string str);
void FindStr(string str,vector &vecRet);
void FindEndStr(PNode pTmp,string str,vector & vecRet);
void DeleteNode( PNode node);
private:
PNode pRoot;
};
Trie::Trie()
{
pRoot=new Node();
}
Trie::~Trie()
{
DeleteNode(pRoot);
}
void Trie::InsertTree(string str)
{
int i=0;
PNode pTmp=pRoot;
while(ipNodeArr[index]==NULL)
{
pTmp->pNodeArr[index]=new Node();
}
pTmp=pTmp->pNodeArr[index];
i++;
}
pTmp->bEnd=true;
}
void Trie::FindEndStr(PNode pTmp,string str,vector & vecRet)
{
//
if(pTmp->bEnd)
{
vecRet.push_back(str);
return;
}
int i;
//
for(i=0;i<256;i++)
{
if(pTmp->pNodeArr[i]==NULL)
continue;
unsigned char c=(unsigned char )i;
FindEndStr(pTmp->pNodeArr[i],str+(char)c,vecRet);
}
return;
}
void Trie::FindStr(string str,vector & vecRet)
{
int i=0;
PNode pTmp=pRoot;
while(ipNodeArr[index]==NULL)
{
// ,
cout<pNodeArr[index];
i++;
}
FindEndStr(pTmp,str,vecRet);
}
void Trie::DeleteNode(PNode node)
{
//
if(node->bEnd)
{
delete node;
return;
}
int i;
for(i=0;i<256;i++)
{
if(node->pNodeArr[i]==NULL)
continue;
DeleteNode(node->pNodeArr[i]);
}
delete node;
return;
}
int main()
{
Trie * myTrie=new Trie();
myTrie->InsertTree(" 1 ");
myTrie->InsertTree(" 2 ");
myTrie->InsertTree(" 3 ");
string query;
cout<>query; // query
vector result;
myTrie->FindStr(query,result);
vector::iterator iter = result.begin(); //
cout<