漢明距離分治演算法

① 分治的設計步驟

1. 劃分步：把輸入的問題劃分為k個子問題，並盡量使這k個子問題的規模大致相同。
2. 治理步：當問題的規模大於某個預定的閾值n0時，治理步由k個遞歸調用組成。
3. 組合步：組合步把各個子問題的解組合起來，它對分治演算法的實際性能至關重要，演算法的有效性很大地依賴於組合步的實現。
分治法的關鍵是演算法的組合步。究竟應該怎樣合並，目前沒有統一的模式，因此需要對具體問題進行具體分析，以得出比較好的合並演算法。

② 感知哈希演算法

感知哈希演算法是一類哈希演算法的總稱，其作用在於生成每張圖像的「指紋」(fingerprint)字元串，比較不同圖像的指紋信息來判斷圖像的相似性。結果越接近圖像越相似。感知哈希演算法包括均值哈希（aHash）、感知哈希（pHash）和dHash（差異值哈希）。
aHash速度較快，但精確度較低；pHash則反其道而行之，精確度較高但速度較慢；dHash兼顧二者，精確度較高且速度較快。
在得到64位hash值後，使用漢明距離量化兩張圖像的相似性。漢明距離越大，圖像的相似度越小，漢明距離越小，圖像的相似度越大。

a) 縮放圖片：為了保留圖像的結構，降低圖像的信息量，需要去掉細節、大小和橫縱比的差異，建議把圖片統一縮放到8*8，共64個像素的圖片；
b) 轉化為灰度圖：把縮放後的圖片轉化為256階的灰度圖；

c) 計算平均值： 計算進行灰度處理後圖片的所有像素點的平均值；
d) 比較像素灰度值：遍歷灰度圖片每一個像素，如果大於平均值記錄為1，否則為0；
e) 構造hash值：組合64個bit位生成hash值，順序隨意但前後保持一致性即可；
f) 對比指紋：計算兩幅圖片的指紋，計算漢明距離。

感知哈希演算法可以獲得更精確的結果，它採用的是DCT（離散餘弦變換）來降低頻率。
a) 縮小尺寸
為了簡化了DCT的計算，pHash以小圖片開始（建議圖片大於8x8，32x32）。
b) 簡化色彩
與aHash相同，需要將圖片轉化成灰度圖像，進一步簡化計算量（具體演算法見aHash演算法步驟）。
c) 計算DCT
DCT是把圖片分解頻率聚集和梯狀形。這里以32x32的圖片為例。

d) 縮小DCT
DCT的結果為32x32大小的矩陣，但只需保留左上角的8x8的矩陣，這部分呈現了圖片中的最低頻率。
e) 計算平均值
如同均值哈希一樣，計算DCT的均值
f) 進一步減小DCT
根據8x8的DCT矩陣進行比較，大於等於DCT均值的設為」1」，小於DCT均值的設為「0」。圖片的整體結構保持不變的情況下，hash結果值不變。
g) 構造hash值
組合64個bit位生成hash值，順序隨意但前後保持一致性即可。
h）對比指紋：計算兩幅圖片的指紋，計算漢明距離。

相比pHash，dHash的速度更快，相比aHash，dHash在效率幾乎相同的情況下的效果要更好，它是基於漸變實現的。
a) 縮小圖片：收縮至9*8的大小，它有72的像素點；
b) 轉化為灰度圖：把縮放後的圖片轉化為256階的灰度圖。（具體演算法見aHash演算法步驟）；
c) 計算差異值：計算相鄰像素間的差異值，這樣每行9個像素之間產生了8個不同的差異，一共8行，則產生了64個差異值；
d) 比較差異值：如果前一個像素的顏色強度大於第二個像素，那麼差異值就設置為「1」，如果不大於第二個像素，就設置「0」。
e) 構造hash值：組合64個bit位生成hash值，順序隨意但前後保持一致性即可。
f) 對比指紋：計算兩幅圖片的指紋，計算漢明距離。

③ 均值哈希演算法和感知哈希演算法

1.離散餘弦變換

離散餘弦變換由於為數據與餘弦函數乘積累計，將無規律數列改為規則排列，如圖像數據原數據為無規則二維矩陣，離散餘弦變換後矩陣左上角包含圖像數據的低頻信息部分，右下角為高頻信息部分，低頻信息為圖像主體框架，高頻信息記錄圖像細節，去掉50%高頻信息存儲部分，圖像信息量損失不超過5%(未驗證此數據)，常用於圖像壓縮(如jpeg圖像)

