n個list，求兩兩相似度大約70%的list的組合？

01-16

手頭有n個list（n&>7000k)，每個list大約30個左右的相同格式字元串（10位0-z），求兩兩相list元素重複率大於%70的list的組合。
這裡有個類比總是誤導答題者，我給去掉了

能想到的解法是講所有list元素建立倒排索引，通過倒排索引減少兩兩頁面的對比次數。但最壞情況下還是避免不了n方的時間複雜度。
請問各位大牛有什麼更好的解法嗎

這是一個All-Pairs Similarity Search （APSS）的問題。即，

給定一個數據集 $mathcal{D} = {o_1, o_2, cdots, o_n}$ ，一個相似性函數 $mathsf{sim}$ ，和一個閾值 $t$ ，找到所有滿足 $mathsf{sim}(o_i, o_j) geq t$ 的 $(o_i, o_j)$ 對。

對應於你的問題， $mathcal{D} = {ell_1, ell_2, cdots, ell_n}$ ，其中， $ell_i$ 代表一個list，每個list包含了30個左右的字元串。因為你沒有特別指明 $mathsf{sim}$ 的定義，這裡假設 $mathsf{sim}(ell_i, ell_j) = frac{|ell_i cap ell_j|}{|ell_i cup ell_j|}$ ，即， $ell_i$ ， $ell_j$ 的交集的大小與 $ell_i$ ， $ell_j$ 的並集的大小的比值。換句話說，我們把每個list都當作一個集合。這裡 $mathsf{sim}$ 也稱作Jaccard相似性度量。我們也可以用其他常用的相似性度量，比如Cosine，Edit Distance，Overlap等等，但演算法的原理是類似的。問題中，閾值 $t$ 為0.7。

APSS問題的演算法可粗略分成兩類：精確演算法和近似演算法。精確演算法包括但不限於All-Pairs, PPJoin, PPJoin+, L2AP等等。All-Pairs，PPJoin，PPJoin+是非常經典的工作，提出了很多高效的剪枝策略。比如說，All-Pairs中基於前綴的剪枝，PPJoin中基於位置的剪枝和PPJoin+中基於後綴的剪枝。L2AP是相對比較新的工作，用Cauchy-Schwarz不等式推出的bound來做剪枝。近似演算法包括 ATLAS，Bayesian LSH，LSH等等。相比精確演算法，它們能在 $t$ 相對比較小的情況下，更快地找出結果來，儘管結果可能有誤差。ATLAS的預處理部分跟前面 vczh 提到的比較像，其用affinity propagation演算法預先把數據分成幾個類（類與類之間允許有重疊），然後再在各個類的內部用signature的方法求解APSS。Bayesian LSH效果不錯，但是沒有一個理論上的bound。

下面主要介紹一下PPJoin。它是精確演算法裡面非常經典的工作（Mining of Massive Datasets裡面有專門一章講LSH和PPJoin），而且（當閾值比較高的時候）效率很高。代碼可從Efficient Similarity Query Processing下載。PPJoin的基本數據結構是一個倒排索引。對應於你的問題，這個索引的key是字元串。對於字元串 $s$ ，用 $I_s$ 表示其對應的倒排表。下面，從最簡單的演算法開始，我們依次介紹PPJoin的各個優化。

（1） Naive演算法

這是你題目中描述的方法，偽代碼如下。一開始，倒排索引是空的。對於 $mathcal{D}$ 中的每個list $ell$ （第3行），我們維護一個candidate的集合，即所有與 $ell$ 的相似性有可能大於等於 $t$ 的list。我們遍歷 $ell$ 中的所有字元串（第5行）。其中， $ell$ 的第 $i$ 個字元串用 $ell[i]$ 表示。如果一個list $ell$ 與 $ell$ 共享了一個字元串，我們就認為它是一個candidate，並把 $ell$ 加入 $mathcal{C}$ （第8行）。找到所有candidate之後，我們會把 $ell$ 也插入倒排表（第9行）。第10到12行是驗證一個candidate是否真的滿足要求。

這個演算法有兩個不好的地方：（a）消耗的空間過多，每個list都要放進它所包含的字元串的倒排表中；（b）兩個list， $ell$ 和 $ell$ ，會被認為是候選對，只要它們共享了一個字元串，這樣誤差會很大。PPJoin加了以下剪枝的優化。

（2）基於大小的剪枝

對於兩個list $ell$ 和 $ell$ ，我們有：

