计算机网络与通讯协议
Hu Junfeng 2010/10/20
1
如何统计一篇英文文章中所有单词出现的次数?
/* * 假设有M个单词,单词平均长度为L,按你的设计单词统计算法的时间、空间复杂度是多少?
* 如何还能有效的降低统计程序的算法复杂度?
*
* 算法:
* 用一个Trie来保存所有的单词,在每个结点上记录该单词已经出现了多少次。
* 时间复杂度与空间复杂度都和文章中的总字数成正比,即时间复杂度和空间复杂度均为O(ML)。
* 还可以用平衡树、哈希表来存储,但是时间效率都不如Trie。
*
* 可以改进的方面:
* 这个程序是不区分大小写的,所以像I这样的单词会变成i。
**/
2
A Trie:
3
//by 芦苇丛
4
//by 芦苇丛
5
统计多个文件中的汉语词频
文件操作
字符串比较、排序、计数
新浪评价\ments\*.seg
6
7
8
//by 芦苇丛
9
By 陈云帆 1000010012
程序中对一切特殊符号进行了滤除并认为是分隔符,包括英文符号,空格,全角符号等。
全角符号包括中文标点,平假名和片假名,希腊字符,俄文字符,拼音字符,制表符,还有一些有意义的符号比如℃、$、￥、%等
程序用字典树实现了对词频的统计。字典数通过左孩子右兄弟的方式进行了二叉树转换并动态分配空间。
10
计算机网络与通讯协议 来自淘豆网m.daumloan.com转载请标明出处.
