mysileng

第二十三章、杨氏矩阵查找

1. //函数prepareCryptTable以下的函数生成一个长度为0x500（合10进制数：1280）的cryptTable[0x500]  
2. void prepareCryptTable()  
3. {   
4.     unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;  
5.   
6.     for( index1 = 0; index1 < 0x100; index1++ )  
7.     {   
8.         for( index2 = index1, i = 0; i < 5; i++, index2 += 0x100 )  
9.         {   
10.             unsigned long temp1, temp2;  
11.   
12.             seed = (seed * 125 + 3) % 0x2AAAAB;  
13.             temp1 = (seed & 0xFFFF) << 0x10;  
14.   
15.             seed = (seed * 125 + 3) % 0x2AAAAB;  
16.             temp2 = (seed & 0xFFFF);  
17.   
18.             cryptTable[index2] = ( temp1 | temp2 );   
19.         }   
20.     }   
21. }   

1. //函数HashString以下函数计算lpszFileName 字符串的hash值，其中dwHashType 为hash的类型，  
2. unsigned long HashString(const char *lpszkeyName, unsigned long dwHashType )  
3. {  
4.     unsigned char *key  = (unsigned char *)lpszkeyName;  
5.     unsigned long seed1 = 0x7FED7FED;  
6.     unsigned long seed2 = 0xEEEEEEEE;  
7.     int ch;  
8.   
9.     while( *key != 0 )  
10.     {  
11.         ch = *key++;  
12.         seed1 = cryptTable[(dwHashType<<8) + ch] ^ (seed1 + seed2);  
13.         seed2 = ch + seed1 + seed2 + (seed2<<5) + 3;  
14.     }  
15.     return seed1;  
16. }  

1. typedef struct  
2. {  
3.     int nHashA;  
4.     int nHashB;  
5.     char bExists;  
6.    ......  
7. } SOMESTRUCTRUE;  
8. //一种可能的结构体定义？  

1. //函数GetHashTablePos下述函数为在Hash表中查找是否存在目标字符串，有则返回要查找字符串的Hash值，无则，return -1.  
2. int GetHashTablePos( har *lpszString, SOMESTRUCTURE *lpTable )   
3. //lpszString要在Hash表中查找的字符串，lpTable为存储字符串Hash值的Hash表。  
4. {   
5.     int nHash = HashString(lpszString);  //调用上述函数HashString，返回要查找字符串lpszString的Hash值。  
6.     int nHashPos = nHash % nTableSize;  
7.    
8.     if ( lpTable[nHashPos].bExists  &&  !strcmp( lpTable[nHashPos].pString, lpszString ) )   
9.     {  //如果找到的Hash值在表中存在，且要查找的字符串与表中对应位置的字符串相同，  
10.         return nHashPos;    //返回找到的Hash值  
11.     }   
12.     else  
13.     {  
14.         return -1;    
15.     }   
16. }  

1. //函数GetHashTablePos中，lpszString 为要在hash表中查找的字符串；lpTable 为存储字符串hash值的hash表；nTableSize 为hash表的长度：   
2. int GetHashTablePos( char *lpszString, MPQHASHTABLE *lpTable, int nTableSize )  
3. {  
4.     const int  HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;  
5.    
6.     int  nHash = HashString( lpszString, HASH_OFFSET );  
7.     int  nHashA = HashString( lpszString, HASH_A );  
8.     int  nHashB = HashString( lpszString, HASH_B );  
9.     int  nHashStart = nHash % nTableSize;  
10.     int  nHashPos = nHashStart;  
11.    
12.     while ( lpTable[nHashPos].bExists )  
13.    {  
14. //     如果仅仅是判断在该表中时候存在这个字符串，就比较这两个hash值就可以了，不用对结构体中的字符串进行比较。  
15. //         这样会加快运行的速度？减少hash表占用的空间？这种方法一般应用在什么场合？  
16.         if ( 　 lpTable[nHashPos].nHashA == nHashA  
17.         &&  lpTable[nHashPos].nHashB == nHashB )  
18.        {  
19.             return nHashPos;  
20.        }  
21.        else  
22.        {  
23.             nHashPos = (nHashPos + 1) % nTableSize;  
24.        }  
25.    
26.         if (nHashPos == nHashStart)  
27.               break;  
28.     }  
29.      return -1;  
30. }  

