文本比較算法再實作-3

周末在家把思路理了一邊，先是用python實作了一下，但性能不太理想（100k/s），考慮到可能是由于動态語言的效率本身比較慢的原因，于是 将算法改成c語言實作，最終的結果是：1.8M/s（硬體環境：Intel Core Duo 1.73G, 記憶體2G）。對于這個結果來說，我還是不太滿意，比較現在動辄都是上G的資料。這樣的效率太慢了，下面放上代碼，各位讨論下是否還有優化的餘地或者這個算 法本身比較慢，或者這個方案是不可行的？

以下代碼在Ubuntu9.04下編譯并運作通過，測試資料是從je上随便搞了幾篇文章。 gcc版本：4.3.3

C代碼

1. #include <stdio.h>   
2. #include <string.h>   
3. #include <sys/types.h>      
4. #include <dirent.h>      
5. #include <sys/stat.h>    
6. #include <time.h>    
7. #include <stdlib.h>    
8. #define STEP 10   
9. int  count = 0; //文檔個數   
10. char * str = NULL; //一個大的字元串，存儲所有文檔的内容   
11. int * ends; //文檔的結束點集合   
12. int  ends_len = 0, ends_mem_len = 10; //文檔結束點的記憶體參數（目前長度，記憶體長度）   
13. int  str_len = 0, str_mem_len = 10, str_unicode_len=0; //字元串的記憶體參數（字元串長度，字元串記憶體長度， 字元串unicode長度：即一個漢字占一個長度時的長度）   
14. struct  id_map{ //一個文檔在記憶體中的映射位置   
15.     int  id; //文檔id   
16.     int  start; //字元串中的開始位置   
17.     int  end; //字元串中的結束位置   
18. };  
19. struct  id_map * idmaps=NULL; //文檔在記憶體中的映射位址   
20. int  idmaps_len = 0, idmaps_mem_len=0; //文檔映射參數   
21. //添加一個文檔映射參數   
22. void  addIdMap( struct  id_map map){  
23.     if (idmaps==NULL){ //如果數組還沒有建立，就建立一個數組來進行存儲   
24.         idmaps = (struct  id_map *)malloc( sizeof ( struct  id_map)*10);  
25.     }  
26.     //如果目前的文檔數已經到達了上一次建立的記憶體長度，則擴充記憶體，步長為10   
27.     if (idmaps_len==idmaps_mem_len){  
28.         idmaps_mem_len += STEP;  
29.         idmaps = (struct  id_map *)realloc(idmaps,  sizeof ( struct  id_map)*idmaps_mem_len);  
30.         if (idmaps==NULL){  
31.             printf("記憶體不足" );  
32.             return ;  
33.         }  
34.     }  
35.     *(idmaps+idmaps_len) = map;  
36.     idmaps_len++;  
37. }  
38. //讀取一個文本檔案   
39. char * readTextFile( char * path){  
40.     char  ch; //目前的字元   
41.     FILE  *fp; //檔案指針   
42.     int  result;  
43.     fp = fopen(path, "rb" );  
44.     if (fp!=NULL){ //如果文檔讀取成功   
45.         if (str==NULL){  
46.             //初始化str,ends的記憶體。這兩個的增長步長均為10   
47.             ends = (int  *)malloc(  sizeof ( int ) * 10);  
48.             str = (char  *)malloc(10);  
49.         }  
50.         if (!str){  
51.             printf("記憶體不足" );  
52.             fclose(fp);  
53.             return  NULL;  
54.         }  
55.         int  unicode_ = 0;  
56.         while ((ch=fgetc(fp))!=EOF){ //讀取檔案，一直讀到最後，将内容放到str中。   
57.             if (str_len == str_mem_len){  
58.                 str_mem_len += STEP;  
59.                 str = (char  *)realloc(str, str_mem_len);  
60.                 if (str == NULL){  
61.                     printf("記憶體不足" );  
62.                     fclose(fp);  
63.                     return  NULL;  
64.                 }  
65.             }  
66.             if (unicode_ == 0){ //如果上一個字元不是Unicode字元，則判斷如果目前字元為unicode字元，則進入unicode計數。   
67.                 if (ch>=0 && ch<127){  
68.                     str_unicode_len++;  
69.                 }else {  
70.                     unicode_ = 1;  
71.                 }  
72.             }else   if (unicode_ == 1){  
73.                 unicode_ =2;  
74.             }else   if (unicode_ == 2){ //按照utf-8編碼進行計算，每個漢字占三個字元。   
75.                 unicode_ = 0;  
76.                 str_unicode_len++;  
77.             }  
78.             *(str+str_len)=ch;  
79.             str_len++;  
80.         }  
81.         //記錄結束點   
82.         if (ends_len == ends_mem_len){  
83.             ends_mem_len += STEP;  
84.             ends = (int  *)realloc(ends,   sizeof ( int ) * ends_mem_len);  
85.             if (ends == NULL){  
86.                 printf("記憶體不足" );  
87.                 fclose(fp);  
88.                 return  NULL;  
89.             }  
90.         }  
91.         //printf("---%d,%d,%d/n", ends_len,ends_mem_len,str_unicode_len);          
92.         //*(ends+ends_len) = str_unicode_len;   
93.         *(ends+ends_len) = str_unicode_len;  
94.         ends_len++;  
95.         str = (char  *)realloc(str, str_len);  
96.         //*(str+len)='/0';   
97.         fclose(fp);  
98.         return  str;  
99.     }  
100.     return  NULL;  
101. }  
102. //讀入一個檔案夾内的所有檔案   
103. int  init_search_dir( char  *path)  
104. {  
105.     DIR *dir;     
106.         struct  dirent *s_dir;     
107.         struct   stat file_stat;   
108.     char  currfile[1024]={0};     
109.     int  len = strlen(path);  
110.     printf("%s/n" ,path);  
111.     if ( (dir=opendir(path)) == NULL)  
112.     {     
113.         printf("opendir(path) error./n" );     
114.         return  -1;     
115.     }  
116.         while ((s_dir=readdir(dir))!=NULL)     
117.     {     
118.             if ((strcmp(s_dir->d_name, "." )==0)||(strcmp(s_dir->d_name, ".." )==0))     
119.             continue ;  
120.             sprintf(currfile,"%s%s" ,path,s_dir->d_name);     
121.             stat(currfile,&file_stat);     
122.             if (S_ISDIR(file_stat.st_mode)){ //如果是檔案夾，則遞歸讀取   
123.                     init_search_dir(currfile);     
124.             }else {  
125.                     printf("%-32s/tOK" ,currfile);  
126.             //設定一個文檔與 str的映射，并讀取文檔的内容   
127.             struct  id_map map;  
128.             map.id=atoi(s_dir->d_name);  
129.             map.start = str_unicode_len;  
130.             readTextFile(currfile);  
131.             map.end = str_unicode_len;  
132.             addIdMap(map);  
133.             printf("/t%d/n" , str_unicode_len);  
134.         }  
135.         count++;  
136.         }     
137.         closedir(dir);  
138.     ends = (int  *)realloc(ends,  sizeof ( int ) * ends_len);  
139.     return  0;  
140. }  
141. //計算一個utf-8字元串的長度(漢字占一個長度)   
142. int  utf8_str_len( char * utf8_str){  
143.     int  length = 0, unicode_ = 0, i=0;  
144.     for (;i<strlen(utf8_str);i++){  
145.         if (unicode_ == 0){  
146.             if (utf8_str[i]>=0 && utf8_str[i]<127){  
147.                 length++;  
148.             }else {  
149.                 unicode_ = 1;  
150.             }  
151.         }else   if (unicode_ == 1){  
152.             unicode_ =2;  
153.         }else   if (unicode_ == 2){  
154.             unicode_ = 0;  
155.             length++;  
156.         }  
157.     }  
158.     return  length;  
159. }  
160. //查找該結束點是否存在(2分查找)   
161. int  find_ends( int  num){  
162.     if (num>ends[ends_len-1]||num<ends[0]){  
163.         return  -1;  
164.     }  
165.     int  end = ends_len;  
166.     int  start = 0;  
167.     int  index=ends_len / 2;  
168.     while (1){  
169.         if (ends[index]==num){  
170.             return  index;  
171.         }  
172.         if (start == end || index == start || index == end){  
173.             return  -1;  
174.         }  
175.         if (ends[index] > num){  
176.             end  = index;  
177.         }else {  
178.             start = index;  
179.         }  
180.         index = start + ((end-start) / 2);  
181.     }  
182. }  
183. //主要函數。搜尋所有文檔中所有存在于該字元串相似的文檔，算法出處及JAVA實作參見：http://www.blogjava.net/phyeas/archive/2009/02/15/254743.html   
184. void  search( char * key){  
185.     int  key_len = utf8_str_len(key); //計算key的長度   
186.     int  i=0, j=0, j_ = 0, i_ = 0;  
187.     //char barr[key_len][str_unicode_len];   
188.     char * barr[key_len]; //   
189.     //char narr[key_len][str_unicode_len];   
190.     char * narr[key_len];  
191.     //char darr[key_len][str_unicode_len];   
192.     char * darr[key_len];  
193.     //一個按照最大比對度排序的文檔序列。最大比對度不可能大于key的長度+1，是以聲明一個key_len+1長度的數組進行儲存即可。資料格式類似：[[],[2,3],[5],[]]   
194.     int * max_id_maps[key_len + 1]; //該數組的第n個下标表示最大比對度為n的文檔有哪些   
195.     int  max_id_maps_lens[key_len + 1], max_id_maps_mem_lens[key_len + 1];  
196.     int  key_ascii_len = strlen(key);  
197.     struct  timeval tpstart,tpend;  
198.     float   timeuse;   
199.     gettimeofday(&tpstart,NULL);  
200.     //初始化三個數組。i_,j_表示目前的坐标，i,j表示目前左右的字元串中的字元位置   
201.     for (i_=key_len-1, i=key_ascii_len-1;i>=0 && i_>=0;i--,i_--){  
202.         barr[i_] = (char *) malloc(str_unicode_len); //動态申請記憶體是為了解決c語言函數内聲明數組的長度有限制   
203.         narr[i_] = (char *) malloc(str_unicode_len);  
204.         darr[i_] = (char *) malloc(str_unicode_len);  
205.         int  is_left_ascii = key[i]<0 || key[i] >= 127 ? 0 : 1;  
206.         for (j=str_len-1, j_=str_unicode_len-1;j>=0&&j_>=0;j--,j_--){  
207.             int  is_right_ascii = str[j] < 0 || str[j] >= 127 ? 0 : 1;  
208.             barr[i_][j_] = 0;  
209.             if (!is_left_ascii || !is_right_ascii){  
210.                 if (!is_left_ascii && !is_right_ascii){  
211.                     int  k = 2, eq=1;  
212.                     for (;k>=0;k--){  
213.                         if (i-k >= 0 && j-k>=0 && key[i-k] != str[j-k]){  
214.                             eq = 0;  
215.                             break ;  
216.                         }  
217.                     }  
218.                     barr[i_][j_] = eq;  
219.                 }else {  
220.                     barr[i_][j_] = 0;  
221.                 }  
222.             }else {  
223.                 barr[i_][j_] = str[j] == key[i] || tolower(str[j]) == tolower(key[i]) ? 1 : 0;  
224.             }  
225.             darr[i_][j_] = 0;  
226.             narr[i_][j_] = 0;  
227.             int  indexOfEnds = find_ends(j_);  
228.             int  n_right = 0, n_down = 0, n_rightdown = 0, d_right = 0, d_down = 0, d_rightdown = 0;  
229.             if (indexOfEnds == -1 && j_!=str_unicode_len - 1){  
230.                 n_right = narr[i_][j_ + 1];  
231.                 d_right = darr[i_][j_ + 1];  
232.             }  
233.             if (i_!=key_len -1){  
234.                 n_down = narr[i_ + 1][j_];  
235.                 d_down = darr[i_ + 1][j_];  
236.             }  
237.             if (indexOfEnds == -1 && j_!=str_unicode_len - 1 && i_!=key_len -1){  
238.                 n_rightdown = narr[i_ + 1][j_ + 1];  
239.                 d_rightdown = darr[i_ + 1][j_ + 1];  
240.             }  
241.             n_rightdown += barr[i_][j_];  
242.             narr[i_][j_] = n_right > n_down ? (n_right > n_rightdown ?  n_right : n_rightdown) : (n_down > n_rightdown ? n_down : n_rightdown);  
243.             if (barr[i_][j_]){  
244.                 darr[i_][j_] = d_rightdown + 1;  
245.             }else   if (n_right >= n_down){  
246.                 darr[i_][j_] = d_right;  
247.             }else {  
248.                 darr[i_][j_] = d_down + 1;  
249.             }  
250.             if (!is_right_ascii){  
251.                 j-=2;  
252.             }  
253.             //printf("%d/t", narr[i_][j_]);   
254.         }  
255.         //printf("/n");   
256.         //max_id_maps[i] = (int *)malloc(sizeof(int)*10);   
257.         max_id_maps_mem_lens[i_] = 0;  
258.         max_id_maps_lens[i_] = 0;  
259.         if (!is_left_ascii){  
260.             i-=2;  
261.         }  
262.     }  
263.     //max_id_maps[key_len] = (int *)malloc(sizeof(int)*10);   
264.     max_id_maps_mem_lens[key_len] = 0;  
265.     max_id_maps_lens[key_len] = 0;  
266.     int  k=0;  
267.     //計算最大比對度和最優比對路徑長度。并将其放到如到max_id_maps中   
268.     for (k=0;k<idmaps_len;k++){  
269.         int  end=idmaps[k].end, j=idmaps[k].start, end_i = key_len, max_ = 0, min_ = -1;  
270.         while (j<end){  
271.             int  temp_end_i = -1;  
272.             for (i=0;i<end_i;i++){  
273.                 if (barr[i][j]){  
274.                     if (temp_end_i==-1){  
275.                         temp_end_i = i;  
276.                     }  
277.                     if (narr[i][j] > max_){  
278.                         max_ = narr[i][j];  
279.                     }  
280.                     if (min_ == -1 || darr[i][j] < min_){  
281.                         min_ = darr[i][j];  
282.                     }  
283.                 }  
284.             }  
285.             if (temp_end_i != -1){  
286.                 end_i = temp_end_i;  
287.             }  
288.             j++;  
289.         }  
290.         if (max_ != 0){  
291.             if (max_id_maps_mem_lens[max_] == 0){  
292.                 max_id_maps[max_] = (int  *)malloc( sizeof ( int )*10);  
293.                 max_id_maps_mem_lens[max_] = 10;  
294.             }else   if (max_id_maps_mem_lens[max_] == max_id_maps_lens[max_]){  
295.                 max_id_maps_mem_lens[max_] += STEP;  
296.                 max_id_maps[max_] = (int  *)realloc(max_id_maps[max_],  sizeof ( int )*max_id_maps_mem_lens[max_]);  
297.             }  
298.             *(max_id_maps[max_] + max_id_maps_lens[max_]) = idmaps[k].id;  
299.             max_id_maps_lens[max_]++;  
300.         }  
301.     }  
302.     //-----------------計時，計算性能   
303.     gettimeofday(&tpend,NULL);   
304.     timeuse=1000000*(tpend.tv_sec-tpstart.tv_sec)+tpend.tv_usec-tpstart.tv_usec;   
305.     timeuse/=1000000;   
306.     printf("Used Time:%f/n" ,timeuse);   
307.     for (i=0;i<=key_len;i++){  
308.         printf("%d -- " ,i);  
309.         for (j=0;j<max_id_maps_lens[i];j++){  
310.             printf("%d/t" , max_id_maps[i][j]);  
311.         }  
312.         printf("/n" );  
313.     }  
314.     //--------------計時結束   
315.     //釋放在這個函數中申請的動态記憶體。   
316.     for (i=0;i<=key_len;i++){  
317.         if (max_id_maps_mem_lens[i]>0){  
318.             //printf("%d,",max_id_maps_mem_lens[i]);   
319.             free(max_id_maps[i]);  
320.         }  
321.         if (i!=key_len){  
322.             free(barr[i]);  
323.             free(narr[i]);  
324.             free(darr[i]);  
325.         }  
326.     }  
327.     //testPrint(&narr, key_len, str_unicode_len);   
328. }  
329. //釋放程式中申請的動态記憶體   
330. void  freeMemory(){  
331.     free(ends);  
332.     free(idmaps);  
333.     free(str);  
334. }  
335. int  main(){   
336.     init_search_dir("/home/phyeas/test/" );  
337.     search("Java雲計算" );  
338.     //search("BCXCADFESBABCACA");   
339.     //init_search_dir("/home/phyeas/test/test2/");   
340.     //int i=0;   
341.     freeMemory();  
342.     return  0;  
343. }  

