Nodejs实现可训练的中文分词实践

前段时间在研究 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 ]

附录:代码传送门

Write a response...
Mofei Zhu
publish
haozxuan
2015-07-15 20:56
that's cool,today 4 group join game, one group use Nodejs, one use Python 3, one use Java, last one use Lua,but you's answer is different. you can check “逻辑”:)
1
 Replay
@haozxuan  
Replay
匿名
2015-07-12 01:30
学习了
1
 Replay
@  
Replay
匿名
2015-07-08 06:00
nice
1
 Replay
@  
Replay