Board logo

标题: 多国语言词频、字频统计工具 trie [打印本页]

作者: happy886rr    时间: 2017-10-25 22:45     标题: 多国语言词频、字频统计工具 trie

本帖最后由 happy886rr 于 2017-10-25 23:27 编辑

[词频、字频统计工具trie]

这是继文本工具tl之后的又一文本第三方,统计多国语言词频、字频、单词频率。可以智能的做前缀是否去重,智能粒进匹配。智能切词。速度比同类软件快100倍。

存下图为a.zip解压便是(外链图有效期仅7天,过期不再提供任何下载)



用法:
-------------------------------------------------------------------------
trie u:[统计字典文件] <[待统计文本流]>[输出文本流]

echo hello world|trie -u:C1.DI
trie +u:C2.DI <in.txt>out.txt
trie u:S2_IDIOM.DI <in.txt>out.txt
trie m

注:u前面可以加正负号,表示正逆序排序输出统计表。
-------------------------------------------------------------------------


原创代码:
  1. /*
  2. CONSOLE TXT CHARACTER STATISTICS TOOL @COPYRIGHT@2017~2019 BY HAPPY, VERSION 1.0
  3. WED OCT 25 2017 21:10:16 GMT+0800
  4. **********************************************************************
  5. gcc trie.c -o trie.exe                 REM For Windows
  6. gcc trie.c -o trie                     REM For Linux
  7. gcc trie.c -o trie                     REM For Android
  8. cl  trie.cpp /MD /Ox /out:trie.exe     REM For VS
  9. **********************************************************************
  10. */
  11. #include <stdio.h>
  12. #include <stdlib.h>
  13. #include <string.h>
  14. #include <time.h>
  15. // 定义帮助说明
  16. #define HELP_INFORMATION "\
  17. Trie v1.0 - Console txt character statistics tool\n\
  18. Usage:\n\
  19.     trie [option] <[infile]>[outfile]\n\
  20. \n\
  21. General options:\n\
  22.      u:[userdic] Not sorting statistics result\n\
  23.     +u:[userdic] Sorting result order by ASC\n\
  24.     -u:[userdic] Sorting result order by DESC\n\
  25. \n\
  26. You can use switch 'm' to make a user dictionary head file\n\
  27. "
  28. // 定义字典注释头
  29. #define DICFILE_HEAD "\
  30. /|||\n\
  31. TRIE - USER DICTIONARY TABLE 1.0\n\
  32. ==============================================================\n\
  33. DICTIONARY NAME:  EMPTY\n\
  34. MADE DATE:        1970-01-01\n\
  35. CHARSET:          ANSI/UTF8\n\
  36. MAX SHOW:\n\
  37. ==============================================================\n\
  38. BYTE LOW:         0\n\
  39. BYTE HIGH:        255\n\
  40. INSERT MIN:       1\n\
  41. INSERT MAX:       8\n\
  42. STEP FORWARD MIN: 1\n\
  43. STEP FORWARD MAX: 2\n\
  44. ==============================================================\n\
  45. |||/\n\
  46. "
  47. #ifndef byte
  48. typedef unsigned char byte;
  49. #endif
  50. #ifndef bool
  51. typedef enum {false, true} bool;
  52. #endif
  53. // 比特数组结尾
  54. #define BYTE_EOF 0xFF
  55. // 标准行长
  56. #define LINE_BUFF_SIZE     (1024 * 64)
  57. // 拼接缓存区最大长度
  58. #define MAX_JOIN_SIZE     32
  59. // 展示数组词条容量(不超过64万条)
  60. #define SHOW_ARRAY_SIZE    (1024 * 10 * 64)
  61. // Trie树深度,即字典词目最大字节数
  62. #define TRIE_DEEP_SIZE     24
  63. // Trie树价值数组长度
  64. #define TRIE_VALUE_SIZE    1
  65. // Trie树启动参数
  66. static int trie_low_offset;
  67. static int trie_high_offset;
  68. static int trie_min_granularity;
  69. static int trie_max_granularity;
  70. static int trie_min_insert;
  71. static int trie_max_insert;
  72. static int use_english_mode;
  73. static int use_substring_match;
  74. // Trie树分支宽度
  75. static int trie_branch_size;
  76. // 统计表数组辅助指针
  77. static int* p_static_array;
  78. // 展示列表数目
  79. static int show_list_size;
  80. // 已经展示的数目
  81. static int already_show_list;
  82. // 判断是否字母的宏
  83. #define ISLETTER(x) ( ((0x41 <= (x)) && ((x) <= 0x5A)) || ((0x61 <= (x)) && ((x) <= 0x7A)) )
  84. // 判断是否小写字母的宏
  85. #define ISLOWERLETTER(x) ((0x61 <= (x)) && ((x) <= 0x7A))
  86. // 判断是否大写字母的宏
  87. #define ISUPPERLETTER(x) ((0x41 <= (x)) && ((x) <= 0x5A))
  88. // 取最值
  89. #define MAXVALUE(a,b) (((a)>(b))?(a):(b))
  90. // 排序类型
  91. typedef enum
  92. {
  93. SORT_NO = 0,
  94. SORT_ASC = 1,
  95. SORT_DESC = -1
  96. } SortMode;
  97. // 快排堆栈尺寸
  98. #define QSORT_STACK_SIZE   1024
  99. // 快排数据交换
  100. #define SWAP(a,b) (((a)==(b))?0:((a)^=(b)^=(a)^=(b)))
  101. // #define SWAP(a,b) do{int _tmp=(a);(a)=(b),(b)=_tmp;}while(false)
  102. // 快排比较函数
  103. #define COMP(a,b,sortMode) (((a)-(b))*(sortMode))
  104. // 增强型快排算法
  105. bool QsortStaticArray(int* staticArray, SortMode sortMode, int left, int right)
  106. {
  107. // 针对仅排序一个元素时,无需排序,直接返回真
  108. if(right == left)
  109. {
  110. return true;
  111. }
  112. // 检验输入参数合法性
  113. if(
  114.     staticArray == NULL
  115.     || left < 0
  116.     || right < 0
  117.     || left > right
  118. )
  119. {
  120. return false;
  121. }
  122. // 数据类型转化
  123. int (*iArray)[2] = (int(*)[2])staticArray;
  124. // 定义数组堆栈,用来记录
  125. int pStack[QSORT_STACK_SIZE][2], pStackIndex = 0;
  126. // 快排分区首次出栈
  127. pStack[pStackIndex   ][0] = left;
  128. pStack[pStackIndex ++][1] = right;
  129. // 混排算法核心
  130. while(pStackIndex > 0)
  131. {
  132. // 快排分区出栈
  133. int i = pStack[-- pStackIndex][0];
  134. int j = pStack[   pStackIndex][1];
  135. if(i < j)
  136. {
  137. int ls = i, rs = j;
  138. // 对于小数组,直接采用选择排序
  139. if(j - i + 1 < 8)
  140. {
  141. int p, max;
  142. while (ls < rs)
  143. {
  144. max = ls;
  145. for (p = ls + 1; p <= rs; p ++)
  146. {
  147. if(COMP(iArray[p][0], iArray[max][0], sortMode) > 0)
  148. {
  149. max = p;
  150. }
  151. }
  152. SWAP(iArray[max][0], iArray[rs][0]);
  153. SWAP(iArray[max][1], iArray[rs][1]);
  154. rs--;
  155. }
  156. continue;
  157. }
  158. // 计算中间项数
  159. int mid = (j-i)/2 + i + 1;
  160. // 整理局部数组,以使中位数居中
  161. if(COMP(iArray[i][0], iArray[mid][0], sortMode) > 0)
  162. {
  163. SWAP(iArray[i][0], iArray[mid][0]);
  164. SWAP(iArray[i][1], iArray[mid][1]);
  165. }
  166. if(COMP(iArray[i][0], iArray[j][0], sortMode) > 0)
  167. {
  168. SWAP(iArray[i][0], iArray[j][0]);
  169. SWAP(iArray[i][1], iArray[j][1]);
  170. }
  171. if(COMP(iArray[mid][0], iArray[j][0], sortMode) > 0)
  172. {
  173. SWAP(iArray[mid][0], iArray[j][0]);
  174. SWAP(iArray[mid][1], iArray[j][1]);
  175. }
  176. SWAP(iArray[mid][0], iArray[i][0]);
  177. SWAP(iArray[mid][1], iArray[i][1]);
  178. // 获取基准数据
  179. int base[2] = {iArray[ls][0], iArray[ls][1]};
  180. bool needsCheck = false;
  181. bool alreadyCheck = false;
  182. // 快排交换核心
  183. while(ls < rs)
  184. {
  185. while(ls < rs && COMP(iArray[rs][0], base[0], sortMode) >= 0)
  186. {
  187. rs--;
  188. }
  189. iArray[ls][0] = iArray[rs][0];
  190. iArray[ls][1] = iArray[rs][1];
  191. // 右排序检查器
  192. if(alreadyCheck == false)
  193. {
  194. if(rs == ls)
  195. {
  196. needsCheck = true;
  197. }
  198. }
  199. while(ls < rs && COMP(iArray[ls][0], base[0], sortMode) <= 0)
  200. {
  201. ls++;
  202. }
  203. iArray[rs][0] = iArray[ls][0];
  204. iArray[rs][1] = iArray[ls][1];
  205. // 左排序检查器
  206. if(alreadyCheck == false)
  207. {
  208. if(rs == ls)
  209. {
  210. needsCheck = true;
  211. }
  212. }
  213. // 已经检查完毕
  214. alreadyCheck = true;
  215. }
  216. iArray[ls][0] = base[0];
  217. iArray[ls][1] = base[1];
  218. // 如果需要检查排序
  219. if(needsCheck == true)
  220. {
  221. int check = i;
  222. while(check < j && COMP(iArray[check][0], iArray[check + 1][0], sortMode) <= 0)
  223. {
  224. check ++;
  225. }
  226. if(check == j)
  227. {
  228. // 已经排序,直接跳转
  229. continue;
  230. }
  231. }
  232. // 快排分区数组堆栈实现
  233. int k = ls;
  234. if(i < k - 1)
  235. {
  236. // 快排分区入栈
  237. pStack[pStackIndex   ][0] = i;
  238. pStack[pStackIndex ++][1] = k-1;
  239. }
  240. if(k +1 < j)
  241. {
  242. // 快排分区入栈
  243. pStack[pStackIndex   ][0] = k+1;
  244. pStack[pStackIndex ++][1] = j;
  245. }
  246. }
  247. }
  248. return true;
  249. }
  250. // 创建TrieNode结构体
  251. typedef struct TrieNode
  252. {
  253. // 节点词尾
  254. bool end;
  255. // 节点数据 (value[]数组用于词频统计)
  256. int value[TRIE_VALUE_SIZE];
  257. // 节点分支
  258. struct TrieNode** branch;
  259. } TrieNode, *PTrieNode;
  260. // 创建TrieNode节点
  261. PTrieNode PTrieNodeCreate(int branchSize)
  262. {
  263. // 动态分配TrieNode内存
  264. PTrieNode pTrieNode = (PTrieNode)malloc(1 * sizeof(TrieNode));
  265. // 分配内存识别
  266. if(pTrieNode == NULL)
  267. {
  268. // 如果开辟内存失败,直接退出
  269. fprintf(stderr, "Can't have enough memory\n");
  270. exit(1);
  271. }
  272. // 词目结尾标记
  273. pTrieNode->end = false;
  274. // 统计信息记录点
  275. memset((void*)pTrieNode->value, (int)NULL, TRIE_VALUE_SIZE * sizeof(int));
  276. // 分配Trie树节点内存
  277. pTrieNode->branch = (TrieNode**)calloc(branchSize, sizeof(TrieNode*));
  278. // 如果开辟内存失败,直接退出
  279. if(pTrieNode->branch == NULL)
  280. {
  281. // 如果开辟内存失败,直接退出
  282. fprintf(stderr, "Can't have enough memory\n");
  283. exit(1);
  284. }
  285. // 分配内存成功,则返回节点指针
  286. return pTrieNode;
  287. }
  288. // 释放Trie树内存
  289. void TrieFree(PTrieNode rootPTrieNode)
  290. {
  291. PTrieNode pTrie = rootPTrieNode;
  292. int i;
  293. for(i = 0; i < trie_branch_size; i ++)
  294. {
  295. if(pTrie->branch[i] != NULL)
  296. {
  297. TrieFree(pTrie->branch[i]);
  298. }
  299. }
  300. free(pTrie);
  301. }
  302. // Trie树插入函数
  303. int TrieInsert(PTrieNode rootPTrieNode, byte* insertData, size_t insertDataLen)
  304. {
  305. // 当插入数据过深时直接拒绝
  306. if(insertDataLen >= TRIE_DEEP_SIZE)
  307. {
  308. // 抛出错误
  309. fprintf(stderr, "The dictionary tree is inserted too deep\n");
  310. exit(1);
  311. }
  312. PTrieNode pTrie = rootPTrieNode;
  313. byte* p = insertData;
  314. while(p - insertData < insertDataLen)
  315. {
  316. if(pTrie->branch[*p - trie_low_offset] == NULL)
  317. {
  318. // 创建分支节点
  319. pTrie->branch[*p - trie_low_offset] = PTrieNodeCreate(trie_branch_size);
  320. }
  321. // 深入下层节点
  322. pTrie = pTrie->branch[*p - trie_low_offset];
  323. // 插入词组
  324. if(pTrie->end == false)
  325. {
  326. if((p + 1) - insertData == insertDataLen)
  327. {
  328. pTrie->end = true;
  329. break;
  330. }
  331. }
  332. // 指针移位
  333. p ++;
  334. }
  335. return 0;
  336. }
  337. // 创建TrieStatic返回结构体
  338. typedef struct RetTrieStatic
  339. {
  340. // 单次匹配的词目数
  341. int thisMatchedCount;
  342. // 剩余的字节数目
  343. int restBytesNumber;
  344. // 剩余的匹配位置
  345. byte* restMatchPtr;
  346. } RetTrieStatic, *PRetTrieStatic;
  347. // Trie树统计函数
  348. int TrieStatic(PTrieNode rootPTrieNode, byte* originalDataPtr, size_t originalDataLen, bool useSubstringMatch, bool useEnglishMode, bool isJoinMatch, PRetTrieStatic pRetTrieStatic, size_t minGranularity, size_t maxGranularity)
  349. {
  350. // Trie节点堆栈
  351. PTrieNode p_trie_stack[TRIE_DEEP_SIZE + 1];
  352. // 本次匹配的词目数
  353. int mathedCount = 0;
  354. // 余下的数据长度
  355. int restDataLen = 0;
  356. // 设置数据指针
  357. byte* searchDataPtr = originalDataPtr;
  358. // 循环切片匹配
  359. while(*searchDataPtr != BYTE_EOF)
  360. {
  361. // 字符过滤器
  362. while(*searchDataPtr != BYTE_EOF)
  363. {
  364. if(
  365. // 判断字节范围
  366. (! ((trie_low_offset <= *searchDataPtr) && (*searchDataPtr <= trie_high_offset)))
  367. // 或者是英文模式下,非字母
  368. || ((useEnglishMode) && (! ISLETTER(*searchDataPtr)))
  369. )
  370. {
  371. searchDataPtr ++;
  372. }
  373. else
  374. {
  375. // 符合字节范围的、则中断内层循环,送入外层循环
  376. break;
  377. }
  378. }
  379. // 辅助主指针
  380. PTrieNode pTrie = rootPTrieNode;
  381. byte* p = searchDataPtr;
  382. // 堆栈索引
  383. int p_trie_index = 0;
  384. // 声明匹配参量
  385. int matchLen = 0;
  386. bool matchAlready = false;
  387. // 匹配算法核心
  388. while(*p != BYTE_EOF)
  389. {
  390. if(
  391.     // 字节过滤范围
  392.     (!(
  393.             // 字节筛选器低位
  394.             (*p >= trie_low_offset)
  395.             // 字节筛选器高位
  396.             && (*p <= trie_high_offset)
  397.     ))
  398.     // 匹配失败
  399.     || (pTrie->branch[*p - trie_low_offset] == NULL)
  400. )
  401. {
  402. // 如果是英文匹配模式,则会自动忽略大小写
  403. if(
  404. (useEnglishMode)
  405. && (pTrie->branch[*p - trie_low_offset] == NULL)
  406. && (ISLETTER(*p))
  407. )
  408. {
  409. *p = ISUPPERLETTER(*p) ?(*p + 0x20) :(*p - 0x20);
  410. int V = (int)(*p) - trie_low_offset;
  411. // 忽略大小写匹配英文单词
  412. if(! ((0 <= V) && (V < trie_branch_size) && (pTrie->branch[V] != NULL)))
  413. {
  414. break;
  415. }
  416. }
  417. else
  418. {
  419. break;
  420. }
  421. }
  422. // 深入下层节点
  423. pTrie = pTrie->branch[*p - trie_low_offset];
  424. // 下层节点入栈
  425. p_trie_stack[++ p_trie_index] = pTrie;
  426. // 词频统计器
  427. if(pTrie->end == true)
  428. {
  429. // 如果英文匹配模式
  430. if(useEnglishMode)
  431. {
  432. if(! ISLETTER(*(p+1)))
  433. {
  434. // 标记为已匹配
  435. matchAlready = true;
  436. // 计算匹配的长度
  437. matchLen = p_trie_index;
  438. pTrie->value[0] ++;
  439. break;
  440. }
  441. }
  442. else
  443. {
  444. pTrie->value[0] ++;
  445. }
  446. }
  447. // 指针移位
  448. p ++;
  449. }
  450. // 扫尾处理
  451. while((p_trie_index > 0) && (! useEnglishMode))
  452. {
  453. // 正常匹配模式
  454. if((p_trie_stack[p_trie_index])->end == true)
  455. {
  456. // 词条统计消重
  457. if(
  458.     // 并且已经匹配过
  459.     (matchAlready)
  460.     // 并且统计数目大于0
  461.     && ((p_trie_stack[p_trie_index]->value)[0] > 0)
  462. )
  463. {
  464. // 之前匹配的子串去重
  465. (p_trie_stack[p_trie_index]->value)[0] --;
  466. }
  467. // 计算匹配到的词组长度
  468. if(! matchAlready)
  469. {
  470. // 标记为已匹配
  471. matchAlready = true;
  472. // 计算匹配到的词组长度
  473. matchLen = p_trie_index;
  474. // 是否启用子串统计
  475. if(! useSubstringMatch)
  476. {
  477. break;
  478. }
  479. }
  480. }
  481. p_trie_index --;
  482. }
  483. // 根据匹配长度去结算下一数据点位
  484. if(matchAlready)
  485. {
  486. // 匹配词目计数器
  487. mathedCount ++;
  488. // 数据指针推进
  489. searchDataPtr += matchLen;
  490. }
  491. else
  492. {
  493. if(! useEnglishMode)
  494. {
  495. // 数据指针粒度推进
  496. searchDataPtr += ((*p) < 0x80) ?minGranularity :maxGranularity;
  497. }
  498. else
  499. {
  500. // 当为英文匹配模式时,先略过匹配失败的连续字母
  501. while((*searchDataPtr != BYTE_EOF) && (ISLETTER(*searchDataPtr)))
  502. {
  503. searchDataPtr ++;
  504. }
  505. }
  506. }
  507. //  是否进入拼接匹配模式
  508. if(isJoinMatch)
  509. {
  510. // 计算剩余数据长度
  511. if(*searchDataPtr != BYTE_EOF)
  512. {
  513. restDataLen = originalDataLen - (searchDataPtr - originalDataPtr);
  514. }
  515. else
  516. {
  517. restDataLen = 0;
  518. }
  519. // 如果余下的数据过短
  520. if(restDataLen + 1 < MAX_JOIN_SIZE)
  521. {
  522. // 直接跳出
  523. break;
  524. }
  525. }
  526. }
  527. // 装载返回值结构体
  528. pRetTrieStatic->thisMatchedCount = (int)mathedCount;
  529. pRetTrieStatic->restBytesNumber = (int)restDataLen;
  530. pRetTrieStatic->restMatchPtr = (searchDataPtr == originalDataPtr) ?NULL :(byte*)searchDataPtr;
  531. return 0;
  532. }
  533. // 打印Trie统计结果
  534. static byte branch_stack[TRIE_DEEP_SIZE + 1] = {};
  535. static int branch_stack_index = -1;
  536. // Trie打印
  537. int TriePrint(PTrieNode rootPTrieNode, const int* inArray, int totalMatchedNum)
  538. {
  539. // 入栈
  540. branch_stack_index ++;
  541. // 辅助结构体指针
  542. PTrieNode pTrie = rootPTrieNode;
  543. int i;
  544. for(i = 0; i < trie_branch_size; i ++)
  545. {
  546. if(pTrie->branch[i] != NULL)
  547. {
  548. branch_stack[branch_stack_index] = (char)(i + (int)trie_low_offset);
  549. if((pTrie->branch[i])->end == true)
  550. {
  551. if((pTrie->branch[i])->value[0] > 0)
  552. {
  553. // 置结词条结束符
  554. branch_stack[branch_stack_index + 1] = 0x00;
  555. // 如果是非排序打印
  556. if(inArray == NULL)
  557. {
  558. // 打印统计列表
  559. fprintf(stdout, "%8d    %7.4f    %s\n", (pTrie->branch[i])->value[0], (((pTrie->branch[i])->value[0] * 1.0 / totalMatchedNum) * 100.0), (char*)branch_stack);
  560. // 列表显示计数器
  561. if(
  562.     (show_list_size > 0)
  563.     // 超过设定范围,直接退出
  564.     && ((++ already_show_list) >= show_list_size)
  565. )
  566. {
  567. exit(0);
  568. }
  569. }
  570. // 如果是排序打印
  571. else
  572. {
  573. // 分配展示字串内存
  574. byte* pShowStr = (byte*)malloc((branch_stack_index + 2) * sizeof(byte));
  575. if(pShowStr == NULL)
  576. {
  577. // 无法分配内存
  578. fprintf(stderr, "Can't have enough memory\n");
  579. exit(1);
  580. }
  581. // 复制展示字串
  582. memcpy((void*)pShowStr, (const void*)branch_stack, (size_t)(branch_stack_index + 2));
  583. // 将展示字串地址存入staticArray展示数组
  584. *(p_static_array ++) = (int)((pTrie->branch[i])->value[0]);
  585. *(p_static_array ++) = (int)pShowStr;
  586. // 防御数组越界
  587. if(((int)(p_static_array - inArray))/2 + 8 >= SHOW_ARRAY_SIZE)
  588. {
  589. // 温数组越界,直接退出
  590. fprintf(stderr, "Array out of bounds\n");
  591. exit(1);
  592. }
  593. }
  594. }
  595. }
  596. // 递归打印
  597. TriePrint(pTrie->branch[i], inArray, totalMatchedNum);
  598. }
  599. }
  600. // 出栈
  601. branch_stack_index --;
  602. return 0;
  603. }
  604. // 字典注释键值表
  605. static const byte* dictionary_annotation_key[][2] =
  606. {
  607. {(byte*)((int*)&show_list_size),       (byte*)"MAX SHOW:"},
  608. {(byte*)((int*)&trie_low_offset),      (byte*)"BYTE LOW:"},
  609. {(byte*)((int*)&trie_high_offset),     (byte*)"BYTE HIGH:"},
  610. {(byte*)((int*)&trie_min_insert),      (byte*)"INSERT MIN:"},
  611. {(byte*)((int*)&trie_max_insert),      (byte*)"INSERT MAX:"},
  612. {(byte*)((int*)&trie_min_granularity), (byte*)"STEP FORWARD MIN:"},
  613. {(byte*)((int*)&trie_max_granularity), (byte*)"STEP FORWARD MAX:"},
  614. {(byte*)((int*)&use_english_mode),     (byte*)"USE ENGLISH MODE:"},
  615. {(byte*)((int*)&use_substring_match),  (byte*)"USE SUBMATCH MODE:"},
  616. {NULL,                                 (byte*)"|||/"},
  617. {NULL,                                 (byte*)NULL}
  618. };
  619. // 获取字典启动参数函数
  620. bool AlreadyGetStartupParameters(byte* pLineHead, byte* pLineEnd)
  621. {
  622. // 空行返回假
  623. if(pLineHead == NULL || pLineEnd == NULL || pLineHead == pLineEnd)
  624. {
  625. return false;
  626. }
  627. // 临时变量(先存下结尾的字节)
  628. byte tmp = *pLineEnd;
  629. // 置字符串结束符
  630. *pLineEnd = 0x00;
  631. // 三级指针
  632. byte*** ptr = (byte***)dictionary_annotation_key;
  633. // 计算启动参数数组长度
  634. while((*(ptr + 1)) != NULL)
  635. {
  636. // 利用指针实现memcasecmp功能
  637. byte *lp = (byte*)pLineHead, *rp = (byte*)(*(ptr + 1));
  638. while((*lp != 0x00) && (*rp != 0x00))
  639. {
  640. if(
  641. (ISUPPERLETTER(*lp) ?(*lp + 0x20) :*lp) != (ISUPPERLETTER(*rp) ?(*rp + 0x20) :*rp)
  642. )
  643. {
  644. break;
  645. }
  646. lp ++, rp ++;
  647. }
  648. // 如果右指针滑动到结尾,说明匹配成功
  649. if(*rp == 0x00)
  650. {
  651. // 判断是否为字典注释结束符串“|||/”
  652. if((*(ptr + 0)) == NULL)
  653. {
  654. // 还原原始数据
  655. *pLineEnd = tmp;
  656. // 获取参数已经结束
  657. return true;
  658. }
  659. // 提取启动参数
  660. int thisParameters = atoi((char*)((byte*)pLineHead + ((byte*)rp - (byte*)(*(ptr + 1)))));
  661. // 赋值给对应键名变量
  662. *((int*)(*(ptr + 0))) = (int)thisParameters;
  663. // 匹配了就跳出循环
  664. break;
  665. }
  666. // 三级指针推进
  667. ptr += sizeof(*dictionary_annotation_key) / sizeof(**dictionary_annotation_key);
  668. }
  669. // 还原原始数据
  670. *pLineEnd = tmp;
  671. // 还未获取到字典注释结束符串“|||/”
  672. return false;
  673. }
  674. // 填充字典树
  675. int TrieFillDictionary(PTrieNode rootPTrieNode, char* inFile)
  676. {
  677. //初始化一些全局参数,offset取值0 ~ 255
  678. trie_low_offset = 0x00;
  679. trie_high_offset = 0xFF;
  680. trie_branch_size = trie_high_offset - trie_low_offset + 1;
  681. // 插入长度限制阈
  682. trie_min_insert = 1;
  683. trie_max_insert = TRIE_DEEP_SIZE - 1;
  684. // 设置统计粒度
  685. trie_min_granularity = 1;
  686. trie_max_granularity = 1;
  687. // 是否启用英文匹配模式
  688. use_english_mode = false;
  689. use_substring_match = false;
  690. // 读取字典文件
  691. FILE* fp = fopen(inFile, "rb");
  692. if(fp == NULL)
  693. {
  694. fprintf(stderr, "Can't read the dictionary \"%s\"\n", inFile);
  695. exit(1);
  696. }
  697. // 文件流回首(非常必要)
  698. fseek(fp, 0, SEEK_SET);
  699. // 文件流置末尾
  700. fseek(fp, 0, SEEK_END);
  701. // 测量db字典文件尺寸
  702. int inFileLen = ftell(fp);
  703. // 文件流回首
  704. fseek(fp, 0, SEEK_SET);
  705. // 开辟行存容器
  706. const byte* inFileContainer = (byte*)malloc((inFileLen + 3) * sizeof(byte));
  707. if(inFileContainer == NULL)
  708. {
  709. // 无法分配内存
  710. fprintf(stderr, "Can't have enough memory\n");
  711. exit(1);
  712. }
  713. // 读入内存
  714. fread((void*)inFileContainer, (size_t)inFileLen, sizeof(byte), fp);
  715. // 关闭文件流
  716. fclose(fp);
  717. // 设置数据行指针
  718. byte* pLine = (byte*)inFileContainer;
  719. // 行末置结束符(防止行末无换行)
  720. pLine[inFileLen + 0] = 0x0D;
  721. pLine[inFileLen + 1] = 0x0A;
  722. pLine[inFileLen + 2] = BYTE_EOF;
  723. // 辅助指针
  724. byte* p = pLine;
  725. // 当前小行的长度
  726. int lineLen = 0;
  727. // 是否已经获取启动参数
  728. bool alreadyGetParameters = false;
  729. // 插入的词组数目
  730. int insertWordsCount = 0;
  731. // 获取字典启动参数的步探深度
  732. int getStartupParametersDeep = 0;
  733. // 开启主循环
  734. while(*p != BYTE_EOF)
  735. {
  736. // 过滤换行符
  737. while((*p != BYTE_EOF) && (*p != 0x0D) && (*p != 0x0A))
  738. {
  739. // 字节筛选器
  740. if(
  741.     // 如果已经获取到启动参数
  742.     (alreadyGetParameters == true)
  743.     &&
  744.     (!(
  745.             // 字节筛选器低位
  746.             (*p >= trie_low_offset)
  747.             // 字节筛选器高位
  748.             && (*p <= trie_high_offset)
  749. ))
  750. )
  751. {
  752. while((*p != BYTE_EOF) && (*p != 0x0D) && (*p != 0x0A))
  753. {
  754. p ++;
  755. }
  756. while((*p != BYTE_EOF) && ((*p == 0x0D) || (*p == 0x0A)))
  757. {
  758. p ++;
  759. }
  760. pLine = p;
  761. continue;
  762. }
  763. p ++;
  764. }
  765. // 计算行长
  766. lineLen = p - pLine;
  767. // 当行长太短或太长,则抛弃
  768. if(
  769.     // 如果已经获取到启动参数
  770.     (alreadyGetParameters == true)
  771.     // 插入词组长度限制
  772.     && (trie_min_insert <= lineLen)
  773.     && (lineLen <= trie_max_insert)
  774.     // 系统最大长度限制
  775.     && ((lineLen + 1) < TRIE_DEEP_SIZE)
  776. )
  777. {
  778. // 将该词行插入字典树
  779. TrieInsert(rootPTrieNode, (byte*)pLine, lineLen);
  780. insertWordsCount ++;
  781. }
  782. // 获取启动参数子程
  783. if(alreadyGetParameters == false)
  784. {
  785. if((++ getStartupParametersDeep) > 512)
  786. {
  787. // 启动参数隐藏太深,无法获取
  788. fprintf(stderr, "Can't get startup parameters\n");
  789. exit(1);
  790. }
  791. // 当检测到注释结束符“|||/”时
  792. if(AlreadyGetStartupParameters(pLine, p) == true)
  793. {
  794. // 检验已获取的参数的合法性
  795. if(
  796.     (! ( (0 <= trie_low_offset) && (trie_low_offset <= 255) ) )
  797.     || (! ( (0 <= trie_high_offset) && (trie_high_offset <= 255) ) )
  798.     || (trie_low_offset > trie_high_offset)
  799.     || (trie_min_insert > trie_max_insert)
  800.     || (trie_max_insert > TRIE_DEEP_SIZE)
  801.     || (trie_min_granularity <= 0)
  802.     || (trie_max_granularity <= 0)
  803. )
  804. {
  805. // 启动参数错误,直接退出
  806. fprintf(stderr, "Wrong startup trie database parameters\n");
  807. exit(1);
  808. }
  809. // 计算Trie节点分支数目(这是一个全局变量)
  810. trie_branch_size = (trie_high_offset - trie_low_offset) + 1;
  811. // 关闭获取参数开关,开始执行字典词条插入
  812. alreadyGetParameters = true;
  813. }
  814. }
  815. // 过滤换行符
  816. while((*p != BYTE_EOF) && ((*p == 0x0D) || (*p == 0x0A)))
  817. {
  818. p ++;
  819. }
  820. // 指针行进
  821. pLine = p;
  822. }
  823. // 释放行存容器
  824. free((byte*)inFileContainer);
  825. // 检测是否已插入词条
  826. if(insertWordsCount == 0)
  827. {
  828. // 读取错误,直接退出
  829. fprintf(stderr, "Do not insert any words\n");
  830. exit(1);
  831. }
  832. return 0;
  833. }
  834. // 统计字典树
  835. int TrieStaticDictionary(PTrieNode rootPTrieNode, FILE* fp)
  836. {
  837. if(fp == NULL)
  838. {
  839. // 读取错误,直接退出
  840. fprintf(stderr, "Read stdin error\n");
  841. exit(1);
  842. }
  843. // 指针流位重置(非常必要)
  844. fseek(fp, 0, SEEK_SET);
  845. // 初始化匹配返回结构体
  846. RetTrieStatic retTrieStatic = {}, *pRetTrieStatic = &retTrieStatic;
  847. // 余行拼接器:|余行区域|读行区域|末端|
  848. byte line[MAX_JOIN_SIZE + LINE_BUFF_SIZE + 3];
  849. // 调用TrieStatic函数时,line的偏移量
  850. int offset = 0;
  851. // 总匹配词目
  852. int totalMatched = 0;
  853. // 是否开启拼接匹配
  854. bool isJoinMatchMode = false;
  855. // 循环读取STDIN输入流,统计词频
  856. while(! feof(fp))
  857. {
  858. // 每次实际读取的字节数
  859. size_t readLen = fread((void*)(line + MAX_JOIN_SIZE), sizeof(byte), LINE_BUFF_SIZE, fp);
  860. // 置byte结束符
  861. *(line + MAX_JOIN_SIZE + readLen) = BYTE_EOF;
  862. // 最后一次读取可以关闭拼接模式,因为readLen长度过小
  863. if(readLen < LINE_BUFF_SIZE)
  864. {
  865. isJoinMatchMode = false;
  866. }
  867. // 在Trie中匹配数据块
  868. TrieStatic(rootPTrieNode, (byte*)(line + MAX_JOIN_SIZE - offset), (size_t)(readLen + offset), use_substring_match, use_english_mode, isJoinMatchMode, pRetTrieStatic, trie_min_granularity, trie_max_granularity);
  869. // 下次调用TrieStatic函数line的偏移值
  870. offset = pRetTrieStatic->restBytesNumber;
  871. // 是否开启拼接匹配
  872. if(pRetTrieStatic->restMatchPtr != NULL)
  873. {
  874. // 拼接上次余下的数据
  875. memcpy((void*)((line + MAX_JOIN_SIZE) - offset), (const void*)pRetTrieStatic->restMatchPtr, (size_t)pRetTrieStatic->restBytesNumber);
  876. // 开启拼接匹配开关
  877. isJoinMatchMode = true;
  878. }
  879. else
  880. {
  881. // 关闭拼接匹配开关
  882. isJoinMatchMode = false;
  883. }
  884. // 总匹配词数计数器
  885. totalMatched += pRetTrieStatic->thisMatchedCount;
  886. }
  887. // 返回匹配的词次
  888. return totalMatched;
  889. }
  890. // 打印统计表头
  891. int PrintStaticHead()
  892. {
  893. // 创建时间结构体
  894. time_t startTime;
  895. struct tm* timeinfo;
  896. // 打印统计表头
  897. time(&startTime);
  898. timeinfo=localtime(&startTime);
  899. fprintf
  900. (
  901.     stdout
  902.     ,
  903.     "%s"
  904.     "------------------------------------------\n"
  905.     "   Times    Percent    Words\n"
  906.     "------------------------------------------\n"
  907.     ,
  908.     asctime(timeinfo)
  909. );
  910. return 0;
  911. }
  912. // MAIN主函数入口
  913. int main(int argc, char** argv)
  914. {
  915. // 参数数目不对
  916. if(argc != 2)
  917. {
  918. // 第一次开关筛选
  919. fputs(HELP_INFORMATION, stderr);
  920. exit(1);
  921. }
  922. // 检测是否为-m开关
  923. if(strcasecmp(argv[1], "m") == 0)
  924. {
  925. // 打印dicfile头
  926. fputs(DICFILE_HEAD, stdout);
  927. exit(0);
  928. }
  929. // 是否符合规则
  930. char* ptr = strchr(argv[1], ':');
  931. if(ptr == NULL)
  932. {
  933. // 第二次开关筛选
  934. fputs(HELP_INFORMATION, stderr);
  935. exit(1);
  936. }
  937. // 设结束符,同时后移指针
  938. *(ptr ++) = '\0';
  939. // 排序枚举类
  940. SortMode sortMode = SORT_NO;
  941. // 解析开关
  942. if(strcasecmp(argv[1], "+u") == 0)
  943. {
  944. sortMode = SORT_ASC;
  945. }
  946. else if(strcasecmp(argv[1], "-u") == 0)
  947. {
  948. sortMode = SORT_DESC;
  949. }
  950. else if(strcasecmp(argv[1], "u") == 0)
  951. {
  952. sortMode = SORT_NO;
  953. }
  954. else
  955. {
  956. // 第三次开关筛选
  957. fputs(HELP_INFORMATION, stderr);
  958. exit(1);
  959. }
  960. // 创建Trie树根
  961. PTrieNode rootPTrieNode = PTrieNodeCreate((int)(0xFF - 0x00 + 1));
  962. // 获取启动参数,并填充Trie树
  963. TrieFillDictionary(rootPTrieNode, ptr);
  964. // 统计词条
  965. int totalMatchedNum = TrieStaticDictionary(rootPTrieNode, stdin);
  966. //  如果不排序,则直接输出
  967. if(sortMode == SORT_NO)
  968. {
  969. // 打印统计表头
  970. PrintStaticHead();
  971. // 将词频统计印到staticArray数组中
  972. TriePrint(rootPTrieNode, NULL, totalMatchedNum);
  973. // 释放Trie树
  974. TrieFree(rootPTrieNode);
  975. return 0;
  976. }
  977. else
  978. {
  979. // 分配展示数组内存 (占用不超过8M)
  980. const int* staticArray = (int*)malloc(SHOW_ARRAY_SIZE * 2 * sizeof(int));
  981. // 将全局指针置为展示数组首地址
  982. p_static_array = (int*)staticArray;
  983. // 将词频统计印到staticArray数组中
  984. TriePrint(rootPTrieNode, staticArray, totalMatchedNum);
  985. // 释放Trie树
  986. TrieFree(rootPTrieNode);
  987. // 计算统计到的不同词条数目
  988. int staticKeyCount = (p_static_array - staticArray) / 2;
  989. if(staticKeyCount == 0)
  990. {
  991. // 没有匹配到任何关键词目,直接退出
  992. fprintf(stderr, "Do not match any keywords\n");
  993. exit(1);
  994. }
  995. // 根据抽屉原理
  996. if(totalMatchedNum == staticKeyCount)
  997. {
  998. // 如果没有重复,则不需要排序
  999. }
  1000. else
  1001. {
  1002. // 对展示数组进行混合快排
  1003. if(QsortStaticArray((int*)staticArray, sortMode, 0, (staticKeyCount - 1)) == false)
  1004. {
  1005. // 如果排序失败,直接终止
  1006. fprintf(stderr, "Qsort the result failed\n");
  1007. exit(1);
  1008. }
  1009. }
  1010. // 打印统计表头
  1011. PrintStaticHead();
  1012. // 创建辅助指针,指向展示数组首地址
  1013. int* pStaticArray = (int*)staticArray;
  1014. // 打印排序后的统计表
  1015. while(pStaticArray < p_static_array)
  1016. {
  1017. // 转变数据类型
  1018. int staticStrTimes = (int)(*(pStaticArray ++));
  1019. char* staticStr = (char*)(*(pStaticArray ++));
  1020. // 打印统计列表
  1021. fprintf(stdout, "%8d    %7.4f    %s\n", staticStrTimes, ((staticStrTimes * 1.0 / totalMatchedNum) * 100.0), staticStr);
  1022. // 列表显示计数器
  1023. if(
  1024.     (show_list_size > 0)
  1025.     // 超过设定范围,直接退出
  1026.     && ((++ already_show_list) >= show_list_size)
  1027. )
  1028. {
  1029. exit(1);
  1030. }
  1031. // 释放展示字串空间
  1032. if(staticStr != NULL)
  1033. {
  1034. free(staticStr);
  1035. }
  1036. }
  1037. // 释放展示数组
  1038. free((int*)staticArray);
  1039. }
  1040. return 0;
  1041. }
