Google字符串模糊匹配算法，字典树模糊查询

时间：2022-12-30 13:34:50

转载自：http://blog.csdn.net/shifuwawa/article/details/5595514

好吧，我承认我又装13标题党了。其实是G查询关键词过程中匹配的一点大概的算法框架，G的模糊匹配大家都知道，比如你输入64什么的，G会自动列出你心里可能要找

到东西，如下图:Google字符串模糊匹配算法，字典树模糊查询

那这个算法是怎么实现的呢，用到了一种高级数据结构--字典树，或者说是字典树思想，因为字典树不规定你具体怎么实现，可以二维数组，可以map……也可以通常的结构体+next指针。可以通过一个题来讲述，就是2009ACM/ICPC 哈尔滨 reginal现场赛G题：Fuzzy Google Suggest（http://acm.hit.edu.cn/judge/show.php?Proid=2888&Contestid=0）讲解。当时我搞这题，不知道字典树，然后一直模拟，结果……(— —|||)先用输入的单词构造一棵字典树，节点数据包括：cnt，表示节点上的字母被多少个单词经过；vis，0表示经过此节点不能继续匹配，1表示经过此节点可继续匹配，2表示此节点就是恰好用于匹配的前缀的最后一个字符；然后一个next数组，大小26，但不是node指针，而是int数组，表示当前节点的儿子，next[i]==-1表示当前节点没有第i个儿子，否则有，并将此儿子结点进行编号，其编号就是它在字典树中的编号。然后根据编辑距离进行dfs遍历；函数设计为dfs(int x,int pos,intedit,char* key),x是trie树中第x个节点，pos表示匹配到了前缀字符key的第pos个字符，edit表示剩余可用的编辑距离。假如某个字符符合当前前缀的匹配条件，则trie节点向儿子结点递归，pos++，edit不变dfs(root[x].next[key[pos]-'a'],++pos,edit,key)；否则尝试使用编辑距离：1，增加一个字符，此时要遍历26个字符，看增加哪个合法（即此字符在trie中出现了并且是当前key[pos]的儿子节点并且此字符不跟key[pos]相同），然后继续dfs,此时编辑距离少一个，key的位置不变，trie走向儿子节点，假设增加的字符编号为i，则dfs(root[x].next[i],++pos,edit-1,key)；2，替换一个字符，此时edit减一，pos向前走一个，dfs(root[x].next[i],pos+1,edit-1,key);3,删除一个字符，删除表示为trie节点不变，但是前缀字符串key串往下走一个，相当于就没匹配上的忽略，dfs(x,pos+1,edit-1,key),若能遍历下去，且x节点之前不可通行，则将x标记为可通行.到达匹配终点的条件有三个：1，前缀串key一路匹配到了末尾，此时的结点x被标记为，root[x].vis=2,表示它是某个前缀串的终结者。2，在tire中一路通行突然edit用完透支了，那这个前缀串没有找到匹配的单词，回溯。3，碰到了某个节点x,root[x].vis=2,说明到x这个前缀串已经能够匹配。返回可以匹配。然后再利用dfs_calc函数计数符合匹配的单词数量:vis=2的结点。最后用dfs_clear()函数清理trie树。关于销毁trie树，见有人用一个for循环搞定的，那样只是把和根节点直接相连的结点进行了delete，但是其他的都变成悬空状态，并未被销毁。坏习惯(但对ACM题来说不失为一种销毁的捷径)。不过用struct写的交上去老是RE，极度掣肘，只好参看某牛的改作数组实现的trie：
RE的：

