99999久久久久久亚洲,欧美人与禽猛交狂配,高清日韩av在线影院,一个人在线高清免费观看,啦啦啦在线视频免费观看www

熱線電話：13121318867

登錄
首頁(yè)精彩閱讀從Trie樹談到后綴樹之后綴樹的C++簡(jiǎn)單實(shí)現(xiàn)_數(shù)據(jù)分析師
從Trie樹談到后綴樹之后綴樹的C++簡(jiǎn)單實(shí)現(xiàn)_數(shù)據(jù)分析師
2014-11-19
收藏

從Trie樹談到后綴樹之后綴樹的C++簡(jiǎn)單實(shí)現(xiàn)_數(shù)據(jù)分析師

本程序只是簡(jiǎn)單實(shí)現(xiàn)了后綴樹的構(gòu)造，查詢等基本的操作。如果此文能引出讀者更好的suffixtree 的實(shí)現(xiàn)，此文的價(jià)值便更甚了。謝謝。

suffix-tree的c++實(shí)現(xiàn)

    完整源碼如下，由于注釋已經(jīng)夠詳細(xì)，便不再多說(shuō)什么了：

   

  1. // suffer tree.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。
  2. //copyright@ 2011 July && 匿名
  4. //1、參考了他人的程序，但不知道原作者是誰(shuí)。
  5. //如果你知道，請(qǐng)立馬聯(lián)系我，一定把原作者的大名署上，謝謝。
  6. //2、主函數(shù)沒(méi)有寫全了，讀者視需要自己補(bǔ)上吧。
  8. #include "stdafx.h"
  9. #ifndef __SUFFIXTREE_H
  10. #define __SUFFIXTREE_H
  11. #include 
  12. #include 
  13. #include 
  14. usingnamespacestd;
  15. usingstd::list;
  16. usingstd::vector;
  18. //對(duì)于葉節(jié)點(diǎn),通過(guò)m_nActiveLen和m_nEdgeLabelEndPos可以得到節(jié)點(diǎn)對(duì)應(yīng)的字符串.對(duì)于分支節(jié)點(diǎn),也是如此.
  19. structtagSuffixNode
  20. {
  21. public:
  22. tagSuffixNode* m_tpChild;//子節(jié)點(diǎn),如果為0,說(shuō)明是葉子節(jié)點(diǎn)
  23. tagSuffixNode* m_tpParent;//父節(jié)點(diǎn),根節(jié)點(diǎn)的父節(jié)點(diǎn)為0
  24. tagSuffixNode* m_tpLeftSibling;//左兄弟
  25. tagSuffixNode* m_tpRightSibling;//右兄弟
  26. tagSuffixNode* m_tpMostRightChild;//最右子節(jié)點(diǎn)
  27. tagSuffixNode* m_tpSuffixLink;//指向當(dāng)前節(jié)點(diǎn)表示的子串的最大后綴所對(duì)應(yīng)的分支節(jié)點(diǎn)
  29. intm_nActiveLen;//節(jié)點(diǎn)代表的字符串的長(zhǎng)度.
  30. intm_nEdgeLabelStartPos;//入邊開始字符的下標(biāo).對(duì)于分支節(jié)點(diǎn),只是用來(lái)表示邊對(duì)應(yīng)的字符串是什么,并不表示其在子孫葉節(jié)點(diǎn)表示的串中對(duì)應(yīng)位置的字符在整個(gè)串中的下標(biāo).
  31. intm_nEdgeLabelEndPos;//入邊結(jié)束字符的下標(biāo)
  32. boolm_bIsLeaf;//是否是葉節(jié)點(diǎn)
  34. charm_cIndex;//test
  36. public:
  37. //全部初始化為0
  38. voidinit()
  39. {
  40. m_tpChild = 0;
  41. m_tpParent = 0;
  42. m_tpLeftSibling = 0;
  43. m_tpRightSibling = 0;
  44. m_tpMostRightChild = 0;
  45. m_tpSuffixLink = 0;
  47. m_nEdgeLabelStartPos = 0;
  48. m_nEdgeLabelEndPos = 0;
  50. m_nActiveLen = 0;
  51. m_bIsLeaf =true;
  52. }
  53. };
  55. classCSuffixTree
  56. {
  57. public:
  58. CSuffixTree(char*str);
  59. ~CSuffixTree();
  60. voiddeleteTree();
  61. voidconstruct();
  62. voidreset(char*str);
  63. intsearch(char*str);
  64. tagSuffixNode* getTree();
  65. voidprintTree();
  66. voidtest();
  67. private:
  68. tagSuffixNode* __allocNode();
  69. tagSuffixNode* __findChildBeginWithChar(tagSuffixNode* node,charc);
  71. void__printHelper(tagSuffixNode* node,intlevel);
  72. private:
  73. intm_nActiveLen;
  74. intm_nStrLen;//字符串長(zhǎng)度
  75. tagSuffixNode* m_tpRoot;//根節(jié)點(diǎn)
  76. tagSuffixNode* m_tpActiveNode;//活動(dòng)節(jié)點(diǎn)
  77. char*m_cpInternalStr;//字符串內(nèi)存存儲(chǔ)
  79. list m_tagNodeList;//保存分配的節(jié)點(diǎn)的指針
  80. vector m_tagFromNodeVec;//保存還未確定后綴指針的分支節(jié)點(diǎn)的指針，用于判定suffix link
  81. vector m_tagToNodeVec;//保存所有分支節(jié)點(diǎn)
  82. #ifdef DEBUG
  83. charm_cIndex;
  84. #endif
  85. };
  87. #endif //
  89. //#include "suffixtree.h"
  90. #include 
  91. #include 
  92. #include 
  93. #include 
  94. #include 
  95. usingnamespacestd;
  97. CSuffixTree::CSuffixTree(char*str)
  98. :m_nActiveLen(0),
  99. m_tpRoot(0),
  100. m_tpActiveNode(0)
  101. {
  102. m_nStrLen = strlen(str) + 1;
  103. m_cpInternalStr =newchar[m_nStrLen+1];
  105. sprintf(m_cpInternalStr,"%s#", str);
  106. #ifdef DEBUG
  107. m_cIndex ='A';
  108. #endif
  109. }
  111. CSuffixTree::~CSuffixTree()
  112. {
  113. deleteTree();
  114. delete[] m_cpInternalStr;
  115. }
  117. voidCSuffixTree::deleteTree()
  118. {
  119. list::iterator iter = m_tagNodeList.begin();
  120. for(; iter != m_tagNodeList.end(); ++iter)
  121. {
  122. delete*iter;
  123. }
  125. m_tagNodeList.clear();
  126. }
  128. voidCSuffixTree::reset(char*str)
  129. {
  130. deleteTree();
  132. inttmp = strlen(str);
  133. if(tmp+1 > m_nStrLen)
  134. {
  135. m_nStrLen = tmp+1;
  136. delete[] m_cpInternalStr;
  137. m_cpInternalStr =newchar[m_nStrLen+1];
  138. }
  139. else
  140. {
  141. m_nStrLen = tmp+1;
  142. }
  143. sprintf(m_cpInternalStr,"%s#", str);
  145. m_nActiveLen = 0;
  146. m_nStrLen = 0;
  147. m_tpActiveNode = 0;
  148. m_tpRoot = 0;
  150. m_tagFromNodeVec.clear();
  151. //reconstruct tree for new string
  152. construct();
  153. }
  156. //suffixTree之構(gòu)造
  157. voidCSuffixTree::construct()
  158. {
  159. m_tpRoot = __allocNode();
  160. if(m_tpRoot == 0)
  161. {
  162. #ifdef DEBUG
  163. printf("__allocNode error!\n");
  164. #endif
  165. return;
  166. }
  167. m_nActiveLen = 0;
  168. m_tpRoot->m_nActiveLen = 0;
  169. //initial active node
  170. m_tpActiveNode = m_tpRoot;
  172. m_tagToNodeVec.push_back(m_tpRoot);
  174. for(inti = 0; i
  175. {
  176. #ifdef DEBUG
  177. printf("\ninsert %s\n", &(m_cpInternalStr[i]));
  178. printf("active node:[%c]\n", m_tpActiveNode->m_cIndex);
  179. #endif
  180. //判斷是否有后繼節(jié)點(diǎn)
  181. if(m_tpActiveNode->m_tpSuffixLink != 0)
  182. {
  183. m_tpActiveNode = m_tpActiveNode->m_tpSuffixLink;
  184. m_nActiveLen--;
  185. }
  186. intpos = i;
  188. #ifdef DEBUG
  189. printf("new active node:[%c]\n", m_tpActiveNode->m_cIndex);
  190. printf("pos:%d\n", pos);
  191. printf("active length:%d\n", m_nActiveLen);
  192. #endif
  194. while(true)
  195. {
  196. //查找以當(dāng)前后綴串的開始字符開始的子節(jié)點(diǎn)
  197. tagSuffixNode* node = __findChildBeginWithChar(m_tpActiveNode, m_cpInternalStr[i+m_nActiveLen]);
  198. //未找到以suffix[i]的開始字符開頭的節(jié)點(diǎn)
  199. if(node == 0)
  200. {
  201. #ifdef DEBUG
  202. printf("__findChildBeginWithChar null\n");
  203. #endif
  204. tagSuffixNode* child = __allocNode();
  206. //設(shè)置開始、結(jié)束位置的下標(biāo)
  207. child->m_nEdgeLabelStartPos = pos;
  208. child->m_nEdgeLabelEndPos = m_nStrLen-1;
  209. //設(shè)置葉節(jié)點(diǎn)代表的后綴串的長(zhǎng)度
  210. child->m_nActiveLen = m_nStrLen - i;
  211. //設(shè)置父節(jié)點(diǎn)
  212. child->m_tpParent = m_tpActiveNode;
  213. if( m_tpActiveNode->m_tpChild == 0)
  214. {
  215. m_tpActiveNode->m_tpChild = child;
  216. m_tpActiveNode->m_tpMostRightChild = child;
  217. }
  218. else
  219. {
  220. m_tpActiveNode->m_tpMostRightChild->m_tpRightSibling = child;
  221. child->m_tpLeftSibling = m_tpActiveNode->m_tpMostRightChild;
  222. m_tpActiveNode->m_tpMostRightChild = child;
  223. }
  225. break;
  226. }
  227. else
  228. {
  229. #ifdef DEBUG
  230. printf("__findChildBeginWithChar ok\n");
  231. printf("node start:%d\n", node->m_nEdgeLabelStartPos);
  232. printf("node end:%d\n", node->m_nEdgeLabelEndPos);
  233. printf("node index:%c\n", node->m_cIndex);
  234. #endif
  235. //TODO
  236. //確定 m_nMinDistance
  237. intedgeStart = node->m_nEdgeLabelStartPos;
  238. intstrStart = i + m_nActiveLen;
  239. boolsplit =false;
  241. for(; edgeStart<=node->m_nEdgeLabelEndPos; edgeStart++, strStart++)
  242. {
  243. if( m_cpInternalStr[edgeStart] != m_cpInternalStr[strStart])
  244. {
  245. split =true;
  246. break;
  247. }
  248. }
  249. if(!split)
  250. {
  251. m_tpActiveNode = node;
  252. m_nActiveLen += node->m_nEdgeLabelEndPos - node->m_nEdgeLabelStartPos + 1;
  253. pos += node->m_nEdgeLabelEndPos - node->m_nEdgeLabelStartPos + 1;
  254. continue;
  255. }
  256. else
  257. {
  258. tagSuffixNode* parent = node->m_tpParent;
  259. //new branch node
  260. tagSuffixNode* branch = __allocNode();
  261. branch->m_bIsLeaf =false;
  262. branch->m_nEdgeLabelStartPos = node->m_nEdgeLabelStartPos;
  263. branch->m_nEdgeLabelEndPos = edgeStart-1;
  264. branch->m_nActiveLen = parent->m_nActiveLen + (branch->m_nEdgeLabelEndPos - branch->m_nEdgeLabelStartPos + 1);
  265. //original node
  266. node->m_nEdgeLabelStartPos = edgeStart;
  268. tagSuffixNode* info = __allocNode();
  269. info->m_nEdgeLabelStartPos = strStart;
  270. info->m_nEdgeLabelEndPos = m_nStrLen - 1;
  271. info->m_nActiveLen = branch->m_nActiveLen + (info->m_nEdgeLabelEndPos - info->m_nEdgeLabelStartPos + 1);
  273. branch->m_tpParent = parent;
  274. branch->m_tpRightSibling = parent->m_tpChild;
  275. parent->m_tpChild->m_tpLeftSibling = branch;
  276. parent->m_tpChild = branch;
  278. node->m_tpLeftSibling->m_tpRightSibling = node->m_tpRightSibling;
  279. if( node->m_tpRightSibling != 0)
  280. {
  281. node->m_tpRightSibling->m_tpLeftSibling = node->m_tpLeftSibling;
  282. }
  283. else
  284. {
  285. parent->m_tpMostRightChild = node->m_tpLeftSibling;
  286. }
  288. branch->m_tpChild = info;
  289. branch->m_tpMostRightChild = node;
  291. info->m_tpRightSibling = node;
  292. info->m_tpParent = branch;
  294. node->m_tpParent = branch;
  295. node->m_tpLeftSibling = info;
  296. node->m_tpRightSibling = 0;
  299. //設(shè)置節(jié)點(diǎn)的suffix link
  301. boolsetSuffix =false;
  302. vector::iterator iter = m_tagToNodeVec.begin();
  303. for(; iter != m_tagToNodeVec.end(); ++iter)
  304. {
  305. tagSuffixNode* tmp = *iter;
  306. if( strncmp( &(m_cpInternalStr[branch->m_nEdgeLabelEndPos - branch->m_nActiveLen + 2]), &(m_cpInternalStr[tmp->m_nEdgeLabelEndPos - tmp->m_nActiveLen + 1]), branch->m_nActiveLen - 1) == 0)
  307. {
  308. branch->m_tpSuffixLink = tmp;
  309. setSuffix =true;
  310. break;
  311. #ifdef DEBUG
  312. printf("branch[%c] suffix_link is branch[%c]\n", tmp->m_cIndex, branch->m_cIndex);
  313. #endif
  314. }
  315. }
  316. m_tagToNodeVec.push_back(branch);
  318. vector::iterator iter2 = m_tagFromNodeVec.begin();
  319. for(; iter2 != m_tagFromNodeVec.end(); ++iter2)
  320. {
  321. tagSuffixNode* tmp = *iter2;
  322. //找到后綴節(jié)點(diǎn)，結(jié)束循環(huán)
  323. if( strncmp( &(m_cpInternalStr[tmp->m_nEdgeLabelEndPos - tmp->m_nActiveLen + 2]), &(m_cpInternalStr[branch->m_nEdgeLabelEndPos - branch->m_nActiveLen + 1]), tmp->m_nActiveLen - 1) == 0)
  324. {
  325. tmp->m_tpSuffixLink = branch;
  326. m_tagFromNodeVec.erase(iter2);
  327. #ifdef DEBUG
  328. printf("branch[%c] suffix_link is branch[%c]\n", tmp->m_cIndex, branch->m_cIndex);
  329. #endif
  330. break;
  331. }
  332. }
  334. if( !setSuffix )
  335. {
  336. m_tagFromNodeVec.push_back(branch);
  337. }
  339. //已經(jīng)將新的后綴字符串插入到樹中，這時(shí)可以結(jié)束while了。
  340. break;
  341. }
  342. }
  343. }
  344. //test
  345. #ifdef DEBUG
  346. printf("print\n");
  347. printTree();
  348. #endif
  349. }
  350. }
  353. //查詢
  354. intCSuffixTree::search(char*str)
  355. {
  356. if(str == 0)
  357. return-1;
  358. //TODO
  359. //添加處理過(guò)程
  361. intlen = strlen(str);
  363. tagSuffixNode* node = 0;
  364. tagSuffixNode* cur = m_tpRoot;
  365. for(inti=0; i
  366. {
  367. node = __findChildBeginWithChar(cur, str[i]);
  368. if(node == 0)
  369. {
  370. break;
  371. }
  372. else
  373. {
  374. intedgeLen = node->m_nEdgeLabelEndPos - node->m_nEdgeLabelStartPos + 1;
  375. intremain = len - i;
  376. if( remain <= edgeLen )
  377. {
  378. if( strncmp(&(str[i]), &(m_cpInternalStr[node->m_nEdgeLabelStartPos]), remain) != 0)
  379. {
  380. return-1;
  381. }
  382. else
  383. {
  384. returnnode->m_nEdgeLabelEndPos - node->m_nActiveLen + 1;
  385. }
  386. }
  387. else
  388. {
  389. if( strncmp(&(str[i]), &(m_cpInternalStr[node->m_nEdgeLabelStartPos]), edgeLen) != 0)
  390. {
  391. return-1;
  392. }
  393. else
  394. {
  395. i += edgeLen;
  396. cur = node;
  397. }
  398. }
  399. }
  400. }
  401. return-1;
  402. }
  404. tagSuffixNode* CSuffixTree::__allocNode()
  405. {
  406. tagSuffixNode* node =newtagSuffixNode;
  408. m_tagNodeList.push_back(node);
  410. node->init();
  411. #ifdef DEBUG
  412. node->m_cIndex = m_cIndex;
  413. m_cIndex++;
  414. #endif
  415. returnnode;
  416. }
  418. tagSuffixNode* CSuffixTree::__findChildBeginWithChar(tagSuffixNode* node,charc)
  419. {
  420. assert(node != 0);
  422. tagSuffixNode* child = node->m_tpChild;
  423. while(child != 0)
  424. {
  425. if( m_cpInternalStr[child->m_nEdgeLabelStartPos] == c)
  426. returnchild;
  428. child = child->m_tpRightSibling;
  429. }
  431. return0;
  432. }
  434. voidCSuffixTree::test()
  435. {
  436. //printf("%s\n", m_cpInternalStr);
  437. printTree();
  438. }
  440. voidCSuffixTree::printTree()
  441. {
  442. #ifdef DEBUG
  443. printf("[A]\n");
  444. #endif
  445. __printHelper(m_tpRoot, 0);
  446. }
  448. voidCSuffixTree::__printHelper(tagSuffixNode* node,intlevel)
  449. {
  450. intstart = node->m_nEdgeLabelStartPos;
  451. intend = node->m_nEdgeLabelEndPos;
  452. tagSuffixNode* child = node->m_tpChild;
  453. if( level > 0 )
  454. {
  455. for(inti=0; i
  456. {
  457. printf(" |");
  458. }
  459. printf(" + ");
  460. for(intj = start; j <= end; j++)
  461. {
  462. printf("%c", m_cpInternalStr[j]);
  463. }
  464. #ifdef DEBUG
  465. printf("[%c]", node->m_cIndex);
  466. //         printf("[%d:%d:%d]", node->m_nEdgeLabelStartPos, node->m_nEdgeLabelEndPos, node->m_nActiveLen);
  467. #endif
  468. printf("\n");
  469. }
  471. while( child != 0 )
  472. {
  473. __printHelper(child, level+1);
  474. child = child->m_tpRightSibling;
  475. }
  476. }
  478. intmain()
  479. {
  480. cout<<"hello suffixtree"<
  481. system("pause");
  482. return0;
  483. }

   

    運(yùn)行結(jié)果如下：1024x551

Shlomo Yona的實(shí)現(xiàn)

    下面是國(guó)外一牛人Shlomo Yona寫的實(shí)現(xiàn)（摘取了部分非完整代碼）：

   

  1. /******************************************************************************
  2. Suffix Tree Version 2.1
  4. AUTHORS
  6. Dotan Tsadok
  7. Instructor: Mr. Shlomo Yona, University of Haifa, Israel. December 2002.
  8. Current maintainer: Shlomo Yona 
  10. COPYRIGHT
  12. Copyright 2002-2003 Shlomo Yona
  14. LICENSE
  16. This library is free software; you can redistribute it and/or modify it
  17. under the same terms as Perl itself.
  20. DESCRIPTION OF THIS FILE:
  22. This is the implementation file suffix_tree.c implementing the header file
  23. suffix_tree.h.
  25. This code is an Open Source implementation of Ukkonen's algorithm for
  26. constructing a suffix tree over a string in time and space complexity
  27. O(length of the string). The code is written under strict ANSI C.
  29. For a complete understanding of the code see Ukkonen's algorithm and the
  30. readme.txt file.
  32. The general pseudo code is:
  34. n = length of the string.
  35. ST_CreateTree:
  36. Calls n times to SPA (Single Phase Algorithm). SPA:
  37. Increase the variable e (virtual end of all leaves).
  38. Calls SEA (Single Extension Algorithm) starting with the first extension that
  39. does not already exist in the tree and ending at the first extension that
  40. already exists. SEA :
  41. Follow suffix link.
  42. Check if current suffix exists in the tree.
  43. If it does not - apply rule 2 and then create a new suffix link.
  44. apply_rule_2:
  45. Create a new leaf and maybe a new internal node as well.
  46. create_node:
  47. Create a new node or a leaf.
  50. For implementation interpretations see Basic Ideas paragraph in the Developement
  51. section of the readme.txt file.
  53. An example of the implementations of a node and its sons using linked lists
  54. instead of arrays:
  56. (1)
  57. |
  58. |
  59. |
  60. (2)--(3)--(4)--(5)
  62. (2) is the only son of (1) (call it the first son). Other sons of (1) are
  63. connected using a linked lists starting from (2) and going to the right. (3) is
  64. the right sibling of (2) (and (2) is the left sibling of (3)), (4) is the right
  65. sibling of (3), etc.
  66. The father field of all (2), (3), (4) and (5) points to (1), but the son field
  67. of (1) points only to (2).
  69. *******************************************************************************/
  71. #include "stdlib.h"
  72. #include "stdio.h"
  73. #include "string.h"
  74. #include "suffix_tree.h"
  76. /* See function body */
  77. voidST_PrintTree(SUFFIX_TREE* tree);
  78. /* See function body */
  79. voidST_PrintFullNode(SUFFIX_TREE* tree, NODE* node);
  81. /* Used in function trace_string for skipping (Ukkonen's Skip Trick). */
  82. typedefenumSKIP_TYPE     {skip, no_skip}                 SKIP_TYPE;
  83. /* Used in function apply_rule_2 - two types of rule 2 - see function for more
  84. details.*/
  85. typedefenumRULE_2_TYPE   {new_son, split}                RULE_2_TYPE;
  86. /* Signals whether last matching position is the last one of the current edge */
  87. typedefenumLAST_POS_TYPE {last_char_in_edge, other_char} LAST_POS_TYPE;
  89. /* Used for statistic measures of speed. */
  90. DBL_WORD counter;
  91. /* Used for statistic measures of space. */
  92. DBL_WORD heap;
  93. /* Used to mark the node that has no suffix link yet. By Ukkonen, it will have
  94. one by the end of the current phase. */
  95. NODE*    suffixless;
  97. typedefstructSUFFIXTREEPATH
  98. {
  99. DBL_WORD   begin;
  100. DBL_WORD   end;
  101. } PATH;
  103. typedefstructSUFFIXTREEPOS
  104. {
  105. NODE*      node;
  106. DBL_WORD   edge_pos;
  107. }POS;
  109. /******************************************************************************/
  110. /*
  111. Define STATISTICS in order to view measures of speed and space while
  112. constructing and searching the suffix tree. Measures will be printed on the
  113. screen.
  114. */
  115. /* #define STATISTICS */
  117. /*
  118. Define DEBUG in order to view debug printouts to the screen while
  119. constructing and searching the suffix tree.
  120. */
  121. /* #define DEBUG */
  123. /******************************************************************************/
  124. /*
  125. create_node :
  126. Creates a node with the given init field-values.
  128. Input : The father of the node, the starting and ending indices
  129. of the incloming edge to that node,
  130. the path starting position of the node.
  132. Output: A pointer to that node.
  133. */
  136. NODE* create_node(NODE* father, DBL_WORD start, DBL_WORD end, DBL_WORD position)
  137. {
  138. /*Allocate a node.*/
  139. NODE* node   = (NODE*)malloc(sizeof(NODE));
  140. if(node == 0)
  141. {
  142. printf("\nOut of memory.\n");
  143. exit(0);
  144. }
  146. #ifdef STATISTICS
  147. heap+=sizeof(NODE);
  148. #endif
  150. /* Initialize node fields. For detailed description of the fields see
  151. suffix_tree.h */
  152. node->sons             = 0;
  153. node->right_sibling    = 0;
  154. node->left_sibling     = 0;
  155. node->suffix_link      = 0;
  156. node->father           = father;
  157. node->path_position    = position;
  158. node->edge_label_start = start;
  159. node->edge_label_end   = end;
  160. returnnode;
  161. }
  163. /******************************************************************************/
  164. /*
  165. find_son :
  166. Finds son of node that starts with a certain character.
  168. Input : the tree, the node to start searching from and the character to be
  169. searched in the sons.
  171. Output: A pointer to the found son, 0 if no such son.
  172. */
  174. NODE* find_son(SUFFIX_TREE* tree, NODE* node,charcharacter)
  175. {
  176. /* Point to the first son. */
  177. node = node->sons;
  178. /* scan all sons (all right siblings of the first son) for their first
  179. character (it has to match the character given as input to this function. */
  180. while(node != 0 && tree->tree_string[node->edge_label_start] != character)
  181. {
  182. #ifdef STATISTICS
  183. counter++;
  184. #endif
  185. node = node->right_sibling;
  186. }
  187. returnnode;
  188. }
  190. /******************************************************************************/
  191. /*
  192. get_node_label_end :
  193. Returns the end index of the incoming edge to that node. This function is
  194. needed because for leaves the end index is not relevant, instead we must look
  195. at the variable "e" (the global virtual end of all leaves). Never refer
  196. directly to a leaf's end-index.
  198. Input : the tree, the node its end index we need.
  200. Output: The end index of that node (meaning the end index of the node's
  201. incoming edge).
  202. */
  204. DBL_WORD get_node_label_end(SUFFIX_TREE* tree, NODE* node)
  205. {
  206. /* If it's a leaf - return e */
  207. if(node->sons == 0)
  208. returntree->e;
  209. /* If it's not a leaf - return its real end */
  210. returnnode->edge_label_end;
  211. }
  213. /******************************************************************************/
  214. /*
  215. get_node_label_length :
  216. Returns the length of the incoming edge to that node. Uses get_node_label_end
  217. (see above).
  219. Input : The tree and the node its length we need.
  221. Output: the length of that node.
  222. */
  224. DBL_WORD get_node_label_length(SUFFIX_TREE* tree, NODE* node)
  225. {
  226. /* Calculate and return the lentgh of the node */
  227. returnget_node_label_end(tree, node) - node->edge_label_start + 1;
  228. }
  230. /******************************************************************************/
  231. /*
  232. is_last_char_in_edge :
  233. Returns 1 if edge_pos is the last position in node's incoming edge.
  235. Input : The tree, the node to be checked and the position in its incoming
  236. edge.
  238. Output: the length of that node.
  239. */
  241. charis_last_char_in_edge(SUFFIX_TREE* tree, NODE* node, DBL_WORD edge_pos)
  242. {
  243. if(edge_pos == get_node_label_length(tree,node)-1)
  244. return1;
  245. return0;
  246. }
  248. /******************************************************************************/
  249. /*
  250. connect_siblings :
  251. Connect right_sib as the right sibling of left_sib and vice versa.
  253. Input : The two nodes to be connected.
  255. Output: None.
  256. */
  258. voidconnect_siblings(NODE* left_sib, NODE* right_sib)
  259. {
  260. /* Connect the right node as the right sibling of the left node */
  261. if(left_sib != 0)
  262. left_sib->right_sibling = right_sib;
  263. /* Connect the left node as the left sibling of the right node */
  264. if(right_sib != 0)
  265. right_sib->left_sibling = left_sib;
  266. }
  268. /******************************************************************************/
  269. /*
  270. apply_extension_rule_2 :
  271. Apply "extension rule 2" in 2 cases:
  272. 1. A new son (leaf 4) is added to a node that already has sons:
  273. (1)        (1)
  274. /   \     ->   / | \
  275. (2)  (3)      (2)(3)(4)
  277. 2. An edge is split and a new leaf (2) and an internal node (3) are added:
  278. |       |
  279. |      (3)
  280. |     ->   / \
  281. (1)       (1) (2)
  283. Input : See parameters.
  285. Output: A pointer to the newly created leaf (new_son case) or internal node
  286. (split case).
  287. */
  289. NODE* apply_extension_rule_2(
  290. /* Node 1 (see drawings) */
  291. NODE*           node,
  292. /* Start index of node 2's incoming edge */
  293. DBL_WORD        edge_label_begin,
  294. /* End index of node 2's incoming edge */
  295. DBL_WORD        edge_label_end,
  296. /* Path start index of node 2 */
  297. DBL_WORD        path_pos,
  298. /* Position in node 1's incoming edge where split is to be
  299. performed */
  300. DBL_WORD        edge_pos,
  301. /* Can be 'new_son' or 'split' */
  302. RULE_2_TYPE     type)
  303. {
  304. NODE *new_leaf,
  305. *new_internal,
  306. *son;
  307. /*-------new_son-------*/
  308. if(type == new_son)
  309. {
  310. #ifdef DEBUG
  311. printf("rule 2: new leaf (%lu,%lu)\n",edge_label_begin,edge_label_end);
  312. #endif
  313. /* Create a new leaf (4) with the characters of the extension */
  314. new_leaf = create_node(node, edge_label_begin , edge_label_end, path_pos);
  315. /* Connect new_leaf (4) as the new son of node (1) */
  316. son = node->sons;
  317. while(son->right_sibling != 0)
  318. son = son->right_sibling;
  319. connect_siblings(son, new_leaf);
  320. /* return (4) */
  321. returnnew_leaf;
  322. }
  323. /*-------split-------*/
  324. #ifdef DEBUG
  325. printf("rule 2: split (%lu,%lu)\n",edge_label_begin,edge_label_end);
  326. #endif
  327. /* Create a new internal node (3) at the split point */
  328. new_internal = create_node(
  329. node->father,
  330. node->edge_label_start,
  331. node->edge_label_start+edge_pos,
  332. node->path_position);
  333. /* Update the node (1) incoming edge starting index (it now starts where node
  334. (3) incoming edge ends) */
  335. node->edge_label_start += edge_pos+1;
  337. /* Create a new leaf (2) with the characters of the extension */
  338. new_leaf = create_node(
  339. new_internal,
  340. edge_label_begin,
  341. edge_label_end,
  342. path_pos);
  344. /* Connect new_internal (3) where node (1) was */
  345. /* Connect (3) with (1)'s left sibling */
  346. connect_siblings(node->left_sibling, new_internal);
  347. /* connect (3) with (1)'s right sibling */
  348. connect_siblings(new_internal, node->right_sibling);
  349. node->left_sibling = 0;
  351. /* Connect (3) with (1)'s father */
  352. if(new_internal->father->sons == node)
  353. new_internal->father->sons = new_internal;
  355. /* Connect new_leaf (2) and node (1) as sons of new_internal (3) */
  356. new_internal->sons = node;
  357. node->father = new_internal;
  358. connect_siblings(node, new_leaf);
  359. /* return (3) */
  360. returnnew_internal;
  361. }
  363. /******************************************************************************/
  364. /*
  365. trace_single_edge :
  366. Traces for a string in a given node's OUTcoming edge. It searches only in the
  367. given edge and not other ones. Search stops when either whole string was
  368. found in the given edge, a part of the string was found but the edge ended
  369. (and the next edge must be searched too - performed by function trace_string)
  370. or one non-matching character was found.
  372. Input : The string to be searched, given in indices of the main string.
  374. Output: (by value) the node where tracing has stopped.
  375. (by reference) the edge position where last match occured, the string
  376. position where last match occured, number of characters found, a flag
  377. for signaling whether search is done, and a flag to signal whether
  378. search stopped at a last character of an edge.
  379. */
  381. NODE* trace_single_edge(
  382. SUFFIX_TREE*    tree,
  383. /* Node to start from */
  384. NODE*           node,
  385. /* String to trace */
  386. PATH            str,
  387. /* Last matching position in edge */
  388. DBL_WORD*       edge_pos,
  389. /* Last matching position in tree source string */
  390. DBL_WORD*       chars_found,
  391. /* Skip or no_skip*/
  392. SKIP_TYPE       type,
  393. /* 1 if search is done, 0 if not */
  394. int*            search_done)
  395. {
  396. NODE*      cont_node;
  397. DBL_WORD   length,str_len;
  399. /* Set default return values */
  400. *search_done = 1;
  401. *edge_pos    = 0;
  403. /* Search for the first character of the string in the outcoming edge of
  404. node */
  405. cont_node = find_son(tree, node, tree->tree_string[str.begin]);
  406. if(cont_node == 0)
  407. {
  408. /* Search is done, string not found */
  409. *edge_pos = get_node_label_length(tree,node)-1;
  410. *chars_found = 0;
  411. returnnode;
  412. }
  414. /* Found first character - prepare for continuing the search */
  415. node    = cont_node;
  416. length  = get_node_label_length(tree,node);
  417. str_len = str.end - str.begin + 1;
  419. /* Compare edge length and string length. */
  420. /* If edge is shorter then the string being searched and skipping is
  421. enabled - skip edge */
  422. if(type == skip)
  423. {
  424. if(length <= str_len)
  425. {
  426. (*chars_found)   = length;
  427. (*edge_pos)      = length-1;
  428. if(length < str_len)
  429. *search_done  = 0;
  430. }
  431. else
  432. {
  433. (*chars_found)   = str_len;
  434. (*edge_pos)      = str_len-1;
  435. }
  437. #ifdef STATISTICS
  438. counter++;
  439. #endif
  441. returnnode;
  442. }
  443. else
  444. {
  445. /* Find minimum out of edge length and string length, and scan it */
  446. if(str_len < length)
  447. length = str_len;
  449. for(*edge_pos=1, *chars_found=1; *edge_pos
  450. {
  452. #ifdef STATISTICS
  453. counter++;
  454. #endif
  456. /* Compare current characters of the string and the edge. If equal -
  457. continue */
  458. if(tree->tree_string[node->edge_label_start+*edge_pos] != tree->tree_string[str.begin+*edge_pos])
  459. {
  460. (*edge_pos)--;
  461. returnnode;
  462. }
  463. }
  464. }
  466. /* The loop has advanced *edge_pos one too much */
  467. (*edge_pos)--;
  469. if((*chars_found) < str_len)
  470. /* Search is not done yet */
  471. *search_done = 0;
  473. returnnode;
  474. }
  476. /******************************************************************************/
  477. /*
  478. trace_string :
  479. Traces for a string in the tree. This function is used in construction
  480. process only, and not for after-construction search of substrings. It is
  481. tailored to enable skipping (when we know a suffix is in the tree (when
  482. following a suffix link) we can avoid comparing all symbols of the edge by
  483. skipping its length immediately and thus save atomic operations - see
  484. Ukkonen's algorithm, skip trick).
  485. This function, in contradiction to the function trace_single_edge, 'sees' the
  486. whole picture, meaning it searches a string in the whole tree and not just in
  487. a specific edge.
  489. Input : The string, given in indice of the main string.
  491. Output: (by value) the node where tracing has stopped.
  492. (by reference) the edge position where last match occured, the string
  493. position where last match occured, number of characters found, a flag
  494. for signaling whether search is done.
  495. */
  497. NODE* trace_string(
  498. SUFFIX_TREE*    tree,
  499. /* Node to start from */
  500. NODE*           node,
  501. /* String to trace */
  502. PATH            str,
  503. /* Last matching position in edge */
  504. DBL_WORD*       edge_pos,
  505. /* Last matching position in tree string */
  506. DBL_WORD*       chars_found,
  507. /* skip or not */
  508. SKIP_TYPE       type)
  509. {
  510. /* This variable will be 1 when search is done.
  511. It is a return value from function trace_single_edge */
  512. intsearch_done = 0;
  514. /* This variable will hold the number of matching characters found in the
  515. current edge. It is a return value from function trace_single_edge */
  516. DBL_WORD edge_chars_found;
  518. *chars_found = 0;
  520. while(search_done == 0)
  521. {
  522. *edge_pos        = 0;
  523. edge_chars_found = 0;
  524. node = trace_single_edge(tree, node, str, edge_pos, &edge_chars_found, type, &search_done);
  525. str.begin       += edge_chars_found;
  526. *chars_found    += edge_chars_found;
  527. }
  528. returnnode;
  529. }
  531. /******************************************************************************/
  532. /*
  533. ST_FindSubstring :
  534. See suffix_tree.h for description.
  535. */
  537. DBL_WORD ST_FindSubstring(
  538. /* The suffix array */
  539. SUFFIX_TREE*    tree,
  540. /* The substring to find */
  541. char*  W,
  542. /* The length of W */
  543. DBL_WORD        P)
  544. {
  545. /* Starts with the root's son that has the first character of W as its
  546. incoming edge first character */
  547. NODE* node   = find_son(tree, tree->root, W[0]);
  548. DBL_WORD k,j = 0, node_label_en

數(shù)據(jù)分析咨詢請(qǐng)掃描二維碼

若不方便掃碼，搜微信號(hào)：CDAshujufenxi

數(shù)據(jù)分析師資訊
更多

OK
客服在線
立即咨詢
客服在線
立即咨詢
') } function initGt() { var handler = function (captchaObj) { captchaObj.appendTo('#captcha'); captchaObj.onReady(function () { $("#wait").hide(); }).onSuccess(function(){ $('.getcheckcode').removeClass('dis'); $('.getcheckcode').trigger('click'); }); window.captchaObj = captchaObj; }; $('#captcha').show(); $.ajax({ url: "/login/gtstart?t=" + (new Date()).getTime(), // 加隨機(jī)數(shù)防止緩存 type: "get", dataType: "json", success: function (data) { $('#text').hide(); $('#wait').show(); // 調(diào)用 initGeetest 進(jìn)行初始化 // 參數(shù)1：配置參數(shù) // 參數(shù)2：回調(diào)，回調(diào)的第一個(gè)參數(shù)驗(yàn)證碼對(duì)象，之后可以使用它調(diào)用相應(yīng)的接口 initGeetest({ // 以下 4 個(gè)配置參數(shù)為必須，不能缺少 gt: data.gt, challenge: data.challenge, offline: !data.success, // 表示用戶后臺(tái)檢測(cè)極驗(yàn)服務(wù)器是否宕機(jī) new_captcha: data.new_captcha, // 用于宕機(jī)時(shí)表示是新驗(yàn)證碼的宕機(jī) product: "float", // 產(chǎn)品形式，包括：float，popup width: "280px", https: true // 更多配置參數(shù)說(shuō)明請(qǐng)參見：http://docs.geetest.com/install/client/web-front/ }, handler); } }); } function codeCutdown() { if(_wait == 0){ //倒計(jì)時(shí)完成 $(".getcheckcode").removeClass('dis').html("重新獲取"); }else{ $(".getcheckcode").addClass('dis').html("重新獲取("+_wait+"s)"); _wait--; setTimeout(function () { codeCutdown(); },1000); } } function inputValidate(ele,telInput) { var oInput = ele; var inputVal = oInput.val(); var oType = ele.attr('data-type'); var oEtag = $('#etag').val(); var oErr = oInput.closest('.form_box').next('.err_txt'); var empTxt = '請(qǐng)輸入'+oInput.attr('placeholder')+'！'; var errTxt = '請(qǐng)輸入正確的'+oInput.attr('placeholder')+'！'; var pattern; if(inputVal==""){ if(!telInput){ errFun(oErr,empTxt); } return false; }else { switch (oType){ case 'login_mobile': pattern = /^1[3456789]\d{9}$/; if(inputVal.length==11) { $.ajax({ url: '/login/checkmobile', type: "post", dataType: "json", data: { mobile: inputVal, etag: oEtag, page_ur: window.location.href, page_referer: document.referrer }, success: function (data) { } }); } break; case 'login_yzm': pattern = /^\d{6}$/; break; } if(oType=='login_mobile'){ } if(!!validateFun(pattern,inputVal)){ errFun(oErr,'') if(telInput){ $('.getcheckcode').removeClass('dis'); } }else { if(!telInput) { errFun(oErr, errTxt); }else { $('.getcheckcode').addClass('dis'); } return false; } } return true; } function errFun(obj,msg) { obj.html(msg); if(msg==''){ $('.login_submit').removeClass('dis'); }else { $('.login_submit').addClass('dis'); } } function validateFun(pat,val) { return pat.test(val); }