复制代码
.
.
最后再附上一个自己写的成语接龙机器人,名字叫小娜(可在安卓上用C4直接编译,为节约空间,成语表 需要自己补全方可使用。)
  1. /*
  2. IDSO.EXE, IDIOM SOLITAIRE TOOL, COPYRIGHT(C)2017~2019 BY HAPPY, VERSION 1.0
  3. **************************************************************************
  4. gcc ./idso.c -o idso
  5. **************************************************************************
  6. */
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9. #include <string.h>
  10. #include <stdbool.h>
  11. #include <time.h>
  12. // 引入头文件
  13. //#include "idso.h"
  14. // 跨平台宏函数
  15. #if defined(WIN32) || defined(_WIN32) || defined(__MINGW32__) || defined(_MSC_VER)
  16. #include <windows.h>
  17. #define IDSO_SLEEP(x) Sleep(x)
  18. #else
  19. #include <unistd.h>
  20. #define IDSO_SLEEP(x) usleep(x*1000)
  21. #endif
  22. // 定义成语接龙舒适度 (满分100)
  23. #define IDSO_SHELL_DIFFICULTY 16
  24. // 标准行长
  25. #define LINE_BUFF_SIZE   1024
  26. // 用户输入字长
  27. #define INPUT_BUFF_SIZE  36
  28. // 定义hash桶深度
  29. #define BUCKET_DEEP_SIZE 4
  30. // 声明成语接龙数组 (在idso.h文件中定义)
  31. static char* idso_data[];
  32. // 定义成语接龙数组
  33. static char* idso_data[] =
  34. {
  35. NULL,
  36. "一丁不识",
  37. "一不扭众",
  38. "一世之雄",
  39. "一世龙门",
  40. "一丘一壑",
  41. "一丘之貉",
  42. "一丝一毫",
  43. "一丝不挂",
  44. "一丝不紊",
  45. "一丝不苟",
  46. "一丝两气",
  47. "一丝半粟",
  48. "一个半个",
  49. "一串骊珠",
  50. "一举一动",
  51. "一举万里",
  52. "一举三反",
  53. "一举两全",
  54. "一举两得",
  55. "一举千里",
  56. "一举成名",
  57. "一之为甚",
  58. "一之已甚",
  59. "一之谓甚",
  60. "一乱涂地",
  61. "一了百了",
  62. "一了百当",
  63. "一事不知",
  64. "一事无成",
  65. "一五一十",
  66. "一些半些",
  67. "一人之交",
  68. };
  69. // 计算接龙数组长度
  70. static const int idso_data_size = sizeof(idso_data) / sizeof(idso_data[0]);
  71. // 定义BDKR哈希模式 枚举类型
  72. typedef enum
  73. {
  74. FIRST_UC = 1, // 首字hash
  75. LAST_UC = -1, // 末字hash
  76. WHOLE_UC = 0  // 全字hash
  77. } BdkrMode;
  78. // 定义IdsoShellCore函数返回值枚举类型
  79. typedef enum
  80. {
  81. SHELL_USER_EXIT = 0,    // 退出SHELL
  82. SHELL_USER_SUCCEED = 1, // 用户获胜
  83. SHELL_USER_FAILED = 2,  // 用户战败
  84. SHELL_USER_RAND = 3     // 随机成语
  85. } RetIdso;
  86. // 获取UTF8汉字字节长度
  87. int GetUcLen(unsigned char inUc)
  88. {
  89. if((inUc & 0x80) == 0x00)
  90. {
  91. return 1;
  92. }
  93. int ucLen = 0;
  94. while((inUc & 0x80) == 0x80)
  95. {
  96. ucLen ++;
  97. inUc <<= 1;
  98. }
  99. return ucLen;
  100. }
  101. // 快排辅助宏
  102. #define UQSORT_STACK_SIZE 1024
  103. #define UCS2UINT(x) (unsigned int)(((unsigned char)(x)[0]<<24)|((unsigned char)(x)[1]<<16)|((unsigned char)(x)[2]<<8)|((unsigned char)(x)[3]))
  104. #define SWAP(a,b) do{char* __tmpNumber=(a); (a)=(b), (b)=__tmpNumber;}while(0)
  105. // 混合型快排算法
  106. int UcsQsort(char* ucStr[], int left, int right)
  107. {
  108. if(
  109.     ucStr == NULL
  110.     || left < 0
  111.     || right < 0
  112.     || left >= right
  113. )
  114. {
  115. return 1;
  116. }
  117. // 定义数组堆栈,用来记录
  118. int pStack[UQSORT_STACK_SIZE][2], pStackIndex = 0;
  119. // 快排分区首次出栈
  120. pStack[pStackIndex   ][0] = left;
  121. pStack[pStackIndex ++][1] = right;
  122. int i, j;
  123. while(pStackIndex > 0)
  124. {
  125. // 快排分区出栈
  126. i = pStack[-- pStackIndex][0];
  127. j = pStack[   pStackIndex][1];
  128. if(i < j)
  129. {
  130. int ls = i, rs = j;
  131. char* baseNum = NULL;
  132. // 对于小数组,直接采用选择排序
  133. if(j-i+1 < 8)
  134. {
  135. int p, max;
  136. while (ls < rs)
  137. {
  138. max = ls;
  139. for (p = ls+1; p <= rs; p ++)
  140. {
  141. if (UCS2UINT(ucStr[p]) > UCS2UINT(ucStr[max]))
  142. {
  143. max = p;
  144. }
  145. }
  146. SWAP(ucStr[max], ucStr[rs]);
  147. rs--;
  148. }
  149. continue;
  150. }
  151. // 计算中间项数
  152. int mid = (j-i)/2 + i + 1;
  153. // 整理局部数组,以使中位数居中
  154. if(UCS2UINT(ucStr[i]) > UCS2UINT(ucStr[mid]))
  155. {
  156. SWAP(ucStr[i], ucStr[mid]);
  157. }
  158. if(UCS2UINT(ucStr[i]) > UCS2UINT(ucStr[j]))
  159. {
  160. SWAP(ucStr[i], ucStr[j]);
  161. }
  162. if(UCS2UINT(ucStr[mid]) > UCS2UINT(ucStr[j]))
  163. {
  164. SWAP(ucStr[mid], ucStr[j]);
  165. }
  166. SWAP(ucStr[mid], ucStr[i]);
  167. // 快排交换核心
  168. ls = i, rs = j, baseNum = ucStr[ls];
  169. while(ls<rs)
  170. {
  171. while(ls < rs && UCS2UINT(ucStr[rs]) >= UCS2UINT(baseNum))
  172. {
  173. rs--;
  174. }
  175. ucStr[ls] = ucStr[rs];
  176. while(ls < rs && UCS2UINT(ucStr[ls]) <= UCS2UINT(baseNum))
  177. {
  178. ls++;
  179. }
  180. ucStr[rs] = ucStr[ls];
  181. }
  182. ucStr[ls] = baseNum;
  183. // 快排分区数组堆栈实现
  184. int k = ls;
  185. if(i < k)
  186. {
  187. // 快排分区入栈
  188. pStack[pStackIndex   ][0] = i;
  189. pStack[pStackIndex ++][1] = k-1;
  190. }
  191. if(k < j)
  192. {
  193. // 快排分区入栈
  194. pStack[pStackIndex   ][0] = k+1;
  195. pStack[pStackIndex ++][1] = j;
  196. }
  197. }
  198. }
  199. return 0;
  200. }
  201. // BKDR哈希算法(当传递参数inStrLen为1时表示获取首字hash,为-1时表示获取尾字hash,其他数表示获取全字hash)
  202. int BKDRHash(char *inStr, BdkrMode inMode, int bkdrBase)
  203. {
  204. // 空串返回直接零
  205. if(inStr == NULL)
  206. {
  207. return 0;
  208. }
  209. int inStrLen = -1;
  210. if(inMode == FIRST_UC)
  211. {
  212. inStrLen = GetUcLen((unsigned char)*inStr);
  213. }
  214. else if(inMode == LAST_UC)
  215. {
  216. inStrLen = 1;
  217. inStr += (int)(strlen(inStr) - 1);
  218. while(((*inStr) & 0xC0) == 0x80)
  219. {
  220. inStrLen ++;
  221. inStr --;
  222. }
  223. }
  224. unsigned int seed = 131;
  225. unsigned int hash = 0;
  226. char* str = inStr;
  227. while ((str - inStr < inStrLen) || ((inMode == WHOLE_UC) && (*str)))
  228. {
  229. hash = hash * seed + (*(str ++));
  230. }
  231. return (int)(hash % bkdrBase);
  232. }
  233. // 获取成语首字索引hash表
  234. void* GetFirstUCharacterHashTable(char** idsoData, int idsoDataSize, int hashBase)
  235. {
  236. // 当hash表基数小于成语数组长度时,返回空指针
  237. if(hashBase < idsoDataSize)
  238. {
  239. // return NULL;
  240. }
  241. // 动态分配首字索引hash表内存
  242. int (*firstUcHashTable)[2] = (int(*)[2])calloc(hashBase * 2, sizeof(int));
  243. // 循环遍历每个成语,构建首字索引hash表
  244. int i;
  245. for(i = 1; i < idsoDataSize; i++)
  246. {
  247. // 计算首字hash值
  248. int firstUcHashIndex = BKDRHash((char*)idsoData[i], FIRST_UC, hashBase);
  249. // 构建首字索引hash表
  250. if(firstUcHashTable[firstUcHashIndex][0] == 0)
  251. {
  252. firstUcHashTable[firstUcHashIndex][0] = i;
  253. firstUcHashTable[firstUcHashIndex][1] ++;
  254. continue;
  255. }
  256. // 获取UTF汉字字节长度
  257. int ucLen = GetUcLen((unsigned char)(*(idsoData[i])));
  258. // 比对成语首字是否重复
  259. if(strncmp((char*)idsoData[i], (char*)idsoData[firstUcHashTable[firstUcHashIndex][0]], ucLen) == 0)
  260. {
  261. // 首字成语 组计数器
  262. firstUcHashTable[firstUcHashIndex][1] ++;
  263. }
  264. else
  265. {
  266. // 构建首字索引失败,释放hash表内存
  267. free(firstUcHashTable);
  268. // 返回空指针
  269. return NULL;
  270. }
  271. }
  272. // 返回首字索引hash表
  273. return (void*)firstUcHashTable;
  274. }
  275. // 获取成语全字hash桶
  276. void* GetWholeUCharacterHashTable(char** idsoData, int idsoDataSize, int hashBase)
  277. {
  278. // 当hash表基数小于成语数组长度时,返回空指针
  279. if(hashBase < idsoDataSize)
  280. {
  281. // return NULL;
  282. }
  283. // 计算需要的hash桶数量
  284. int bucketNumber = (hashBase / BUCKET_DEEP_SIZE) * (64 / BUCKET_DEEP_SIZE);
  285. // 动态分配hash桶内存
  286. int (*wholeUcHashTable)[BUCKET_DEEP_SIZE] = (int(*)[BUCKET_DEEP_SIZE])calloc(bucketNumber * BUCKET_DEEP_SIZE, sizeof(int));
  287. // 循环遍历每个成语,构建全字hash桶
  288. int i;
  289. for(i = 1; i< idsoDataSize; i++)
  290. {
  291. // 计算全字hash值
  292. int wholeUcHashIndex = BKDRHash((char*)idsoData[i], WHOLE_UC, bucketNumber);
  293. // 循环桶深度
  294. int j;
  295. for(j = 0; ; j++)
  296. {
  297. // 超过桶深度、则返回空指针
  298. if(j >= BUCKET_DEEP_SIZE)
  299. {
  300. // 构建hash桶失败,释放hash桶内存
  301. free(wholeUcHashTable);
  302. return NULL;
  303. }
  304. // 构建hash桶
  305. if(wholeUcHashTable[wholeUcHashIndex][j] == 0)
  306. {
  307. wholeUcHashTable[wholeUcHashIndex][j] = i;
  308. break;
  309. }
  310. }
  311. }
  312. // 返回首字索引hash表
  313. return (void*)wholeUcHashTable;
  314. }
  315. // 帮助信息
  316. int GetHelpInformation()
  317. {
  318. fprintf
  319. (
  320.     stdout
  321.     ,
  322.     "[欢迎你使用 \"成语接龙\"] --- 输入Q退出\n"
  323.     "[小娜]: 我是萌萌的小娜!\n"
  324. );
  325. return 0;
  326. }
  327. // 成语接龙SHELL
  328. RetIdso IdsoShellCore(int firstUcHashBase, int bucketNumber, int (*firstUcHashTable)[2], int (*wholeUcHashTable)[BUCKET_DEEP_SIZE])
  329. {
  330. // 随机一个待接成语
  331. char* needUcStr = (char*)idso_data[rand()% (idso_data_size-1) + 1];
  332. // 计算待接成语末字hash
  333. int needUcStrLastUcHash = BKDRHash(needUcStr, LAST_UC, firstUcHashBase);
  334. // 如果待接成语不可接,则退出SHELL,休眠随机种子以待下次随机
  335. if((firstUcHashTable[needUcStrLastUcHash][0] == 0) || (firstUcHashTable[needUcStrLastUcHash][1] <= IDSO_SHELL_DIFFICULTY))
  336. {
  337. return SHELL_USER_RAND;
  338. }
  339. // 接受输入字符串的容器
  340. char inPut[INPUT_BUFF_SIZE + 1];
  341. // 接受输入字符串转输入数组的容器
  342. char* sArgv[3];
  343. int sArgc;
  344. // 接龙循环
  345. while(true)
  346. {
  347. // 显示人机交互信息
  348. fprintf
  349. (
  350. stdout
  351. ,
  352. "[小娜]: %s\n"
  353. "[>>>>]: "
  354. ,
  355. needUcStr
  356. );
  357. // 接收用户输入流
  358. fgets(inPut, INPUT_BUFF_SIZE, stdin);
  359. // 找到第一个换行符的位置
  360. char* p =strchr(inPut, '\n');
  361. // 如果输入为空,则显示帮助信息
  362. if(p == inPut)
  363. {
  364. GetHelpInformation();
  365. continue;
  366. }
  367. // 置输入流结束符
  368. if(p != NULL)
  369. {
  370. *p='\0';
  371. }
  372. // 使用按键 Q退出
  373. if(! strcasecmp(inPut, "Q"))
  374. {
  375. fprintf(stdout, "[感谢使用,再见!]");
  376. return SHELL_USER_EXIT;
  377. }
  378. // 切分输入字符流
  379. sArgc = 0;
  380. p = inPut;
  381. while(*p)
  382. {
  383. while(*p == ' '|| *p == '\t')
  384. {
  385. *(p ++) = 0;
  386. }
  387. if(*p)
  388. {
  389. if(++ sArgc > 3)
  390. {
  391. break;
  392. }
  393. sArgv[sArgc - 1] = p;
  394. }
  395. while(*p && (*p != ' ') && (*p != '\t'))
  396. {
  397. p += GetUcLen((unsigned char)*p);
  398. }
  399. }
  400. // 执行成语接龙核心
  401. if(sArgc == 1)
  402. {
  403. bool isCorrect = false;
  404. // 计算用户输入全字hash值
  405. int inPutWholeUcHash = BKDRHash(sArgv[0], WHOLE_UC, bucketNumber);
  406. // 遍历全字hash桶
  407. int j;
  408. for(j=0; (j<BUCKET_DEEP_SIZE) && (wholeUcHashTable[inPutWholeUcHash][j] != 0); j++)
  409. {
  410. char* pUcStr = (char*)idso_data[wholeUcHashTable[inPutWholeUcHash][j]];
  411. // 比对桶中字符串
  412. if(! strcmp(sArgv[0], (char*)pUcStr))
  413. {
  414. // 计算用户输入 首字hash
  415. int inPutFirstUcHash = BKDRHash((char*)pUcStr, FIRST_UC, firstUcHashBase);
  416. // 比对首字hash,判断首字是否可接龙
  417. if(inPutFirstUcHash != needUcStrLastUcHash)
  418. {
  419. // 用户首字没有接上、退出循环
  420. break;
  421. }
  422. // 计算末字hash索引
  423. int inPutLastUcHash = BKDRHash((char*)pUcStr, LAST_UC, firstUcHashBase);
  424. // 依据末字hash 检索以其打头的成语
  425. if(firstUcHashTable[inPutLastUcHash][0] != 0)
  426. {
  427. // 机器随机挑选一个 以其字打头的成语
  428. int randIndex = rand() % firstUcHashTable[inPutLastUcHash][1];
  429. char* rUcStr = (char*)idso_data[firstUcHashTable[inPutLastUcHash][0] + randIndex];
  430. // 计算此随机成语末字hash
  431. int rUcStrLastUcHash = BKDRHash(rUcStr, LAST_UC, firstUcHashBase);
  432. // 判断此随机成语,若末字不可接
  433. if(firstUcHashTable[rUcStrLastUcHash][0] == 0)
  434. {
  435. // 显示绝杀成语
  436. fprintf(stdout, "[绝杀]: %s\n", rUcStr);
  437. fprintf(stdout, "[你输了]\n");
  438. return SHELL_USER_FAILED;
  439. }
  440. // 末字可接,更新待接成语
  441. needUcStr = rUcStr;
  442. // 末字可接,更新待接首字hash
  443. needUcStrLastUcHash = rUcStrLastUcHash;
  444. }
  445. else
  446. {
  447. // 机器无法接龙用户输入的成语,用户获胜
  448. return SHELL_USER_SUCCEED;
  449. }
  450. // 回答正确,则标记为真
  451. isCorrect = true;
  452. break;
  453. }
  454. }
  455. // 用户回答错误
  456. if(! isCorrect)
  457. {
  458. // 计算可接成语数目
  459. int pickUpCount = firstUcHashTable[needUcStrLastUcHash][1];
  460. // 当接龙难度过高时,机器给予用户提示
  461. if(pickUpCount <= IDSO_SHELL_DIFFICULTY)
  462. {
  463. // 机器随机一个答案
  464. char* promptUcStr = (char*)idso_data[firstUcHashTable[needUcStrLastUcHash][0] + rand() % pickUpCount];
  465. fprintf(stdout, "[小娜悄悄提示 \"%s\"]\n", promptUcStr);
  466. }
  467. else
  468. {
  469. fprintf(stdout, "[小娜希望你能认真考虑!]\n");
  470. }
  471. }
  472. }
  473. else
  474. {
  475. // 帮助信息
  476. GetHelpInformation();
  477. }
  478. }
  479. }
  480. // 主函数
  481. int main(int argc, char *argv[])
  482. {
  483. // 使用混合快排,先对成语数组进行前4字节索引排序
  484. UcsQsort((char**)idso_data, 1, idso_data_size-1);
  485. int firstUcHashBase = 25511, wholeUcHashBase = 18311;
  486. void *pFc = NULL, *pHc = NULL;
  487. // 建立首字索引hash表
  488. while((pFc = GetFirstUCharacterHashTable((char**)idso_data, idso_data_size, (++ firstUcHashBase))) == NULL);
  489. int (*firstUcHashTable)[2] = (int(*)[2])pFc;
  490. // 建立全字hash桶
  491. while((pHc = GetWholeUCharacterHashTable((char**)idso_data, idso_data_size, (++ wholeUcHashBase))) == NULL);
  492. int (*wholeUcHashTable)[BUCKET_DEEP_SIZE] = (int(*)[BUCKET_DEEP_SIZE])pHc;
  493. // 计算hash桶基数
  494. int bucketNumber = (wholeUcHashBase / BUCKET_DEEP_SIZE) * (64 / BUCKET_DEEP_SIZE);
  495. // 初始化随机种子
  496. srand((unsigned)time(NULL));
  497. // 打印SHELL题头
  498. GetHelpInformation();
  499. // 调用成语接龙SHELL核心
  500. while(true)
  501. {
  502. // 获取接口SHELL返回值
  503. RetIdso retIdso = IdsoShellCore(firstUcHashBase, bucketNumber, firstUcHashTable, wholeUcHashTable);
  504. // 检测是否退出接龙SHELL
  505. if(retIdso == SHELL_USER_EXIT)
  506. {
  507. // 退出接龙SHELL
  508. break;
  509. }
  510. else if(retIdso == SHELL_USER_SUCCEED)
  511. {
  512. // 用户获胜 fprintf(stdout, "[你赢了]\n");
  513. fprintf
  514. (
  515.     stdout
  516.     ,
  517.     "[欢迎你使用 \"成语接龙\"] --- 输入Q退出\n"
  518.     "[小娜]: 我是萌萌的小娜!\n"
  519. );
  520. }
  521. else if(retIdso == SHELL_USER_FAILED)
  522. {
  523. // 用户战败
  524. fprintf
  525. (
  526.     stdout
  527.     ,
  528.     "[欢迎你使用 \"成语接龙\"] --- 输入Q退出\n"
  529.     "[小娜]: 我是萌萌的小娜!\n"
  530. );
  531. }
  532. else if(retIdso == SHELL_USER_RAND)
  533. {
  534. // 延缓时间,提高rand()成语随机性
  535. IDSO_SLEEP(1);
  536. }
  537. }
  538. // 释放内存
  539. free(firstUcHashTable);
  540. free(wholeUcHashTable);
  541. return 0;
  542. }