#include <stdio.h>

#include <string.h>

#include <sys/types.h>   

#include <dirent.h>   

#include <sys/stat.h> 
#include <time.h> 
#include <stdlib.h> 

#define STEP 10

int count = 0;//文檔個數
char* str = NULL;//一個大的字元串，存儲所有文檔的内容
int* ends;//文檔的結束點集合
int ends_len = 0, ends_mem_len = 10;//文檔結束點的記憶體參數（目前長度，記憶體長度）
int str_len = 0, str_mem_len = 10, str_unicode_len=0;//字元串的記憶體參數（字元串長度，字元串記憶體長度， 字元串unicode長度：即一個漢字占一個長度時的長度）
struct id_map{//一個文檔在記憶體中的映射位置
	int id;//文檔id
	int start;//字元串中的開始位置
	int end;//字元串中的結束位置
};
struct id_map * idmaps=NULL;//文檔在記憶體中的映射位址
int idmaps_len = 0, idmaps_mem_len=0;//文檔映射參數
//添加一個文檔映射參數
void addIdMap(struct id_map map){
	if(idmaps==NULL){//如果數組還沒有建立，就建立一個數組來進行存儲
		idmaps = (struct id_map *)malloc(sizeof(struct id_map)*10);
	}
	//如果目前的文檔數已經到達了上一次建立的記憶體長度，則擴充記憶體，步長為10
	if(idmaps_len==idmaps_mem_len){
		idmaps_mem_len += STEP;
		idmaps = (struct id_map *)realloc(idmaps, sizeof(struct id_map)*idmaps_mem_len);
		if(idmaps==NULL){
			printf("記憶體不足");
			return;
		}
	}
	*(idmaps+idmaps_len) = map;
	idmaps_len++;
}