2.漢明距離

兩個字碼中不同位值的數目叫漢明距離，即a^b後驗證結果的非0個數即為漢明距離

3.均值哈希演算法和感知哈希演算法

均值哈希演算法和感知哈希演算法常用於相似圖像識別，將基準圖縮小為較小尺寸圖片，均值哈希演算法計算圖像平均像素值(未驗證添加權值，理論可使圖像部分區域具有更大權重)，然後將每個元素點與平均像素值比較，大於或等於均值，記為位1，小於均值記為位0，得到一串哈希值；感知哈希演算法先進行離散餘弦變換，取矩陣左上角區域數據(圖像低頻信息區域)，計算均值並將每個數值與均值比較，得到一串哈希值。在原圖片中取相同大小圖片，計算出另一串哈希值，得到兩串哈希值漢明距離，值越小兩張圖片相似度越高

④ 分治法指的是什麼呢

分治法指的是將原問題遞歸地分成若干個子問題，直到子問題滿足邊界條件，停止遞歸，將子問題逐個解決（一般是同種方法），將已經解決的子問題合並，最後，演算法會層層合並得到原問題的答案。

分治演算法步驟：

分：遞歸地將問題分解為各個的子問題（性質相同的，相互獨立的子問題）。

治：將這些規模更小的子問題逐個擊破。

合：將已解決的問題逐層合並，最終得出原問題的解。

分治法適用條件

1、問題的規模縮小到一定的規模就可以較容易地解決。

2、問題可以分解為若干個規模較小的模式相同的子問題，即該問題具有最優子結構性質。

3、合並問題分解出的子問題的解可以得到問題的解。

4、問題所分解出的各個子問題之間是獨立的，即子問題之間不存在公共的子問題。

⑤ 演算法設計與分析|5個演算法

1）分治法

對於一個規模為n的問題，若該問題可以容易地解決（比如說規模n較小），則直接解決；否則將其分解為k個規模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然後將各子問題的解合並得到原問題的解。

2）回溯法（深度優先）

回溯法是一種選優搜索法，按選優條件向前搜索，以達到目標。但當搜索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇。這種走不通就退回再走的技術就是回溯法。

3）貪心法

總是做出在當前來說是最好的選擇，而並不從整體上加以考慮，它所做的每步選擇只是當前步驟的局部最優選擇，但從整體來說不一定是最優的選擇。由於它不必為了尋找最優解而窮盡所有可能解，因此其耗費時間少，一般可以快速得到滿意的解，但得不到最優解。

4）動態規劃法

在求解問題中，對於每一步決策，列出各種可能的局部解，再依據某種判定條件，舍棄哪些肯定不能得到最優解的局部解，在每一步都經過篩選，以每一判瞎步都是最優解來保證全局是最優解。

5）分支限界法（廣度優先）

分治演算法求出的子問題是互相獨立的。

動態規劃演算法具有最優子結構性質和重疊子問題性質。

貪心演算法不追求最優解，只求可森早行解，因此不具備最優子結構的特性。

回溯演算法把問題的解空間轉化成圖或者樹結構，然後使用深度優先搜索策略進行遍歷，遍歷的過程中記錄和尋找所有可此沖雀行解或者最優解。

分支限界演算法類似於回溯演算法，它以廣度優先方式搜索解空間樹。

⑥ 分治演算法是什麼呢

分治演算法的基本思想是將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。即一種分目標完成程序演算法，簡單問題可用二分法完成。

解題步驟

分治法解題的一般步驟：

（1）分解，將要解決的問題劃分成若干規模較小的同類問題；

（2）求解，當子問題劃分得足夠小時，用較簡單的方法解決；

（3）合並，按原問題的要求，將子問題的解逐層合並構成原問題的解。

⑦ 分治演算法時間復雜度

一：分治演算法和遞歸
1.簡述遞歸

我們要講到分治演算法，我覺得有必要說一下遞歸，他們就像一對孿生兄弟，經常同時應用在演算法設計中，並由此產生許多高效的演算法。
直接或間接的調用自身的演算法稱為遞歸演算法。用函數自身給出定義的函數稱為遞歸函數。