$mathsf{Jaccard}(ell, ell$

也就是說，

剪枝1： 只有當 $|ell$ 時， $mathsf{Jaccard}(ell, ell$ 才有可能大於等於 $t$ 。

（3）基於前綴的剪枝

對於兩個list $ell$ 和 $ell$ ，由 $|ell cup ell$ ，我們有：

$mathsf{Jaccard}(ell, ell$

注意，這裡用的是 $Leftrightarrow$ 符號，即這些條件是等價的。正式地，

剪枝2：假設 $O$ 是 $mathcal{D}$ 中所有的字元串的一種排序，並且所有list的字元串都按照 $O$ 這個順序從小到大排。對於兩個list $ell$ 和 $ell$ ，令 $alpha = lceil frac{t}{1+t}(|ell| + |ell$ 。如果 $mathsf{Jaccard}(ell, ell$ ，那麼 $|ell cap ell$ ，那麼 $ell$ 的前 $|ell| - alpha + 1$ 個字元串與 $ell$ 的前 $|ell$ 個字元串必然有非空的交集。換句話說，如果交集為空，則 $mathsf{Jaccard}(ell, ell$ 。

注意這裡要求每個list的字元串都按照某個給定的順序 $O$ 排列，否則結論可能不成立。 $O$ 一般按照字元串在 $mathcal{D}$ 中的出現頻率將字元串從小到大排。

這個剪枝說明我們只需要考慮 $ell$ 的一小部分前綴，就可以找出所有的candidate，從而減少了產生的candidate的數量；另外，我們也只需要把 $ell$ 保存在前綴所對應的那部分字元串的倒排表裡，從而減少了空間消耗。考慮到我們並不能提前知道 $|ell$ 的大小，我們需要求前綴長度的一個上界。由剪枝1，我們知道我們只需要考慮滿足 $|ell$ 的 $ell$ ，因此，前綴長度的一個上界是：

$|ell| - alpha + 1 leq |ell| - lceil frac{t}{1+t}(|ell| + t|ell|) ceil + 1 = |ell| - lceil t|ell| ceil + 1 = p$

下面給出加了這兩個剪枝的演算法。紅色部分為與前一個演算法的不同。我們先把所有list按照大小從小到大排序，這樣有利於基於大小的排序發揮效果。第6行我們計算了前綴的可能最大長度。第7行我們只考慮前綴裡面的字元串。第9行利用大小進行剪枝。

（4）基於位置的剪枝

剪枝3：假設 $O$ 是 $mathcal{D}$ 中所有的字元串的一種排序，並且所有list的字元串都按照 $O$ 這個順序從小到大排。我們用 $ell_l(i)$ 表示 $ell[1, 2, cdots, (i-1)]$ ，即 $ell$ 的前 $i-1$ 個字元串；用 $ell_r(i)$ 表示 $ell$ 剩餘的部分。對於兩個list $ell$ ， $ell$ 和兩個整數 $i$ ， $j$ ，如果 $mathsf{Jaccard}(ell, ell$ 且 $ell[i] = ell$ ， $|ell_l(i) cap ell$ 。

我們可以利用這個剪枝來進一步減少產生的candidate。代碼如下（紅色部分為新添加的代碼）。在PPJoin裡面，倒排表額外存了位置信息。比如，如果 $(ell, i) in I_s$ ，那麼 $s$ 是 $ell$ 的第 $i$ 個字元串。演算法中，第5行創建了一個hash map，用來存儲一個list $ell$ 與 $ell$ 目前的交集的大小。隨著我們掃描更多 $ell$ 裡面的字元串， $h[ell$ 會逐漸增大。第11行計算了 $ell$ 與 $ell$ 未掃描部分的交集可能的最大大小。第12行利用了基於位置的剪枝。不滿足條件的 $ell$ 的 $h[ell$ 會被清零。在第15行的Verify裡面，我們只考慮那些 $h[ell$ 非零的list。關於Verify函數，原理相似，不再詳述，有興趣的可以看看原論文。

如果樓主list的例子是來源於比較兩個網頁的相似度，NLP領域裡面這方面的研究不少，不過這更像是一個系統的工程，從網頁爬取時候的來源鏈接，網頁上的摘要（有不少摘要提取演算法，這些演算法會考慮HTML標籤），到抽取網頁主體，分詞並去除無意義的干擾詞，然後最後比較兩個網頁的分詞結果的向量夾角。有時候前面的步驟能提供不少有價值的信息，如果排除掉這些步驟，直接進入最後一步比較list 相似度，那麼有點類似兩個set的交集(intersection)的問題。比如

Set S1 ： A B C D E（對英文就是一個單詞，排除各種複數、過去式；對中文就是分詞）

Set S2:：B F Q U E V D

是不是可以認為如果S1中包含S2中70%的單詞，那麼S1跟S2相似；反之亦然。

就這個小的點來說，也有不少值得考量的：

1. S1包含S2 70%的單詞，反之不成立，比如一篇文章是另一篇的其中一個段落，那麼想嚴格點就正反個計算一次，都是70%才OK；寬鬆點就是只要一個方向70%就可以了；

2. 有些單詞可以有不同的權重，比如文章A出現了計算機5次，出現了人工智慧1次，跟文章B出現計算機1次，出現人工智慧5次的就可能不相似

3. 某些常見詞單詞不應該被考慮，比如很、非常、激動人心，這方面文章摘要演算法已經做得不錯了，比如bing 搜索 abstract extraction of document

4. 快速確認一個單詞在另外的set中是否存在，可以考慮bloomfilter，這些計算好的bloomfilter可以保存起來，這樣整體上應該也能提高效率

最後，搜索similarity of html document會有不少文章，如果不是發論文，國際一流會議上的此類論文提到的思路中選一個最簡單的就可以滿足一般性的需求，重點是工程實現。

如果有錢，貌似這家提供服務，gensim: topic modelling for humans

This module contains functions and classes for computing similarities across a collection of documents in the Vector Space Model.

The main class is Similarity, which b...

當時在MSRA做過類似的演算法，是針對圖像的。大框架就是，你要是要把他們分類，同一個類下面的再去n2去重，這樣雖然你的演算法複雜度沒有降低，還是會被搞競賽的圖樣指手畫腳，但是最高項的常數可以猛減幾萬倍，從不可用變成可用。

轉成餘弦相似度來計算.

給"字元串"編號.轉向量,這樣list就變成一個稀疏向量.

然後兩兩求餘弦夾角.70%是多少度你可以自己試驗下.向量的模可以預先計算存起來.

複雜度還n方,但是常數應該要比比較2個list快

n-gram min-hash.

把每個 list 先轉變成一個 signature, 比較 list 之前先比較 signature。假如 signature相似，在掃原list 進行計算。

怎麼變Signature 根據可具體應用變化。

1. 假如vocabulary 不大的話直接變成單詞vector 表示。

2. 大的話可以參考 Minhash 計算 set similarly, 還有 locality sensitive hashing 相關內容。

關於題主提到的基於倒排列表的方法，我舉一個簡單的例子，來說明這個方法的弊端。

考慮一個常用詞（比如is），它對應的倒排條目幾乎覆蓋了所有的句子，而每次選取candidates時，都會選擇當前句子中各個token對應的倒排項的並集，這麼一來相當於每次都要和幾乎全部其他項比較，因此是非常慢的。所以這一方法的主要問題就是理論最壞情況在現實中很常見。

基於前綴的方法

@K-ZhY 已經介紹了PPJoin，在此就不加以贅述了。這裡只補充一點，PPJoin是一種fixed-length prefix filtering的方法，在jaccard閾值比較低的情況下，prefix會變得很長，因此也有針對這方面的改進。

比如李國良老師他們在2012年的一個工作Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search

記得斯坦福公開課Mining of Massive Datasets里有一章跟這個類似(Chapter 3 - Finding Similar Items)，不知道能不能幫助樓主。

教材：http://infolab.stanford.edu/~ullman/mmds/ch3.pdf

PPT: http://www.mmds.org/mmds/v2.1/ch03-lsh.pdf

Youtube:https://www.youtube.com/watch?v=c6xK9WgRFhI

之前在1號店工作的時候做過類似的，總體的和輪子說的很類似，但是有點差別，具體場景是這樣的，我們有kw級別的sku，想找出每個sku的top20 相似品，每一個sku經過MF是隱向量，大概200維，我們在這之後做一個Kmean的聚類（K值按你最後聚類出來的最大的簇做適當修改）然後當一個sku要計算時，我們先找到其簇號，然後在簇內找相似性最高的top 20的sku，沒有用Kmeans之前，演算法基本是跑不出來的，用了Kmeans之後印象中job只跑了幾個小時

先想辦法分桶，然後再把字元串折算成編號

1。如果字元串少的話，用bit array存儲，比較的時候直接異或，計算1的數量是否滿足70%

2。如果字元串多的話，用array存儲，n^2比較時間

難點在於列表的排序吧

要是數組就好辦多了