//讀取一個文本檔案
char* readTextFile(char* path){
	char ch;//目前的字元
	FILE *fp;//檔案指針
	int result;
	fp = fopen(path, "rb");
	if(fp!=NULL){//如果文檔讀取成功
		if(str==NULL){
			//初始化str,ends的記憶體。這兩個的增長步長均為10
			ends = (int *)malloc( sizeof(int) * 10);
			str = (char *)malloc(10);
		}
		if(!str){
			printf("記憶體不足");
			fclose(fp);
			return NULL;
		}
		int unicode_ = 0;
		while((ch=fgetc(fp))!=EOF){//讀取檔案，一直讀到最後，将内容放到str中。
			if(str_len == str_mem_len){
				str_mem_len += STEP;
				str = (char *)realloc(str, str_mem_len);
				if(str == NULL){
					printf("記憶體不足");
					fclose(fp);
					return NULL;
				}
			}
			if(unicode_ == 0){//如果上一個字元不是Unicode字元，則判斷如果目前字元為unicode字元，則進入unicode計數。
				if(ch>=0 && ch<127){
					str_unicode_len++;
				}else{
					unicode_ = 1;
				}
			}else if(unicode_ == 1){
				unicode_ =2;
			}else if(unicode_ == 2){//按照utf-8編碼進行計算，每個漢字占三個字元。
				unicode_ = 0;
				str_unicode_len++;
			}
			*(str+str_len)=ch;
			str_len++;
		}
		//記錄結束點
		if(ends_len == ends_mem_len){
			ends_mem_len += STEP;
			ends = (int *)realloc(ends,  sizeof(int) * ends_mem_len);
			if(ends == NULL){
				printf("記憶體不足");
				fclose(fp);
				return NULL;
			}
		}
		//printf("---%d,%d,%d/n", ends_len,ends_mem_len,str_unicode_len);		
		//*(ends+ends_len) = str_unicode_len;
		*(ends+ends_len) = str_unicode_len;
		ends_len++;
		str = (char *)realloc(str, str_len);
		//*(str+len)='/0';
		fclose(fp);
		return str;
	}
	return NULL;
}