int fibonacci(int n){
if (n <= 1) return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
先簡單看一下經典的遞歸例子，博主會找個時間系統詳細的總結一下關於遞歸的內容。

2.簡述分治

分治法的設計思想是：

分–將問題分解為規模更小的子問題；
治–將這些規模更小的子問題逐個擊破；
合–將已解決的子問題合並，最終得出「母」問題的解；
一個先自頂向下，再自底向上的過程。

凡治眾如治寡，分數是也。—孫子兵法

3.分治法與遞歸的聯系

由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。

二：分治法的適用條件
分治法所能解決的問題一般具有以下幾個特徵：

1) 該問題的規模縮小到一定的程度就可以容易地解決
2) 該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質。
3) 利用該問題分解出的子問題的解可以合並為該問題的解；
4) 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。

第一條特徵是絕大多數問題都可以滿足的，因為問題的復雜性一般是隨著問題規模的增加而增加；

第二條特徵是應用分治法的前提它也是大多數問題可以滿足的，此特徵反映了遞歸思想的應用；、

第三條是關鍵，能否利用分治法完全取決於問題是否具有第三條特徵，如果具備了第一條和第二條特徵，而不具備第三條特徵，則可以考慮用貪心法或動態規劃法。

第四條特徵涉及到分治法的效率，如果各子問題是不獨立的則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然可用分治法，但一般用動態規劃法較好

三：分治法的基本步驟
分解問題：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；（自頂向下）
這里涉及到一個平衡子問題的思想：人們從大量實踐中發現，在用分治法設計演算法時，最好使子問題的規模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種使子問題規模大致相等的做法是出自一種平衡子問題的思想，它幾乎總是比子問題規模不等的做法要好。

解決問題：如果問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題，以得到小問題的解。
合並結果：將各個子問題的解合並為原問題的解：（自底向上）。
它的一般演算法設計模式如下：
divide-and-conquer(P){
if ( | P | <= n0) adhoc(P); //（2）解決問題：遞歸到小問題，則解決小規模的問題（自頂向下）
divide P into smaller subinstances P1,P2,...,Pk；//（1）分解問題
for (i=1,i<=k,i++)
yi=divide-and-conquer(Pi); //利用遞歸的解各子問題
return merge(y1,...,yk); //將各子問題的解合並為原問題的解（自底向上）
}
四：分治法的復雜性分析
從分治法的一般設計模式可以看出，用他設計出的程序一般是遞歸演算法。因此分治法的計算效率通常可以用遞歸方程來進行分析。
一個分治法將規模為n的問題分成k個規模為n/m的子問題去解。設分解閥值（表示當問題P規模不超過n0時，問題已容易解出，不必再繼續分解）n0=1，且adhoc解規模為1的問題耗費1個單位時間。再設將原問題分解為k個子問題以及用merge將k個子問題的解合並為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規模為|P|=n的問題所需的計算時間，則有：

通常可以用展開遞歸式的方法來解這類遞歸方程，反復帶入求解得

⑧ 分治演算法的應用實例

