图片 展示 网站模板,南宁市网站建设,如何在eclipse上做网站,甘肃建设项目公示网站机械提取词频
环境
在 Windows 10 系统下#xff0c;使用 Visual Studio 2019 编译运行的 C 控制台程序。
任务分析
根据大作业要求#xff0c;主要有以下两个任务需要完成#xff1a;
统计两个文档多少字符相同#xff0c;多少字符不相同统计前十高频字或词
第一个任…机械提取词频
环境
在 Windows 10 系统下使用 Visual Studio 2019 编译运行的 C 控制台程序。
任务分析
根据大作业要求主要有以下两个任务需要完成
统计两个文档多少字符相同多少字符不相同统计前十高频字或词
第一个任务比较简单我们只需要记录第一个文档中各字符出现的次数再和第二个文档进行比较即可。第二个任务我认为相对来说比较复杂。对于一篇汉语文档我们并不能像对一篇英语文档那样通过标点和空格识别出词语这就是摆在我面前的第一个难题——分词。同时处理一篇汉语文档势必要特别注意编码这是我需要处理的第二个难题。
编码
现在比较常用的中文编码是 UTF-8 和 GBK。
UTF-8 编码在 Linux 系统下很常见采用 1~4 的变长字节字符集全是当下各领域比较通用、主流的编码GBK 编码是 Windows 系统下的默认编码Windows 下的文件路径、控制台等都默认采用这一编码采用 1~2 的变长字节涵盖绝大部分汉字。
除此之外在 C 环境下还支持 UTF-16 字符的相关操作宽字符类型 wchar_t 的基本操作便是基于 UTF-16 编码的。但是这种编码不常使用因此被我排除在外。
综合考量我选择了 GBK 编码作为本项目的统一编码。本项目下所有代码源文件、txt 文件均采用这一编码标准。选择这一编码的原因主要有以下几点
输入和输出较 UTF-8 编码方便读入一个字符判断最高位为 1 时(表示该字符为非 ASCII 字符)我们只需要再读入一个字符便得到了该汉字的编码而对于 UTF-8 编码我们需要统计高位在 0 出现之前连续 1 的个数以此决定再读入几个字符得到这个汉字的编码输出同理无论是 x86 还是 x64MSVC 编译器对 wchar_t 类型的定义都是 2 字节的 unsigned short 类型GBK 由于最多只有两个字节可以方便地用 wchar_t 类型表示而 UTF-8 则需要 4 个字节的 unsigned int 类型表示这会让程序所占内存空间提高一倍由于文件路径在 Windows 环境下采用 GBK 编码表示如果我们统一采用 UTF-8 编码当文件路径中有中文时可能会出现 BUG而我们直接采用 GBK 编码就可以避免这一问题。
在读入 GBK 字符时核心操作如下
wchar_t WInFile::convertUCharToWChar(unsigned char c)
{wchar_t wc 0;if (c 0x80) //首位为1{wc | static_castwchar_t(c) 8;c inFile-get(); //再读入一个字符作为完整汉字wc | static_castwchar_t(c);}else{wc static_castwchar_t(c) 8;}return wc;
}
这个函数完成了将一个 unsigned char 类型字符转换为 wchar_t 类型字符需要注意的是char 类型是有符号的最高位为符号位因此最高位不能直接进行诸如移位、按位于、按位或等位运算需要使用 unsigned char 类型。
转换 DOC 文件到 TXT
讨论完编码问题后接踵而至的问题便是如何使用 C 分析 DOC 文件。DOC 文件的文件格式很复杂对于 .docx 扩展名类型的文件我们可以更改扩展名为 .zip 然后利用 C 的 zlib 库将其解压成一个 xml 文件组成的文件夹然后提取内容但是对于 .doc 扩展名我没有找到合适的方法。最后我决定先将 DOC 文件转换为 TXT 文件然后再进行分析。因此我写了一个 Windows PowerShell 脚本完成这一转换操作位于 DocAnalysis\tools\doc2txt.ps1。
分词
查阅相关资料现在主要有以下几种分词方法
字符匹配也叫做机械分词法将待分析的汉字串与一个“充分大的”机器词典中的词条进行匹配理解法通过让计算机模拟人对句子的理解达到识别词的效果涉及句法、语义分析统计法涉及机器学习。
我挑选了其中最容易实现的机械分词法。
首先我需要一个足够大的词典作为支撑。在 GitHub 上我找到了《现代汉语词典第七版》通过简单的字符串处理我得到了一个只含词头的词典文件在本项目中的位置是 DocAnalysis\dict\dict.txt该文件的每一行都是一个词。
接着自然想到利用串的模式匹配把词典中每个词逐个与目标字符串作匹配。但是在计算了时间复杂度后我发现事情并没有这么简单。即使我们采用 KMP 算法对于单个词条匹配的时间复杂度是 O(n m)n 是文档的字数m 是单词的字数由于词典中大部分都是单双音节词m 是远小于 n 的单次匹配的时间复杂度可以近似看成 O(n)。词典中的词条的数量级为 1e6所以做完所有匹配的时间复杂度是 O(1e6 * n)。考虑到一般文章的长度从几百字到几万字不等我们这里假设 n 的数量级为 1e5所得时间复杂度达到了 O(1e11)而现代计算机 1 秒可以处理的时间复杂度数量级一半在 O(1e7)~O(1e8)显然采用直接模式匹配的方法并不可行。
那么问题出在哪里了呢试想对于文档字符串中的字符“一”从这个字符开始它只用匹配“一”开头的所有词就行了而在上述算法中它和非“一”开头的词进行了大量无用的匹配。那么如何避免这种无用的匹配呢自然想到使用 Tire树字典树。
以前我只写过英文的 Tire树通常一个 Tire树 节点的定义如下
struct TrieTreeNode
{char c; //当前节点所存字符bool isEnd; //是否是单词的结尾TrieTreeNode *next[26]; //next[c]表示下个字符的地址
};
根据需要如果区分大小写可能指针数组 next 要开到 52 的大小。然而这对于汉字来说仍然远远不够。对于 GBK 编码的汉字我使用两字节的 wchar_t 来存储难道我们要开一个 2^16 长度的 next 数组吗这样的解决策略显然不行后面的结点用不了这么大的空间我们也没有这么充裕的空间。难道我们要采用变长数组吗考虑到查询的时间复杂度也不是一种高效的解决方案。如果既要求 next 大小动态变化又要求能够在较低的时间复杂度内完成查询自然想到采用红黑树来存储 next。这样插入和查找都可以在 log 的时间复杂度下完成且可以动态变化。分析至此我们的树节点应定义如下
templatetypename T
struct TrieTreeNode
{T c; //当前节点所存字符bool isEnd; //是否是单词的结尾std::mapT, TrieTreeNodeT* next; //next[c]表示下个字符对应树节点的地址int freq; //单词的频数TrieTreeNode(T c_, bool isEnd_) : c(c_), isEnd(isEnd_), freq(0) {};
};
c 的 map 类型采用红黑树实现为了方便以后在别的项目中使用这里并没有指定字符 c 的类型为 wchar_t而是采用了 C 的模板 template 完成对这一数据结构的定义。
由于词典中的字大约在 1e5 数量级分支最多的根节点一次查询的时间复杂度为 O(log(1e5))而词典中的词大多为 2~4 字最多不超过 10 字且其后节点分支的数量级一般在 100 左右这里可以近似将从某个字符开始在字典树中匹配的时间复杂度视为 O(k)k 的数量级为 O(log(1e5))总时间复杂度为 O(k * n)这个时间复杂度我们可以在 1s 左右处理百万字级别的文章。
停止词
统计词频之后我们会发现诸如“你”、“我”、“这个”、“或者”、“然后”等对理解文章内容没有意义的词大量出现这些词称为停止词(stopword)统计词频时需要将这类词去掉。我选择了百度的停止词典在本项目中的位置是 DocAnalysis\dict\baidu_stopwords.txt。程序开始我们不止给分词词典建立字典树同样给停止词典建立一个字典树在统计完词频输出结果时如果对应词条可以与停止词典字典树中的词条匹配那么就忽略这一词条。
相同和不相同字符数统计
统计字符数我们需要建立一张表可以根据汉字找到其对应出现的次数可以有三种方式实现
直接使用静态的顺序表以汉字字符的编码直接作为下标进行索引这样我们需要建立一个包含 13 万左右元素的 int 类型的数组使用起来比较方便但是有大量空间未利用。使用哈希表建立起汉字编码 - 数组下标的映射关系我们知道 GBK 的汉字编码绝大多数集中在一个区间内只需找到合适的哈希映射函数就可以节省大量空间。使用 C 标准库提供的 std::map红黑树存储汉字编码 - 汉字频数这个关系。
其实这里直接使用第一种方法经计算也只占用 0.5MB 左右的空间但是如果使用 UTF-8 编码而不是 GBK 编码空间就会不够用了。这里我采用了第三种方法来存储汉字对应的字频。
统计字频时我还进行了另外的过滤操作我认为统计像标点符号、换行符、空格符这样的字符没有意义因此统计时将这些字符排除在外
bool DocAnalysis::isWCharValid(wchar_t wc) //判断是否为有效字符
{if (!(wc 0x00ff)) //不是汉字{char c wc 8;//下面的判断表示wc是除字母、数字外的无效字符if (!((c a c z) || (c A c Z) || (c 0 c 9))){return false;}}return true;
}
文件结构
下面展示的是 DocAnalysis/DocAnalysis 目录下的文件结构
.
-- main.cpp // 包含main函数定义程序入口// DocAnalysis类包含了程序运行的主逻辑
-- DocAnalysis.h
-- DocAnalysis.cpp// WInFile类完成了基本的从文件中读取GBK编码字符并存储为宽字符类型的操作
-- WInFile.h
-- WInFile.cpp// WOutFile类完成了输出GBK编码宽字符到文件的操作
-- WOutFile.h
-- WOutFile.cpp// TrieTree类定义了字典树这一数据结构及其基本操作由于template类的声明与实现必须放在同一个文件当中所以这里采用.hpp文件类型
-- TrieTree.hpp-- tools // tools文件夹存储相关工具
| -- doc2txt.ps1 // Windows PowerShell命令行脚本用于完成.doc或.docx文件转换为GBK编码的txt文件的操作-- dict // dict文件夹存储相关字典
| -- baidu_stopwords.txt // 百度停止词词典
| -- dict.txt // 现代汉语词典-- 资本论 //输入文件1用于Release下测试的长文档
| -- 资本论.docx
| -- 资本论.txt //1.docx转换之后的txt文件
| -- 资本论_result.txt //输出结果文件包含词频和字频-- 共产党宣言 //输入文件2用于Release下测试的长文档
| -- 共产党宣言.docx
| -- 共产党宣言.txt
| -- 共产党宣言_result.txt-- 1 //输入文件1用于Debug下测试的短文档
| -- 1.docx
| -- 1.txt //1.docx转换之后的txt文件
| -- 1_result.txt //输出结果文件包含词频和字频-- 2 //输入文件2用于Debug下测试的短文档
| -- 2.docx
| -- 2.txt
| -- 2_result.txt
输出结果
对于词频和字频由于要统计出前十这里我采用了优先队列来存储频数表优先队列类型如下
typedef std::priority_queuestd::pairint, std::vectorT qtype;
使用了 C 标准库的 vectorpair 和 priority_queue。在统计完词频后遍历一遍字典树将频数大于 0 的词条以 std::pairint, std::vectorT(这里 T 的类型是 wchar_t)存储在优先队列中std::pair 的第一个 int 类型关键字为频数第二个关键字是 wchar_t 类型字符的数组表示一个词采用 std::pair 的原因是其自动按照第一关键字、第二关键字的顺序比较大小因此无需重载比较运算符。最后依次 pop 出优先队列的元素即可得到前十词频和字频。
对 资本论.docx 的分析如下
前十高频词: 资本 18273 次 生产 12384 次 价值 10518 次 劳动 9528 次 商品 6728 次 货币 5590 次 工人 4360 次 形式 4011 次 剩余 3482 次 产品 3332 次 前十高频字: 资 23366 次 产 18583 次 不 16957 次 生 16681 次 价 14592 次 动 12319 次 人 11920 次 工 11324 次 值 10841 次 品 10783 次 结果存储在 资本论\资本论_result.txt 当中。对于字符相等与不相等数目的比较则直接显示在控制台窗口中。
根据 VS 的代码分析本程序大部分时间都花在 doc 文件与 txt 文件的转换上大约需要 5-7 秒钟。若是直接分析 txt 文件在 Release 模式下程序仅需 0.9 秒左右即可完成所有操作。如果要直接分析 txt 文件可以将对应 txt 文件放在对应文件夹中在主程序执行以下语句
DocAnalysis::useTxtFileDirectly(); //直接使用txt文件请执行本函数, 否则将本行代码注释掉
如果要使用别的文件名比如 foo.docx注意三个地方
在 DocAnalysis 文件夹下创建对应文件夹文件夹名为 foo对应文件夹下放对应 docx 文件foo 文件夹下放 foo.docx如果是 txt 文件那么放 foo.txt在 main.cpp 中更改对应 inFileName 如下
const char* inFileAName foo;
如果要使用 .doc 的后缀名注意在主函数运行语句
DocAnalysis::changeDocExtension(.doc); //设置文件后缀名, 如果为.doc请执行本函数
问题与不足
由于我统计词频时分词的策略是遇到一个在字典树中的词就将这个词的词频加 1所以如果原文当中多次出现了词条 中国特色社会主义我会将词条 中国特色社会主义社会主义中国特色社会主义 的词频都加一然而这里显然只需要将词条 中国特色社会主义 的词频加一即可。除了这种策略外还有正向最大匹配、反向最大匹配的策略这些策略可能一定程度上避免这种问题但是有时也会产生歧义。若想实现更加准确的分词与词频统计可能需要借助人工智能与机器学习中 NLP 领域的相关方法。
