面試題：怎樣快速找出兩兩相似的數組？

01-03

有2000萬個數組，每個數組等長且長度大於100。這裡數組相似的定義是：倆個數組對應下標的元素有百分之八十以上相等即可。如何在2000萬個數組裡較快找出所有兩兩相似的數組？
相等舉例：倆個數組分別為a,b長度為6.
對應下標相等的元素分別為 a0=b0.a2=b2.a3=b3.a4=b4.a5=b5
有六分之五相等，大於百分之八十，根據定義，這倆個數組相等。
2000萬數組中元素都是互相重排列。

比如三個元素的數組
數組1中的元素是1，2，3
數組2中的可能就是 2，1，3或其它排列（相等的定義如上所述）
允許結果有極小的誤差，也就是說，這是個實際的統計問題，精確演算法雖然更好，但不是必須的。

這個問題很像生物信息學分析的問題，特別是對環境菌群的marker基因進行高通量測序之後的分析工作。「倆個數組對應元素有百分之八十以上相等即可」這句話，簡直讓我直接想到了「OTU聚類相似性閾值為80%」。

實際的數據分析情景里，有很多允許引入誤差的簡化姿勢，以大幅度減少計算量。比如：

以聚類代替所有個體的兩兩相等比較，
以抽樣比較代替全體比較，
兩兩比較的時候，以K子串成分代替序列本身。

本來想用simhash之類的高級技巧的，結果測試之後，綜合表現還不如下面這個簡單粗暴的辦法:

基於如下事實:

例如[1,3,5,4,2]與 [1,3,5,2,4] 相似, 所以隨機抽取下標[0,2]得到[1,5]以及[1,5]兩個hash也很可能一致。

例如[1,3,5,4,2]與 [1,5,3,2,4] 不相似, 所以隨機抽取下標[0,2]得到[1,5]以及[1,3]兩個hash更可能不一致。

隨機選用20組，每組5個位置的(數字+位置)的字串代表數組本身，然後通過hash索引的方式幹掉，下面的super_check()是核心代碼。

2. 時間空間分析

大概公式請查看super_check函數的注釋，本例子的

召回度估計可以是99.96%, 精確100%，時間「幾乎」是隨干擾項（干擾項指的是接近完全隨機的其他數組）的增長而線性增長，額外空間10G內存*某hash的空間放大係數（2000萬的時候）。

具體過程看下面注釋以及代碼，自帶demo測試。

時間、空間、召回的評估不是很嚴格，大概是那個數字。

3. 其他

暫時不考慮並行計算，只考慮單核演算法部分。

暫時不考慮逆向的針對攻擊，比如：構造長度是120，然後大部分的數組的前面50個數字都是一摸一樣的，而後70個數字卻幾乎隨機。。這種特定的干擾有可能導致演算法退化成類似N * N的時間複雜度。一個可能的思路是先過一遍數組，如果發現某些位置出現的數字過於單一，則那個位置就盡量不要進入hash索引的抽樣串中。

具體情況攻防情況可能會很複雜，不再展開分析。

Talk is cheap， there is the code：

import random import copy import time


datas = []

arr_len = 50  # 每個數組長度， 可以調成120之類的，時間線性增長，注意和相似部分的參數構造關係

def init():

    # 3000條無關的干擾

    # 3000干擾項可以自己調節， 比如調節成10萬, python計算速度很渣，比較大的數據建議用其他語言。

    for num in range(3000):

        row = [i for i in range(1, arr_len)]

        random.shuffle(row)

        datas.append(row)

    # 刻意引入400組大量可能兩兩相似的部分

    for k in range(400):

        row = [i for i in range(1, arr_len)]

        random.shuffle(row)

        for index in range(6):

            sub_row = copy.copy(row)

            for _ in range(3):

                i = random.randint(0, arr_len-2)

                j = random.randint(0, arr_len-2)

                sub_row[i], sub_row[j] = sub_row[j], sub_row[i]

            datas.append(sub_row)
total_sub_check = 0  # 調用sub_check次數統計
def sub_check(row_1, row_2):

    global total_sub_check

    total_sub_check += 1

    l = len(row_1)

    count = 0

    for i in range(len(row_1)):

        if row_1[i] == row_2[i]:

            count += 1

    if count &>= 0.8 * l:  # 80%的標準

        return True

    return False
def check():

    # 全部檢查一遍

    c = 0

    for i in range(len(datas)):

        for j in range(i + 1, len(datas)):

            if sub_check(datas[i], datas[j]):

                c += 1

    print "true pair:", c