下面通過實例加以說明： 給你一個裝有1 6個硬幣的袋子。1 6個硬幣中有一個是偽造的，並且那個偽造的硬幣比真的硬幣要輕一些。你的任務是找出這個偽造的硬幣。為了幫助你完成這一任務，將提供一台可用來比較兩組硬幣重量的儀器，利用這台儀器，可以知道兩組硬幣的重量是否相同。比較硬幣1與硬幣2的重量。假如硬幣1比硬幣2輕，則硬幣1是偽造的；假如硬幣2比硬幣1輕，則硬幣2是偽造的。這樣就完成了任務。假如兩硬幣重量相等，則比較硬幣3和硬幣4。同樣，假如有一個硬幣輕一些，則尋找偽幣的任務完成。假如兩硬幣重量相等，則繼續比較硬幣5和硬幣6。按照這種方式，可以最多通過8次比較來判斷偽幣的存在並找出這一偽幣。
另外一種方法就是利用分而治之方法。假如把1 6硬幣的例子看成一個大的問題。第一步，把這一問題分成兩個小問題。隨機選擇8個硬幣作為第一組稱為A組，剩下的8個硬幣作為第二組稱為B組。這樣，就把1 6個硬幣的問題分成兩個8硬幣的問題來解決。第二步，判斷A和B組中是否有偽幣。可以利用儀器來比較A組硬幣和B組硬幣的重量。假如兩組硬幣重量相等，則可以判斷偽幣不存在。假如兩組硬幣重量不相等，則存在偽幣，並且可以判斷它位於較輕的那一組硬幣中。最後，在第三步中，用第二步的結果得出原先1 6個硬幣問題的答案。若僅僅判斷硬幣是否存在，則第三步非常簡單。無論A組還是B組中有偽幣，都可以推斷這1 6個硬幣中存在偽幣。因此，僅僅通過一次重量的比較，就可以判斷偽幣是否存在。
假設需要識別出這一偽幣。把兩個或三個硬幣的情況作為不可再分的小問題。注意如果只有一個硬幣，那麼不能判斷出它是否就是偽幣。在一個小問題中，通過將一個硬幣分別與其他兩個硬幣比較，最多比較兩次就可以找到偽幣。這樣，1 6硬幣的問題就被分為兩個8硬幣（A組和B組）的問題。通過比較這兩組硬幣的重量，可以判斷偽幣是否存在。如果沒有偽幣，則演算法終止。否則，繼續劃分這兩組硬幣來尋找偽幣。假設B是輕的那一組，因此再把它分成兩組，每組有4個硬幣。稱其中一組為B1，另一組為B2。比較這兩組，肯定有一組輕一些。如果B1輕，則偽幣在B1中，再將B1又分成兩組，每組有兩個硬幣，稱其中一組為B1a，另一組為B1b。比較這兩組，可以得到一個較輕的組。由於這個組只有兩個硬幣，因此不必再細分。比較組中兩個硬幣的重量，可以立即知道哪一個硬幣輕一些。較輕的硬幣就是所要找的偽幣。 在n個元素中找出最大元素和最小元素。我們可以把這n個元素放在一個數組中，用直接比較法求出。演算法如下：
void maxmin1(int A[],int n,int *max,int *min)
{ int i;
*min=*max=A[0];
for(i=0;i <= n;i++)
{ if(A[i]> *max) *max= A[i];
if(A[i] < *min) *min= A[i];
}
}
上面這個演算法需比較2(n-1)次。能否找到更好的演算法呢？我們用分治策略來討論。
把n個元素分成兩組：
A1={A[1],...,A[int(n/2)]}和A2={A[INT(N/2)+1],...,A[N]}
分別求這兩組的最大值和最小值，然後分別將這兩組的最大值和最小值相比較，求出全部元素的最大值和最小值。如果A1和A2中的元素多於兩個，則再用上述方法各分為兩個子集。直至子集中元素至多兩個元素為止。
例如有下面一組元素：-13，13，9，-5，7，23，0，15。用分治策略比較的演算法如下：
void maxmin2(int A[],int i,int j,int *max,int *min)
/*A存放輸入的數據，i，j存放數據的范圍，初值為0，n-1，*max,*min 存放最大和最小值*/
{ int mid,max1,max2,min1,min2;
if (j==i) {最大和最小值為同一個數;return;}
if (j-1==i) {將兩個數直接比較，求得最大會最小值；return；}
mid=(i+j)/2;
求i~mid之間的最大最小值分別為max1，min1;
求mid+1~j之間的最大最小值分別為max2，min2;
比較max1和max2，大的就是最大值;
比較min1和min2，小的就是最小值;
} 題目：在一個(2^k)*(2^k)個方格組成的棋盤上，有一個特殊方格與其他方格不同，稱為特殊方格，稱這樣的棋盤為一個特殊棋盤。我們要求對棋盤的其餘部分用L型方塊填滿（註：L型方塊由3個單元格組成。即圍棋中比較忌諱的愚形三角，方向隨意），且任何兩個L型方塊不能重疊覆蓋。L型方塊的形態如下：
題目的解法使用分治法，即子問題和整體問題具有相同的形式。我們對棋盤做一個分割，切割一次後的棋盤如圖1所示，我們可以看到棋盤被切成4個一樣大小的子棋盤，特殊方塊必定位於四個子棋盤中的一個。假設如圖1所示，特殊方格位於右上角，我們把一個L型方塊（灰色填充）放到圖中位置。這樣對於每個子棋盤又各有一個「特殊方塊」，我們對每個子棋盤繼續這樣分割，直到子棋盤的大小為1為止。
用到的L型方塊需要（4^k-1)/3 個，演算法的時間是O（4^k)，是漸進最優解法。
本題目的C語言的完整代碼如下（TC2.0下調試），運行時，先輸入k的大小，(1<=k<=6)，然後分別輸入特殊方格所在的位置(x,y), 0<=x,y<=(2^k-1)。 #include<stdio.h>//#include<conio.h>//#include<math.h>inttitle=1;intboard[64][64];voidchessBoard(inttr,inttc,intdr,intdc,intsize){ints,t;if(size==1)return;t=title++;s=size/2;if(dr<tr+s&&dc<tc+s)chessBoard(tr,tc,dr,dc,s);else{board[tr+s-1][tc+s-1]=t;chessBoard(tr,tc,tr+s-1,tc+s-1,s);}if(dr<tr+s&&dc>=tc+s)chessBoard(tr,tc+s,dr,dc,s);else{board[tr+s-1][tc+s]=t;chessBoard(tr,tc+s,tr+s-1,tc+s,s);}if(dr>=tr+s&&dc<tc+s)chessBoard(tr+s,tc,dr,dc,s);else{board[tr+s][tc+s-1]=t;chessBoard(tr+s,tc,tr+s,tc+s-1,s);}if(dr>=tr+s&&dc>=tc+s)chessBoard(tr+s,tc+s,dr,dc,s);else{board[tr+s][tc+s]=t;chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}voidmain(){intdr=0,dc=0,s=1,i=0,j=0;printf(printinthesizeofchess: );scanf(%d,&s);printf(printinspecalpointx,y: );scanf(%d%d,&dr,&dc);if(dr<s&&dc<s){chessBoard(0,0,dr,dc,s);for(i=0;i<s;i++){for(j=0;j<s;j++){printf(%4d,board[i][j]);}printf( );}}elseprintf(thewrongspecalpoint!! );getch();}

