引言

技術(shù)無關(guān), 可跳過.

最近在寫一個(gè)獨(dú)立項(xiàng)目,
基于斗魚直播平臺的開放接口, 對斗魚的彈幕進(jìn)行實(shí)時(shí)的分析,
最近抽空記錄一下其中一些我個(gè)人覺得值得分享的技術(shù).

在寫這個(gè)項(xiàng)目的時(shí)候我一直在思考, 彈幕這種形式已經(jīng)出來了很久,
而且被廣大網(wǎng)友熱愛, 確實(shí)增強(qiáng)了參與者之間的溝通,
但近年彈幕的形式卻沒什么很大的創(chuàng)新, 而問題卻有許多,
其中有一條彈幕非常多的時(shí)候, 其實(shí)很多是重復(fù)的, 非常影響觀感.

于是我提出了一個(gè)需求: 實(shí)時(shí)采集彈幕, 并相互之間對比,
合并相近的彈幕, 這里的"相近"是個(gè)什么樣的標(biāo)準(zhǔn)就是值得去思考的一個(gè)東西了.

在查閱了很多資料之后, 發(fā)現(xiàn)這里已經(jīng)到了一個(gè)對自然語言處理的問題,
說大一點(diǎn)屬于AI的范疇了, 各大云平臺例如騰訊云都有這方面的功能,
蘋果最近WWDC發(fā)布的CoreML就可以使用訓(xùn)練好的自然語言識別模型.
在還不能用到CoreML(性能問題有待斟酌)之前,
連接云平臺在瞬間高并發(fā)的使用場景下是不太現(xiàn)實(shí)的,
所以需要本地算出兩個(gè)中文句子的"語義近似度".

理論

編輯距離算法:

編輯距離雏亚，又稱Levenshtein距離，是指兩個(gè)字串之間，
由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯操作次數(shù)。
許可的編輯操作包括將一個(gè)字符替換成另一個(gè)字符，插入一個(gè)字符侠姑，刪除一個(gè)字符创橄。
每個(gè)操作成本不同, 最終可以得到一個(gè)編輯距離.
編輯距離越短, 句子就越相似, 編輯距離越長, 句子相似度就越低.

這種算法很早就被提出來了, 而且網(wǎng)上資料非常齊全, 先看算法:

#import "NSString+Distance.h"
static inline int min(int a, int b) {
    return a < b ? a : b;
}

@implementation NSString (Distance)
- (float)SimilarPercentWithStringA:(NSString *)stringA andStringB:(NSString *)stringB{
    NSInteger n = stringA.length;
    NSInteger m = stringB.length;
    if (m == 0 || n == 0) return 0;
    
    //Construct a matrix, need C99 support
    NSInteger matrix[n + 1][m + 1];
    memset(&matrix[0], 0, m + 1);
    for(NSInteger i=1; i<=n; i++) {
        memset(&matrix[i], 0, m + 1);
        matrix[i][0] = i;
    }
    for(NSInteger i = 1; i <= m; i++) {
        matrix[0][i] = i;
    }
    for(NSInteger i = 1; i <= n; i++) {
        unichar si = [stringA characterAtIndex:i - 1];
        for(NSInteger j = 1; j <= m; j++) {
            unichar dj = [stringB characterAtIndex:j-1];
            NSInteger cost;
            if(si == dj){
                cost = 0;
            } else {
                cost = 1;
            }
            const NSInteger above = matrix[i - 1][j] + 1;
            const NSInteger left = matrix[i][j - 1] + 1;
            const NSInteger diag = matrix[i - 1][j - 1] + cost;
            matrix[i][j] = MIN(above, MIN(left, diag));
        }
    }
    return 100.0 - 100.0 * matrix[n][m] / stringA.length;
}
@end

實(shí)際測試起來, 這種算法由于對中文的適應(yīng)性不好, 會有各種問題, 不細(xì)說了.
繼續(xù)查資料, 看到另一種算法.

詞頻向量余弦夾角算法:

這種算法思想也挺簡單的,
將兩個(gè)句子構(gòu)造成兩個(gè)向量, 并計(jì)算這兩個(gè)向量的余弦夾角cos(θ),
夾角為0°, 則代表兩個(gè)句子意思完全相同,
夾角為180°, 則代表兩個(gè)句子相似度為零.

下一個(gè)問題, 怎樣將句子構(gòu)造成向量?
這里就引入"詞頻向量",
簡單的說就是先將兩個(gè)句子分詞,
通過詞第一次出現(xiàn)的位置以及詞出現(xiàn)的頻率組成向量,
再計(jì)算夾角.

舉個(gè)例子:
句子A: 斗魚伴侶真是有意思,支持斗魚直播
句子B: 斗魚伴侶挺有意思,斗魚直播可以用

分詞之后:
句子A: 斗魚/伴侶/真是/有意思/支持/斗魚/直播
句子B: 斗魚/伴侶/挺/有意思/斗魚/直播/可以/用