//讀入一個檔案夾内的所有檔案
int init_search_dir(char *path)

{

	DIR *dir;   

      	struct dirent *s_dir;   

      	struct  stat file_stat;	

	char currfile[1024]={0};   

	int len = strlen(path);

	printf("%s/n",path);

	if( (dir=opendir(path)) == NULL)

	{   

		printf("opendir(path) error./n");   

		return -1;   

	}

      	while((s_dir=readdir(dir))!=NULL)   

	{   

          	if((strcmp(s_dir->d_name,".")==0)||(strcmp(s_dir->d_name,"..")==0))   

			continue;

          	sprintf(currfile,"%s%s",path,s_dir->d_name);   

          	stat(currfile,&file_stat);   

          	if(S_ISDIR(file_stat.st_mode)){//如果是檔案夾，則遞歸讀取

              		init_search_dir(currfile);   

          	}else{

              		printf("%-32s/tOK",currfile);
			//設定一個文檔與 str的映射，并讀取文檔的内容
			struct id_map map;
			map.id=atoi(s_dir->d_name);
			map.start = str_unicode_len;
			readTextFile(currfile);
			map.end = str_unicode_len;
			addIdMap(map);
			printf("/t%d/n", str_unicode_len);
		}

		count++;

      	}   

      	closedir(dir);
	ends = (int *)realloc(ends, sizeof(int) * ends_len);

	return 0;

}