⑨ 分治演算法幾個經典例子

分治法，字面意思是「分而治之」，就是把一個復雜的1問題分成兩個或多個相同或相似的子問題，再把子問題分成更小的子問題直到最後子問題可以簡單地直接求解，原問題的解即子問題的解的合並，這個思想是很多高效演算法的基礎。

圖二

大整數乘法

Strassen矩陣乘法

棋盤覆蓋

合並排序

快速排序

線性時間選擇

最接近點對問題

循環賽日程表

漢諾塔

⑩ 文本相似度之Sim_hash演算法

    本文記錄的目的是方便自己學習和復習，有誤之處請諒解，歡迎指出。

    最近項目有用到Sim_hash，做個簡單記錄。

    Sim_hash是Google用來處理大量文本去重的演算法，屬於 局部敏感哈希（Locality Sensitive Hashing，LSH） ，LSH哈希能夠使兩篇只有小部分改動的文章編碼後哈希值具有相似性，既可用於去重，也可用於計算相似度。對於只有小部分改動的兩篇文章，在計算他們之間的相似度時，如果採用md5，兩篇文章的md5編碼值差異會非常大。但使用局部敏感哈希可以使相似的文章哈希編碼後聚集在一起，刪除符合閾值條件的文章，達到去重的效果。

一、演算法流程

    1）分詞：對文本進行去停用詞、分詞，提取n個關鍵詞和關鍵詞的tf-idf權重來表徵文章。如下圖分詞及權重。

    2）關鍵詞哈希編碼：每個關鍵詞通過hash函數生成固定位數二進制哈希。

    3）權重編碼：二進制編碼中0調整為-1變為權重向量，與權重相乘。

    4）權重編碼疊加：將所有權重編碼縱向求和，得到最終的文章權重。

    5）二值化：按正數為1負數為0的規則將文章權重二值化。

    6）漢明距離相似度：排除漢明距離小於閾值的文章，一般設置為3。漢明距離計算速度快，思路簡單，原理是計算兩個二值化編碼相同位置處的不同值的個數。

二、Sim_hash整體流程

    需求： 來了一個相似文章推薦需求，需要推薦出與文章內容相似的數據，但又不能完全相似。利用目前庫中已有的POI標簽和POI權重數據，結合simhash演算法，計算出每個文章poi_sim_hash，計算距離

     數據： 線上拉取10W文章數據

     測試結果： 下圖為隨機抽樣的測試結果（第一條為查詢數據），基本 符合預期效果 。前期還可以使用 類目和發布時間 進行前置過濾，減少數據量。