def super_check():

    # 核心演算法代碼

    # 空間換時間的基本策略

    # 基於如下事實:

    # 例如[1,3,5,4,2]與 [1,3,5,2,4]  相似, 所以 隨機抽取下標[0,2]得到[1,5]以及[1,5]兩個hash也很可能一致 。

    # 例如[1,3,5,4,2]與 [1,5,3,2,4] 不相似, 所以 隨機抽取下標[0,2]得到[1,5]以及[1,3]兩個hash更可能不一致 。

    # 對於每一個數組，抽取parts組, 每一組使用width個隨機下標作為，該數組的hash標記, 兩兩hash一致的數組更有可能相似度高。

    # 根據arr_len, 適當調節width, parts

    # 額外空間 width * parts * row_nums(真實情況下2000w) * (每個字長度一般不超過5) byte, 也可以考慮壓縮成256進位類似ascii碼的東西, 更加節約空間

    # **在python中表示次方, 2**3 = 8    2.5**2 = 6.25

    # 時間複雜度是O((2000w * 2000w/X + 2000w) * parts), 當arr_len比較大時X最大可以是arr_len**width

    # 精確100%，召回估計, 1- (1-0.8**width)**parts

    width = 5

    parts = 20

    dics = [{} for i in range(parts)]

part_index = 0 index_arr = [] while part_index &< parts: # 1: arr_len的數組, 所以這裡減去1 row = [i for i in range(arr_len - 1)] random.shuffle(row) if row[:width] not in index_arr: index_arr.append(row[:width]) part_index += 1 pair_set = set() prefix = len(datas[0]) + 1 for data_index, data in enumerate(datas): tmp_arr = [] for i in range(parts): v = "".join([str(prefix * p + data[tmp_i]) for p, tmp_i in enumerate(index_arr[i])]) if v not in dics[i]: dics[i][v] = [] else: for candidate_index in dics[i][v]: if candidate_index in tmp_arr: continue if sub_check(datas[data_index], datas[candidate_index]): tmp_arr.append(candidate_index) pair_set.add((data_index, candidate_index)) dics[i][v].append(data_index) print "predict pair:", len(pair_set) init() t1 = time.time() super_check() t2 = time.time() print total_sub_check print "super_check() costs", t2 - t1 check() t3 = time.time() print total_sub_check print "check() costs", t3 - t2

確認下題目，所以假設數組長度為x,即共有x個不同數，隨機散布？是不是？

到底是相等還是相似啊，姑且認為是相似吧。

N個數組最多會產生 $N^2$ 對結果，而兩兩比較也需要 $N^2$ 次比較，如果數組長度為L的話，那直接兩兩比較的解法的漸進複雜度是O( $N^2L$ )。

由於相似不像相等具有傳遞性，如果一定要精確結果， $N^2$ 次比較，每次兩個數組至少比較0.2L個元素，這部分計算量是跑不掉的。

允許結果有極小的誤差——這個條件很模糊，極小是多小。如果太小，那其實和精確比較沒什麼區別。如果這個條件放鬆一些，就可以繼續考慮。

不知道數組有沒有什麼特性，比如完全相同的數組的分布如何？存不存在某些位集中在某幾個值，抑或是接近完全隨機排列？

如果是幾乎完全隨機排列形成的數組，那可以使用多種Locality Sensitive Hashing映射到不同的bucket，然後在桶內比較。由於是完全隨機排列的，分到桶的元素理論上會比較均勻，這樣可以大大減少比較次數。當然也有問題，比如一些相同的「邊緣份子」會被分到不同的桶，導致遺漏。但是如果分桶的時候分得比較粗，或者用不同的LSH多做幾次會減少這種情況的發生。而且平均遺漏的個數是可以計算並調整的——這樣就可以有一個「誤差大小」跟「運行速度」的取捨。

如果數據的分布比較扭曲，存在大量高度相似的數組，那可以考慮先利用數據分布的統計信息進行降維，比如99%的數組在某一位都是相同的，那就可以刪除這一維，再使用LSH，這樣能夠一定緩解映射之後大量元素仍然分布在同一個桶中的概率。當然降維會導致信息丟失，有可能會導致遺漏，但是這部分損失的期望也是可以算出來的。

個人感覺這作為一道面試題綜合性還是比較強的，考察得比較全面，要問可以問很深，比如遺漏的期望，複雜度的計算；優化的思路，如何用精度換速度；編程細節上面的細節優化，比如比較的時候如果已經有20%不一樣就沒必要比較下去了，等等。

這個問題在圖像處理的時候會碰到，而且一般是後一種情況。

比如我在做畢業設計（班主任之眼！——看穿彥正瑪少女の薄紗）的時候就需要將稍有變化（有少量噪點和色差）的圖片合併起來，其實本質上就是將幾千萬個「相似」的向量合併的問題。

我們當時的做法是這樣的，左上角是原圖，用灰度圖二值化以後做一次粗hash，再用RGB三個通道二值化之後拼成一個0/1的向量作為圖像進行合併，最後在hash的位數上做了調整取到了一個不太影響模型精度、計算量又在我們的錢包可以承受範圍內的值。

