소스코드 좀 봐주세요
글쓴이: 이상훈 / 작성시간: 월, 2003/08/04 - 4:50오전
Aho-Corasick Algorithm 구현할려구 만든 소스인데 텍스트에서 2~8자의 문자열을 입력받고, 그것을 이용해서 트리를 생성하는 소스입니다.
트리를 배열로 구현할려고 하는데, 뭐가 문제인지 모르겠네요...ㅠㅠ
depth가 계속 증가만하고, 문자열도 제대로 입력 받지 못하는 것 같고...ㅠㅠ
고수님들 도와주세요..ㅠ0ㅠ
/*table.txt state table */ #include<stdio.h> #include<stdlib.h> #include<math.h> #include<time.h> #include<fstream.h> #include<iostream.h> struct StateTable{ char forNext; int NextState; int failState; bool isOutput; }; struct outputTable{ int state; char output[8]; }; struct depthTable{ int State[1000]; }; int r_depthTable[8000] ={0}; typedef struct outputTable outputTable; typedef struct StateTable StateTable; typedef struct depthTable depthTable; StateTable wStateTable[8000][30]; outputTable woutputTable[1000]; depthTable wdepthTable[10]; int finalState = 0; int finalsubState = 0; int finaloutput = 0; int Failure(int state, char tmp_char); void constructTable(char cur_input[8]); void constructOutput(int tState, char *tempinput); void main() { FILE *input,*result; if((input = fopen("text1.txt","rb"))== NULL) /*text1.txt : input string*/ { printf("can't open file for reading"); exit(1); } if((result = fopen("table.txt","wb")) ==NULL) { printf("can't open file for writing"); exit(1); } char cur_input[8]; int tState = 0; int k; srand( (unsigned)time( NULL ) ); k = (rand()%8)+1; while(fread(cur_input, k, 1,input) == 1) { printf("%c\n",cur_input); constructTable(cur_input); k = (rand()%8)+1; free(cur_input); } int t_depth = 0; for(int a=1;a<8000;a++) { t_depth = r_depthTable[a]; printf("%d",t_depth); int u = 0; while(wdepthTable[t_depth].State[u] != 0) u++; wdepthTable[t_depth].State[u] = a; } for(int i=0;i<8000;i++) for(int j=0;j<30;j++) { if(wStateTable[i][j].forNext == '\n') { wStateTable[i][j].failState = 0; continue; } wStateTable[i][j].failState = Failure(i, wStateTable[i][j].forNext); } fwrite(wStateTable,sizeof(StateTable),1,result); fclose(input); fclose(result); } void constructTable(char tempinput[]) { r_depthTable[1] = 1; r_depthTable[0] = 0; char curinput[8]; int kth = 0; *curinput = *tempinput; int _tState = 0; int tempState = 0; wStateTable[0][0].NextState = 1; for(int j = 0 ; j<30 ; j++) { if ((wStateTable[_tState][j].forNext == '\n') || (wStateTable[_tState][j].forNext == NULL)) break; if(wStateTable[_tState][j].forNext == ((char) curinput[kth])) { _tState = wStateTable[_tState][j].NextState; j = 0; kth++; if( (curinput[kth]) == '\n') { constructOutput(_tState, tempinput); exit(1); } } } while((curinput[kth]) != '\n') { for(int z=0 ; z<30 ; z++) if(wStateTable[_tState][z].forNext == '\n') break; r_depthTable[finalState + 1] = r_depthTable[_tState]+1; wStateTable[_tState][z].forNext =curinput[kth]; wStateTable[_tState][z].isOutput = 0; wStateTable[_tState][z].failState = 0; wStateTable[_tState][z].NextState = (finalState++); _tState = finalState; kth++; } wStateTable[_tState][0].isOutput = 1; constructOutput(_tState, tempinput); } void constructOutput(int tState, char tempinput[]) { woutputTable[finaloutput].state = tState; *woutputTable[finaloutput].output = *tempinput; finaloutput++; } int Failure(int state, char tmp_char) { int depth = r_depthTable[state]; if(depth == 0 || depth == 1) return 0; int tState = 0; int i = 0; while((tState = wdepthTable[depth - 1].State[i]) !=0) { for(int j=0; j<30;j++) { if(wStateTable[tState][j].forNext == tmp_char) return tState; } i++; } return 0; }
Forums:
댓글 달기