[cpp] view plaincopy
  1. #include<pzjay>  
  2. #<一坨头文件>  
  3. const int sup=500005;  
  4. int tot;//tire结点个数  
  5. int len;//记录前缀词 的长度  
  6. int ans;//记录此前缀匹配单词的个数  
  7. struct node  
  8. {  
  9.     int cnt;//表示此字母被多少个单词经过  
  10.     int vis;//vis=0表示经过此单词不能够到达要匹配的结点;1表示可以;2表示此字母就是匹配前缀的最后一个字母(即匹配完毕)  
  11.     int next[26];  
  12. }root[sup];  
  13. void creat(char key[])  
  14. {  
  15.     int i=0,index;  
  16.     int k=1;//root下标  
  17.     while(key[i])  
  18.     {  
  19.         index=key[i]-'a';  
  20.         if(-1==root[k].next[index])  
  21.         {  
  22.             root[k].next[index]=tot;//将root[tot]的地址赋给tmp->next[index]  
  23.             root[tot].cnt=1;  
  24.             root[tot].vis=0;  
  25.             ++tot;  
  26.         }  
  27.         else  
  28.             ++root[root[k].next[index]].cnt;  
  29.         k=root[k].next[index];  
  30.         ++i;  
  31.     }  
  32. }  
  33. int dfs(int x,int pos,int edit,char* key)//返回是否成功匹配  
  34. {  
  35.     if(2==root[x].vis)//到达一个匹配的结束点  
  36.         return 1;  
  37.     if(edit<0)  
  38.         return 0;  
  39.     if(pos==len)//到达前缀的末尾  
  40.     {  
  41.         root[x].vis=2;//该节点是前缀的结束字母，x之前的单词串被成功匹配  
  42.         return 1;  
  43.     }  
  44.     int index=key[pos]-'a';  
  45.     if(-1!=root[x].next[index])//还有儿子结点  
  46.         if(dfs(root[x].next[index],pos+1,edit,key))  
  47.             root[x].vis=1;  
  48.     for(int i=0;i<26;++i)  
  49.     {  
  50.         index=key[pos]-'a';  
  51.         if(index==i || -1==root[x].next[i])//在树中找可替换的字符  
  52.             continue;  
  53.         if(dfs(root[x].next[i],pos+1,edit-1,key))//将pos处的字母尝试用i+'a'代替  
  54.             root[x].vis=1;  
  55.         if(dfs(root[x].next[i],pos,edit-1,key))//插入一个字母  
  56.             root[x].vis=1;  
  57.     }  
  58.     if(dfs(x,pos+1,edit-1,key))//delete  
  59.         if(0==root[x].vis)  
  60.             root[x].vis=1;  
  61.     return root[x].vis;  
  62. }  
  63. void dfs_calc(int x)  
  64. {  
  65.     if(2==root[x].vis)  
  66.     {  
  67.         ans+=root[x].cnt;  
  68.         return;  
  69.     }  
  70.     for(int i=0;i<26;++i)  
  71.         if(root[root[x].next[i]].vis > 0)  
  72.             dfs_calc(root[x].next[i]);  
  73. }  
  74. void dfs_clear(int x)  
  75. {  
  76.     root[x].vis=0;  
  77.     for(int i=0;i<26;++i)  
  78.         if(root[root[x].next[i]].vis > 0)  
  79.             dfs_clear(root[x].next[i]);  
  80. }  
  81. int main()  
  82. {  
  83.     int n;  
  84.     //freopen("1.txt","r",stdin);  
  85.     while(scanf("%d",&n)!=EOF)  
  86.     {  
  87.         tot=2;  
  88.         char key[25];  
  89.         int m;  
  90.         int edit;//编辑距离  
  91.         for(int i=0;i<sup;++i)  
  92.             memset(root[i].next,-1,sizeof(root[i].next));  
  93.         //fill(root[i].next,root[i].next+26,-1);  
  94.         while(n--)  
  95.         {  
  96.             scanf("%s",key);  
  97.             creat(key);  
  98.         }  
  99.         scanf("%d",&m);//m个前缀  
  100.         while(m--)  
  101.         {  
  102.             ans=0;  
  103.             scanf("%s %d",key,&edit);  
  104.             len=strlen(key);  
  105.             dfs(1,0,edit,key);  
  106.             //1是x的起始遍历位置，0是前缀key的起始位置，edit是剩余的编辑距离  
  107.             dfs_calc(1);//计数符合匹配的单词个数  
  108.             dfs_clear(1);//清空x  
  109.             printf("%d/n",ans);  
  110.         }  
  111.     }  
  112.     return 0;  
  113. }  
  114.   
  115. AC：  
  116. const int sup=700005;  
  117. int tot;//tire结点个数  
  118. int len;//记录前缀词 的长度  
  119. int ans;//记录此前缀匹配单词的个数  
  120. int root[sup][26];//每个节点最多26个分支  
  121. int cnt[sup],vis[sup];//cnt[i]记录字母i被多少个单词经过  
  122. void creat(char key[])  
  123. {  
  124.     int k=1,index,i=0;  
  125.     while(key[i])  
  126.     {  
  127.         index=key[i]-'a';  
  128.         if(-1==root[k][index])  
  129.             root[k][index]=tot++;  
  130.         k=root[k][index];  
  131.         ++cnt[k];  
  132.         ++i;  
  133.     }  
  134. }  
  135. int dfs(int x,int pos,int edit,char key[])  
  136. {  
  137.     if(2==vis[x])  
  138.         return 1;  
  139.     if(edit<0)  
  140.         return 0;  
  141.     if(pos==len)//匹配完毕，节点x成为前缀词key的结尾字母  
  142.     {  
  143.         vis[x]=2;  
  144.         return  1;  
  145.     }//以上可以直接return的，都是最终的结果:匹配成功或者失败  
  146.     //下面的只是递归到最重结果的过程，故是对vis赋值  
  147.     int index=key[pos]-'a';  
  148.     if(-1!=root[x][index])//可以继续往深层遍历  
  149.         if(dfs(root[x][index],pos+1,edit,key))  
  150.             vis[x]=1;//从x往下可以走到目标节点  
  151.     for(int i=0;i<26;++i)  
  152.     {  
  153.         index=key[pos]-'a';  
  154.         if(index==i || -1==root[x][i])//筛选掉跟要替换的字母相同的字母和未在trie树中出现的字母  
  155.             continue;  
  156.         if(dfs(root[x][i],pos+1,edit-1,key))//pos++，遍历下一个字母，表示替换一个trie树中存在的字母  
  157.                 vis[x]=1;  
  158.         if(dfs(root[x][i],pos,edit-1,key))//pos不变.表示增加一个字母  
  159.                 vis[x]=1;  
  160.     }  
  161.     if(dfs(x,pos+1,edit-1,key))//删除一个字母  
  162.         if(0==vis[x])  
  163.             vis[x]=1;  
  164.     return vis[x];  
  165. }  
  166. void dfs_calc(int x)  
  167. {  
  168.     if(2==vis[x])  
  169.     {  
  170.         ans+=cnt[x];  
  171.         return;  
  172.     }  
  173.     for(int i=0;i<26;++i)  
  174.         if(vis[root[x][i]])  
  175.             dfs_calc(root[x][i]);  
  176. }  
  177. void dfs_clear(int x)  
  178. {  
  179.     vis[x]=0;  
  180.     for(int i=0;i<26;++i)  
  181.         if(vis[root[x][i]])  
  182.             dfs_clear(root[x][i]);  
  183. }  
  184. int main()  
  185. {  
  186.     int n;  
  187.       
  188.     char key[16];  
  189.       
  190.     while(scanf("%d",&n)!=EOF)  
  191.     {  
  192.         int edit,m;  
  193.         memset(root,-1,sizeof(root));  
  194.         memset(vis,0,sizeof(vis));  
  195.         memset(cnt,0,sizeof(cnt));  
  196.         tot=2;  
  197.         while(n--)  
  198.         {  
  199.             scanf("%s",key);  
  200.             creat(key);  
  201.         }  
  202.         scanf("%d",&m);  
  203.         while(m--)  
  204.         {  
  205.             ans=0;  
  206.             scanf("%s %d",key,&edit);  
  207.             len=strlen(key);  
  208.             dfs(1,0,edit,key);  
  209.             dfs_calc(1);  
  210.             printf("%d/n",ans);  
  211.             dfs_clear(1);  
  212.         }  
  213.     }  
  214.     return 0;  
  215. }参看：http://acmicpc.org.cn/wiki/index.php?title=2009_Harbin_Fuzzy_Google_Suggest_Solution  
  216.   
  217. ps:转载注明出处：pzjay！  

