# SentenTree

**Repository Path**: qingxi8/senten-tree

## Basic Information

- **Project Name**: SentenTree
- **Description**: 《Visualizing Social Media Content with SentenTree 》论文核心算法部分的Java实现
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-10-22
- **Last Updated**: 2021-10-22

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# SentenTree
基础概念：

几个句子构成一个数据集

序列a来源的数据集D~a~，称为a的**支持数据集**

序列a的**support**是指a在句子中出现的次数（a在句子中出现的次数是说序列a中的每个词在句子中出现次数中的最小值）

如果这个次数（support）超过了**最小支持阈值**，则称序列a为**频繁序列模式**

【模式是一个序列】



我们可以把句子或其一部分看成是一个单词序列

序列a的来源数据集就是其支持数据集D

support：支持数据集中含有序列a的数目，就是a的support

如果这个数目（support）超过了**最小支持阈值**，则称序列a为**频繁序列模式**









算法一：*graphCreation()*



> 输入：原始句子集
>
> 输出：图
>
> 标记的句子集 = *init*（原始句子集）
>
> 创建一个没有单词的空模式s
>
> 令s的支持数据集D~s~ = 标记的句子集
>
> 叶子顺序模式列表 = *patternGeneration*(s,s, 屏幕上的默认字数)
>
> 根据叶子顺序模式导出图



1、init():

初始化==>将句子规范为小写、分段、切割为单词

使用正则表达式，匹配单词、数字、主题标签、URL、@句柄等等社交媒体中常见的用法。

过滤停用词和标点符号

否定词"no"不能被视作停用词，因为删除它会颠倒句子的含义

目前该算法尚未过滤掉主题标签或者网址，但我们注意到通常他们比常规单词信息少，可能浪费屏幕资源，计划未来过滤掉

2、初始模式s是顺序模式树的根结点

我们使用它来存储顺序模式生成过程的中间状态。该树很重要，因为在放大和缩小可视化效果时我们可以重用这些中间状态。然后，该算法调用 *patternGeneration*（）函数，从根源开始扩展新的顺序模式。



算法二：*patternGeneration*（）

> 输入：顺序模式根结点（现在是s），初始模式（现在是s），屏幕上的默认字数
>
> 输出：叶子顺序模式列表
>
> 如果 初始模式s没有单词 则 屏幕上的默认字数 -= 初始模式中的单词数
>
> 初始化叶子顺序模式列表=空列表
>
> 将初始模式s放入叶子顺序模式列表
>
> **循环**：当 叶子顺序模式中至少有一个单词 & 屏幕上的默认字数>0 时
>
> ​				s = 叶子顺序模式中频率最大（support最大）的序列
>
> ​				1、如果 s 没有子序列：找到只比s多一个单词的最频繁的超集s‘，把s'变为原始s的左结点，s本身变成原始s的右结点
>
> ​				2、如果s有子序列 ：令s'=s的左结点，令s=s的右结点（即进入下一次去拓展，这一层是完成了的）
>
> ​				屏幕上的默认字数-1
>
> ​				把s和s‘加入叶子顺序模式列表中					
>
> 返回叶子顺序模式列表





首先我们拿到句子集，以这个句子集为基础构建去构建叶子顺序模式列表

找一个空模式作为叶子顺序模式列表的根结点，这个空模式也叫初始模式

然后在句子集中找到最频繁的单词a【应理解为初始模式最频繁的超集，这个超集只能多一个单词】，把句子集含a和不含a的分成两个，把不含a 的句子集看成新的句子集

叶子顺序模式列表变为：初始模式（空模式），超集a

不断重复上述：（**在叶子顺序列表中找到下一个最频繁模式**，在最频繁模式的句子集找最频繁的单词t，改变数据集，在叶子顺序模式中增加t），注意每个t都包含先前的模式





PPT要求：
PPT必须包含的内容
1，这篇文章做什么
2，它怎么做
3，它哪里做的不好
4，这个问题还可以有别的方法来做吗
5，这个问题可以扩展到相关的其他问题吗
6，实现系统的技术路线
7，实现时可能遇到的困难与可能的解决方案





1、预处理（分割单词、过滤停用词等等）要写个js文件

2、构造一个处理后的**数据集类**，这个数据集至少应该包含如下参数：

（1）单词总列表（数据集中所有句子处理后得到的）

（2）句子数组，每一项对应数据集中的一个句子，每一项应该包含如下属性

​									a. 句子id

​									b. 句子本身的文本

​									c. 句子经过处理后的单词组，用数组呈现

​									d.一个数组，其的索引和值都是数字。表达索引某个位置上的单词在句子中的位置。便于后续处理。

3、初始化一个总序列列表，构造为“大堆”，调用含义为pop的方法时，size最大的数据集将首先弹出。

把初始序列s，作为根结点放入总序列列表（此时的s的支持数据集是全部的数据集）

再初始化一个空的叶子顺序模式列表，之后用来存放找出的序列。

调用方法上面的方法*patternGeneration*()，实现思路已经在上面ppt中给出。其中“*查找下一个最频繁的超集并分割数据集*”实现比较复杂，单独构建为方法*findNext*()

***findNext*()具体实现思路：**

这个方法的作用是：通过往当前频繁序列**添加**一个新单词得到下一个频繁序列

实现：因为要添加单词，用一个变量记录添加的这个新单词相对于序列的位置

遍历该序列的支持数据集，截取在序列中的每两个词对应的句子里的位置之间的其他所有词，遍历这些单词，用一个对象统计它们出现的次数，然后选出次数最大的，加入到原序列中构成新序列，新单词将插入到**当前遍历到的序列单词的位置**，以保证文本逻辑性。【注意：如果同一个句子里出现了两边同一个单词，单词计数只能算一次！我们这里记录的次数是句子的count，而不是单词在句子中出现的次数】

之后分割支持数据集，构造s1是不含新单词的序列，s2是含有新单词的序列。方法是遍历旧序列的支持数据集中的每一个句子，含有新单词，就加入s2，否则加入s1。





1、创建一个Node类，含有以下属性：

​	a.数据值（单词）

​	b.左边的边数组

​	c.右边的边数组

​	d.坐标

并且实现两个方法：

(1)建立从左到右的顺序约束

(2)建立x轴和y轴的约束（即水平约束和垂直约束）

2、创建一个Link类，含有以下属性：

​	a.这条边连接的左结点

​	b.这条边连接的右结点

​	c.左边结点坐标和右边结点坐标

实现方法：

如果是1对1连接，则将间距设为a

如果不是1对1连接，则将间距设为b，满足b>a

3、构建图的思路：

构建一个堆，调用含义为pop的方法时，能够弹出数据id最小的元素。

选出左边或者右边连着多条边的结点，放入堆中。

分别遍历从堆中弹出的结点N的左结点数组和右结点数组，将它们**连接**到N上。

再把他们放入堆中，循环重复上述步骤，直至堆中没有元素。

***如何将他们连接到N上呢？***比较复杂，再写一个函数connect()

**connect()**的实现思路：

在原结点数组中添加新的结点们，并给他们一个布尔值作为标记。

遍历原来的所有结点，将每个结点作为讨论对象，讨论其左边连接的边，如果有连接新的结点（有标记的），则new一个新Link，用来连接新结点和讨论的结点。这就把新结点的左边的边都连接上了，右边同理。

于是可将新结点正确连接到左边和右边的边上。









​