前段时间在研究 TF-IDF、杰卡德相似系数计算文本的相似度的时候（目前我的博客中部分文章底部的“猜你喜欢”推荐的文章就是用这种算法计算出来的），用到了中文分词的一些东西，由于当时精力有限，直接用了python的“结巴分词”来实现。

恰巧听说老东家最近出了个算法大赛，题目就是就是对小说《三体》进行中文分词！闲下来简单的动手写了一个Node版的算法，100行代码，虽然还是很初级的，但是还是想写些东西“纪念”一下。

背景

分词是搜索、自然语言分析等领域应用的比较多的比较基础的技术之一。由于英文本身每个单词间使用空格分隔，所以分词对于英语系的文本来说，就没有那么的复杂了，难题出现在类似于中文之类的语言，这类语言在每个词之间并没有明显的分隔，想要对这样的语言进行分词确实比较困难。

市面上常用的几种方法是，第一种通过统计分析来拆词，第二种是通过自然语言的分析，判断句子成分，来进行分词，等等。这些方法各有利弊，没有明确的说法说哪一种方法完胜于另外一种。

思考

由于条件有限，大规模机器学习什么的并不现实，所以我们采用了第一种基于统计的方法进行分词。

方法有了，那么问题来了，如何知道一句话中的哪些字的组合是一个词呢？ 维护一个字典通过字典来判断？ 但问题又来了，字典哪里来？ 网上找？ 但这样和直接用别人的库又有什么区别呢？ 有没有一种方法可以让机器自己去学习，去判断词呢？

当然可以，我们可以把一句话中所有可能的词语组合都找到，然后判断这写组合出现的频次，大于某些频次的，就可以判定为是一个词组。

OK，到此为止我们想到了一种“可行”的方法，但是把所有的字的组合都找到对于一篇文章来说靠谱么？这会是一个天文数字吧？！！ 别急，我们一步一步来。 这里先买个关子，后面我会结合 trie树(字典树) 和 HMM(隐马尔可夫模型) 来实现。

实现过程

我们开动吧！

开始前还是先奉贤上 实现代码。

OK, Let's Do It!

首先是拿到我们的素材 三体II-黑暗森林 这里我们暂且把它存为 text.txt .

新建一个 task.js 文件，接下来我们开始搬砖。

// 引用fs模块
var fs = require('fs')

// 创建一些变量，后面会说到
var trie = {}
var tempWords = {};

// 开始读取文件text.txt
fs.readFile('./text.txt',function(err,callback){
    // 将读取的二进制转换成String，
    // 注意，大文件的话要小心的分片处理，当心内存爆掉。
    var str = callback.toString();

    // 接下来，我们需要“清理”我们的素材，
    // 首先，把所有的不是中文的字符统统替换成“@”，
    // “@”只是个临时字符串，如果你喜欢，可以是任意字符
    // 例如：
    //     "大家好！：）我是Mofei" => "大家好@@@我是@@@@@"
    str = str.replace(/[^\u4e00-\u9fa5]/g,'@');
    // 把替换下来的@替换成空格
    // 例如：
    //     "大家好@@@我是@@@@@" => "大家好 我是 "
    str = str.replace(/@+/g,' ')
    split(str);
})

通过上面的操作，我们拿到的就是一份比较干净的数据了，接下来是我们的重点了。

这里我们要处理一句话中的字符串的所有可能的组合，介于通常情况下中文的词汇大多数都是4个字以内的，我们以4个字来举个例子：

比如字符串 “欢迎大家关注” 可以组合成：

欢迎大家 迎大家关 大家关注 欢迎大 迎大家 大家关 家关注 欢迎 迎大 大家 家关 关注

简简单单的6个字可以有12种组合，那么我们要把所有的组合都记录下来么？STOP！当你有这种想法的时候，你的计算机一定在痛哭流涕，对于一篇长篇小说来说，这真的是一场灾难！那么能不能用什么比较好的方法来实现呢？对那就是 trie树(字典树) 原理什么的不说了，大家可以自己去看。

我在trie的基础上又增加了计数len字段，来帮助我们辅助判断

树化之后我们得到的是这样的结构：

{
    "欢": {
        "迎": {
            "大": {
                "家": {
                    "len": 1
                },
                "len": 2
            },
            "len": 3
        },
        "len": 3
    },
    "迎": {
        "大": {
            "家": {
                "关": {
                    "len": 1
                },
                "len": 2
            },
            "len": 3
        },
        "len": 3
    },
    "大": {
        "家": {
            "关": {
                "注": {
                    "len": 1
                },
                "len": 2
            },
            "len": 3
        },
        "len": 3
    },
    "家": {
        "关": {
            "注": {
                "len": 1
            },
            "len": 2
        },
        "len": 2
    },
    "关": {
        "注": {
            "len": 1
        },
        "len": 1
    }
}