向量:
句子A:[2(斗魚),1(伴侶),1(真是),1(有意思),1(支持),1(直播)] (斗魚出現(xiàn)2次, 其他出現(xiàn)1次)
句子B:[2(斗魚),1(伴侶),1(挺),1(有意思),1(直播),1(可以),1(用)] (同上)

先看下面公式

分子就是2個(gè)向量的內(nèi)積
ab = 2x2(斗魚) + 1x1(伴侶) + 1x0(真是) + 1x0(挺) + 1x1(有意思) + 1x0(支持) + 1x1(直播) + 1x0(可以) + 1x0(用)
= 7

分母是兩個(gè)向量的模長乘積
||a|| = sqrt(2x2(斗魚) + 1x1(伴侶) + 1x1(真是) + 1x1(有意思) + 1x1(支持) + 1x1(直播))
= 3

||b|| = 2x2(斗魚) + 1x1(伴侶) + 1x1(挺) + 1x1(有意思) + 1x1(直播) + 1x1(可以) + 1x1(用)
= 3.16....

最終可以得出來
cos θ = 0.737865

其實(shí)到此為止基本上可以判斷出這兩個(gè)句子的相似度了,
換算成角度其實(shí)更精確
similarity = arccos(0.737865) / M_PI
= 0.764166

參考文章: https://mp.weixin.qq.com/s/dohbdkQvHIGnAWR_uPZPuA

實(shí)際

下面具體說說這套算法思想的實(shí)現(xiàn)
這里面實(shí)際用起來有兩個(gè)難點(diǎn):
1.分詞: iOS系統(tǒng)其實(shí)自帶分詞Api, 只是對中文的支持并不是那么友好,
而且在高并發(fā)的情況下性能也堪憂, 自定義詞庫那是更加不能實(shí)現(xiàn)的了.
2.構(gòu)造向量并計(jì)算: 這個(gè)其實(shí)在iOS中直接構(gòu)造向量也是不那么好實(shí)現(xiàn)的,
因?yàn)樯婕暗絻蓚€(gè)句子詞的對比, 需要補(bǔ)0.

分詞

這里感謝開源的分詞庫 結(jié)巴分詞
這個(gè)庫有各個(gè)語言的版本 其中iOS的版本地址:
https://github.com/yanyiwu/iosjieba

集成以及使用起來也非常簡單, 性能也非常不錯(蘋果自帶甩分詞不見了)
庫的底層是C++, 所以只是要注意的是用到庫的文件改為.mm后綴名.

結(jié)巴分詞支持自定義詞庫 直接將詞寫入下面文件
注意不能空行 否則會報(bào)錯
iosjieba.bundle/dict/user.dict.utf8

具體詞哪里來...
用抓包軟件在某些輸入法中抓的= =..

//初始化后直接使用
- (void)loadJieba{
    NSString *dictPath = [[[NSBundle mainBundle] resourcePath] stringByAppendingPathComponent:@"iosjieba.bundle/dict/jieba.dict.small.utf8"];
    NSString *hmmPath = [[[NSBundle mainBundle] resourcePath] stringByAppendingPathComponent:@"iosjieba.bundle/dict/hmm_model.utf8"];
    NSString *userDictPath = [[[NSBundle mainBundle] resourcePath] stringByAppendingPathComponent:@"iosjieba.bundle/dict/user.dict.utf8"];
    
    const char *cDictPath = [dictPath UTF8String];
    const char *cHmmPath = [hmmPath UTF8String];
    const char *cUserDictPath = [userDictPath UTF8String];
    
    JiebaInit(cDictPath, cHmmPath, cUserDictPath);
}


//字符串轉(zhuǎn)詞數(shù)組
- (NSArray *)stringCutByJieba:(NSString *)string{
    
    //結(jié)巴分詞, 轉(zhuǎn)為詞數(shù)組
    const char* sentence = [string UTF8String];
    std::vector<std::string> words;
    JiebaCut(sentence, words);
    std::string result;
    result << words;
    
    NSString *relustString = [NSString stringWithUTF8String:result.c_str()].copy;
    
    relustString = [relustString stringByReplacingOccurrencesOfString:@"[" withString:@""];
    relustString = [relustString stringByReplacingOccurrencesOfString:@"]" withString:@""];
    relustString = [relustString stringByReplacingOccurrencesOfString:@" " withString:@""];
    relustString = [relustString stringByReplacingOccurrencesOfString:@"\"" withString:@""];
    NSArray *wordsArray = [relustString componentsSeparatedByString:@","];
    
    return wordsArray;
}

計(jì)算

上面已經(jīng)解決了分詞的問題, 下面說說具體怎么算,
這里我沒有直接構(gòu)造向量解決, 并沒有太好的思路.
但是利用算法的思路和面向?qū)ο蟮乃枷胛沂沁@樣解決的:

