这里用于存放我的思路 要实现的核心功能是大规模词频统计，取前n位多的词语作为特征向量。 这里我考虑大顶堆，不知是否可以。 我需要对这个小项目做出分段

0、总体设计 1、指纹获取阶段 2、article.txt指纹计算阶段 3、sample.txt要求阶段 4、API设计 0、总体设计 本次希望通过这个设计，提升项目管理能力，具体体现在1）要熟悉多种数据结构，如hash、大顶堆；2）要熟悉多源文件编写c语言程序与分模块调试，实现不同功能之间的配合与测试、封装；3）编写优秀的技术文档，培养良好的项目开发习惯。

1、指纹获取阶段 1.1 词频统计 传统的词频统计要想做到排序，需要将文章中所有词句全部审计完毕后才能进行sort，本项目显然不现实，故考虑采用大顶堆结构，拥有o(logn)的查找与近乎相等的效率，比较适合处理大数据。然而，我们需要复习大顶堆的基础知识才能继续。 1.2 特征向量生成与指纹生成 特征向量即为x = (w1,w2,w3...)其中w为词频，很简单，N属于命令行参数其一。生成指纹首先要获取命令行参数其二的M，这个M很关键，指纹矩阵即为x与hash.m相乘生成。随后，指纹的生成基于矩阵的列，我们最终将得到这样的一个映射： f(article) -> fingerprint(1,0,0,1,1,1,1,0...)

看了看例题，发现：指针那里p++、--p不清楚，同时指针数组和数组指针也不清楚

5.22 现在要解决的问题是，如何存储大量的单词，以及其数量。数量好存储，关键是合法的英语单词我们不知道有多少。如果很多的话，内存开销浪费会很大很大

综合作业大数据规模： 网页个数<16,000 总单词数<6,000,000 不同单词数<106,000 单个网页不同单词数<6500 单词长度<80 Hash matrix 10000*128 前N单词：10000 指纹长度：不超过128 Sample 网页数目：暂定10000个

常用的英文单词有20万个左右，假设单词的平均长度是10个字母，平均一个单词占用10个字节的内存空间，那20万英文单词大约占2MB的存储空间，就算放大10倍也就是20MB。对于现在的计算机来说，这个大小完全可以放在内存里面。所以我们可以用散列表来存储整个英文单词词典。

综上，我们要排序前先要搞好内存管理，我决定使用realloc每次分配一百个单词的空间，每个长度为81， 如果不够就接着分配，而且需要一个计量最终共有多少个单词的。 伪代码： init container = malloc(100);(char *[80]) int ans = 0; char word[80] scanf word : to_lower(word); if word not in ABANDONED: container[end_index++] = word;

qsort(container,ans ,sizeof(char *[80]), cmp);

fscnaf(fp, )

然而使用realloc有隐患，我不希望使用它，我只是希望创造一个内存安全的变长数组，最大程度解决内存浪费。 于是乎，当下论证的重点就是如何选择合适的线性数据结构来保存单词并使用qsort。 那么这段内存就不能间断，间断了就无法qsort。选择不间断的内存就意味着无法控制浪费。 我给出的方案包括一个极其复杂的数组 首先alphabet[26][80] 然后长度23以下的单词进行一次qsort，长度23以上的单词进行一次qsort，分别用不同长度的数组空间，并且根据各自的数量设置数组长度（malloc并free），随后各自取得前十，二路归并，进入新数组，长度为其中最长单词的长度。

以上皆为bst，由于注意到单词以字典序已经排好，我们创立char* stw_20_stack

资料： 全局变量、静态局部变量、静态全局变量都在静态存储区分配空间，而局部变量在栈分配空间。

全局变量本身就是静态存储方式，静态全局变量当然也是静态存储方式。这两者在存储方式上没有什么不同。区别在于非静态全局变量的作用域是整个源程序，当一个源程序由多个源文件组成时，非静态的全局变量在各个源文件中都是有效的。而静态全局变量则限制了其作用域，即只在定义该变量的源文件内有效，在同一源程序的其他源文件中不能使用它。由于静态全局变量的作用域局限于一个源文件内，只能为该源文件内的函数公用，因此可以避免在其他源文件中引起错误。

一个由C/C++编译的程序占用的内存分为以下几个部分 :

栈区stack：先进后出(FILO)，编译器自动分配释放，存放函数的局部变量、函数参数、返回值、返回地址等。 堆区heap：需要手动 malloc/new 动态分配 ， free/delete 释放。 静态区static：存储全局变量和静态变量。分为初始化数据区和未初始化数据区。 常量区：存放常量字符串。 代码区：存放函数体的二进制代码。 理论大小对比 栈区大小：2M或1M。 函数内申请的变量、数组，是在栈（stack）中申请的一段连续的空间。

