汉明距离分治算法

① 分治的设计步骤

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文章数据

     测试结果： 下图为随机抽样的测试结果（第一条为查询数据），基本 符合预期效果 。前期还可以使用 类目和发布时间 进行前置过滤，减少数据量。