通过上面的数的len我们可以精简到如下的几个“词” （从根节点的不停深入，直到len有异常变化为止）：

欢迎 迎大 大家 家关 关注

OK，这里我们从12个组合中精简到5个

等等！ WTF！！！ 迎大 家关 是什么东西？耍我呢？这是词么？

到这里，大家先别着急，有没有注意到我们后面的len字段？而且我们现在用的也仅仅才是一句话而已。我们暂且叫这个trie树是我们的模型（其实他只是训练的结果罢了）。

”卧了个槽？训练？“

没错！！如果我们拿更多的语句来训练的话，这里的len会有显著的变化，最终我们可以自己定一个策略，比如len小于10的全部废弃，从根节点开始，len的偏移量大于一定的值再舍去等等。

尝试多跑一些文章之后，你会发现你真的训练出了一个字典！ 如果你成功实现了的话，让我们开瓶香槟庆祝一下！

好，回到我们的代码：

// 处理句子
function split(str) {
    // 将clean的字符串按照空格拆分，
    // 最终我们拿到的是一句一句的数组
    str = str.split(' ');

    for (var i = 0; i < str.length; i++) {
        // 把每句话拆分成一个一个的字
        var words = str[i];

        if (words.length <= 1) {
            // 废弃一个字的“词”
            continue;
        }

        if (words.length === 2) {
            // 如果是两个长度的直接处理
            wordsToTrie(words);
        } else {
            // 如果是大于2个长度的，
            // 找到所有字的组合进行处理
            for (var j = 0; j < words.length - 2; j++) {
                // 阀值我们取4，即默认一个词的最大字数是4
                // 当然你可以取更大的值，越大越耗费性能
                wordsToTrie(words.substr(j, 4));
            }
        }
    }

    // 把trie数转换成 词的字典
    // 即 {"你好":14,"大楼":45}
    trieToWords();
    // 输出结果
    wordsToArrAndRank()
}

function wordsToTrie(str) {

    var words = str.split('');

    // stopWords 很好理解，在语言中有些词出现的频率过高没有实际意义，
    // 比如 “我的” “这个” 等，这些词对搜索、判断文章的特征来说没有任何帮助，
    // 我们可以将它们过滤掉
    // 网上有现成的stopwords的字典，这里我选取了一小部分
    var stopWords = ["和", "与", "你", "我", "两", "这", "把", "那", "个", "他", "您", "它", "们", "是", "的", "一", "了", "在"]
    if (stopWords.indexOf(words[0]) !== -1) {
        return false;
    }

    var temp = trie;
    for (var i = 0; i < words.length; i++) {
        // 把字符串存储到trie数上
        temp = saveToTrie(temp, words[i]);
    }

}

// 把字符串存储到trie数上
function saveToTrie(obj, chart) {

    // 如果不存在就新创建一个空间
    // 如 {“你”:{len:0}} + "我" => 
    // {“你”:{"我":{len:0},len:0}}
    obj[chart] = obj[chart] || {
        len: 0
    }

    // 如果存在，计数加1
    obj[chart].len += 1;
    return obj[chart];
}

function trieToWords() {
    var words = [];
    conmbine(trie, '');

}

自此，我们的trie树就“调教”好了，接下来就是一些小小的善后工作了

// 把trie树转换成 词的字典
// 比如：
//     {"你好":14,"大楼":45}
// 这里你可以设置成自己的规则
// 比如设置len的阀值，len的变化异常时候停止等
// 举例：
// {"你:{
//      "好":{
//          "明":{
//              "天":{
//                  len: 2,
//              }
//              len: 2,
//          },
//          len: 14
//      },
//      len: 14
//   }
// }
// 这种情况下，我们可以判断这个词到“好”就结束了，
// 因为后面的“明”的权只有 2，明显的低于前面的14
function conmbine(obj, str) {
    var retObj = [];
    var haveSone = false;
    var pow = obj.len;
    for (i in obj) {
        if (obj[i].len <= 6) {
            continue;
        }
        if (i !== 'len') {
            conmbine(obj[i], str + i);
        }
    }

    if (!haveSone && str.length >= 2) {
        tempWords[str] = tempWords[str] || 0
        tempWords[str] = Math.max(tempWords[str], pow)
    }
}

