文檔相識度

例子

比如輿論控制，我們假設你開發了一個微博網站，並且已經把世界上罵人的句子都已經收錄進了資料庫，那么當一個用戶發微博時會先跟罵人句子的資料庫進行比較，如果符合裡面的句子就不讓用戶發出。

通常情況下，很多工程師就會想到用like或者where的sql語法去查找。可是當情況更為複雜呢？資料庫存放了“你是個壞人”，用戶要發“小明是個壞人”，這時應該怎么辦呢？最簡單的辦法就是通過判斷文本的相似程度來決定用戶發的內容是否是罵人的。

相關算法

餘弦相似性

TF-IDF，餘弦相似度，向量空間模型這幾個知識點在信息檢索中是最基本的，入門級的參考資料可以看看吳軍老師在《數學之美》中第11章“如何確定網頁和查詢的相關性”和第14章“餘弦定理和新聞的分類”中的通俗介紹或者阮一峰老師寫的兩篇科普文章“TF-IDF與餘弦相似性的套用（一）：自動提取關鍵字**”和“TF-IDF與餘弦相似性的套用（二）：找出相似文章”。

專業一點的參考資料推薦王斌老師在中科院所授的研究生課程“現代信息檢索(Modern Information Retrieval)”的課件，其中“第六講向量模型及權重計算”和該主題相關。或者更詳細的可參考王斌老師翻譯的經典的《信息檢索導論》第6章或者其它相關的信息檢索書籍。

子序列與子字元串

這個系列問題包含這么幾種：最大子序列、最長遞增子序列、最長公共子串、最長公共子序列。幾個子問題都可以用動態規劃的思路來求解。對於長度為i、j的兩個字元串，使用矩陣來存放中間結果。

字元串編輯距離

精確計算兩個字元串的編輯距離，可以使用經典的動態規劃思路。這裡來看下如何判斷字元串A與B的編輯是否>N？這樣我們就可以比較兩個字元串的相似度了。可以構建一個編輯距離自動機（超酷算法：Levenshtein自動機），把測試字元集合輸入自動機進行判斷。可用於拼寫檢查，模糊匹配等場景。

向量相似度

使用TF-IDF計算出文本中詞的詞頻集合，把該集合作一個向量，比較不同集合向量線上性空間中的相似度。如：餘弦距離、歐氏距離、機率分布距離（K-L距離）等。

SimHash

simhash算法的主要思想是降維，將高維的特徵向量映射成一個f-bit的指紋(fingerprint)，通過比較兩篇文章的f-bit指紋的Hamming Distance來確定文章是否重複或者高度近似。

主要分以下幾步：

1、抽取文本中的關鍵字及其權重。

2、對關鍵字取傳統hash，並與權重疊加，算出文本的fingerprint值。

3、計算出兩個文本之間fingerprint值的海明距離。