除了模糊匹配外还有精确匹配，金山词霸手机版E文输入，T9输入法等许多优秀的手机E文输入软件都采用了精确匹配。以T9输入法为例，它摒弃传统的输入按键模式，假如你想输入ccc，传统的是要摁3*3=9下2键，但是假如ccc是经常使用的高频词汇的话，T9输入法只摁三下即可。牵扯到频率，肯定又是字典树的应用了，题目相关：HDOJ1298
本题先输入一个单词表，包括单词以及该单词的权值。然后输入一些数字串，要求模拟手机输入的过程，每输入一个数字，就输出对应的单词（如果没有对应的就输出MANUALLY），如果输入的数字会对应不同的单词的前缀，就输出权值之和最高的前缀（如果权值一样就按字母表顺序）。用Sample来说明，输入了hell，hello，idea这3个单词，权值对应分别为3,4,8，开始输入数字：输入4，4可以对应i和h，i是idea的前缀，权值之和为8，h是hell和hello的前缀，权值之和是3+4=7，输出权值较大的i；继续输入3,43对应的可以是he和id，同样因为id的权值大于he，就输出id；接下来输入5,435就只能对应hel了……依此类推，每次输出的都是权值之和最高的词
思想：trie+BFS
算法流程：
1。根据输入的单词建树
2。根据输入的按键序列依次转化为可能的字符序列，维护一个双端队列，将树中出现过(通过查找字典树实现)的字符序列入列，用于下次增加字符序列
3。若当前枚举到的按键序列遍历完所有可能后若最大权值还是-1，说明该按键序列没有匹配的字符串；否则输出权值最大的字符串即可。注意若字符序列中间出现不匹配，那么以后的都不匹配，但此时仍然要继续遍历依次输出不匹配，不能退出。见过HH大神map实现trie树的代码，很好很强大。(map <string,int>表示string出现的频率int)