1. //函数prepareCryptTable以下的函数生成一个长度为0x500（合10进制数：1280）的cryptTable[0x500]  
2. void prepareCryptTable()  
3. {  
4.     unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;  
5.   
6.     for( index1 = 0; index1 <0x100; index1++ )  
7.     {  
8.         for( index2 = index1, i = 0; i < 5; i++, index2 += 0x100)  
9.         {  
10.             unsigned long temp1, temp2;  
11.             seed = (seed * 125 + 3) % 0x2AAAAB;  
12.             temp1 = (seed & 0xFFFF)<<0x10;  
13.             seed = (seed * 125 + 3) % 0x2AAAAB;  
14.             temp2 = (seed & 0xFFFF);  
15.             cryptTable[index2] = ( temp1 | temp2 );  
16.         }  
17.     }  
18. }  
19.   
20. //函数HashString以下函数计算lpszFileName 字符串的hash值，其中dwHashType 为hash的类型，  
21. unsigned long HashString(const char *lpszkeyName, unsigned long dwHashType )  
22. {  
23.     unsigned char *key  = (unsigned char *)lpszkeyName;  
24.     unsigned long seed1 = 0x7FED7FED;  
25.     unsigned long seed2 = 0xEEEEEEEE;  
26.     int ch;  
27.   
28.     while( *key != 0 )  
29.     {  
30.         ch = *key++;  
31.         seed1 = cryptTable[(dwHashType<<8) + ch] ^ (seed1 + seed2);  
32.         seed2 = ch + seed1 + seed2 + (seed2<<5) + 3;  
33.     }  
34.     return seed1;  
35. }  
36.   
37. /////////////////////////////////////////////////////////////////////  
38. //function: 哈希词典 编码  
39. //parameter:  
40. //author: lei.zhou  
41. //time: 2011-12-14  
42. /////////////////////////////////////////////////////////////////////  
43. MPQHASHTABLE TestHashTable[nTableSize];  
44. int TestHashCTable[nTableSize];  
45. int TestHashDTable[nTableSize];  
46. key_list test_data[nTableSize];  
47.   
48. //直接调用上面的hashstring，nHashPos就是对应的HASH值。  
49. int insert_string(const char *string_in)  
50. {  
51.     const int HASH_OFFSET = 0, HASH_C = 1, HASH_D = 2;  
52.     unsigned int nHash = HashString(string_in, HASH_OFFSET);  
53.     unsigned int nHashC = HashString(string_in, HASH_C);  
54.     unsigned int nHashD = HashString(string_in, HASH_D);  
55.     unsigned int nHashStart = nHash % nTableSize;  
56.     unsigned int nHashPos = nHashStart;  
57.     int ln, ires = 0;  
58.   
59.     while (TestHashTable[nHashPos].bExists)  
60.     {  
61. //      if (TestHashCTable[nHashPos]  == (int) nHashC && TestHashDTable[nHashPos] == (int) nHashD)  
62. //          break;  
63. //      //...  
64. //      else  
65.         //如之前所提示读者的那般，暴雪的Hash算法对于查询那样处理可以，但对插入就不能那么解决  
66.             nHashPos = (nHashPos + 1) % nTableSize;  
67.   
68.         if (nHashPos == nHashStart)  
69.             break;  
70.     }  
71.   
72.     ln = strlen(string_in);  
73.     if (!TestHashTable[nHashPos].bExists && (ln < nMaxStrLen))  
74.     {   
75.         TestHashCTable[nHashPos] = nHashC;  
76.         TestHashDTable[nHashPos] = nHashD;  
77.   
78.         test_data[nHashPos] = (KEYNODE *) malloc (sizeof(KEYNODE) * 1);  
79.         if(test_data[nHashPos] == NULL)  
80.         {  
81.             printf("10000 EMS ERROR !!!!\n");  
82.             return 0;  
83.         }  
84.   
85.         test_data[nHashPos]->pkey = (char *)malloc(ln+1);  
86.         if(test_data[nHashPos]->pkey == NULL)  
87.         {  
88.             printf("10000 EMS ERROR !!!!\n");  
89.             return 0;  
90.         }  
91.   
92.         memset(test_data[nHashPos]->pkey, 0, ln+1);  
93.         strncpy(test_data[nHashPos]->pkey, string_in, ln);  
94.         *((test_data[nHashPos]->pkey)+ln) = 0;  
95.         test_data[nHashPos]->weight = nHashPos;  
96.   
97.         TestHashTable[nHashPos].bExists = 1;  
98.     }  
99.     else  
100.     {  
101.         if(TestHashTable[nHashPos].bExists)  
102.             printf("30000 in the hash table %s !!!\n", string_in);  
103.         else  
104.             printf("90000 strkey error !!!\n");  
105.     }  
106.     return nHashPos;  
107. }  