我們需要得到的是向量的內(nèi)積和模長乘積,
先說模長乘積, 這個(gè)數(shù)字是固定的, 跟對比的句子無關(guān), 比較好得到.
我們發(fā)現(xiàn)向量的內(nèi)積其實(shí)在這里跟詞的位置無關(guān),
所以可以用字典來構(gòu)造, key為詞, value為詞頻,
遍歷數(shù)組對比, 可以得到每個(gè)詞的詞頻, 構(gòu)造詞頻字典,
再將兩個(gè)字典相同key的value相乘即為模長乘積.

說起來有點(diǎn)繞, 看代碼:

//這里構(gòu)造了兩個(gè)BASentenceModel用來存原來的文本,分詞后的詞數(shù)組,以及詞頻字典.

在設(shè)置分詞數(shù)組時(shí)候遍歷數(shù)組得出詞頻
- (void)setWordsArray:(NSArray *)wordsArray{
    _wordsArray = wordsArray;
    
    //根據(jù)句子出現(xiàn)的頻率構(gòu)造一個(gè)字典
    __block NSMutableDictionary *wordsDic = [NSMutableDictionary dictionary];
    [wordsArray enumerateObjectsUsingBlock:^(NSString *obj1, NSUInteger idx1, BOOL * _Nonnull stop1) {
        
        //若字典中已有這個(gè)詞的詞頻 +1
        if (![[wordsDic objectForKey:obj1] integerValue]) {
            __block NSInteger count = 1;
            [wordsArray enumerateObjectsUsingBlock:^(NSString *obj2, NSUInteger idx2, BOOL * _Nonnull stop2) {
                if ([obj1 isEqualToString:obj2] && idx1 != idx2) {
                    count += 1;
                }
            }];
            
            [wordsDic setObject:@(count) forKey:obj1];
        }
    }];
    _wordsDic = wordsDic;
}


//傳入兩個(gè)句子對象即可得出兩個(gè)句子之間的近似度

/**
 余弦夾角算法計(jì)算句子近似度
 */
- (CGFloat)similarityPercentWithSentenceA:(BASentenceModel *)sentenceA sentenceB:(BASentenceModel *)sentenceB{
    //計(jì)算余弦角度
    //兩個(gè)向量內(nèi)積
    //兩個(gè)向量模長乘積
    __block NSInteger A = 0; //兩個(gè)向量內(nèi)積
    __block NSInteger B = 0; //第一個(gè)句子的模長乘積的平方
    __block NSInteger C = 0; //第二個(gè)句子的模長乘積的平方
    [sentenceA.wordsDic enumerateKeysAndObjectsUsingBlock:^(NSString *key1, NSNumber *value1, BOOL * _Nonnull stop) {
        
        NSNumber *value2 = [sentenceB.wordsDic objectForKey:key1];
        if (value2.integerValue) {
            A += (value1.integerValue * value2.integerValue);
        }
        
        B += value1.integerValue * value1.integerValue;
    }];
    
    [sentenceB.wordsDic enumerateKeysAndObjectsUsingBlock:^(NSString *key2, NSNumber *value2, BOOL * _Nonnull stop) {
        
        C += value2.integerValue * value2.integerValue;
    }];
    
    CGFloat percent = 1 - acos(A / (sqrt(B) * sqrt(C))) / M_PI;
    
    return percent;
}

結(jié)論

我知道很多人覺得這個(gè)挺沒有意義的,畢竟沒有人在前端上做這些事情..
但實(shí)際效果確實(shí)不錯, 在高峰彈幕期間彈幕合并大于1000+.
這里用的iphone6測試, 30秒1500條彈幕, 分詞就可以分成6000+,
再進(jìn)行各種分析(活躍度, 等級, 詞頻, 句子, 禮物統(tǒng)計(jì), 篩選等等等),
這種強(qiáng)度下的計(jì)算, iphone完全無問題, 多線程處理好之后如下圖:

相對于服務(wù)器高度依賴于數(shù)據(jù)庫計(jì)算, 受制于數(shù)據(jù)庫與硬盤性能來說,
內(nèi)存中的讀寫顯然更有優(yōu)勢, 問題其實(shí)在ARC的情況下內(nèi)存的釋放不太受控制,
非常多彈幕的情況下可能會告警, 不過也只能這樣了.
畢竟海量彈幕模式PC打開瀏覽器僅作展示都會卡死...

另一方面AI計(jì)算放在移動設(shè)備上可能也是一種趨勢,
蘋果推出CoreML希望在兼顧隱私的同時(shí),讓隨身設(shè)備更智能,
想象一下全球的手機(jī)都有AI系統(tǒng)獨(dú)立計(jì)算各種數(shù)據(jù), 數(shù)據(jù)存在云中再一次處理,
這會是一個(gè)很近而且很爆炸的未來.

Github:https://github.com/syik/ZJSentenceAnalyze/tree/master

以上.
題外話:App已上架, 名字叫:直播伴侶, 功能點(diǎn)還挺多的
其中繪圖(quartz2D),動畫(CoreAnimation/lottie)運(yùn)用的都挺多的.
感覺大家會有興趣, 有需要可以寫寫經(jīng)驗(yàn).
App大家可以下下來看看, 順便給個(gè)好評, 3Q!