論文地址：https://arxiv.org/pdf/1705.07768.pdf

進行一次O(1/2*(n^2-n))遍歷，為了追求高效可以從數據規模進行轉換，數組比較不看80的相似度而是看20的不相似度，加速精確匹配，但結論上允許不絕對的精確，。那就可以進一步減少數據規模，比如，數據統計1234567，其中6和7的分布較少，那就直接得出帶有6和7的數組較大概率認為不相似度較高被移除，當然，這是為了加速得出模糊結果所做的優化。

可以用80%的元素建立索引。

比如數組長度為5，有1，2，3，4，5這組數據。分別用1234，2345，1235，1245，1345建立索引。建立索引時候要先排序。

假設有另外的一個數組，23456，有一個索引是2345，跟上面的一個索引匹配，就判定相同。

有人說提議是元素下標對應相同才是相同，只需要索引時按照下標索引即可，不需要排序了，上面舉例的12345改成下標12345對應的元素即可（下標從1開始）

分段hash吧，然後同hash的串再互相比較。就像四叉樹那樣的，劃分一下。

可以隨機嗎。。。。

既然沒提空間複雜度，我就當作內存無限來做了。

數組長N，匹配長度L，誤差個數為K。（如果L為5，相識度為80%，那K就是1）

掃描數組A生成一個巨大的，產生所有可能匹配的項。時間複雜度O(N)，空間複雜度O((N-L+1)*C(K,L))。C是排列組合。比如，A中的前5個能夠被（*,a1,a2,a3,a4),（a0,*,a2,a3,a4)...這5個匹配。
用以上的匹配數組生成自動機。上面的數組用或連接變成一個正則表達式。好像時間複雜度是O((N-L+1)*C(K,L)*L).
然後用這個自動機去匹配B就好了。O(L*N)。好像還能優化。

因此複雜度大概就是O(N*L^3)。

可以嘗試這麼做：

1、將所有元素求N次方和（N大於0）

2、根據和的值對數組進行排序

懶人法

3.1、相鄰兩個數組分為一組

非懶人法

3.2.1、將兩兩數組的和做減法，取差的絕對值

3.2.2、將差的值不大於M（M大於等於0，建議第一次運算取0，以後運算取差的中位數或者三分位）的數組分為一組，如果在有三組或以上，縮小M的值，對該小段數組繼續進行3.2.2操作，如果M==0，隨機兩兩分成一組，餘下的返回到未兩兩分組的序列里

3.2.3、對餘下未分組的數組，重複從3.2.1開始運算，指導餘下數組數不大於1

舉例：

取N=1

a1=｛2，3，4｝

a2=｛1，3，5｝

a3=｛2，4，3｝

a4=｛3，4，5｝

排序

a2=｛1，3，5｝

a1=｛2，3，4｝

a3=｛2，4，3｝

a4=｛3，4，5｝

懶人結果：｛a2，a1｝，｛a3，a4｝誤差較大

非懶人結果｛a1，a3｝，｛a2，a4｝誤差較小

kd-tree

輸出所有兩兩等價的數組本身就要O(n^2)了

隨機滿足大數定律即可

說到允許誤差，難道不是先考慮布隆過濾器嗎

我的想法是

1, 建立一個字典(記錄其中兩兩數組相同元素個數,假設) 從1-1到1-2000萬，2-1到2000萬，……最後19999999-2000萬。

2, 依次判斷兩兩數組相同元素的個數(倆個數組對應下標的元素)，然後記錄在字典中 (判斷相同 value增1)

3, 字典中值大於80%(值/數組長度的比值)的兩數組即為所求數組

首先定性，這個是個比較簡單的聚類問題

可以把每個數組理解成一個100維以上的變數，每個變數之間的距離就是對應下標不同的數量之和

可以通過各種聚類的演算法，算出這2000萬個樣本點能夠聚成多少個我們接受大小的團

聚類演算法就很多了，隨便說個最簡單的，比如k-means

這個是一個常見的NP問題

問題可以轉化成矩陣中的子矩陣來求解。

只提一個百度搜索得到的解決方法給你 http://pubs.acs.org/doi/abs/10.1021/ci8003013

真正的原理涉及到很多，就不一一解答了。有空去看下畫一個分子式，怎麼查找含有這個結構式的所有物質出來。其中就包含有你這種演算法！

個人感覺可以把這2000萬個元素抽象到一個n維空間，然後用聚類演算法找出多個聚集團。

通過限制團直徑來讓團內元素兩兩相似。

如果元素的值範圍是常量k的話可以轉換緯度，時間換空間：轉換成k個長度為2000w的數組，數組的元素為有或無。取這些數組的排列C(k*0.8,k)即可

由於等長，每個數組抽象成相同大小圖形