PAT trie

最近在上计算机应用编程，老师给了一个大小为900MB的含20000000行邮箱地址的文件。 然后再给出了1000条查询数据，让你用字典树建树然后查询是否出现过。

试了下普通的tire树，特意用二进制写了下，结果才建了300000的时候就快用了2G内存，根本不行。

后面学习了下 PAT trie,发现确实是好东西，已经几乎达到最优内存了，如果有N个记录，那么只需要2*N个节点即可建成字典树。

算法的关键在于先将记录用一串二进制位表示，然后在建树的时候只在一些具有区别作用的二进制位进行节点分裂。

具体见http://hxraid.iteye.com/blog/615295，这篇博客讲的比较详细。

这里给出我用C++实现的代码。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
using namespace std;
#define MAXLEN 1000000000LL
#define N 20020000
struct node
{
    int l,r;
    int pos;
    bool flag;//用来标记是否是叶子节点
    int end_point;//指向叶子节点.
}g[2*N];

char saveword[MAXLEN];
int word_pos[N];
short int word_len[N];
int n;
char str[120];
int len;
int cnt;
char qest[1010][120];
bool flag_ans[1100];

void build_tree(int s,int head)
{
    if(g[head].flag==1)//表示叶子结点
    {
        int tn=g[head].end_point;
        int num=(s>>3);
        int other=(s&7);
        int ta,tb;
        while(1)
        {
            if(num>=len) break;
            ta=(str[num]&(1<<(7-other)) );
            tb=(saveword[(word_pos[tn]+num)]&(1<<(7-other)));
            if( ta!=tb )
            {
                //开始分裂
                g[cnt]=g[head];
                cnt++;
                g[head].flag=0;
                g[head].pos=(num<<3)+other;
                if(tb==0)
                    g[head].l=cnt-1;
                else g[head].r=cnt-1;
                g[cnt].end_point=n;
                g[cnt].flag=1;
                cnt++;
                if(ta!=0)
                    g[head].r=cnt-1;
                else g[head].l=cnt-1;
                break;
            }
            other++;
            if(other==8)
            {
                num++;
                other=0;
            }
        }
    }
    else
    {
        int tn=g[head].end_point;
        int tpos=g[head].pos;
        int num;
        int other;
        int ta,tb;
        for(int i=s;i<tpos;i++)
        {
            num=(i>>3);
            other=(i&7);
            ta=(str[num]&(1<<(7-other)) );
            tb=(saveword[(word_pos[tn]+num)]&(1<<(7-other)));
            if(ta!=tb)//ta!=tb
            {
                g[cnt]=g[head];
                cnt++;
                g[head].flag=0;
                g[head].pos=i;
                if(tb!=0)
                    g[head].r=cnt-1;
                else g[head].l=cnt-1;
                g[cnt].flag=1;
                g[cnt].end_point=n;
                cnt++;
                if(ta!=0) g[head].r=cnt-1;
                else g[head].l=cnt-1;
                return ;
            }
        }
        num=(tpos>>3);
        other=(tpos&7);
        ta=(str[num]&(1<<(7-other)) );
        if(ta==0)
        {
            build_tree(tpos+1,g[head].l);
        }
        else build_tree(tpos+1,g[head].r);
    }
}

int check_tree(int s)
{
    if(g[s].flag==1)
    {
        int tn=g[s].end_point;
        if(len!=word_len[tn]) return 0;
        for(int i=0;i<len;i++)
        {
            if(str[i]!=saveword[ word_pos[tn]+i ]) return 0;
        }
        return 1;
    }
    int tpos=g[s].pos;
    int num=(tpos>>3);
    int other=(tpos&7);
    int ta;
    ta=(str[num]&(1<<(7-other)) );
    if(ta!=0) return check_tree(g[s].r);
    else return check_tree(g[s].l);
}

void check()
{
    //freopen("G:\\session1\\checklist.dat","r",stdin);
    //cin>>T;
    //getchar();

    //int ansans=0;
    for(int i=0;i<1000;i++)
    {
        strcpy(str,qest[i]);
        len=strlen(str);
        str[len]='#';
        len++;
        str[len]=0;
        for(int j=0;j<len;j++)
        {
            if(str[j]>='A'&&str[j]<='Z')
                str[j]=str[j]-'A'+'a';
        }
        int sign1=check_tree(0);
        //ansans+=sign1;
        if(sign1==1)
            flag_ans[i]=1;
        //if(sign1==1) printf("%s\n",str);
        //T--;
        //if(T==0) break;
    }
}

int main()
{
    freopen("checklist.dat","r",stdin);
    freopen("checkedresult.dat","w",stdout);
    int tcnt=0;
    while(scanf("%s",qest[tcnt])!=EOF) tcnt++;
    //printf("%d\n",tcnt);
    freopen("emaillist.dat","r",stdin);
    //int T;
    //cin>>T;
    //getchar();
    n=0;
    cnt=0;
    int first_flag=0;
    int tmp_pos=0;
    int cntt=0;
    while(scanf("%s",str)!=EOF)
    {
        cntt++;
        if(cntt==10000000)
        {
            char tstr[120];
            strcpy(tstr,str);
            check();
            cnt=0;
            n=0;
            first_flag=0;
            tmp_pos=0;
            strcpy(str,tstr);
        }
        word_pos[n]=tmp_pos;
        len=strlen(str);
        str[len]='#';
        len++;
        word_len[n]=len;
        for(int i=0;i<len;i++)
        {
            if(str[i]>='A'&&str[i]<='Z')
                str[i]=str[i]-'A'+'a';
            saveword[tmp_pos++] = str[i];
        }
        //然后就是构树了
        if(first_flag==0)
        {
            first_flag=1;
            g[0].flag=1;//为n号叶子结点。
            g[0].end_point=n;
            cnt++;
        }
        else
        {
            build_tree(0,0);
        }
        n++;
        //if(n%100000==0) printf("%d\n",n);

        //T--;
        //if(T==0) break;
    }
    check();
    int ansans=0;
    for(int i=0;i<1000;i++)
    {
        if(flag_ans[i]==1)
            printf("yes\n");
        else printf("no\n");
        ansans+=flag_ans[i];
    }
    printf("%d\n",ansans);
    return 0;
}

原文链接: https://www.cnblogs.com/chenhuan001/p/4885599.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