静态区大小：2G. 全局变量，全局数组，静态数组（static）则是开在）。大小为2G。

堆区大小：视内存而定，可以开很大 malloc、new出的空间，则是开在堆（heap）的一段不连续的空间，理论上则是硬盘大小。

!!!关于fgets不能给char *ch[15]读取字符串的原因 fgets()函数的原型是: char *fgets(char *str, int n, FILE *stream); 它的作用是:从stream中读取n-1个字符,并将其存储在str指向的内存中。 但在您的代码中,str参数传入的是inhalte[zaehler],这是一个指针,并不是真正的内存块。 fgets()无法将读取的字符串存储在一个指针本身,它需要一个真实的、可写的内存块。

也就是说先定义一个char word[80]这样的容器，再malloc一块合适长度的 空间并memcpy

现在，我就剩下最后三个突破点，static关键字的使用，free机制的原理和 功能的封装形式。 事实证明，static在单文件里就是个装B的东东。 free可以释放堆空间中的东西

发现一个有趣的事实，fscanf会忽略结尾的\n等空白字符

今天要攻坚了，需要确定最后的数据结构：前N挑选 首先在存储方面，我决定采用一个数组（队列），每个数组元素是 一个指针，指向一个变长数组；遇到新单词队尾入队，遇到旧单词 查询归并。其次在查找方面，我决定采用...

我又有新想法了：既然指针占空间，那我可以化零为整，每隔1000个指针 设置一个高位指针，单词数每多1000，我新分配一个1000员的指针群，这样就有营合成旅的感觉了。然而这样是会削弱查找效率的。课上好像不能写 qsort的威力只有在超大数组内才能展现，然而我现在既不希望将查找和存储分为两个数组，又不想一次性分配超多指针。联想磁盘分区，我考虑分为0，1，2...15,16区，每个区是node (*ptr[1000]),于是乎总共为node (*ptr[1000])[16],十六个分区，自己写bsearch和qsort(建立虚拟连接，利用 我们可以考虑用求余运算，指针指标%1000得到分区排序的离散特性，将十六个分区糅合到一起)。有一个计位址标，word_num，每填入一个词就+1，当word_num%1000==0时，就要新分配一个1000员的指针群，这样就有营合成旅的感觉了，同时不会削弱qsort效率！，现在问题的关键就是 边界条件，我们需要在testbase实验一下。

现在看来这些东东属实是雕虫小技，没有trie树来的实惠。 一课trie树，一列8000指针的数组，trie树排完后指针数组列qsort 选出前N个，确定其权重，权重确定后结合hash就可以得到指纹了，之后就可以熔断trie树和指针数组了。 得到指纹就可以撤离了！！！啊啊啊写不出lei！！！ 树结构可以写成这样 0 1 2 3 4 5 /
0 1 2 3 4 5 0 1 2 3 4 5 / \ \ \ \ \ \ \ \ \ \ \

if(word_not_exist) now_node.next['a'] = (node*)malloc(sizeof(node)); if(word_exist) now_node.index = array[word_num]; word_num++; array_append(word,now_node.index); 面对这样的情形，我们提出指针树。每个节点都是int *node[27],全部设置为 -1,而叶子节点

今天好消息是字典树和排序走通了 坏消息是我发现需求理解错了 我现在需要整个文章数据集合走一遍，获取每个单词，建立一棵大树 并且记录出现次数，走完之后对节点进行排序，选出前N个 在这时候熔毁树 然后再整个数据集走一遍，对于每篇文章，获取属于前N个中的单词（考虑用bsearch）， 并以此生成指纹 最后再在sample里用相似的方法生成指纹，随后计算汉明距离。

这时候我在想，大数据集要走两遍非常不合适，能否动态规划？ 建立大树的同时，在记录count的过程中，能否标定每次count的来源为何处？ 这样就可以直接继承count信息，而不用再走一遍了。

下面进行选型论证：我会采用trie树来应对106000个单词的情况，然后为 每个单词配备一个unify码来确定每个单词在哪个文章里被读取

然而我现在决定稳健一点，先生成整体树交上去

5.29 现在悲剧的事情发生了，统计过程出现问题，我们要一个一个的排查。 首先要确信统计原理没有问题。这个可以保证，因为词频统计那一关是过了的。 然后要确定hash 有没有问题。我考虑打印一下进行对比。 随后既然大树没有问题，我要确认小树的构造过程没有问题。 目前我们汉明距离的计算没有问题，weight的检查立刻开启。 现在1、weight转化FGP是否考虑到weight==0的情况 2、weight转化汉明的hash使用是否正确 3、get_sample_num的过程能否改为fscanf而非fgets，因为要兼容linux