1. void bigIndex_hash(const char *docpath, const char *hashpath)  
2. {  
3.     FILE *fr, *fw;  
4.     int len;  
5.     char *pbuf, *p;  
6.     char dockey[TERM_MAX_LENG];  
7.   
8.     if(docpath == NULL || *docpath == '\0')  
9.         return;  
10.   
11.     if(hashpath == NULL || *hashpath == '\0')  
12.         return;  
13.   
14.     fr = fopen(docpath, "rb");  //读取文件docpath  
15.     fw = fopen(hashpath, "wb");  
16.     if(fr == NULL || fw == NULL)  
17.     {  
18.         printf("open read or write file error!\n");  
19.         return;  
20.     }  
21.   
22.     pbuf = (char*)malloc(BUFF_MAX_LENG);  
23.     if(pbuf == NULL)  
24.     {  
25.         fclose(fr);  
26.         return ;  
27.     }  
28.   
29.     memset(pbuf, 0, BUFF_MAX_LENG);  
30.   
31.     while(fgets(pbuf, BUFF_MAX_LENG, fr))  
32.     {  
33.         len = GetRealString(pbuf);  
34.         if(len <= 1)  
35.             continue;  
36.         p = strstr(pbuf, "#####");    
37.         if(p != NULL)  
38.             continue;  
39.   
40.         p = strstr(pbuf, "  ");  
41.         if (p == NULL)  
42.         {  
43.             printf("file contents error!");  
44.         }  
45.   
46.         len = p - pbuf;  
47.         dockey[0] = 0;  
48.         strncpy(dockey, pbuf, len);  
49.   
50.         dockey[len] = 0;        
51.   
52.         int num = insert_string(dockey);   
53.   
54.         dockey[len] = ' ';  
55.         dockey[len+1] = '\0';  
56.         char str[20];  
57.         itoa(num, str, 10);  
58.   
59.         strcat(dockey, str);  
60.         dockey[len+strlen(str)+1] = '\0';  
61.         fprintf (fw, "%s\n", dockey);  
62.   
63.     }  
64.     free(pbuf);  
65.     fclose(fr);  
66.     fclose(fw);  
67. }  

1. int main()  
2. {  
3.     prepareCryptTable();  //Hash表起初要初始化  
4.   
5.     //现在要把整个big_index文件插入hash表，以取得编码结果  
6.     bigIndex_hash("big_index.txt", "hashpath.txt");  
7.     system("pause");  
8.   
9.     return 0;  
10. }  

1. void bigIndex_hashcode(const char *in_file_path, const char *out_file_path)  
2. {  
3.     FILE *fr, *fw;  
4.     int len, value;  
5.     char *pbuf, *pleft, *p;  
6.     char keyvalue[TERM_MAX_LENG], str[WORD_MAX_LENG];  
7.   
8.     if(in_file_path == NULL || *in_file_path == '\0') {  
9.         printf("input file path error!\n");  
10.         return;  
11.     }  
12.   
13.     if(out_file_path == NULL || *out_file_path == '\0') {  
14.         printf("output file path error!\n");  
15.         return;  
16.     }  
17.   
18.     fr = fopen(in_file_path, "r");  //读取in_file_path路径文件  
19.     fw = fopen(out_file_path, "w");  
20.   
21.     if(fr == NULL || fw == NULL)  
22.     {  
23.         printf("open read or write file error!\n");  
24.         return;  
25.     }  
26.   
27.     pbuf = (char*)malloc(BUFF_MAX_LENG);  
28.     pleft = (char*)malloc(BUFF_MAX_LENG);  
29.     if(pbuf == NULL || pleft == NULL)  
30.     {  
31.         printf("allocate memory error!");  
32.         fclose(fr);  
33.         return ;  
34.     }  
35.   
36.     memset(pbuf, 0, BUFF_MAX_LENG);  
37.   
38.     int offset = 1;  
39.     while(fgets(pbuf, BUFF_MAX_LENG, fr))  
40.     {  
41.         if (--offset > 0)  
42.             continue;  
43.   
44.         if(GetRealString(pbuf) <= 1)  
45.             continue;  
46.   
47.         p = strstr(pbuf, "#####");    
48.         if(p != NULL)  
49.             continue;  
50.   
51.         p = strstr(pbuf, "  ");  
52.         if (p == NULL)  
53.         {  
54.             printf("file contents error!");  
55.         }  
56.   
57.         len = p - pbuf;  
58.   
59.         // 确定跳过行数  
60.         strcpy(pleft, p+1);   
61.         offset = atoi(pleft) + 1;  
62.   
63.         strncpy(keyvalue, pbuf, len);    
64.         keyvalue[len] = '\0';  
65.         value = insert_string(keyvalue);  
66.   
67.         if (value != -1) {  
68.   
69.             // key value中插入空格  
70.             keyvalue[len] = ' ';  
71.             keyvalue[len+1] = '\0';  
72.   
73.             itoa(value, str, 10);  
74.             strcat(keyvalue, str);  
75.   
76.             keyvalue[len+strlen(str)+1] = ' ';  
77.             keyvalue[len+strlen(str)+2] = '\0';  
78.   
79.             keysize++;  
80.             itoa(keysize, str, 10);  
81.             strcat(keyvalue, str);  
82.   
83.             // 将key value写入文件  
84.             fprintf (fw, "%s\n", keyvalue);  
85.   
86.         }  
87.     }  
88.     free(pbuf);  
89.     fclose(fr);  
90.     fclose(fw);  
91. }