接下来就是输出结果的时候了

// 输出结果，并按照词频排序
function wordsToArrAndRank() {
    var wordsArr = [];
    var keys = [];
    for (var i in tempWords) {
        keys.push(i);
    }

    keys = '|' + keys.join('|') + '|'
    for (var i in tempWords) {
        // 注意这个正则，它是为了满足比赛规则而出现的
        // 其实可以去掉,
        // 规则是： 
        // 对于“苹果”,“青苹果”只取 “青苹果”
        // 对于“宝石”,“红宝石”只取 “红宝石”
        // 当然了如果需要判断权值的话，这里也可以判断，就不做演示了
        var noLeft = !RegExp('[^|]+' + i + '\\|').test(keys);
        var noRight = !RegExp('\\|+' + i + '[^|]+').test(keys)
        if (noLeft && noRight) {
            wordsArr.push([i, tempWords[i]])
        }
    }
    // 按照词频排序
    wordsArr.sort(function (a, b) {
        return a[1] - b[1]
    })
    // 输出
    console.log(JSON.stringify(wordsArr))
    console.log(wordsArr)
}

下面是用这套算法跑出来的结果（仅取了前20个结果供参考）

  ['必须', 59 ],
  [ '第一次', 60 ],
  [ '眼睛', 60 ],
  [ '首先', 61 ],
  [ '来自', 62 ],
  [ '三体世界', 63 ],
  [ '似乎', 64 ],
  [ '立刻', 64 ],
  [ '变得', 65 ],
  [ '突然', 69 ],
  [ '信息', 69 ],
  [ '字幕', 70 ],
  [ '虽然', 76 ],
  [ '东方延绪', 81 ],
  [ '几乎', 81 ],
  [ '正在', 85 ],
  [ '完全', 87 ],
  [ '自然选择', 91 ],
  [ '面壁计划', 94 ],
  [ '雷迪亚兹', 195 ]

附录：代码传送门

var fs = require('fs')
 
var trie = {}
var tempWords = {};
 
fs.readFile('./text.txt',function(err,callback){
    var str = callback.toString();
    str = str.replace(/[^\u4e00-\u9fa5]/g,'@');
    str = str.replace(/@+/g,' ')
    split(str);
})
 
function split(str){
    str = str.split(' ');
    for(var i = 0;i<str.length;i++){
        var words = str[i];
        if(words.length<=1){
            continue;
        }
 
        //var wordsArr = [];
        if(words.length===2){
            //wordsArr.push(words);
            wordsToTire(words);
        }else{
            for(var j=0;j<words.length-2;j++){
                wordsToTire(words.substr(j,4));
                //wordsArr.push(words.substr(j,4))
            }
        }
    }
    trieToWords();
    wordsToArrAndRank()
}
 
function wordsToTire(str){
    var words = str.split('');
 
    var stopWords = ["和","与","你","我","两","这","把","那","个","他","您","它","们","是","的","一","了","在"]
    if(stopWords.indexOf(words[0])!==-1){
        return false;
    }
    var temp = trie;
    
    for(var i =0;i<words.length;i++){
        temp = saveToTire(temp,words[i]);
    }
 
}
 
function saveToTire(obj,chart){
    obj[chart]=obj[chart]||{len:0}
    obj[chart].len+=1;
    return obj[chart];
}
 
function trieToWords(){
    var words=[];
    conmbin(trie,'');
 
}
 
function wordsToArrAndRank(){
    var wordsArr=[];
    var keys = [];
    for(var i in tempWords){
        keys.push(i);
    }
    keys = '|'+keys.join('|')+'|'
    for(var i in tempWords){
        if(!RegExp('[^|]+'+ i + '\\|').test(keys) && !RegExp('\\|+'+ i + '[^|]+').test(keys) ){
            wordsArr.push([i,tempWords[i]])
        }
    }
    wordsArr.sort(function(a,b){
        return a[1]-b[1]
    })
    // console.log(JSON.stringify(wordsArr))
    console.log('The Key list is',wordsArr)
}
 
function conmbin(obj,str){
    var retObj = [];
    var haveSone =false;
    var pow = obj.len;
    for(i in obj){
        if(obj[i].len<=6){
            continue;
        }
        if(i!=='len'){
            //console.log(str+i);
            conmbin(obj[i],str+i);
        }
    }
 
    if(!haveSone && str.length>=2){
        tempWords[str] = tempWords[str] || 0
        tempWords[str] = Math.max(tempWords[str],pow)
    }
}