复制代码

作者: CrLf    时间: 2017-11-12 03:55

建议楼主打包一个小样本,或者在 m 选项中提供 10 行左右的示例
而且以下诸项究竟有什么作用也语焉不详
BYTE LOW:         0
BYTE HIGH:        255
INSERT MIN:       1
INSERT MAX:       8
STEP FORWARD MIN: 1
STEP FORWARD MAX: 2
对很多工具来说,文档其实和代码一样重要——除非是自己写着玩
作者: CrLf    时间: 2017-11-12 03:57

为什么出来的结果有一大堆的 (null),这部分对使用者来说毫无意义嘛...
作者: happy886rr    时间: 2017-11-12 09:22

本帖最后由 happy886rr 于 2017-11-12 14:34 编辑

回复 3# CrLf
很抱歉大师,我的文档和压缩包都copy /b到图片里了,你没下载图片存a.zip吗?(外链图有效期仅7天,过期不再提供任何下载,现在图片已经失效。不过我已投递副本到你邮箱请注意查收)
那里边有详细的使用说明,和每个参数的含义,并附带多本统计词典。

压缩包里有个readme.txt,里边已经写明如下信息:
  1. 关于.DI格式,是一种全新研发的字典表统计格式
  2. /|||
  3. TRIE - DICTIONARY DATABASE 1.0
  4. ==============================================================
  5. DICTIONARY NAME:  ENGLISH DICTIONARY TABLE     //字典名
  6. MADE DATE:        2017-10-25                   //字典创建时间
  7. CHARSET:          UTF8                         //字典编码
  8. USE ENGLISH MODE: 1                            //是否英文模式
  9. USE SUBMATCH MODE:0                            //是否前缀模式
  10. MAX SHOW:                                      //最大显示数目
  11. ==============================================================
  12. BYTE LOW:         65                           //字符的最小值
  13. BYTE HIGH:        122                          //字符的最大值
  14. INSERT MIN:       1                            //串长的最小值
  15. INSERT MAX:       16                           //串长的最大值
  16. STEP FORWARD MIN: 1                            //粒度的最小值
  17. STEP FORWARD MAX: 1                            //粒度的最大值
  18. ==============================================================
  19. |||/
复制代码

作者: CrLf    时间: 2017-11-12 13:18

回复 4# happy886rr


    感谢分享,这下会用了
作者: 失控的疯子    时间: 2019-1-25 15:49

感谢分享,这下会用了
作者: CrLf    时间: 2019-8-1 00:12

附一个下载地址:
http://www.bathome.net/s/tool/index.html?key=trie




欢迎光临 批处理之家 (http://www.bathome.net/) Powered by Discuz! 7.2