//計算一個utf-8字元串的長度(漢字占一個長度)
int utf8_str_len(char* utf8_str){
	int length = 0, unicode_ = 0, i=0;
	for(;i<strlen(utf8_str);i++){
		if(unicode_ == 0){
			if(utf8_str[i]>=0 && utf8_str[i]<127){
				length++;
			}else{
				unicode_ = 1;
			}
		}else if(unicode_ == 1){
			unicode_ =2;
		}else if(unicode_ == 2){
			unicode_ = 0;
			length++;
		}
	}
	return length;
}

//查找該結束點是否存在(2分查找)
int find_ends(int num){
	if(num>ends[ends_len-1]||num<ends[0]){
		return -1;
	}
	int end = ends_len;
	int start = 0;
	int index=ends_len / 2;
	while(1){
		if(ends[index]==num){
			return index;
		}
		if(start == end || index == start || index == end){
			return -1;
		}
		if(ends[index] > num){
			end  = index;
		}else{
			start = index;
		}
		index = start + ((end-start) / 2);
	}
}

//主要函數。搜尋所有文檔中所有存在于該字元串相似的文檔，算法出處及JAVA實作參見：http://www.blogjava.net/phyeas/archive/2009/02/15/254743.html
void search(char* key){
	int key_len = utf8_str_len(key);//計算key的長度
	int i=0, j=0, j_ = 0, i_ = 0;
	//char barr[key_len][str_unicode_len];
	char* barr[key_len];//
	//char narr[key_len][str_unicode_len];
	char* narr[key_len];
	//char darr[key_len][str_unicode_len];
	char* darr[key_len];
	//一個按照最大比對度排序的文檔序列。最大比對度不可能大于key的長度+1，是以聲明一個key_len+1長度的數組進行儲存即可。資料格式類似：[[],[2,3],[5],[]]
	int* max_id_maps[key_len + 1];//該數組的第n個下标表示最大比對度為n的文檔有哪些
	int max_id_maps_lens[key_len + 1], max_id_maps_mem_lens[key_len + 1];
	int key_ascii_len = strlen(key);
	
	struct timeval tpstart,tpend;
	float  timeuse; 
	gettimeofday(&tpstart,NULL);
	//初始化三個數組。i_,j_表示目前的坐标，i,j表示目前左右的字元串中的字元位置
	for(i_=key_len-1, i=key_ascii_len-1;i>=0 && i_>=0;i--,i_--){
		barr[i_] = (char*) malloc(str_unicode_len);//動态申請記憶體是為了解決c語言函數内聲明數組的長度有限制
		narr[i_] = (char*) malloc(str_unicode_len);
		darr[i_] = (char*) malloc(str_unicode_len);
		int is_left_ascii = key[i]<0 || key[i] >= 127 ? 0 : 1;
		for(j=str_len-1, j_=str_unicode_len-1;j>=0&&j_>=0;j--,j_--){
			int is_right_ascii = str[j] < 0 || str[j] >= 127 ? 0 : 1;
			barr[i_][j_] = 0;
			if(!is_left_ascii || !is_right_ascii){
				if(!is_left_ascii && !is_right_ascii){
					int k = 2, eq=1;
					for(;k>=0;k--){
						if(i-k >= 0 && j-k>=0 && key[i-k] != str[j-k]){
							eq = 0;
							break;
						}
					}
					barr[i_][j_] = eq;
				}else{
					barr[i_][j_] = 0;
				}
			}else{
				barr[i_][j_] = str[j] == key[i] || tolower(str[j]) == tolower(key[i]) ? 1 : 0;
			}

			darr[i_][j_] = 0;
			narr[i_][j_] = 0;
			int indexOfEnds = find_ends(j_);
			int n_right = 0, n_down = 0, n_rightdown = 0, d_right = 0, d_down = 0, d_rightdown = 0;
			if(indexOfEnds == -1 && j_!=str_unicode_len - 1){
				n_right = narr[i_][j_ + 1];
				d_right = darr[i_][j_ + 1];
			}
			if(i_!=key_len -1){
				n_down = narr[i_ + 1][j_];
				d_down = darr[i_ + 1][j_];
			}
			if(indexOfEnds == -1 && j_!=str_unicode_len - 1 && i_!=key_len -1){
				n_rightdown = narr[i_ + 1][j_ + 1];
				d_rightdown = darr[i_ + 1][j_ + 1];
			}
			n_rightdown += barr[i_][j_];
			narr[i_][j_] = n_right > n_down ? (n_right > n_rightdown ?  n_right : n_rightdown) : (n_down > n_rightdown ? n_down : n_rightdown);
			if(barr[i_][j_]){
				darr[i_][j_] = d_rightdown + 1;
			}else if(n_right >= n_down){
				darr[i_][j_] = d_right;
			}else{
				darr[i_][j_] = d_down + 1;
			}

			
			if(!is_right_ascii){
				j-=2;
			}
			//printf("%d/t", narr[i_][j_]);
		}
		//printf("/n");
		//max_id_maps[i] = (int *)malloc(sizeof(int)*10);
		max_id_maps_mem_lens[i_] = 0;
		max_id_maps_lens[i_] = 0;
		
		if(!is_left_ascii){
			i-=2;
		}
	}

	//max_id_maps[key_len] = (int *)malloc(sizeof(int)*10);
	max_id_maps_mem_lens[key_len] = 0;
	max_id_maps_lens[key_len] = 0;
	int k=0;
	//計算最大比對度和最優比對路徑長度。并将其放到如到max_id_maps中
	for(k=0;k<idmaps_len;k++){
		int end=idmaps[k].end, j=idmaps[k].start, end_i = key_len, max_ = 0, min_ = -1;
		while(j<end){
			int temp_end_i = -1;
			for(i=0;i<end_i;i++){
				if(barr[i][j]){
					if(temp_end_i==-1){
						temp_end_i = i;
					}
					if(narr[i][j] > max_){
						max_ = narr[i][j];
					}
					if(min_ == -1 || darr[i][j] < min_){
						min_ = darr[i][j];
					}
				}
			}
			if(temp_end_i != -1){
				end_i = temp_end_i;
			}
			j++;
		}
		if(max_ != 0){
			if(max_id_maps_mem_lens[max_] == 0){
				max_id_maps[max_] = (int *)malloc(sizeof(int)*10);
				max_id_maps_mem_lens[max_] = 10;
			}else if(max_id_maps_mem_lens[max_] == max_id_maps_lens[max_]){
				max_id_maps_mem_lens[max_] += STEP;
				max_id_maps[max_] = (int *)realloc(max_id_maps[max_], sizeof(int)*max_id_maps_mem_lens[max_]);
			}
			*(max_id_maps[max_] + max_id_maps_lens[max_]) = idmaps[k].id;
			max_id_maps_lens[max_]++;
		}
	}
	//-----------------計時，計算性能
	gettimeofday(&tpend,NULL); 
	timeuse=1000000*(tpend.tv_sec-tpstart.tv_sec)+tpend.tv_usec-tpstart.tv_usec; 
	timeuse/=1000000; 
	printf("Used Time:%f/n",timeuse); 
	for(i=0;i<=key_len;i++){
		printf("%d -- ",i);
		for(j=0;j<max_id_maps_lens[i];j++){
			printf("%d/t", max_id_maps[i][j]);
		}
		printf("/n");
	}
	//--------------計時結束
	//釋放在這個函數中申請的動态記憶體。
	for(i=0;i<=key_len;i++){
		if(max_id_maps_mem_lens[i]>0){
			//printf("%d,",max_id_maps_mem_lens[i]);
			free(max_id_maps[i]);
		}
		if(i!=key_len){
			free(barr[i]);
			free(narr[i]);
			free(darr[i]);
		}
	}
	//testPrint(&narr, key_len, str_unicode_len);
}
//釋放程式中申請的動态記憶體
void freeMemory(){
	free(ends);
	free(idmaps);
	free(str);
}


int main(){	
	init_search_dir("/home/phyeas/test/");
	search("Java雲計算");
	//search("BCXCADFESBABCACA");
	//init_search_dir("/home/phyeas/test/test2/");
	//int i=0;
	freeMemory();
	return 0;
}