# HotWords
基于改进Jieba分词算法和Hadoop框架的中文新闻热词解析、统计与展示平台
## 自然语言处理算法（改编优化开源结巴分词算法）
### 0、定义Word类
  数据成员包括int类型变量id（词语在汉语词典中的编号）、String类型变量word（词语字符串）、int类型变量weight（词语的词频）、String类型变量property（词语的词性），以及int类型变量i、j（有向无环图DAG中词语对应边的起点和终点标号）。
  除构造方法外，还包括每个数据成员的getter、setter方法。
### 1、定义Dictionary类
  Dictionary类需要一个用来存储大型字典的静态成员变量，要求生成字典和从字典中查询指定字符串的效率高。R向单词查找树（trie树）是理论上时间复杂度最小的数据结构，但是及其占用内存空间；三向单词查找树是对二叉查找树的简单优化，优化倍数大约是log3，但是容易出现生成的树不平衡和可能产生深度递归导致栈溢出的情况；2-3红黑树和AVL树也是备选方案，避免了二叉查找树和三向单词搜索树中的问题，但是数据结构实现较为复杂；HashMap的插入put和查找get方法的时间复杂度在理想情况下均为O(1)，效率极高。经过测试对比，我们选择了HashMap。
  数据成员包括HashMap<String, Word>类型变量dictionary（HashMap存储汉语词典，以String字符串为键，Word对象为值）、HashMap<String, Double>类型变量IDF（HashMap存储TF-IDF预设词典，以String字符串为键，Double对象为值）、int类型变量id（汉语词典中的词语个数）。
  静态方法initialize()负责在系统启动初始化时预加载汉语词典和TF-IDF预设词典。设汉语词典中的词语个数为n，TF-IDF预设词典中的词语个数为m。BufferedReader按行读取txt文件，每一行存储了一个词语以及它的词频和词性或IDF值，可根据这些数据创建一个Word类对象，并将其put到HashMap对象中（dictionary和IDF）。该方法的时间复杂度为O(n+m)。
  静态方法search(String)在HashMap对象dictionary中查询词语，若词典中存在被查询词语，则返回一个Word类对象（需要对象克隆，而不能公共一个Word对象），否则，返回null。时间复杂度为O(1)。
  静态方法getIDF(String)在HashMap对象IDF中查询关键词的IDF值，若IDF词典中存在被查找关键词，则返回对应的IDF值，否则，返回一个比IDF词典中最大IDF值稍大的值（max=13.900677652， min=2.81755097213）。
### 2、实现定制的图数据结构
  考虑到之后根据微博生成的有向无环图DAG将较为稀疏，所以在实现图数据结构时，采用邻接表的方式，不论是时间上还是空间上，都是优于邻接矩阵的。使用邻接表，当访问某个结点的所有邻接点时，只需要检查连接此结点与它相邻结点的实际存在的边，时间复杂度为Θ(|V|+|E|)。
  图ADT中定义的方法有根据结点编号v获取其第一条边Edge对象的first(int)方法；根据Edge对象e获取邻接表中的下一条边Edge对象的next(Edge)方法；根据结点编号i和j判断是否有边的isEdge(int,int)方法；根据Edge对象e判断是否为边的isEdge(Edge)方法；返回Edge对象e的起点编号v1(Edge)方法和终点编号v2(Edge)方法；对给定的结点编号i和j建立由i到j的一条边的方法setEdge(int,int,Word)以及将给定的Edge对象作为图中的一条边的方法setEdge(Edge,Word)，边存储一个Word类对象，可以从该对象中获取到边的起点和终点编号以及词语相关信息；从给定的结点编号i和j返回对应ij边的Word对象的方法getWord(int,int)，和从给定的Edge对象e返回对应边的Word对象的方法getWord(Edge)；设置和获取结点标记数的方法setMark(int,int)和getMark(int)。