[cpp] view plaincopy
  1. #include<iostream>  
  2. #include<一坨头文件>  
  3. #include<转载注明pzjay原创>  
  4. const int sup=100;  
  5. int num[10];//num[i]表示第i个键上面的字母个数  
  6. char T9[10][4];//T9[i][j]表示第i个键上第j个字母  
  7. deque <string> dq;  
  8. int n;  
  9. struct node  
  10. {  
  11.     int count;//记录出现次数  
  12.     node* next[26];  
  13.     node(int fre)  
  14.     {  
  15.         count=fre;  
  16.         memset(next,NULL,sizeof(next));  
  17.     }  
  18. };  
  19. node* root;  
  20. void creat(char key[],int freq)  
  21. {  
  22.     int i=0,index;  
  23.     node* tmp=root;  
  24.     while(key[i])  
  25.     {  
  26.         index=key[i]-'a';  
  27.         if(NULL==tmp->next[index])  
  28.             tmp->next[index]=new node(freq);  
  29.         else  
  30.             tmp->next[index]->count+=freq;  
  31.         tmp=tmp->next[index];  
  32.         ++i;  
  33.     }  
  34. }  
  35. int find(string key)  
  36. {  
  37.     int i=0,index;  
  38.     node* tmp=root;  
  39.     while(i<key.length())  
  40.     {  
  41.         index=key[i]-'a';  
  42.         if(NULL==tmp->next[index])  
  43.             return -1;  
  44.         tmp=tmp->next[index];  
  45.         ++i;  
  46.     }  
  47.     return tmp->count;//返回权值  
  48. }  
  49. void init()  
  50. {  
  51.     int i,j;  
  52.     char tmp='a';  
  53.     for(i=2;i<10;++i)  
  54.         num[i]=3;  
  55.     ++num[7];  
  56.     ++num[9];//第7和9个按键上各4个字母  
  57.     for(i=2;i<10;++i)  
  58.         for(j=0;j<num[i];++j)  
  59.             T9[i][j]=tmp++;  
  60. }  
  61. void dele()//删除字典树  
  62. {  
  63.     for(int i=0;i<26;++i)  
  64.         if(root->next[i])  
  65.             delete root->next[i];  
  66.     delete root;  
  67. }  
  68. int main()  
  69. {  
  70.     init();//初始化数组  
  71.     char key[110];  
  72.     int Case;  
  73.     scanf("%d",&Case);  
  74.     char tmp;  
  75.     int frequency;  
  76.     string str;  
  77.     for(int pzjay=1;pzjay<=Case;++pzjay)  
  78.     {  
  79.         root=new node(0);  
  80.         scanf("%d",&n);  
  81.         while(n--)  
  82.         {  
  83.             scanf("%s %d",key,&frequency);  
  84.             creat(key,frequency);  
  85.         }  
  86.         scanf("%d",&n);  
  87.         int id;  
  88.         string head;  
  89.         string ans;  
  90.         int max_frequency;  
  91.         printf("Scenario #%d:/n",pzjay);  
  92.         int increment,size;  
  93.         while(n--)  
  94.         {  
  95.             scanf("%s",key);  
  96.             size=1;//初始队列中一个元素  
  97.             while(!dq.empty())  
  98.                 dq.pop_back();  
  99.             dq.push_back("");//首先压入双端队列一个空字符串  
  100.             //转载注明出处:pzjay  
  101.             for(int i=0;key[i]!='1';++i)  
  102.             {  
  103.                 id=key[i]-'0';//将按键转化为数字  
  104.                 increment=0;  
  105.                 max_frequency=-1;  
  106.                 for(int k=0;k<size;++k)  
  107.                 {  
  108.                     head=dq.front();//或者dq[0]也可  
  109.                     dq.pop_front();  
  110.                     for(int j=0;j<num[id];++j)  
  111.                     {  
  112.                         str=head+T9[id][j];  
  113.                         int value=find(str);  
  114.                         if(-1!=value)//找到了  
  115.                         {  
  116.                             dq.push_back(str);  
  117.                             ++increment;//记录本次新增了多少个元素，本次新增的元素就是下次拓展的起点  
  118.                             if(value > max_frequency)  
  119.                             {  
  120.                                 max_frequency=value;  
  121.                                 ans=str;  
  122.                             }  
  123.                         }     
  124.                     }  
  125.                 }  
  126.                 size=increment;  
  127.                 if(max_frequency!=-1)  
  128.                     printf("%s/n",ans.c_str());  
  129.                 else  
  130.                     printf("MANUALLY/n");//其实这时可以退出for了，不过继续遍历也无妨，因为中间断掉，后面的肯定都不行  
  131.             }  
  132.             printf("/n");  
  133.         }  
  134.         printf("/n");  
  135.         dele();  
  136.     }  
  137.     return pzjay;  
  138. }  
  139. 字典树容易理解，用处广泛并且本文pzjay原创，— —|||  

标签：

相关文章