### 3、根据输入微博，生成有向无环图DAG
  有向无环图DAG的结点个数为n+1，其中n为输入微博的字符串长度，最后还需要一个尾结点以便操作。DAG中一条边的建立规则是：起点i是一个可能分词的词首位置，终点j是下一个可能分词的词首位置。因此每相邻的两个字符结点之间有一条有向边，最后一个字符到尾结点有一条有向边，保证了DAG从第一个结点到最后一个结点至少存在一条路。
  一条微博共有n个字符，标号0~n-1。外层for循环，i从0遍历到n-2，即从句中第一个字符至倒数第二个字符；单个字符，建立当前字符至下一个字符的一条有向边（0→1、1→2、...、n-2→n-1），单个字符的Word对象中词性标记为“#”，词频标记为0；固定起始位置i，结束位置j，遍历后续子字符串进行组词，内层for循环，j取自i+1至n-1，即字符i的下一个字符至最后一个字符；从i到j截取weibo字符串，在预设字典中查询词组，得到Word类对象word，若截取的子字符串可以构成词组，即word != null时，在DAG中建立一条从i到j+1的有向边（当前词的词首指向下一个词的词首），该边存储word对象；最后一个单个字符：建立最后一个字符至空结点的一条有向边，完成整个有向无环图。
  对于长度为n的微博字符串，生成有向无环图DAG的静态方法generateDAG()的算法复杂度为Θ(n^2)。
### 4、在有向无环图DAG中寻找词频最大路径
  由于DAG的每条边都有对应的权值（词频），因此从DAG的第一个结点到最后一个结点的一条权值最大的路，很可能代表了一种比较优的分词结果。所以下一步需要从生成的DAG中寻找词频最大路径。
  原生结巴分词算法采用了动态规划思想，除此之外，还可以使用回溯法来寻找最大路径，但是这两种方法都涉及递归，可能会带来低效率的问题。因此，我们对原生结巴分词算法做以优化。
  一个句子中的所有字符结点自然构成拓扑序，对于这样的特殊情况，即结点满足拓扑序的有向无环图DAG，存在着一个线性级别复杂度的寻找最大路径的算法。
  getLongestPath()方法首先初始化distance数组，除第一个元素外，其它元素均为Integer.MIN_VALUE，该数组中的元素distance[u]表示从第一个结点0到结点u的最大路径（distance数组元素的值会不断更新）。按顺序对拓扑序列中的每个结点u执行以下算法：对u的每个邻接点，即(u,v)是DAG中的一条有向边，如果distance[u] + weight(u,v) > distance[v]，那么调用dag.setMark(v, u)并使distance[v] = distance[u] + weight。当全部遍历所有结点后，算法结束，distance[n]保存着最大路径的词频总和，而GraphL对象dag的Mark数据成员保存着最大路径对应的各切分位置。
  优化后的算法尽管不对所有图类型具有普适性，但是对于我们的特定问题能产生更好的性能，算法复杂度为O(|V|+|E|)。
### 5、构建并保存语句划分，根据划分位置划分语句至若干个词
  根据上一步中更新的dag对象的Mark数组，从dag对象中提取边对应的Word对象保存至ArrayList<Word>类型对象preWordList（初步预分词结果列表）。
  partition()方法对Mark数组进行了一次遍历，循环次数为count（微博的划分个数），count≈0.3n，该方法的时间复杂度为O(n)。
### 6、将预分词结果进行进一步的短词语合并
  考虑字符串“西安交通大学”，由于“西安”、“交通”、“大学”三个词的词频总和显然远大于“西安交通大学”的词频，所以对于这个特定的输入，分词结果将是“�
基于优化中文结巴分词算法和Hadoop的网络新闻热词解析、存储与统计的Web展示系统的设计与实现+部署文档+全部资料 高分项目.zip （19个子文件） 
HotWords-main src dictionary 
Word.java 1KB Dictionary.java 2KB nlp DAG.java 6KB NLP.java 5KB test Test.java 879B graph GraphL.java 2KB Graph.java 1KB List.java 438B Link.java 447B Edge.java 86B LList.java 2KB EdgeL.java 379B GraphList.java 179B trie TST.java 1KB LICENSE 1KB .gitignore 314B README.md 10KB 部署说明文档.md 11KB
171265889347208773632.zip 416B资源评论
