算法

算法

中文分词及结巴分词原理概述

搜索推荐zkbhj 发表了文章 • 0 个评论 • 1034 次浏览 • 2020-08-01 17:08 • 来自相关话题

中文分词概述

简单来说,中文分词根据实现特点大致可分为两个类别:
 

基于词典的分词方法;
基于统计的分词方法。


基于词典的分词方法

基于词典的分词方法首先会建立一个充分大的词典,然后依据一定的策略扫描句子,若句子中的某个子串与词典中的某个词匹配,则分词成功。

常见的扫描策略有:正向最大匹配、逆向最大匹配、双向最大匹配和最少词数分词。


正向最大匹配

对输入的句子从左至右,以贪心的方式切分出当前位置上长度最大的词,组不了词的字单独划开。其分词原理是:词的颗粒度越大,所能表示的含义越精确。

逆向最大匹配

原理与正向最大匹配相同,但顺序不是从首字开始,而是从末字开始,而且它使用的分词词典是逆序词典,其中每个词条都按逆序方式存放。在实际处理时,先将句子进行倒排处理,生成逆序句子,然后根据逆序词典,对逆序句子用正向最大匹配。

双向最大匹配

将正向最大匹配与逆向最大匹配组合起来,对句子使用这两种方式进行扫描切分,如果两种分词方法得到的匹配结果相同,则认为分词正确,否则,按最小集处理。

最少词数分词

即一句话应该分成数量最少的词串,该方法首先会查找词典中最长的词,看是不是所要分词的句子的子串,如果是则切分,然后不断迭代以上步骤,每次都会在剩余的字符串中取最长的词进行分词,最后就可以得到最少的词数。


总结:基于词典的分词方法简单、速度快,效果也还可以,但对歧义和新词的处理不是很好,对词典中未登录的词没法进行处理。

 
基于统计的分词方法

基于统计的分词方法是从大量已经分词的文本中,利用统计学习方法来学习词的切分规律,从而实现对未知文本的切分。随着大规模语料库的建立,基于统计的分词方法不断受到研究和发展,渐渐成为了主流。

常用的统计学习方法有:隐马尔可夫模型(HMM)、条件随机场(CRF)和基于深度学习的方法。

HMM和CRF

这两种方法实质上是对序列进行标注,将分词问题转化为字的分类问题,每个字有4种词位(类别):词首(B)、词中(M)、词尾(E)和单字成词(S)。由字构词的方法并不依赖于事先编制好的词典,只需对分好词的语料进行训练即可。当模型训练好后,就可对新句子进行预测,预测时会针对每个字生成不同的词位。其中HMM属于生成式模型,CRF属于判别式模型。

基于深度学习的方法

神经网络的序列标注算法在词性标注、命名实体识别等问题上取得了优秀的进展,这些端到端的方法也可以迁移到分词问题上。与所有深度学习的方法一样,该方法需要较大的训练语料才能体现优势,代表为BiLSTM-CRF。

 
总结:基于统计的分词方法能很好地处理歧义和新词问题,效果比基于词典的要好,但该方法需要有大量人工标注分好词的语料作为支撑,训练开销大,就分词速度而言不如前一种。


在实际应用中一般是将词典与统计学习方法结合起来,既发挥词典分词切分速度快的特点,又利用了统计分词结合上下文识别生词、自动消除歧义的优点。结巴分词正是这一类的代表,下面简要介绍一下它的实现算法。
 
结巴分词原理

官方Github上对所用算法的描述为:

基于前缀词典实现高效的词图扫描,生成句子中汉字所有可能成词情况所构成的有向无环图 (DAG);
采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合;
对于未登录词,采用了基于汉字成词能力的 HMM 模型,使用了 Viterbi 算法。


下面逐一介绍:

构造前缀词典

结巴分词首先会依照统计词典dict.txt构造前缀词典。dict.txt含有近35万的词条,每个词条占用一行,其中每一行有3列,第一列为词条,第二列为对应的词频,第三列为词性,构造前缀词典需要用到前两列。

具体做法为:首先定义一个空的python字典,然后遍历dict.txt的每一行,取词条作为字典的键,词频作为对应的键值,然后遍历该词条的前缀,如果前缀对应的键不在字典里,就把该前缀设为字典新的键,对应的键值设为0,如果前缀在字典里,则什么都不做。

这样等遍历完dict.txt后,前缀词典就构造好了。在构造前缀词典时,会对统计词典里所有词条的词频做一下累加,累加值等计算最大概率路径时会用到。

生成有向无环图(DAG)

用正则表达式分割句子后,对每一个单独的子句会生成一个有向无环图。

具体方式为:先定义一个空的python字典,然后遍历子句,当前子句元素的索引会作为字典的一个键,对应的键值为一个python列表(初始为空),然后会以当前索引作为子串的起始索引,不断向后遍历生成不同的子串,如果子串在前缀词典里且键值不为0的话,则把子串的终止索引添加到列表中。

这样等遍历完子句的所有字后,对应的DAG就生成好了。(子串的键值如果是0,则说明它不是一个词条)

计算最大概率路径

DAG的起点到终点会有很多路径,需要找到一条概率最大的路径,然后据此进行分词。可以采用动态规划来求解最大概率路径。

具体来说就是:从子句的最后一个字开始,倒序遍历子句的每个字,取当前字对应索引在DAG字典中的键值(一个python列表),然后遍历该列表,当前字会和列表中每个字两两组合成一个词条,然后基于词频计算出当前字到句尾的概率,以python元组的方式保存最大概率,元祖第一个元素是最大概率的对数,第二个元素为最大概率对应词条的终止索引。

词频可看作DAG中边的权重,之所以取概率的对数是为了防止数值下溢。有了最大概率路径,分词结果也就随之确定。

 对未登录词采用HMM模型进行分词

当出现没有在前缀词典里收录的词时,会采用HMM模型进行分词。HMM模型有5个基本组成:观测序列、状态序列、状态初始概率、状态转移概率和状态发射概率。分词属于HMM的预测问题,即已知观测序列、状态初始概率、状态转移概率和状态发射概率的条件下,求状态序列。结巴分词已经内置了训练好的状态初始概率、状态转移概率和状态发射概率。

句子会作为观测序列,当有新句子进来时,具体做法为:先通过Viterbi算法求出概率最大的状态序列,然后基于状态序列输出分词结果(每个字的状态为B、M、E、S之一)。

至此,结巴分词的原理就简单介绍完了。
 
参考文档:
https://www.cnblogs.com/cyandn/p/10891608.html
https://www.cnblogs.com/zhbzz2007/p/6084196.html
  查看全部
中文分词概述

简单来说,中文分词根据实现特点大致可分为两个类别:
 


基于词典的分词方法;
基于统计的分词方法。



基于词典的分词方法

基于词典的分词方法首先会建立一个充分大的词典,然后依据一定的策略扫描句子,若句子中的某个子串与词典中的某个词匹配,则分词成功。

常见的扫描策略有:正向最大匹配、逆向最大匹配、双向最大匹配和最少词数分词。


正向最大匹配

对输入的句子从左至右,以贪心的方式切分出当前位置上长度最大的词,组不了词的字单独划开。其分词原理是:词的颗粒度越大,所能表示的含义越精确。

逆向最大匹配

原理与正向最大匹配相同,但顺序不是从首字开始,而是从末字开始,而且它使用的分词词典是逆序词典,其中每个词条都按逆序方式存放。在实际处理时,先将句子进行倒排处理,生成逆序句子,然后根据逆序词典,对逆序句子用正向最大匹配。

双向最大匹配

将正向最大匹配与逆向最大匹配组合起来,对句子使用这两种方式进行扫描切分,如果两种分词方法得到的匹配结果相同,则认为分词正确,否则,按最小集处理。

最少词数分词

即一句话应该分成数量最少的词串,该方法首先会查找词典中最长的词,看是不是所要分词的句子的子串,如果是则切分,然后不断迭代以上步骤,每次都会在剩余的字符串中取最长的词进行分词,最后就可以得到最少的词数。


总结:基于词典的分词方法简单、速度快,效果也还可以,但对歧义和新词的处理不是很好,对词典中未登录的词没法进行处理。

 
基于统计的分词方法

基于统计的分词方法是从大量已经分词的文本中,利用统计学习方法来学习词的切分规律,从而实现对未知文本的切分。随着大规模语料库的建立,基于统计的分词方法不断受到研究和发展,渐渐成为了主流。

常用的统计学习方法有:隐马尔可夫模型(HMM)、条件随机场(CRF)和基于深度学习的方法。

HMM和CRF

这两种方法实质上是对序列进行标注,将分词问题转化为字的分类问题,每个字有4种词位(类别):词首(B)、词中(M)、词尾(E)和单字成词(S)。由字构词的方法并不依赖于事先编制好的词典,只需对分好词的语料进行训练即可。当模型训练好后,就可对新句子进行预测,预测时会针对每个字生成不同的词位。其中HMM属于生成式模型,CRF属于判别式模型。

基于深度学习的方法

神经网络的序列标注算法在词性标注、命名实体识别等问题上取得了优秀的进展,这些端到端的方法也可以迁移到分词问题上。与所有深度学习的方法一样,该方法需要较大的训练语料才能体现优势,代表为BiLSTM-CRF。

 
总结:基于统计的分词方法能很好地处理歧义和新词问题,效果比基于词典的要好,但该方法需要有大量人工标注分好词的语料作为支撑,训练开销大,就分词速度而言不如前一种。


在实际应用中一般是将词典与统计学习方法结合起来,既发挥词典分词切分速度快的特点,又利用了统计分词结合上下文识别生词、自动消除歧义的优点。结巴分词正是这一类的代表,下面简要介绍一下它的实现算法。
 
结巴分词原理

官方Github上对所用算法的描述为:


基于前缀词典实现高效的词图扫描,生成句子中汉字所有可能成词情况所构成的有向无环图 (DAG)
采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合;
对于未登录词,采用了基于汉字成词能力的 HMM 模型,使用了 Viterbi 算法



下面逐一介绍:

构造前缀词典

结巴分词首先会依照统计词典dict.txt构造前缀词典。dict.txt含有近35万的词条,每个词条占用一行,其中每一行有3列,第一列为词条,第二列为对应的词频,第三列为词性,构造前缀词典需要用到前两列。

具体做法为:首先定义一个空的python字典,然后遍历dict.txt的每一行,取词条作为字典的键,词频作为对应的键值,然后遍历该词条的前缀,如果前缀对应的键不在字典里,就把该前缀设为字典新的键,对应的键值设为0,如果前缀在字典里,则什么都不做。

这样等遍历完dict.txt后,前缀词典就构造好了。在构造前缀词典时,会对统计词典里所有词条的词频做一下累加,累加值等计算最大概率路径时会用到。

生成有向无环图(DAG)

用正则表达式分割句子后,对每一个单独的子句会生成一个有向无环图。

具体方式为:先定义一个空的python字典,然后遍历子句,当前子句元素的索引会作为字典的一个键,对应的键值为一个python列表(初始为空),然后会以当前索引作为子串的起始索引,不断向后遍历生成不同的子串,如果子串在前缀词典里且键值不为0的话,则把子串的终止索引添加到列表中。

这样等遍历完子句的所有字后,对应的DAG就生成好了。(子串的键值如果是0,则说明它不是一个词条)

计算最大概率路径

DAG的起点到终点会有很多路径,需要找到一条概率最大的路径,然后据此进行分词。可以采用动态规划来求解最大概率路径。

具体来说就是:从子句的最后一个字开始,倒序遍历子句的每个字,取当前字对应索引在DAG字典中的键值(一个python列表),然后遍历该列表,当前字会和列表中每个字两两组合成一个词条,然后基于词频计算出当前字到句尾的概率,以python元组的方式保存最大概率,元祖第一个元素是最大概率的对数,第二个元素为最大概率对应词条的终止索引。

词频可看作DAG中边的权重,之所以取概率的对数是为了防止数值下溢。有了最大概率路径,分词结果也就随之确定。

 对未登录词采用HMM模型进行分词

当出现没有在前缀词典里收录的词时,会采用HMM模型进行分词。HMM模型有5个基本组成:观测序列、状态序列、状态初始概率、状态转移概率和状态发射概率。分词属于HMM的预测问题,即已知观测序列、状态初始概率、状态转移概率和状态发射概率的条件下,求状态序列。结巴分词已经内置了训练好的状态初始概率、状态转移概率和状态发射概率。

句子会作为观测序列,当有新句子进来时,具体做法为:先通过Viterbi算法求出概率最大的状态序列,然后基于状态序列输出分词结果(每个字的状态为B、M、E、S之一)。

至此,结巴分词的原理就简单介绍完了。
 
参考文档:
https://www.cnblogs.com/cyandn/p/10891608.html
https://www.cnblogs.com/zhbzz2007/p/6084196.html
 

算法之旅:理解透彻冒泡算法及它的几个优化版本

架构思想zkbhj 发表了文章 • 0 个评论 • 541 次浏览 • 2020-05-11 15:29 • 来自相关话题

什么是冒泡排序?

冒泡排序的英文Bubble Sort,是一种最基础的交换排序。

大家一定都喝过汽水,汽水中常常有许多小小的气泡,哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水要轻,所以小气泡可以一点一点向上浮动。

而我们的冒泡排序之所以叫做冒泡排序,正是因为这种排序算法的每一个元素都可以像小气泡一样,根据自身大小,一点一点向着数组的一侧移动。
 
原始的冒泡排序是稳定排序。由于该排序算法的每一轮要遍历所有元素,轮转的次数和元素数量相当,所以时间复杂度是O(N^2) 。





 
增强版1

对于后面已经有序的部分,不需要在进行比较了。增加isSorted标记,默认true,如果本轮存在交换,就变为false,说明下一轮可能还有排序。否则break跳出循环
 
这一版代码做了小小的改动,利用布尔变量isSorted作为标记。如果在本轮排序中,元素有交换,则说明数列无序;如果没有元素交换,说明数列已然有序,直接跳出大循环。





 
增强版2
提前预知已排好序的边界,减少排序比较次数。最后交换元素的下标记住。
 
这一版代码中,sortBorder就是无序数列的边界。每一轮排序过程中,sortBorder之后的元素就完全不需要比较了,肯定是有序的。





 
鸡尾酒排序
告别冒泡排序的单项比较移动,鸡尾酒排序是左右比较移动轮换着来的。内层循环有2个循环,一个向左,一个向右。
下面这段代码是鸡尾酒排序的原始实现。代码外层的大循环控制着所有排序回合,大循环内包含两个小循环,第一个循环从左向右比较并交换元素,第二个循环从右向左比较并交换元素。
 




 
鸡尾酒排序增强版
 
代码中使用了左右两个边界值,rightSortBorder 代表右边界,leftSortBorder代表左边界。 
在比较和交换元素时,奇数轮从 leftSortBorder 遍历到 rightSortBorder 位置,偶数轮从 rightSortBorder 遍历到 leftSortBorder 位置。





 
地精排序
 
它也像冒泡排序一样,相邻元素之间两两进行比较,如果这两个元素逆序,则交换。与冒泡排序不同的是,它如果遇到交换操作时,变为向前冒泡,直至不发生交换操作位置。相当于做了一个插入操作,将比较小的数插入到前面的有序序列中合适的位置。所以,地精排序可以说是冒泡排序和直接插入排序的综合。
 
BOOL GnomeSort(datatype *array, int size)
{
int i = 0;

if(array == NULL) {
return FALSE;
}

while(i < size) {
//如果i=0或者i-1与i正序时,i++
if(i == 0 || array[i-1] <= array[i]) {
i++;
} else {
//如果i-1与i逆序时,i--
Swap(array + i-1, array + i);
i--;
}
}

return TRUE;
}
参考文档:
https://mp.weixin.qq.com/s/wO11PDZSM5pQ0DfbQjKRQA
https://mp.weixin.qq.com/s/tXqjWWyjQ1ILfvnFv3_f7Q
https://blog.csdn.net/u010647471/article/details/49976345
  查看全部
什么是冒泡排序?

冒泡排序的英文Bubble Sort,是一种最基础的交换排序。

大家一定都喝过汽水,汽水中常常有许多小小的气泡,哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水要轻,所以小气泡可以一点一点向上浮动。

而我们的冒泡排序之所以叫做冒泡排序,正是因为这种排序算法的每一个元素都可以像小气泡一样,根据自身大小,一点一点向着数组的一侧移动。
 
原始的冒泡排序是稳定排序。由于该排序算法的每一轮要遍历所有元素,轮转的次数和元素数量相当,所以时间复杂度是O(N^2) 。

QQ截图20200511152317.jpg

 
增强版1

对于后面已经有序的部分,不需要在进行比较了。增加isSorted标记,默认true,如果本轮存在交换,就变为false,说明下一轮可能还有排序。否则break跳出循环
 
这一版代码做了小小的改动,利用布尔变量isSorted作为标记。如果在本轮排序中,元素有交换,则说明数列无序;如果没有元素交换,说明数列已然有序,直接跳出大循环。

QQ截图20200511152421.jpg

 
增强版2
提前预知已排好序的边界,减少排序比较次数。最后交换元素的下标记住。
 
这一版代码中,sortBorder就是无序数列的边界。每一轮排序过程中,sortBorder之后的元素就完全不需要比较了,肯定是有序的。

QQ截图20200511152513.jpg

 
鸡尾酒排序
告别冒泡排序的单项比较移动,鸡尾酒排序是左右比较移动轮换着来的。内层循环有2个循环,一个向左,一个向右。
下面这段代码是鸡尾酒排序的原始实现。代码外层的大循环控制着所有排序回合,大循环内包含两个小循环,第一个循环从左向右比较并交换元素,第二个循环从右向左比较并交换元素。
 
QQ截图20200511152558.jpg

 
鸡尾酒排序增强版
 
代码中使用了左右两个边界值,rightSortBorder 代表右边界,leftSortBorder代表左边界。 
在比较和交换元素时,奇数轮从 leftSortBorder 遍历到 rightSortBorder 位置,偶数轮从 rightSortBorder 遍历到 leftSortBorder 位置。

QQ截图20200511152638.jpg

 
地精排序
 
它也像冒泡排序一样,相邻元素之间两两进行比较,如果这两个元素逆序,则交换。与冒泡排序不同的是,它如果遇到交换操作时,变为向前冒泡,直至不发生交换操作位置。相当于做了一个插入操作,将比较小的数插入到前面的有序序列中合适的位置。所以,地精排序可以说是冒泡排序和直接插入排序的综合。
 
BOOL GnomeSort(datatype *array, int size)
{
int i = 0;

if(array == NULL) {
return FALSE;
}

while(i < size) {
//如果i=0或者i-1与i正序时,i++
if(i == 0 || array[i-1] <= array[i]) {
i++;
} else {
//如果i-1与i逆序时,i--
Swap(array + i-1, array + i);
i--;
}
}

return TRUE;
}

参考文档:
https://mp.weixin.qq.com/s/wO11PDZSM5pQ0DfbQjKRQA
https://mp.weixin.qq.com/s/tXqjWWyjQ1ILfvnFv3_f7Q
https://blog.csdn.net/u010647471/article/details/49976345
 

#2020学习打卡##C程序设计语言# 什么是排序算法的稳定性?

回复

常识zkbhj 回复了问题 • 1 人关注 • 1 个回复 • 1792 次浏览 • 2020-05-07 19:28 • 来自相关话题

算法之旅:如何评价算法好坏的神器之时间复杂度

架构思想zkbhj 发表了文章 • 0 个评论 • 530 次浏览 • 2020-05-07 14:22 • 来自相关话题

时间复杂度是学习算法的基石,今天我们来聊聊为什么要引入时间复杂度,什么是时间复杂度以及如何去算一个算法的时间复杂度。
 

在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。


若存在函数 f(n),使得当n趋近于无穷大时,T(n)/ f(n)的极限值为不等于零的常数,则称 f(n)是T(n)的同数量级函数。
记作 T(n)= O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
渐进时间复杂度用大写O来表示,所以也被称为大O表示法。





 O(1)< O(logn)< O(n)< O(n^2)
 
 
 
参考文档:
https://mp.weixin.qq.com/s?src=11&timestamp=1588832012&ver=2323&signature=37Md0F80eUGKg9BeRAXTAeHawoHpJxHPzwvPguG0Ow0y5e7oK1IQ5C*36ApecKiCEkT98Vi6hPH2KoVqeHQ6ZSVvuFWp0MEzvDb*Wg657Fcvg9ToEOTDltnC39r*5*I9&new=1
https://mp.weixin.qq.com/s?__biz=MzU1MDE4MzUxNA==&mid=2247483867&idx=1&sn=6270b56b79cb74334eb4faf80de05f0a&chksm=fba536eeccd2bff8e38566b3c12b439666fca9ec7ffa2a6c0d2271550702a3dc0851bd99d0cf&scene=21#wechat_redirect
  查看全部
时间复杂度是学习算法的基石,今天我们来聊聊为什么要引入时间复杂度,什么是时间复杂度以及如何去算一个算法的时间复杂度。
 


在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。



若存在函数 f(n),使得当n趋近于无穷大时,T(n)/ f(n)的极限值为不等于零的常数,则称 f(n)是T(n)的同数量级函数。
记作 T(n)= O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
渐进时间复杂度用大写O来表示,所以也被称为大O表示法。


dcc451da81cb39db86d6cf67dd160924ab1830e8.png

 O(1)< O(logn)< O(n)< O(n^2)
 
 
 
参考文档:
https://mp.weixin.qq.com/s?src=11&timestamp=1588832012&ver=2323&signature=37Md0F80eUGKg9BeRAXTAeHawoHpJxHPzwvPguG0Ow0y5e7oK1IQ5C*36ApecKiCEkT98Vi6hPH2KoVqeHQ6ZSVvuFWp0MEzvDb*Wg657Fcvg9ToEOTDltnC39r*5*I9&new=1
https://mp.weixin.qq.com/s?__biz=MzU1MDE4MzUxNA==&mid=2247483867&idx=1&sn=6270b56b79cb74334eb4faf80de05f0a&chksm=fba536eeccd2bff8e38566b3c12b439666fca9ec7ffa2a6c0d2271550702a3dc0851bd99d0cf&scene=21#wechat_redirect
 

#2020学习打卡##C程序设计语言# 直接插入排序和改进版Shell排序解析

C语言zkbhj 发表了文章 • 0 个评论 • 576 次浏览 • 2020-04-14 17:54 • 来自相关话题

一、直接插入排序

直接插入排序(Straight Insertion Sort)是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的、记录数量增1的有序表。直接插入排序的时间复杂度为 O(n2)。

 
实例如下所示:

定义的数组   :      {23,34,56,78,65,90,88,92,18,21}

过程如下所示:

【23】   34   56   78   65   90   88   92   18   21

第 1 次排序结果:   【23   34】   56   78   65   90   88   92   18   21 

——用34插入到【23】序列中,34>23,故插入后的顺序是【23,34】


第 2 次排序结果:   【 23   34     56 】78   65   90   88   92   18   21

——用56插入到【23,34】序列中,56>34,故插入后的顺序是【23,34,56】


第 3 次排序结果:   【23   34      56    78】65   90   88   92   18   21

——用78插入到【23,34,56】序列中,78>56,故插入后的顺序是【23,34,56,78】


第 4 次排序结果:   【23   34     56     65   78 】90   88   92   18   21    

——用65插入到【23,34,56,78】序列中,65<78,所以78后移一位,和56比较,65>56,故插入后的顺序是【23,34,56,65, 78】


第 5 次排序结果:   【23   34   56   65   78   90 】  88   92   18   21

——用90插入到【23,34,56,65, 78】序列中,78<90 ,故插入后的顺序是【23   34   56   65   78   90 】


第 6 次排序结果:   23   34   56   65   78   88   90   92   18   21

——用88插入到【23   34   56   65   78   90 】序列中,90>88 ,所以90后移一位,故插入后的顺序是【23   34   56   65   78   88   90】


第 7 次排序结果:   23   34   56   65   78   88   90   92   18   21

——用92插入到【23   34   56   65   78   90 】序列中,90<92 ,故插入后的顺序是【23   34   56   65   78   90   92 】


第 8 次排序结果:   18   23   34   56   65   78   88   90   92   21

——用18插入到【23   34   56   65   78   90   92 】序列中,18<92,所以92后移一位,和90比较,90>18,依次后移,直到第一位23,因为18<23, 故插入后的顺序是【18   23   34   56   65   78   88   90   92】


第 9 次排序结果:   18   21   23   34   56   65   78   88   90   92

——用21插入到【23   34   56   65   78   90   92 】序列中,21<92,故92后移一位,和90比较,90>21,依次后移,直到第一位18,因为18<21, 故插入后的顺序是【18   21   23   34   56   65   78   88   90   92】 
C语言实现:#include <stdio.h>
//自定义的输出函数
void print(int a, int n ,int i){
printf("%d:",i);
for(int j=0; j<8; j++){
printf("%d",a[j]);
}
printf("\n");
}
//直接插入排序函数
void InsertSort(int a, int n)
{
for(int i= 1; i<n; i++){
if(a < a[i-1]){//若第 i 个元素大于 i-1 元素则直接插入;反之,需要找到适当的插入位置后在插入。
int j= i-1;
int x = a;
while(j>-1 && x < a[j]){ //采用顺序查找方式找到插入的位置,在查找的同时,将数组中的元素进行后移操作,给插入元素腾出空间
a[j+1] = a[j];
j--;
}
a[j+1] = x; //插入到正确位置
}
print(a,n,i);//打印每次排序后的结果
}
}
int main(){
int a[8] = {3,1,7,5,2,4,9,6};
InsertSort(a,8);
return 0;
}
二、Shell排序:直接插入排序算法的一种高速而稳定的改进版本
 


希尔排序,也称递减增量排序算法,是一种插入排序算法,它出自D.L.Shell,因此而得名。Shell排序又称作缩小增量排序。Shell排序的执行时间依赖于增量序列。


希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量=1(<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
 
Shell排序算法的特点


希尔排序是基于插入排序的以下两点性质而提出改进方法的:
插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率[list][*]但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位

[/*]
[/list]


时间复杂度:最坏情况下为O(n^2),平均时间复杂度为O(nlogn);
空间复杂度:归并排序需要一个大小为1的临时存储空间用以保存合并序列,所以空间复杂度为O(1)
算法稳定性:从上面图片中可以看出,数字5在排序后交换了位置,所以它是不稳定的算法。


例如:12、5、9、34、6、8、33、56、89、0、7、4、22、55、77
具体步骤:




void Shell(int *arr,int len,int gap)
{
for(int i = gap;i < len;i++)
{
int temp = arr;
int j = 0;
for(j = i-gap;j >= 0;j-=gap)
{
if(arr[j] > temp)
{
arr[j+gap] = arr[j];
}
else
{
break;
}
}
arr[j+gap] = temp;
}
}
void Shell_Sort(int *arr,int len)
{
int drr = {5,3,1}; //drr为分的组数,这里5,3,1不固定,但必须相互为素数,且最后数为1
int lend = sizeof(drr)/sizeof(drr[0]);
for(int i = 0;i < lend;i++)
{
Shell(arr,len,drr);
}
}

引用文章:
https://blog.csdn.net/FDk_LCL/java/article/details/90581904
https://www.cnblogs.com/guopengxia0719/p/10520561.html
https://www.cnblogs.com/BaoZiY/p/10931406.html
  查看全部
一、直接插入排序


直接插入排序(Straight Insertion Sort)是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的、记录数量增1的有序表。直接插入排序的时间复杂度为 O(n2)。


 
实例如下所示:

定义的数组   :      {23,34,56,78,65,90,88,92,18,21}

过程如下所示:

【23】   34   56   78   65   90   88   92   18   21

第 1 次排序结果:   【23   34】   56   78   65   90   88   92   18   21 

——用34插入到【23】序列中,34>23,故插入后的顺序是【23,34】


第 2 次排序结果:   【 23   34     56 】78   65   90   88   92   18   21

——用56插入到【23,34】序列中,56>34,故插入后的顺序是【23,34,56】


第 3 次排序结果:   【23   34      56    78】65   90   88   92   18   21

——用78插入到【23,34,56】序列中,78>56,故插入后的顺序是【23,34,56,78】


第 4 次排序结果:   【23   34     56     65   78 】90   88   92   18   21    

——用65插入到【23,34,56,78】序列中,65<78,所以78后移一位,和56比较,65>56,故插入后的顺序是【23,34,56,65, 78】


第 5 次排序结果:   【23   34   56   65   78   90 】  88   92   18   21

——用90插入到【23,34,56,65, 78】序列中,78<90 ,故插入后的顺序是【23   34   56   65   78   90 】


第 6 次排序结果:   23   34   56   65   78   88   90   92   18   21

——用88插入到【23   34   56   65   78   90 】序列中,90>88 ,所以90后移一位,故插入后的顺序是【23   34   56   65   78   88   90】


第 7 次排序结果:   23   34   56   65   78   88   90   92   18   21

——用92插入到【23   34   56   65   78   90 】序列中,90<92 ,故插入后的顺序是【23   34   56   65   78   90   92 】


第 8 次排序结果:   18   23   34   56   65   78   88   90   92   21

——用18插入到【23   34   56   65   78   90   92 】序列中,18<92,所以92后移一位,和90比较,90>18,依次后移,直到第一位23,因为18<23, 故插入后的顺序是【18   23   34   56   65   78   88   90   92】


第 9 次排序结果:   18   21   23   34   56   65   78   88   90   92

——用21插入到【23   34   56   65   78   90   92 】序列中,21<92,故92后移一位,和90比较,90>21,依次后移,直到第一位18,因为18<21, 故插入后的顺序是【18   21   23   34   56   65   78   88   90   92】 
C语言实现:
#include <stdio.h>
//自定义的输出函数
void print(int a, int n ,int i){
printf("%d:",i);
for(int j=0; j<8; j++){
printf("%d",a[j]);
}
printf("\n");
}
//直接插入排序函数
void InsertSort(int a, int n)
{
for(int i= 1; i<n; i++){
if(a < a[i-1]){//若第 i 个元素大于 i-1 元素则直接插入;反之,需要找到适当的插入位置后在插入。
int j= i-1;
int x = a;
while(j>-1 && x < a[j]){ //采用顺序查找方式找到插入的位置,在查找的同时,将数组中的元素进行后移操作,给插入元素腾出空间
a[j+1] = a[j];
j--;
}
a[j+1] = x; //插入到正确位置
}
print(a,n,i);//打印每次排序后的结果
}
}
int main(){
int a[8] = {3,1,7,5,2,4,9,6};
InsertSort(a,8);
return 0;
}

二、Shell排序:直接插入排序算法的一种高速而稳定的改进版本
 



希尔排序,也称递减增量排序算法,是一种插入排序算法,它出自D.L.Shell,因此而得名。Shell排序又称作缩小增量排序。Shell排序的执行时间依赖于增量序列。



希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量=1(<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
 
Shell排序算法的特点



希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率[list][*]但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位


[/*]
[/list]


时间复杂度:最坏情况下为O(n^2),平均时间复杂度为O(nlogn);
空间复杂度:归并排序需要一个大小为1的临时存储空间用以保存合并序列,所以空间复杂度为O(1)
算法稳定性:从上面图片中可以看出,数字5在排序后交换了位置,所以它是不稳定的算法。



例如:12、5、9、34、6、8、33、56、89、0、7、4、22、55、77
具体步骤:

20181122144210405.png
void Shell(int *arr,int len,int gap)
{
for(int i = gap;i < len;i++)
{
int temp = arr;
int j = 0;
for(j = i-gap;j >= 0;j-=gap)
{
if(arr[j] > temp)
{
arr[j+gap] = arr[j];
}
else
{
break;
}
}
arr[j+gap] = temp;
}
}
void Shell_Sort(int *arr,int len)
{
int drr = {5,3,1}; //drr为分的组数,这里5,3,1不固定,但必须相互为素数,且最后数为1
int lend = sizeof(drr)/sizeof(drr[0]);
for(int i = 0;i < lend;i++)
{
Shell(arr,len,drr);
}
}

引用文章:
https://blog.csdn.net/FDk_LCL/java/article/details/90581904
https://www.cnblogs.com/guopengxia0719/p/10520561.html
https://www.cnblogs.com/BaoZiY/p/10931406.html
 

搜索相似度算法探究之MMR

架构思想zkbhj 发表了文章 • 0 个评论 • 1981 次浏览 • 2020-02-21 18:06 • 来自相关话题

最近公司搜索项目在做返回结果相似度相关的需求,需要了解如何计算不同文档之间的相似度排序,进而将返回的结果进行一次“打散”重排操作,让结果看起来不那么“相似的内容”太过于“扎墩儿”出现。
 
今天同事分享了相似度算法中最简单的算法:MMR。接下来就仔细研究学习下。
 
MMR的全称为Maximal Marginal Relevance ,中文名字为最大边界相关法或者最大边缘相关。算法目的是减少排序结果的冗余,同时保证结果的相关性。最早应用于文本摘要提取和信息检索等领域。在推荐场景下体现在,给用户推荐相关商品的同时,保证推荐结果的多样性,即排序结果存在着相关性与多样性的权衡。

MMR的主要思路是:

• Use the query to retrieve a ranking R of documents
• Use MMR to rerank the top N documents (build a new ranking S)
– Select the 1st document based on how well it satisfies the query
– Select subsequent documents based on two criteria
» How well it satisfies the query
» How different it is from documents ranked above it

 
在MMR的公式是这样的:





 
R: The initial ranking
S: Documents already selected for the diverse ranking
– Documents ranked above this position
Sim(di, dj): Similarity metric
– E.g., vector space model or Jensen-Shannon Divergence
λ : 权重系数,调节推荐结果相关性与多样性。λ越大,推荐结果越相关; λ越小,推荐结果多样性越高。
 举个例子,假设λ=0.6λ=0.6,初始排名及其相关性分数如下:Initial Ranking
d1, 0.80
d2, 0.78
d3, 0.76
d4, 0.74
d5, 0.72
d6, 0.70 
第一步,选择与 query 最相关的文档 d1,并从 R 中移除 d1Diversified Ranking
d1计算剩余文档与 {d1} 的相似度和对应的多样性分数





 
选择分数最高的文档作为多样性排名的第 2 篇文档,并从 R 中移除该文档Diversified Ranking
d1
d5分别计算剩余文档与已排序文档 {d1, d5} 的相似度,选相似度最大的值,计算 MMR 分数





 
选择分数最高的文档作为多样性排名的第 3 篇文档,并从 R 中移除该文档Diversified Ranking
d1
d5
d3分别计算剩余文档与已排序文档 {d1, d5, d3} 的相似度,选相似度最大的值,计算 MMR 分数





 
选择分数最高的文档作为多样性排名的第 4 篇文档,并从 R 中移除该文档Diversified Ranking
d1
d5
d3
d6分别计算剩余文档与已排序文档 d1, d5, d3, d6 的相似度,选相似度最大的值,计算 MMR 分数





 
选择分数最高的文档作为多样性排名的第 5 篇文档,并从 R 中移除该文档Diversified Ranking
d1
d5
d3
d6
d2Repeat until all documents in the initial ranking are added to the diversified ranking

所以就有了最后的排名 {d1, d5, d3, d6, d2}

MMR 也会用于其它的任务如文本摘要,因为它是符合摘要的基本要求的,即相关性和多样性的权衡。摘要结果与原文的相关性越高,摘要就接近全文中心意思,而多样性则使摘要内容更加的全面。直观和简单是这种方法最大的优点。
 
参考文档:
http://www.shuang0420.com/2016/12/07/Search%20Engines%E7%AC%94%E8%AE%B0%20-%20Diversity/
文档相似性分数计算:
https://blog.csdn.net/yixianfe ... 17158 查看全部
最近公司搜索项目在做返回结果相似度相关的需求,需要了解如何计算不同文档之间的相似度排序,进而将返回的结果进行一次“打散”重排操作,让结果看起来不那么“相似的内容”太过于“扎墩儿”出现。
 
今天同事分享了相似度算法中最简单的算法:MMR。接下来就仔细研究学习下。
 
MMR的全称为Maximal Marginal Relevance ,中文名字为最大边界相关法或者最大边缘相关。算法目的是减少排序结果的冗余,同时保证结果的相关性。最早应用于文本摘要提取和信息检索等领域。在推荐场景下体现在,给用户推荐相关商品的同时,保证推荐结果的多样性,即排序结果存在着相关性与多样性的权衡。

MMR的主要思路是:


• Use the query to retrieve a ranking R of documents
• Use MMR to rerank the top N documents (build a new ranking S)
– Select the 1st document based on how well it satisfies the query
– Select subsequent documents based on two criteria
» How well it satisfies the query
» How different it is from documents ranked above it


 
在MMR的公式是这样的:

MMR.png

 
R: The initial ranking
S: Documents already selected for the diverse ranking
– Documents ranked above this position
Sim(di, dj): Similarity metric
– E.g., vector space model or Jensen-Shannon Divergence
λ : 权重系数,调节推荐结果相关性与多样性。λ越大,推荐结果越相关; λ越小,推荐结果多样性越高。
 举个例子,假设λ=0.6λ=0.6,初始排名及其相关性分数如下:
Initial Ranking
d1, 0.80
d2, 0.78
d3, 0.76
d4, 0.74
d5, 0.72
d6, 0.70
 
第一步,选择与 query 最相关的文档 d1,并从 R 中移除 d1
Diversified Ranking
d1
计算剩余文档与 {d1} 的相似度和对应的多样性分数

step1.jpg

 
选择分数最高的文档作为多样性排名的第 2 篇文档,并从 R 中移除该文档
Diversified Ranking
d1
d5
分别计算剩余文档与已排序文档 {d1, d5} 的相似度,选相似度最大的值,计算 MMR 分数

step2.jpg

 
选择分数最高的文档作为多样性排名的第 3 篇文档,并从 R 中移除该文档
Diversified Ranking
d1
d5
d3
分别计算剩余文档与已排序文档 {d1, d5, d3} 的相似度,选相似度最大的值,计算 MMR 分数

step3.jpg

 
选择分数最高的文档作为多样性排名的第 4 篇文档,并从 R 中移除该文档
Diversified Ranking
d1
d5
d3
d6
分别计算剩余文档与已排序文档 d1, d5, d3, d6 的相似度,选相似度最大的值,计算 MMR 分数

step4.jpg

 
选择分数最高的文档作为多样性排名的第 5 篇文档,并从 R 中移除该文档
Diversified Ranking
d1
d5
d3
d6
d2
Repeat until all documents in the initial ranking are added to the diversified ranking

所以就有了最后的排名 {d1, d5, d3, d6, d2}

MMR 也会用于其它的任务如文本摘要,因为它是符合摘要的基本要求的,即相关性和多样性的权衡。摘要结果与原文的相关性越高,摘要就接近全文中心意思,而多样性则使摘要内容更加的全面。直观和简单是这种方法最大的优点。
 
参考文档:
http://www.shuang0420.com/2016/12/07/Search%20Engines%E7%AC%94%E8%AE%B0%20-%20Diversity/
文档相似性分数计算:
https://blog.csdn.net/yixianfe ... 17158

什么是HashTime33?

回复

专业名词zkbhj 回复了问题 • 1 人关注 • 1 个回复 • 2258 次浏览 • 2019-10-27 11:18 • 来自相关话题

海量数据相似度计算算法:simhash和海明距离

架构思想zkbhj 发表了文章 • 0 个评论 • 1054 次浏览 • 2018-09-12 16:04 • 来自相关话题

通过 采集系统 我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析。分析前我们需要对这些数据去除重复,如何选择和设计文本的去重算法?常见的有余弦夹角算法、欧式距离、Jaccard相似度、最长公共子串、编辑距离等。这些算法对于待比较的文本数据不多时还比较好用,如果我们的爬虫每天采集的数据以千万计算,我们如何对于这些海量千万级的数据进行高效的合并去重。最简单的做法是拿着待比较的文本和数据库中所有的文本比较一遍如果是重复的数据就标示为重复。看起来很简单,我们来做个测试,就拿最简单的两个数据使用Apache提供的 Levenshtein for 循环100w次计算这两个数据的相似度。代码结果如下:
String s1 = "你妈妈喊你回家吃饭哦,回家罗回家罗" ;
String s2 = "你妈妈叫你回家吃饭啦,回家罗回家罗" ;

long t1 = System.currentTimeMillis();

for (int i = 0; i < 1000000; i++) {
int dis = StringUtils .getLevenshteinDistance(s1, s2);
}

long t2 = System.currentTimeMillis();

System. out .println(" 耗费时间: " + (t2 - t1) + " ms ");耗费时间: 4266 ms

大跌眼镜,居然计算耗费4秒。假设我们一天需要比较100w次,光是比较100w次的数据是否重复就需要4s,就算4s一个文档,单线程一分钟才处理15个文档,一个小时才900个,一天也才21600个文档,这个数字和一天100w相差甚远,需要多少机器和资源才能解决。

为此我们需要一种应对于海量数据场景的去重方案,经过研究发现有种叫 local sensitive hash 局部敏感哈希 的东西,据说这玩意可以把文档降维到hash数字,数字两两计算运算量要小很多。查找很多文档后看到google对于网页去重使用的是simhash,他们每天需要处理的文档在亿级别,大大超过了我们现在文档的水平。既然老大哥也有类似的应用,我们也赶紧尝试下。simhash是由 Charikar 在2002年提出来的,参考 《Similarity estimation techniques from rounding algorithms》 。 介绍下这个算法主要原理,为了便于理解尽量不使用数学公式,分为这几步:
 

1、分词,把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重,我们假设权重分为5个级别(1~5)。比如:“ 美国“51区”雇员称内部有9架飞碟,曾看见灰色外星人 ” ==> 分词后为 “ 美国(4) 51区(5) 雇员(3) 称(1) 内部(2) 有(1) 9架(3) 飞碟(5) 曾(1) 看见(3) 灰色(4) 外星人(5)”,括号里是代表单词在整个句子里重要程度,数字越大越重要。

2、hash,通过hash算法把每个词变成hash值,比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字,还记得文章开头说过的吗,要把文章变为数字计算才能提高相似度计算性能,现在是降维过程进行时。

3、加权,通过 2步骤的hash生成结果,需要按照单词的权重形成加权数字串,比如“美国”的hash值为“100101”,通过加权计算为“4 -4 -4 4 -4 4”;“51区”的hash值为“101011”,通过加权计算为 “ 5 -5 5 -5 5 5”。

4、合并,把上面各个单词算出来的序列值累加,变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”,“51区”的 “ 5 -5 5 -5 5 5”, 把每一位进行累加, “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的,真实计算需要把所有单词的序列串累加。

5、降维,把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串,形成我们最终的simhash签名。 如果每一位大于0 记为 1,小于0 记为 0。最后算出结果为:“1 0 1 0 1 1”。

 
整个过程图为:





 
大家可能会有疑问,经过这么多步骤搞这么麻烦,不就是为了得到个 0 1 字符串吗?我直接把这个文本作为字符串输入,用hash函数生成 0 1 值更简单。其实不是这样的,传统hash函数解决的是生成唯一值,比如 md5、hashmap等。md5是用于生成唯一签名串,只要稍微多加一个字符md5的两个数字看起来相差甚远;hashmap也是用于键值对查找,便于快速插入和查找的数据结构。不过我们主要解决的是文本相似度计算,要比较的是两个文章是否相识,当然我们降维生成了hashcode也是用于这个目的。看到这里估计大家就明白了,我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的,而传统的hashcode却不行。我们可以来做个测试,两个相差只有一个字符的文本串,“你妈妈喊你回家吃饭哦,回家罗回家罗” 和 “你妈妈叫你回家吃饭啦,回家罗回家罗”。

通过simhash计算结果为:

1000010010101101111111100000101011010001001111100001001011001011

1000010010101101011111100000101011010001001111100001101010001011

通过 hashcode计算为:

1111111111111111111111111111111110001000001100110100111011011110

1010010001111111110010110011101

大家可以看得出来,相似的文本只有部分 01 串变化了,而普通的hashcode却不能做到,这个就是局部敏感哈希的魅力。目前Broder提出的shingling算法和Charikar的simhash算法应该算是业界公认比较好的算法。在simhash的发明人Charikar的论文中并没有给出具体的simhash算法和证明,“量子图灵”得出的证明simhash是由随机超平面hash算法演变而来的。

现在通过这样的转换,我们把库里的文本都转换为simhash 代码,并转换为long类型存储,空间大大减少。现在我们虽然解决了空间,但是如何计算两个simhash的相似度呢?难道是比较两个simhash的01有多少个不同吗?对的,其实也就是这样,我们通过海明距离(Hamming distance)就可以计算出两个simhash到底相似不相似。两个simhash对应二进制(01串)取值不同的数量称为这两个simhash的海明距离。举例如下: 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同,则海明距离为3。对于二进制字符串的a和b,海明距离为等于在a XOR b运算结果中1的个数(普遍算法)。

为了高效比较,我们预先加载了库里存在文本并转换为simhash code 存储在内存空间。来一条文本先转换为 simhash code,然后和内存里的simhash code 进行比较,测试100w次计算在100ms。速度大大提升。

未完待续:

1、目前速度提升了但是数据是不断增量的,如果未来数据发展到一个小时100w,按现在一次100ms,一个线程处理一秒钟 10次,一分钟 60 * 10 次,一个小时 60*10 *60 次 = 36000次,一天 60*10*60*24 = 864000次。 我们目标是一天100w次,通过增加两个线程就可以完成。但是如果要一个小时100w次呢?则需要增加30个线程和相应的硬件资源保证速度能够达到,这样成本也上去了。能否有更好的办法,提高我们比较的效率?

2、通过大量测试,simhash用于比较大文本,比如500字以上效果都还蛮好,距离小于3的基本都是相似,误判率也比较低。但是如果我们处理的是微博信息,最多也就140个字,使用simhash的效果并不那么理想。看如下图,在距离为3时是一个比较折中的点,在距离为10时效果已经很差了,不过我们测试短文本很多看起来相似的距离确实为10。如果使用距离为3,短文本大量重复信息不会被过滤,如果使用距离为10,长文本的错误率也非常高,如何解决?




  查看全部
通过 采集系统 我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析。分析前我们需要对这些数据去除重复,如何选择和设计文本的去重算法?常见的有余弦夹角算法、欧式距离、Jaccard相似度、最长公共子串、编辑距离等。这些算法对于待比较的文本数据不多时还比较好用,如果我们的爬虫每天采集的数据以千万计算,我们如何对于这些海量千万级的数据进行高效的合并去重。最简单的做法是拿着待比较的文本和数据库中所有的文本比较一遍如果是重复的数据就标示为重复。看起来很简单,我们来做个测试,就拿最简单的两个数据使用Apache提供的 Levenshtein for 循环100w次计算这两个数据的相似度。代码结果如下:
String s1 = "你妈妈喊你回家吃饭哦,回家罗回家罗" ;
String s2 = "你妈妈叫你回家吃饭啦,回家罗回家罗" ;

long t1 = System.currentTimeMillis();

for (int i = 0; i < 1000000; i++) {
int dis = StringUtils .getLevenshteinDistance(s1, s2);
}

long t2 = System.currentTimeMillis();

System. out .println(" 耗费时间: " + (t2 - t1) + " ms ");
耗费时间: 4266 ms

大跌眼镜,居然计算耗费4秒。假设我们一天需要比较100w次,光是比较100w次的数据是否重复就需要4s,就算4s一个文档,单线程一分钟才处理15个文档,一个小时才900个,一天也才21600个文档,这个数字和一天100w相差甚远,需要多少机器和资源才能解决。

为此我们需要一种应对于海量数据场景的去重方案,经过研究发现有种叫 local sensitive hash 局部敏感哈希 的东西,据说这玩意可以把文档降维到hash数字,数字两两计算运算量要小很多。查找很多文档后看到google对于网页去重使用的是simhash,他们每天需要处理的文档在亿级别,大大超过了我们现在文档的水平。既然老大哥也有类似的应用,我们也赶紧尝试下。simhash是由 Charikar 在2002年提出来的,参考 《Similarity estimation techniques from rounding algorithms》 。 介绍下这个算法主要原理,为了便于理解尽量不使用数学公式,分为这几步:
 


1、分词,把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重,我们假设权重分为5个级别(1~5)。比如:“ 美国“51区”雇员称内部有9架飞碟,曾看见灰色外星人 ” ==> 分词后为 “ 美国(4) 51区(5) 雇员(3) 称(1) 内部(2) 有(1) 9架(3) 飞碟(5) 曾(1) 看见(3) 灰色(4) 外星人(5)”,括号里是代表单词在整个句子里重要程度,数字越大越重要。

2、hash,通过hash算法把每个词变成hash值,比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字,还记得文章开头说过的吗,要把文章变为数字计算才能提高相似度计算性能,现在是降维过程进行时。

3、加权,通过 2步骤的hash生成结果,需要按照单词的权重形成加权数字串,比如“美国”的hash值为“100101”,通过加权计算为“4 -4 -4 4 -4 4”;“51区”的hash值为“101011”,通过加权计算为 “ 5 -5 5 -5 5 5”。

4、合并,把上面各个单词算出来的序列值累加,变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”,“51区”的 “ 5 -5 5 -5 5 5”, 把每一位进行累加, “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的,真实计算需要把所有单词的序列串累加。

5、降维,把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串,形成我们最终的simhash签名。 如果每一位大于0 记为 1,小于0 记为 0。最后算出结果为:“1 0 1 0 1 1”。


 
整个过程图为:

simhash.png

 
大家可能会有疑问,经过这么多步骤搞这么麻烦,不就是为了得到个 0 1 字符串吗?我直接把这个文本作为字符串输入,用hash函数生成 0 1 值更简单。其实不是这样的,传统hash函数解决的是生成唯一值,比如 md5、hashmap等。md5是用于生成唯一签名串,只要稍微多加一个字符md5的两个数字看起来相差甚远;hashmap也是用于键值对查找,便于快速插入和查找的数据结构。不过我们主要解决的是文本相似度计算,要比较的是两个文章是否相识,当然我们降维生成了hashcode也是用于这个目的。看到这里估计大家就明白了,我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的,而传统的hashcode却不行。我们可以来做个测试,两个相差只有一个字符的文本串,“你妈妈喊你回家吃饭哦,回家罗回家罗” 和 “你妈妈叫你回家吃饭啦,回家罗回家罗”。

通过simhash计算结果为:

1000010010101101111111100000101011010001001111100001001011001011

1000010010101101011111100000101011010001001111100001101010001011

通过 hashcode计算为:

1111111111111111111111111111111110001000001100110100111011011110

1010010001111111110010110011101

大家可以看得出来,相似的文本只有部分 01 串变化了,而普通的hashcode却不能做到,这个就是局部敏感哈希的魅力。目前Broder提出的shingling算法和Charikar的simhash算法应该算是业界公认比较好的算法。在simhash的发明人Charikar的论文中并没有给出具体的simhash算法和证明,“量子图灵”得出的证明simhash是由随机超平面hash算法演变而来的。

现在通过这样的转换,我们把库里的文本都转换为simhash 代码,并转换为long类型存储,空间大大减少。现在我们虽然解决了空间,但是如何计算两个simhash的相似度呢?难道是比较两个simhash的01有多少个不同吗?对的,其实也就是这样,我们通过海明距离(Hamming distance)就可以计算出两个simhash到底相似不相似。两个simhash对应二进制(01串)取值不同的数量称为这两个simhash的海明距离。举例如下: 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同,则海明距离为3。对于二进制字符串的a和b,海明距离为等于在a XOR b运算结果中1的个数(普遍算法)。

为了高效比较,我们预先加载了库里存在文本并转换为simhash code 存储在内存空间。来一条文本先转换为 simhash code,然后和内存里的simhash code 进行比较,测试100w次计算在100ms。速度大大提升。

未完待续:

1、目前速度提升了但是数据是不断增量的,如果未来数据发展到一个小时100w,按现在一次100ms,一个线程处理一秒钟 10次,一分钟 60 * 10 次,一个小时 60*10 *60 次 = 36000次,一天 60*10*60*24 = 864000次。 我们目标是一天100w次,通过增加两个线程就可以完成。但是如果要一个小时100w次呢?则需要增加30个线程和相应的硬件资源保证速度能够达到,这样成本也上去了。能否有更好的办法,提高我们比较的效率?

2、通过大量测试,simhash用于比较大文本,比如500字以上效果都还蛮好,距离小于3的基本都是相似,误判率也比较低。但是如果我们处理的是微博信息,最多也就140个字,使用simhash的效果并不那么理想。看如下图,在距离为3时是一个比较折中的点,在距离为10时效果已经很差了,不过我们测试短文本很多看起来相似的距离确实为10。如果使用距离为3,短文本大量重复信息不会被过滤,如果使用距离为10,长文本的错误率也非常高,如何解决?
simhash2.png

 

相似文档查找算法之 simHash

专业名词zkbhj 发表了文章 • 0 个评论 • 1091 次浏览 • 2018-09-05 14:50 • 来自相关话题

简单易懂的理解什么是神经网络

专业名词zkbhj 发表了文章 • 0 个评论 • 976 次浏览 • 2018-06-24 11:57 • 来自相关话题

分类
神经网络最重要的用途是分类,为了让大家对分类有个直观的认识,咱们先看几个例子:
 
 
垃圾邮件识别:现在有一封电子邮件,把出现在里面的所有词汇提取出来,送进一个机器里,机器需要判断这封邮件是否是垃圾邮件。疾病判断:病人到医院去做了一大堆肝功、尿检测验,把测验结果送进一个机器里,机器需要判断这个病人是否得病,得的什么病。猫狗分类:有一大堆猫、狗照片,把每一张照片送进一个机器里,机器需要判断这幅照片里的东西是猫还是狗。

这种能自动对输入的东西进行分类的机器,就叫做分类器。
 
分类器的输入是一个数值向量,叫做特征(向量)。在第一个例子里,分类器的输入是一堆0、1值,表示字典里的每一个词是否在邮件中出现,比如向量(1,1,0,0,0......)就表示这封邮件里只出现了两个词abandon和abnormal;第二个例子里,分类器的输入是一堆化验指标;第三个例子里,分类器的输入是照片,假如每一张照片都是320*240像素的红绿蓝三通道彩色照片,那么分类器的输入就是一个长度为320*240*3=230400的向量。

分类器的输出也是数值。第一个例子中,输出1表示邮件是垃圾邮件,输出0则说明邮件是正常邮件;第二个例子中,输出0表示健康,输出1表示有甲肝,输出2表示有乙肝,输出3表示有饼干等等;第三个例子中,输出0表示图片中是狗,输出1表示是猫。

分类器的目标就是让正确分类的比例尽可能高。一般我们需要首先收集一些样本,人为标记上正确分类结果,然后用这些标记好的数据训练分类器,训练好的分类器就可以在新来的特征向量上工作了。

神经元

咱们假设分类器的输入是通过某种途径获得的两个值,输出是0和1,比如分别代表猫和狗。现在有一些样本:





 
大家想想,最简单地把这两组特征向量分开的方法是啥?当然是在两组数据中间画一条竖直线,直线左边是狗,右边是猫,分类器就完成了。以后来了新的向量,凡是落在直线左边的都是狗,落在右边的都是猫。

一条直线把平面一分为二,一个平面把三维空间一分为二,一个n-1维超平面把n维空间一分为二,两边分属不同的两类,这种分类器就叫做神经元。
 
大家都知道平面上的直线方程是 ax+by+c=0 。,等式左边大于零和小于零分别表示点  (x,y)在直线的一侧还是另一侧,把这个式子推广到n维空间里,直线的高维形式称为超平面,它的方程是:




神经元就是当h大于0时输出1,h小于0时输出0这么一个模型,它的实质就是把特征空间一切两半,认为两瓣分别属两个类。你恐怕再也想不到比这更简单的分类器了,它是McCulloch和Pitts在1943年想出来了。
这个模型有点像人脑中的神经元:从多个感受器接受电信号




,进行处理(加权相加再偏移一点,即判断输入是否在某条直线  h=0 的一侧),发出电信号(在正确的那侧发出1,否则不发信号,可以认为是发出0),这就是它叫神经元的原因。

当然,上面那幅图我们是开了上帝视角才知道“一条竖直线能分开两类”,在实际训练神经元时,我们并不知道特征是怎么抱团的。神经元模型的一种学习方法称为Hebb算法:
先随机选一条直线/平面/超平面,然后把样本一个个拿过来,如果这条直线分错了,说明这个点分错边了,就稍微把直线移动一点,让它靠近这个样本,争取跨过这个样本,让它跑到直线正确的一侧;如果直线分对了,它就暂时停下不动。因此训练神经元的过程就是这条直线不断在跳舞,最终跳到两个类之间的竖直线位置。 
神经网络
MP神经元有几个显著缺点。首先它把直线一侧变为0,另一侧变为1,这东西不可微,不利于数学分析。人们用一个和0-1阶跃函数类似但是更平滑的函数Sigmoid函数来代替它(Sigmoid函数自带一个尺度参数,可以控制神经元对离超平面距离不同的点的响应,这里忽略它),从此神经网络的训练就可以用梯度下降法来构造了,这就是有名的反向传播算法。

神经元的另一个缺点是:它只能切一刀!你给我说说一刀怎么能把下面这两类分开吧。





 
解决办法是多层神经网络,底层神经元的输出是高层神经元的输入。我们可以在中间横着砍一刀,竖着砍一刀,然后把左上和右下的部分合在一起,与右上的左下部分分开;也可以围着左上角的边沿砍10刀把这一部分先挖出来,然后和右下角合并。

每砍一刀,其实就是使用了一个神经元,把不同砍下的半平面做交、并等运算,就是把这些神经元的输出当作输入,后面再连接一个神经元。这个例子中特征的形状称为异或,这种情况一个神经元搞不定,但是两层神经元就能正确对其进行分类。

只要你能砍足够多刀,把结果拼在一起,什么奇怪形状的边界神经网络都能够表示,所以说神经网络在理论上可以表示很复杂的函数/空间分布。但是真实的神经网络是否能摆动到正确的位置还要看网络初始值设置、样本容量和分布。

神经网络神奇的地方在于它的每一个组件非常简单——把空间切一刀+某种激活函数(0-1阶跃、sigmoid、max-pooling),但是可以一层一层级联。输入向量连到许多神经元上,这些神经元的输出又连到一堆神经元上,这一过程可以重复很多次。这和人脑中的神经元很相似:每一个神经元都有一些神经元作为其输入,又是另一些神经元的输入,数值向量就像是电信号,在不同神经元之间传导,每一个神经元只有满足了某种条件才会发射信号到下一层神经元。当然,人脑比神经网络模型复杂很多:人工神经网络一般不存在环状结构;人脑神经元的电信号不仅有强弱,还有时间缓急之分,就像莫尔斯电码,在人工神经网络里没有这种复杂的信号模式。
 
神经网络的训练依靠反向传播算法:最开始输入层输入特征向量,网络层层计算获得输出,输出层发现输出和正确的类号不一样,这时它就让最后一层神经元进行参数调整,最后一层神经元不仅自己调整参数,还会勒令连接它的倒数第二层神经元调整,层层往回退着调整。经过调整的网络会在样本上继续测试,如果输出还是老分错,继续来一轮回退调整,直到网络输出满意为止。这很像中国的文艺体制,武媚娘传奇剧组就是网络中的一个神经元,最近刚刚调整了参数。

大型神经网络

我们不禁要想了,假如我们的这个网络有10层神经元,第8层第2015个神经元,它有什么含义呢?我们知道它把第七层的一大堆神经元的输出作为输入,第七层的神经元又是以第六层的一大堆神经元做为输入,那么这个特殊第八层的神经元,它会不会代表了某种抽象的概念?

就好比你的大脑里有一大堆负责处理声音、视觉、触觉信号的神经元,它们对于不同的信息会发出不同的信号,那么会不会有这么一个神经元(或者神经元小集团),它收集这些信号,分析其是否符合某个抽象的概念,和其他负责更具体和更抽象概念的神经元进行交互。

2012年多伦多大学的Krizhevsky等人构造了一个超大型卷积神经网络[1],有9层,共65万个神经元,6千万个参数。网络的输入是图片,输出是1000个类,比如小虫、美洲豹、救生船等等。这个模型的训练需要海量图片,它的分类准确率也完爆先前所有分类器。纽约大学的Zeiler和Fergusi[2]把这个网络中某些神经元挑出来,把在其上响应特别大的那些输入图像放在一起,看它们有什么共同点。他们发现中间层的神经元响应了某些十分抽象的特征。 
第一层神经元主要负责识别颜色和简单纹理第二层的一些神经元可以识别更加细化的纹理,比如布纹、刻度、叶纹。第三层的一些神经元负责感受黑夜里的黄色烛光、鸡蛋黄、高光。第四层的一些神经元负责识别萌狗的脸、七星瓢虫和一堆圆形物体的存在。第五层的一些神经元可以识别出花、圆形屋顶、键盘、鸟、黑眼圈动物。

这里面的概念并不是整个网络的输出,是网络中间层神经元的偏好,它们为后面的神经元服务。虽然每一个神经元都傻不拉几的(只会切一刀),但是65万个神经元能学到的东西还真是深邃呢。 查看全部
分类
神经网络最重要的用途是分类,为了让大家对分类有个直观的认识,咱们先看几个例子:
 
 
  1. 垃圾邮件识别:现在有一封电子邮件,把出现在里面的所有词汇提取出来,送进一个机器里,机器需要判断这封邮件是否是垃圾邮件。
  2. 疾病判断:病人到医院去做了一大堆肝功、尿检测验,把测验结果送进一个机器里,机器需要判断这个病人是否得病,得的什么病。
  3. 猫狗分类:有一大堆猫、狗照片,把每一张照片送进一个机器里,机器需要判断这幅照片里的东西是猫还是狗。


这种能自动对输入的东西进行分类的机器,就叫做分类器
 
分类器的输入是一个数值向量,叫做特征(向量)。在第一个例子里,分类器的输入是一堆0、1值,表示字典里的每一个词是否在邮件中出现,比如向量(1,1,0,0,0......)就表示这封邮件里只出现了两个词abandon和abnormal;第二个例子里,分类器的输入是一堆化验指标;第三个例子里,分类器的输入是照片,假如每一张照片都是320*240像素的红绿蓝三通道彩色照片,那么分类器的输入就是一个长度为320*240*3=230400的向量。

分类器的输出也是数值。第一个例子中,输出1表示邮件是垃圾邮件,输出0则说明邮件是正常邮件;第二个例子中,输出0表示健康,输出1表示有甲肝,输出2表示有乙肝,输出3表示有饼干等等;第三个例子中,输出0表示图片中是狗,输出1表示是猫。

分类器的目标就是让正确分类的比例尽可能高。一般我们需要首先收集一些样本,人为标记上正确分类结果,然后用这些标记好的数据训练分类器,训练好的分类器就可以在新来的特征向量上工作了。

神经元

咱们假设分类器的输入是通过某种途径获得的两个值,输出是0和1,比如分别代表猫和狗。现在有一些样本:

WX20180624-114555@2x.png

 
大家想想,最简单地把这两组特征向量分开的方法是啥?当然是在两组数据中间画一条竖直线,直线左边是狗,右边是猫,分类器就完成了。以后来了新的向量,凡是落在直线左边的都是狗,落在右边的都是猫。

一条直线把平面一分为二,一个平面把三维空间一分为二,一个n-1维超平面把n维空间一分为二,两边分属不同的两类,这种分类器就叫做神经元。
 
大家都知道平面上的直线方程是 ax+by+c=0 。,等式左边大于零和小于零分别表示点  (x,y)在直线的一侧还是另一侧,把这个式子推广到n维空间里,直线的高维形式称为超平面,它的方程是:
WX20180624-114754@2x.png

神经元就是当h大于0时输出1,h小于0时输出0这么一个模型,它的实质就是把特征空间一切两半,认为两瓣分别属两个类。你恐怕再也想不到比这更简单的分类器了,它是McCulloch和Pitts在1943年想出来了。
这个模型有点像人脑中的神经元:从多个感受器接受电信号
WX20180624-114835@2x.png

,进行处理(加权相加再偏移一点,即判断输入是否在某条直线  h=0 的一侧),发出电信号(在正确的那侧发出1,否则不发信号,可以认为是发出0),这就是它叫神经元的原因。

当然,上面那幅图我们是开了上帝视角才知道“一条竖直线能分开两类”,在实际训练神经元时,我们并不知道特征是怎么抱团的。神经元模型的一种学习方法称为Hebb算法:
先随机选一条直线/平面/超平面,然后把样本一个个拿过来,如果这条直线分错了,说明这个点分错边了,就稍微把直线移动一点,让它靠近这个样本,争取跨过这个样本,让它跑到直线正确的一侧;如果直线分对了,它就暂时停下不动。因此训练神经元的过程就是这条直线不断在跳舞,最终跳到两个类之间的竖直线位置。 
神经网络
MP神经元有几个显著缺点。首先它把直线一侧变为0,另一侧变为1,这东西不可微,不利于数学分析。人们用一个和0-1阶跃函数类似但是更平滑的函数Sigmoid函数来代替它(Sigmoid函数自带一个尺度参数,可以控制神经元对离超平面距离不同的点的响应,这里忽略它),从此神经网络的训练就可以用梯度下降法来构造了,这就是有名的反向传播算法。

神经元的另一个缺点是:它只能切一刀!你给我说说一刀怎么能把下面这两类分开吧。

WX20180624-115229@2x.png

 
解决办法是多层神经网络,底层神经元的输出是高层神经元的输入。我们可以在中间横着砍一刀,竖着砍一刀,然后把左上和右下的部分合在一起,与右上的左下部分分开;也可以围着左上角的边沿砍10刀把这一部分先挖出来,然后和右下角合并。

每砍一刀,其实就是使用了一个神经元,把不同砍下的半平面做交、并等运算,就是把这些神经元的输出当作输入,后面再连接一个神经元。这个例子中特征的形状称为异或,这种情况一个神经元搞不定,但是两层神经元就能正确对其进行分类。

只要你能砍足够多刀,把结果拼在一起,什么奇怪形状的边界神经网络都能够表示,所以说神经网络在理论上可以表示很复杂的函数/空间分布。但是真实的神经网络是否能摆动到正确的位置还要看网络初始值设置、样本容量和分布。

神经网络神奇的地方在于它的每一个组件非常简单——把空间切一刀+某种激活函数(0-1阶跃、sigmoid、max-pooling),但是可以一层一层级联。输入向量连到许多神经元上,这些神经元的输出又连到一堆神经元上,这一过程可以重复很多次。这和人脑中的神经元很相似:每一个神经元都有一些神经元作为其输入,又是另一些神经元的输入,数值向量就像是电信号,在不同神经元之间传导,每一个神经元只有满足了某种条件才会发射信号到下一层神经元。当然,人脑比神经网络模型复杂很多:人工神经网络一般不存在环状结构;人脑神经元的电信号不仅有强弱,还有时间缓急之分,就像莫尔斯电码,在人工神经网络里没有这种复杂的信号模式。
 
神经网络的训练依靠反向传播算法:最开始输入层输入特征向量,网络层层计算获得输出,输出层发现输出和正确的类号不一样,这时它就让最后一层神经元进行参数调整,最后一层神经元不仅自己调整参数,还会勒令连接它的倒数第二层神经元调整,层层往回退着调整。经过调整的网络会在样本上继续测试,如果输出还是老分错,继续来一轮回退调整,直到网络输出满意为止。这很像中国的文艺体制,武媚娘传奇剧组就是网络中的一个神经元,最近刚刚调整了参数。

大型神经网络

我们不禁要想了,假如我们的这个网络有10层神经元,第8层第2015个神经元,它有什么含义呢?我们知道它把第七层的一大堆神经元的输出作为输入,第七层的神经元又是以第六层的一大堆神经元做为输入,那么这个特殊第八层的神经元,它会不会代表了某种抽象的概念?

就好比你的大脑里有一大堆负责处理声音、视觉、触觉信号的神经元,它们对于不同的信息会发出不同的信号,那么会不会有这么一个神经元(或者神经元小集团),它收集这些信号,分析其是否符合某个抽象的概念,和其他负责更具体和更抽象概念的神经元进行交互。

2012年多伦多大学的Krizhevsky等人构造了一个超大型卷积神经网络[1],有9层,共65万个神经元,6千万个参数。网络的输入是图片,输出是1000个类,比如小虫、美洲豹、救生船等等。这个模型的训练需要海量图片,它的分类准确率也完爆先前所有分类器。纽约大学的Zeiler和Fergusi[2]把这个网络中某些神经元挑出来,把在其上响应特别大的那些输入图像放在一起,看它们有什么共同点。他们发现中间层的神经元响应了某些十分抽象的特征。 
  • 第一层神经元主要负责识别颜色和简单纹理
  • 第二层的一些神经元可以识别更加细化的纹理,比如布纹、刻度、叶纹。
  • 第三层的一些神经元负责感受黑夜里的黄色烛光、鸡蛋黄、高光。
  • 第四层的一些神经元负责识别萌狗的脸、七星瓢虫和一堆圆形物体的存在。
  • 第五层的一些神经元可以识别出花、圆形屋顶、键盘、鸟、黑眼圈动物。


这里面的概念并不是整个网络的输出,是网络中间层神经元的偏好,它们为后面的神经元服务。虽然每一个神经元都傻不拉几的(只会切一刀),但是65万个神经元能学到的东西还真是深邃呢。

#2020学习打卡##C程序设计语言# 什么是排序算法的稳定性?

回复

常识zkbhj 回复了问题 • 1 人关注 • 1 个回复 • 1792 次浏览 • 2020-05-07 19:28 • 来自相关话题

什么是HashTime33?

回复

专业名词zkbhj 回复了问题 • 1 人关注 • 1 个回复 • 2258 次浏览 • 2019-10-27 11:18 • 来自相关话题

什么是快速排序?

回复

专业名词zkbhj 回复了问题 • 1 人关注 • 1 个回复 • 1545 次浏览 • 2017-03-01 14:15 • 来自相关话题

什么是冒泡排序?

回复

专业名词zkbhj 回复了问题 • 1 人关注 • 1 个回复 • 1543 次浏览 • 2017-03-01 11:51 • 来自相关话题

如何根据区间进行判断?

回复

PHPzkbhj 回复了问题 • 1 人关注 • 1 个回复 • 2607 次浏览 • 2016-12-07 16:23 • 来自相关话题

中文分词及结巴分词原理概述

搜索推荐zkbhj 发表了文章 • 0 个评论 • 1034 次浏览 • 2020-08-01 17:08 • 来自相关话题

中文分词概述

简单来说,中文分词根据实现特点大致可分为两个类别:
 

基于词典的分词方法;
基于统计的分词方法。


基于词典的分词方法

基于词典的分词方法首先会建立一个充分大的词典,然后依据一定的策略扫描句子,若句子中的某个子串与词典中的某个词匹配,则分词成功。

常见的扫描策略有:正向最大匹配、逆向最大匹配、双向最大匹配和最少词数分词。


正向最大匹配

对输入的句子从左至右,以贪心的方式切分出当前位置上长度最大的词,组不了词的字单独划开。其分词原理是:词的颗粒度越大,所能表示的含义越精确。

逆向最大匹配

原理与正向最大匹配相同,但顺序不是从首字开始,而是从末字开始,而且它使用的分词词典是逆序词典,其中每个词条都按逆序方式存放。在实际处理时,先将句子进行倒排处理,生成逆序句子,然后根据逆序词典,对逆序句子用正向最大匹配。

双向最大匹配

将正向最大匹配与逆向最大匹配组合起来,对句子使用这两种方式进行扫描切分,如果两种分词方法得到的匹配结果相同,则认为分词正确,否则,按最小集处理。

最少词数分词

即一句话应该分成数量最少的词串,该方法首先会查找词典中最长的词,看是不是所要分词的句子的子串,如果是则切分,然后不断迭代以上步骤,每次都会在剩余的字符串中取最长的词进行分词,最后就可以得到最少的词数。


总结:基于词典的分词方法简单、速度快,效果也还可以,但对歧义和新词的处理不是很好,对词典中未登录的词没法进行处理。

 
基于统计的分词方法

基于统计的分词方法是从大量已经分词的文本中,利用统计学习方法来学习词的切分规律,从而实现对未知文本的切分。随着大规模语料库的建立,基于统计的分词方法不断受到研究和发展,渐渐成为了主流。

常用的统计学习方法有:隐马尔可夫模型(HMM)、条件随机场(CRF)和基于深度学习的方法。

HMM和CRF

这两种方法实质上是对序列进行标注,将分词问题转化为字的分类问题,每个字有4种词位(类别):词首(B)、词中(M)、词尾(E)和单字成词(S)。由字构词的方法并不依赖于事先编制好的词典,只需对分好词的语料进行训练即可。当模型训练好后,就可对新句子进行预测,预测时会针对每个字生成不同的词位。其中HMM属于生成式模型,CRF属于判别式模型。

基于深度学习的方法

神经网络的序列标注算法在词性标注、命名实体识别等问题上取得了优秀的进展,这些端到端的方法也可以迁移到分词问题上。与所有深度学习的方法一样,该方法需要较大的训练语料才能体现优势,代表为BiLSTM-CRF。

 
总结:基于统计的分词方法能很好地处理歧义和新词问题,效果比基于词典的要好,但该方法需要有大量人工标注分好词的语料作为支撑,训练开销大,就分词速度而言不如前一种。


在实际应用中一般是将词典与统计学习方法结合起来,既发挥词典分词切分速度快的特点,又利用了统计分词结合上下文识别生词、自动消除歧义的优点。结巴分词正是这一类的代表,下面简要介绍一下它的实现算法。
 
结巴分词原理

官方Github上对所用算法的描述为:

基于前缀词典实现高效的词图扫描,生成句子中汉字所有可能成词情况所构成的有向无环图 (DAG);
采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合;
对于未登录词,采用了基于汉字成词能力的 HMM 模型,使用了 Viterbi 算法。


下面逐一介绍:

构造前缀词典

结巴分词首先会依照统计词典dict.txt构造前缀词典。dict.txt含有近35万的词条,每个词条占用一行,其中每一行有3列,第一列为词条,第二列为对应的词频,第三列为词性,构造前缀词典需要用到前两列。

具体做法为:首先定义一个空的python字典,然后遍历dict.txt的每一行,取词条作为字典的键,词频作为对应的键值,然后遍历该词条的前缀,如果前缀对应的键不在字典里,就把该前缀设为字典新的键,对应的键值设为0,如果前缀在字典里,则什么都不做。

这样等遍历完dict.txt后,前缀词典就构造好了。在构造前缀词典时,会对统计词典里所有词条的词频做一下累加,累加值等计算最大概率路径时会用到。

生成有向无环图(DAG)

用正则表达式分割句子后,对每一个单独的子句会生成一个有向无环图。

具体方式为:先定义一个空的python字典,然后遍历子句,当前子句元素的索引会作为字典的一个键,对应的键值为一个python列表(初始为空),然后会以当前索引作为子串的起始索引,不断向后遍历生成不同的子串,如果子串在前缀词典里且键值不为0的话,则把子串的终止索引添加到列表中。

这样等遍历完子句的所有字后,对应的DAG就生成好了。(子串的键值如果是0,则说明它不是一个词条)

计算最大概率路径

DAG的起点到终点会有很多路径,需要找到一条概率最大的路径,然后据此进行分词。可以采用动态规划来求解最大概率路径。

具体来说就是:从子句的最后一个字开始,倒序遍历子句的每个字,取当前字对应索引在DAG字典中的键值(一个python列表),然后遍历该列表,当前字会和列表中每个字两两组合成一个词条,然后基于词频计算出当前字到句尾的概率,以python元组的方式保存最大概率,元祖第一个元素是最大概率的对数,第二个元素为最大概率对应词条的终止索引。

词频可看作DAG中边的权重,之所以取概率的对数是为了防止数值下溢。有了最大概率路径,分词结果也就随之确定。

 对未登录词采用HMM模型进行分词

当出现没有在前缀词典里收录的词时,会采用HMM模型进行分词。HMM模型有5个基本组成:观测序列、状态序列、状态初始概率、状态转移概率和状态发射概率。分词属于HMM的预测问题,即已知观测序列、状态初始概率、状态转移概率和状态发射概率的条件下,求状态序列。结巴分词已经内置了训练好的状态初始概率、状态转移概率和状态发射概率。

句子会作为观测序列,当有新句子进来时,具体做法为:先通过Viterbi算法求出概率最大的状态序列,然后基于状态序列输出分词结果(每个字的状态为B、M、E、S之一)。

至此,结巴分词的原理就简单介绍完了。
 
参考文档:
https://www.cnblogs.com/cyandn/p/10891608.html
https://www.cnblogs.com/zhbzz2007/p/6084196.html
  查看全部
中文分词概述

简单来说,中文分词根据实现特点大致可分为两个类别:
 


基于词典的分词方法;
基于统计的分词方法。



基于词典的分词方法

基于词典的分词方法首先会建立一个充分大的词典,然后依据一定的策略扫描句子,若句子中的某个子串与词典中的某个词匹配,则分词成功。

常见的扫描策略有:正向最大匹配、逆向最大匹配、双向最大匹配和最少词数分词。


正向最大匹配

对输入的句子从左至右,以贪心的方式切分出当前位置上长度最大的词,组不了词的字单独划开。其分词原理是:词的颗粒度越大,所能表示的含义越精确。

逆向最大匹配

原理与正向最大匹配相同,但顺序不是从首字开始,而是从末字开始,而且它使用的分词词典是逆序词典,其中每个词条都按逆序方式存放。在实际处理时,先将句子进行倒排处理,生成逆序句子,然后根据逆序词典,对逆序句子用正向最大匹配。

双向最大匹配

将正向最大匹配与逆向最大匹配组合起来,对句子使用这两种方式进行扫描切分,如果两种分词方法得到的匹配结果相同,则认为分词正确,否则,按最小集处理。

最少词数分词

即一句话应该分成数量最少的词串,该方法首先会查找词典中最长的词,看是不是所要分词的句子的子串,如果是则切分,然后不断迭代以上步骤,每次都会在剩余的字符串中取最长的词进行分词,最后就可以得到最少的词数。


总结:基于词典的分词方法简单、速度快,效果也还可以,但对歧义和新词的处理不是很好,对词典中未登录的词没法进行处理。

 
基于统计的分词方法

基于统计的分词方法是从大量已经分词的文本中,利用统计学习方法来学习词的切分规律,从而实现对未知文本的切分。随着大规模语料库的建立,基于统计的分词方法不断受到研究和发展,渐渐成为了主流。

常用的统计学习方法有:隐马尔可夫模型(HMM)、条件随机场(CRF)和基于深度学习的方法。

HMM和CRF

这两种方法实质上是对序列进行标注,将分词问题转化为字的分类问题,每个字有4种词位(类别):词首(B)、词中(M)、词尾(E)和单字成词(S)。由字构词的方法并不依赖于事先编制好的词典,只需对分好词的语料进行训练即可。当模型训练好后,就可对新句子进行预测,预测时会针对每个字生成不同的词位。其中HMM属于生成式模型,CRF属于判别式模型。

基于深度学习的方法

神经网络的序列标注算法在词性标注、命名实体识别等问题上取得了优秀的进展,这些端到端的方法也可以迁移到分词问题上。与所有深度学习的方法一样,该方法需要较大的训练语料才能体现优势,代表为BiLSTM-CRF。

 
总结:基于统计的分词方法能很好地处理歧义和新词问题,效果比基于词典的要好,但该方法需要有大量人工标注分好词的语料作为支撑,训练开销大,就分词速度而言不如前一种。


在实际应用中一般是将词典与统计学习方法结合起来,既发挥词典分词切分速度快的特点,又利用了统计分词结合上下文识别生词、自动消除歧义的优点。结巴分词正是这一类的代表,下面简要介绍一下它的实现算法。
 
结巴分词原理

官方Github上对所用算法的描述为:


基于前缀词典实现高效的词图扫描,生成句子中汉字所有可能成词情况所构成的有向无环图 (DAG)
采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合;
对于未登录词,采用了基于汉字成词能力的 HMM 模型,使用了 Viterbi 算法



下面逐一介绍:

构造前缀词典

结巴分词首先会依照统计词典dict.txt构造前缀词典。dict.txt含有近35万的词条,每个词条占用一行,其中每一行有3列,第一列为词条,第二列为对应的词频,第三列为词性,构造前缀词典需要用到前两列。

具体做法为:首先定义一个空的python字典,然后遍历dict.txt的每一行,取词条作为字典的键,词频作为对应的键值,然后遍历该词条的前缀,如果前缀对应的键不在字典里,就把该前缀设为字典新的键,对应的键值设为0,如果前缀在字典里,则什么都不做。

这样等遍历完dict.txt后,前缀词典就构造好了。在构造前缀词典时,会对统计词典里所有词条的词频做一下累加,累加值等计算最大概率路径时会用到。

生成有向无环图(DAG)

用正则表达式分割句子后,对每一个单独的子句会生成一个有向无环图。

具体方式为:先定义一个空的python字典,然后遍历子句,当前子句元素的索引会作为字典的一个键,对应的键值为一个python列表(初始为空),然后会以当前索引作为子串的起始索引,不断向后遍历生成不同的子串,如果子串在前缀词典里且键值不为0的话,则把子串的终止索引添加到列表中。

这样等遍历完子句的所有字后,对应的DAG就生成好了。(子串的键值如果是0,则说明它不是一个词条)

计算最大概率路径

DAG的起点到终点会有很多路径,需要找到一条概率最大的路径,然后据此进行分词。可以采用动态规划来求解最大概率路径。

具体来说就是:从子句的最后一个字开始,倒序遍历子句的每个字,取当前字对应索引在DAG字典中的键值(一个python列表),然后遍历该列表,当前字会和列表中每个字两两组合成一个词条,然后基于词频计算出当前字到句尾的概率,以python元组的方式保存最大概率,元祖第一个元素是最大概率的对数,第二个元素为最大概率对应词条的终止索引。

词频可看作DAG中边的权重,之所以取概率的对数是为了防止数值下溢。有了最大概率路径,分词结果也就随之确定。

 对未登录词采用HMM模型进行分词

当出现没有在前缀词典里收录的词时,会采用HMM模型进行分词。HMM模型有5个基本组成:观测序列、状态序列、状态初始概率、状态转移概率和状态发射概率。分词属于HMM的预测问题,即已知观测序列、状态初始概率、状态转移概率和状态发射概率的条件下,求状态序列。结巴分词已经内置了训练好的状态初始概率、状态转移概率和状态发射概率。

句子会作为观测序列,当有新句子进来时,具体做法为:先通过Viterbi算法求出概率最大的状态序列,然后基于状态序列输出分词结果(每个字的状态为B、M、E、S之一)。

至此,结巴分词的原理就简单介绍完了。
 
参考文档:
https://www.cnblogs.com/cyandn/p/10891608.html
https://www.cnblogs.com/zhbzz2007/p/6084196.html
 

算法之旅:理解透彻冒泡算法及它的几个优化版本

架构思想zkbhj 发表了文章 • 0 个评论 • 541 次浏览 • 2020-05-11 15:29 • 来自相关话题

什么是冒泡排序?

冒泡排序的英文Bubble Sort,是一种最基础的交换排序。

大家一定都喝过汽水,汽水中常常有许多小小的气泡,哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水要轻,所以小气泡可以一点一点向上浮动。

而我们的冒泡排序之所以叫做冒泡排序,正是因为这种排序算法的每一个元素都可以像小气泡一样,根据自身大小,一点一点向着数组的一侧移动。
 
原始的冒泡排序是稳定排序。由于该排序算法的每一轮要遍历所有元素,轮转的次数和元素数量相当,所以时间复杂度是O(N^2) 。





 
增强版1

对于后面已经有序的部分,不需要在进行比较了。增加isSorted标记,默认true,如果本轮存在交换,就变为false,说明下一轮可能还有排序。否则break跳出循环
 
这一版代码做了小小的改动,利用布尔变量isSorted作为标记。如果在本轮排序中,元素有交换,则说明数列无序;如果没有元素交换,说明数列已然有序,直接跳出大循环。





 
增强版2
提前预知已排好序的边界,减少排序比较次数。最后交换元素的下标记住。
 
这一版代码中,sortBorder就是无序数列的边界。每一轮排序过程中,sortBorder之后的元素就完全不需要比较了,肯定是有序的。





 
鸡尾酒排序
告别冒泡排序的单项比较移动,鸡尾酒排序是左右比较移动轮换着来的。内层循环有2个循环,一个向左,一个向右。
下面这段代码是鸡尾酒排序的原始实现。代码外层的大循环控制着所有排序回合,大循环内包含两个小循环,第一个循环从左向右比较并交换元素,第二个循环从右向左比较并交换元素。
 




 
鸡尾酒排序增强版
 
代码中使用了左右两个边界值,rightSortBorder 代表右边界,leftSortBorder代表左边界。 
在比较和交换元素时,奇数轮从 leftSortBorder 遍历到 rightSortBorder 位置,偶数轮从 rightSortBorder 遍历到 leftSortBorder 位置。





 
地精排序
 
它也像冒泡排序一样,相邻元素之间两两进行比较,如果这两个元素逆序,则交换。与冒泡排序不同的是,它如果遇到交换操作时,变为向前冒泡,直至不发生交换操作位置。相当于做了一个插入操作,将比较小的数插入到前面的有序序列中合适的位置。所以,地精排序可以说是冒泡排序和直接插入排序的综合。
 
BOOL GnomeSort(datatype *array, int size)
{
int i = 0;

if(array == NULL) {
return FALSE;
}

while(i < size) {
//如果i=0或者i-1与i正序时,i++
if(i == 0 || array[i-1] <= array[i]) {
i++;
} else {
//如果i-1与i逆序时,i--
Swap(array + i-1, array + i);
i--;
}
}

return TRUE;
}
参考文档:
https://mp.weixin.qq.com/s/wO11PDZSM5pQ0DfbQjKRQA
https://mp.weixin.qq.com/s/tXqjWWyjQ1ILfvnFv3_f7Q
https://blog.csdn.net/u010647471/article/details/49976345
  查看全部
什么是冒泡排序?

冒泡排序的英文Bubble Sort,是一种最基础的交换排序。

大家一定都喝过汽水,汽水中常常有许多小小的气泡,哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水要轻,所以小气泡可以一点一点向上浮动。

而我们的冒泡排序之所以叫做冒泡排序,正是因为这种排序算法的每一个元素都可以像小气泡一样,根据自身大小,一点一点向着数组的一侧移动。
 
原始的冒泡排序是稳定排序。由于该排序算法的每一轮要遍历所有元素,轮转的次数和元素数量相当,所以时间复杂度是O(N^2) 。

QQ截图20200511152317.jpg

 
增强版1

对于后面已经有序的部分,不需要在进行比较了。增加isSorted标记,默认true,如果本轮存在交换,就变为false,说明下一轮可能还有排序。否则break跳出循环
 
这一版代码做了小小的改动,利用布尔变量isSorted作为标记。如果在本轮排序中,元素有交换,则说明数列无序;如果没有元素交换,说明数列已然有序,直接跳出大循环。

QQ截图20200511152421.jpg

 
增强版2
提前预知已排好序的边界,减少排序比较次数。最后交换元素的下标记住。
 
这一版代码中,sortBorder就是无序数列的边界。每一轮排序过程中,sortBorder之后的元素就完全不需要比较了,肯定是有序的。

QQ截图20200511152513.jpg

 
鸡尾酒排序
告别冒泡排序的单项比较移动,鸡尾酒排序是左右比较移动轮换着来的。内层循环有2个循环,一个向左,一个向右。
下面这段代码是鸡尾酒排序的原始实现。代码外层的大循环控制着所有排序回合,大循环内包含两个小循环,第一个循环从左向右比较并交换元素,第二个循环从右向左比较并交换元素。
 
QQ截图20200511152558.jpg

 
鸡尾酒排序增强版
 
代码中使用了左右两个边界值,rightSortBorder 代表右边界,leftSortBorder代表左边界。 
在比较和交换元素时,奇数轮从 leftSortBorder 遍历到 rightSortBorder 位置,偶数轮从 rightSortBorder 遍历到 leftSortBorder 位置。

QQ截图20200511152638.jpg

 
地精排序
 
它也像冒泡排序一样,相邻元素之间两两进行比较,如果这两个元素逆序,则交换。与冒泡排序不同的是,它如果遇到交换操作时,变为向前冒泡,直至不发生交换操作位置。相当于做了一个插入操作,将比较小的数插入到前面的有序序列中合适的位置。所以,地精排序可以说是冒泡排序和直接插入排序的综合。
 
BOOL GnomeSort(datatype *array, int size)
{
int i = 0;

if(array == NULL) {
return FALSE;
}

while(i < size) {
//如果i=0或者i-1与i正序时,i++
if(i == 0 || array[i-1] <= array[i]) {
i++;
} else {
//如果i-1与i逆序时,i--
Swap(array + i-1, array + i);
i--;
}
}

return TRUE;
}

参考文档:
https://mp.weixin.qq.com/s/wO11PDZSM5pQ0DfbQjKRQA
https://mp.weixin.qq.com/s/tXqjWWyjQ1ILfvnFv3_f7Q
https://blog.csdn.net/u010647471/article/details/49976345
 

算法之旅:如何评价算法好坏的神器之时间复杂度

架构思想zkbhj 发表了文章 • 0 个评论 • 530 次浏览 • 2020-05-07 14:22 • 来自相关话题

时间复杂度是学习算法的基石,今天我们来聊聊为什么要引入时间复杂度,什么是时间复杂度以及如何去算一个算法的时间复杂度。
 

在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。


若存在函数 f(n),使得当n趋近于无穷大时,T(n)/ f(n)的极限值为不等于零的常数,则称 f(n)是T(n)的同数量级函数。
记作 T(n)= O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
渐进时间复杂度用大写O来表示,所以也被称为大O表示法。





 O(1)< O(logn)< O(n)< O(n^2)
 
 
 
参考文档:
https://mp.weixin.qq.com/s?src=11&timestamp=1588832012&ver=2323&signature=37Md0F80eUGKg9BeRAXTAeHawoHpJxHPzwvPguG0Ow0y5e7oK1IQ5C*36ApecKiCEkT98Vi6hPH2KoVqeHQ6ZSVvuFWp0MEzvDb*Wg657Fcvg9ToEOTDltnC39r*5*I9&new=1
https://mp.weixin.qq.com/s?__biz=MzU1MDE4MzUxNA==&mid=2247483867&idx=1&sn=6270b56b79cb74334eb4faf80de05f0a&chksm=fba536eeccd2bff8e38566b3c12b439666fca9ec7ffa2a6c0d2271550702a3dc0851bd99d0cf&scene=21#wechat_redirect
  查看全部
时间复杂度是学习算法的基石,今天我们来聊聊为什么要引入时间复杂度,什么是时间复杂度以及如何去算一个算法的时间复杂度。
 


在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。



若存在函数 f(n),使得当n趋近于无穷大时,T(n)/ f(n)的极限值为不等于零的常数,则称 f(n)是T(n)的同数量级函数。
记作 T(n)= O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
渐进时间复杂度用大写O来表示,所以也被称为大O表示法。


dcc451da81cb39db86d6cf67dd160924ab1830e8.png

 O(1)< O(logn)< O(n)< O(n^2)
 
 
 
参考文档:
https://mp.weixin.qq.com/s?src=11&timestamp=1588832012&ver=2323&signature=37Md0F80eUGKg9BeRAXTAeHawoHpJxHPzwvPguG0Ow0y5e7oK1IQ5C*36ApecKiCEkT98Vi6hPH2KoVqeHQ6ZSVvuFWp0MEzvDb*Wg657Fcvg9ToEOTDltnC39r*5*I9&new=1
https://mp.weixin.qq.com/s?__biz=MzU1MDE4MzUxNA==&mid=2247483867&idx=1&sn=6270b56b79cb74334eb4faf80de05f0a&chksm=fba536eeccd2bff8e38566b3c12b439666fca9ec7ffa2a6c0d2271550702a3dc0851bd99d0cf&scene=21#wechat_redirect
 

#2020学习打卡##C程序设计语言# 直接插入排序和改进版Shell排序解析

C语言zkbhj 发表了文章 • 0 个评论 • 576 次浏览 • 2020-04-14 17:54 • 来自相关话题

一、直接插入排序

直接插入排序(Straight Insertion Sort)是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的、记录数量增1的有序表。直接插入排序的时间复杂度为 O(n2)。

 
实例如下所示:

定义的数组   :      {23,34,56,78,65,90,88,92,18,21}

过程如下所示:

【23】   34   56   78   65   90   88   92   18   21

第 1 次排序结果:   【23   34】   56   78   65   90   88   92   18   21 

——用34插入到【23】序列中,34>23,故插入后的顺序是【23,34】


第 2 次排序结果:   【 23   34     56 】78   65   90   88   92   18   21

——用56插入到【23,34】序列中,56>34,故插入后的顺序是【23,34,56】


第 3 次排序结果:   【23   34      56    78】65   90   88   92   18   21

——用78插入到【23,34,56】序列中,78>56,故插入后的顺序是【23,34,56,78】


第 4 次排序结果:   【23   34     56     65   78 】90   88   92   18   21    

——用65插入到【23,34,56,78】序列中,65<78,所以78后移一位,和56比较,65>56,故插入后的顺序是【23,34,56,65, 78】


第 5 次排序结果:   【23   34   56   65   78   90 】  88   92   18   21

——用90插入到【23,34,56,65, 78】序列中,78<90 ,故插入后的顺序是【23   34   56   65   78   90 】


第 6 次排序结果:   23   34   56   65   78   88   90   92   18   21

——用88插入到【23   34   56   65   78   90 】序列中,90>88 ,所以90后移一位,故插入后的顺序是【23   34   56   65   78   88   90】


第 7 次排序结果:   23   34   56   65   78   88   90   92   18   21

——用92插入到【23   34   56   65   78   90 】序列中,90<92 ,故插入后的顺序是【23   34   56   65   78   90   92 】


第 8 次排序结果:   18   23   34   56   65   78   88   90   92   21

——用18插入到【23   34   56   65   78   90   92 】序列中,18<92,所以92后移一位,和90比较,90>18,依次后移,直到第一位23,因为18<23, 故插入后的顺序是【18   23   34   56   65   78   88   90   92】


第 9 次排序结果:   18   21   23   34   56   65   78   88   90   92

——用21插入到【23   34   56   65   78   90   92 】序列中,21<92,故92后移一位,和90比较,90>21,依次后移,直到第一位18,因为18<21, 故插入后的顺序是【18   21   23   34   56   65   78   88   90   92】 
C语言实现:#include <stdio.h>
//自定义的输出函数
void print(int a, int n ,int i){
printf("%d:",i);
for(int j=0; j<8; j++){
printf("%d",a[j]);
}
printf("\n");
}
//直接插入排序函数
void InsertSort(int a, int n)
{
for(int i= 1; i<n; i++){
if(a < a[i-1]){//若第 i 个元素大于 i-1 元素则直接插入;反之,需要找到适当的插入位置后在插入。
int j= i-1;
int x = a;
while(j>-1 && x < a[j]){ //采用顺序查找方式找到插入的位置,在查找的同时,将数组中的元素进行后移操作,给插入元素腾出空间
a[j+1] = a[j];
j--;
}
a[j+1] = x; //插入到正确位置
}
print(a,n,i);//打印每次排序后的结果
}
}
int main(){
int a[8] = {3,1,7,5,2,4,9,6};
InsertSort(a,8);
return 0;
}
二、Shell排序:直接插入排序算法的一种高速而稳定的改进版本
 


希尔排序,也称递减增量排序算法,是一种插入排序算法,它出自D.L.Shell,因此而得名。Shell排序又称作缩小增量排序。Shell排序的执行时间依赖于增量序列。


希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量=1(<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
 
Shell排序算法的特点


希尔排序是基于插入排序的以下两点性质而提出改进方法的:
插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率[list][*]但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位

[/*]
[/list]


时间复杂度:最坏情况下为O(n^2),平均时间复杂度为O(nlogn);
空间复杂度:归并排序需要一个大小为1的临时存储空间用以保存合并序列,所以空间复杂度为O(1)
算法稳定性:从上面图片中可以看出,数字5在排序后交换了位置,所以它是不稳定的算法。


例如:12、5、9、34、6、8、33、56、89、0、7、4、22、55、77
具体步骤:




void Shell(int *arr,int len,int gap)
{
for(int i = gap;i < len;i++)
{
int temp = arr;
int j = 0;
for(j = i-gap;j >= 0;j-=gap)
{
if(arr[j] > temp)
{
arr[j+gap] = arr[j];
}
else
{
break;
}
}
arr[j+gap] = temp;
}
}
void Shell_Sort(int *arr,int len)
{
int drr = {5,3,1}; //drr为分的组数,这里5,3,1不固定,但必须相互为素数,且最后数为1
int lend = sizeof(drr)/sizeof(drr[0]);
for(int i = 0;i < lend;i++)
{
Shell(arr,len,drr);
}
}

引用文章:
https://blog.csdn.net/FDk_LCL/java/article/details/90581904
https://www.cnblogs.com/guopengxia0719/p/10520561.html
https://www.cnblogs.com/BaoZiY/p/10931406.html
  查看全部
一、直接插入排序


直接插入排序(Straight Insertion Sort)是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的、记录数量增1的有序表。直接插入排序的时间复杂度为 O(n2)。


 
实例如下所示:

定义的数组   :      {23,34,56,78,65,90,88,92,18,21}

过程如下所示:

【23】   34   56   78   65   90   88   92   18   21

第 1 次排序结果:   【23   34】   56   78   65   90   88   92   18   21 

——用34插入到【23】序列中,34>23,故插入后的顺序是【23,34】


第 2 次排序结果:   【 23   34     56 】78   65   90   88   92   18   21

——用56插入到【23,34】序列中,56>34,故插入后的顺序是【23,34,56】


第 3 次排序结果:   【23   34      56    78】65   90   88   92   18   21

——用78插入到【23,34,56】序列中,78>56,故插入后的顺序是【23,34,56,78】


第 4 次排序结果:   【23   34     56     65   78 】90   88   92   18   21    

——用65插入到【23,34,56,78】序列中,65<78,所以78后移一位,和56比较,65>56,故插入后的顺序是【23,34,56,65, 78】


第 5 次排序结果:   【23   34   56   65   78   90 】  88   92   18   21

——用90插入到【23,34,56,65, 78】序列中,78<90 ,故插入后的顺序是【23   34   56   65   78   90 】


第 6 次排序结果:   23   34   56   65   78   88   90   92   18   21

——用88插入到【23   34   56   65   78   90 】序列中,90>88 ,所以90后移一位,故插入后的顺序是【23   34   56   65   78   88   90】


第 7 次排序结果:   23   34   56   65   78   88   90   92   18   21

——用92插入到【23   34   56   65   78   90 】序列中,90<92 ,故插入后的顺序是【23   34   56   65   78   90   92 】


第 8 次排序结果:   18   23   34   56   65   78   88   90   92   21

——用18插入到【23   34   56   65   78   90   92 】序列中,18<92,所以92后移一位,和90比较,90>18,依次后移,直到第一位23,因为18<23, 故插入后的顺序是【18   23   34   56   65   78   88   90   92】


第 9 次排序结果:   18   21   23   34   56   65   78   88   90   92

——用21插入到【23   34   56   65   78   90   92 】序列中,21<92,故92后移一位,和90比较,90>21,依次后移,直到第一位18,因为18<21, 故插入后的顺序是【18   21   23   34   56   65   78   88   90   92】 
C语言实现:
#include <stdio.h>
//自定义的输出函数
void print(int a, int n ,int i){
printf("%d:",i);
for(int j=0; j<8; j++){
printf("%d",a[j]);
}
printf("\n");
}
//直接插入排序函数
void InsertSort(int a, int n)
{
for(int i= 1; i<n; i++){
if(a < a[i-1]){//若第 i 个元素大于 i-1 元素则直接插入;反之,需要找到适当的插入位置后在插入。
int j= i-1;
int x = a;
while(j>-1 && x < a[j]){ //采用顺序查找方式找到插入的位置,在查找的同时,将数组中的元素进行后移操作,给插入元素腾出空间
a[j+1] = a[j];
j--;
}
a[j+1] = x; //插入到正确位置
}
print(a,n,i);//打印每次排序后的结果
}
}
int main(){
int a[8] = {3,1,7,5,2,4,9,6};
InsertSort(a,8);
return 0;
}

二、Shell排序:直接插入排序算法的一种高速而稳定的改进版本
 



希尔排序,也称递减增量排序算法,是一种插入排序算法,它出自D.L.Shell,因此而得名。Shell排序又称作缩小增量排序。Shell排序的执行时间依赖于增量序列。



希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量=1(<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
 
Shell排序算法的特点



希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率[list][*]但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位


[/*]
[/list]


时间复杂度:最坏情况下为O(n^2),平均时间复杂度为O(nlogn);
空间复杂度:归并排序需要一个大小为1的临时存储空间用以保存合并序列,所以空间复杂度为O(1)
算法稳定性:从上面图片中可以看出,数字5在排序后交换了位置,所以它是不稳定的算法。



例如:12、5、9、34、6、8、33、56、89、0、7、4、22、55、77
具体步骤:

20181122144210405.png
void Shell(int *arr,int len,int gap)
{
for(int i = gap;i < len;i++)
{
int temp = arr;
int j = 0;
for(j = i-gap;j >= 0;j-=gap)
{
if(arr[j] > temp)
{
arr[j+gap] = arr[j];
}
else
{
break;
}
}
arr[j+gap] = temp;
}
}
void Shell_Sort(int *arr,int len)
{
int drr = {5,3,1}; //drr为分的组数,这里5,3,1不固定,但必须相互为素数,且最后数为1
int lend = sizeof(drr)/sizeof(drr[0]);
for(int i = 0;i < lend;i++)
{
Shell(arr,len,drr);
}
}

引用文章:
https://blog.csdn.net/FDk_LCL/java/article/details/90581904
https://www.cnblogs.com/guopengxia0719/p/10520561.html
https://www.cnblogs.com/BaoZiY/p/10931406.html
 

搜索相似度算法探究之MMR

架构思想zkbhj 发表了文章 • 0 个评论 • 1981 次浏览 • 2020-02-21 18:06 • 来自相关话题

最近公司搜索项目在做返回结果相似度相关的需求,需要了解如何计算不同文档之间的相似度排序,进而将返回的结果进行一次“打散”重排操作,让结果看起来不那么“相似的内容”太过于“扎墩儿”出现。
 
今天同事分享了相似度算法中最简单的算法:MMR。接下来就仔细研究学习下。
 
MMR的全称为Maximal Marginal Relevance ,中文名字为最大边界相关法或者最大边缘相关。算法目的是减少排序结果的冗余,同时保证结果的相关性。最早应用于文本摘要提取和信息检索等领域。在推荐场景下体现在,给用户推荐相关商品的同时,保证推荐结果的多样性,即排序结果存在着相关性与多样性的权衡。

MMR的主要思路是:

• Use the query to retrieve a ranking R of documents
• Use MMR to rerank the top N documents (build a new ranking S)
– Select the 1st document based on how well it satisfies the query
– Select subsequent documents based on two criteria
» How well it satisfies the query
» How different it is from documents ranked above it

 
在MMR的公式是这样的:





 
R: The initial ranking
S: Documents already selected for the diverse ranking
– Documents ranked above this position
Sim(di, dj): Similarity metric
– E.g., vector space model or Jensen-Shannon Divergence
λ : 权重系数,调节推荐结果相关性与多样性。λ越大,推荐结果越相关; λ越小,推荐结果多样性越高。
 举个例子,假设λ=0.6λ=0.6,初始排名及其相关性分数如下:Initial Ranking
d1, 0.80
d2, 0.78
d3, 0.76
d4, 0.74
d5, 0.72
d6, 0.70 
第一步,选择与 query 最相关的文档 d1,并从 R 中移除 d1Diversified Ranking
d1计算剩余文档与 {d1} 的相似度和对应的多样性分数





 
选择分数最高的文档作为多样性排名的第 2 篇文档,并从 R 中移除该文档Diversified Ranking
d1
d5分别计算剩余文档与已排序文档 {d1, d5} 的相似度,选相似度最大的值,计算 MMR 分数





 
选择分数最高的文档作为多样性排名的第 3 篇文档,并从 R 中移除该文档Diversified Ranking
d1
d5
d3分别计算剩余文档与已排序文档 {d1, d5, d3} 的相似度,选相似度最大的值,计算 MMR 分数





 
选择分数最高的文档作为多样性排名的第 4 篇文档,并从 R 中移除该文档Diversified Ranking
d1
d5
d3
d6分别计算剩余文档与已排序文档 d1, d5, d3, d6 的相似度,选相似度最大的值,计算 MMR 分数





 
选择分数最高的文档作为多样性排名的第 5 篇文档,并从 R 中移除该文档Diversified Ranking
d1
d5
d3
d6
d2Repeat until all documents in the initial ranking are added to the diversified ranking

所以就有了最后的排名 {d1, d5, d3, d6, d2}

MMR 也会用于其它的任务如文本摘要,因为它是符合摘要的基本要求的,即相关性和多样性的权衡。摘要结果与原文的相关性越高,摘要就接近全文中心意思,而多样性则使摘要内容更加的全面。直观和简单是这种方法最大的优点。
 
参考文档:
http://www.shuang0420.com/2016/12/07/Search%20Engines%E7%AC%94%E8%AE%B0%20-%20Diversity/
文档相似性分数计算:
https://blog.csdn.net/yixianfe ... 17158 查看全部
最近公司搜索项目在做返回结果相似度相关的需求,需要了解如何计算不同文档之间的相似度排序,进而将返回的结果进行一次“打散”重排操作,让结果看起来不那么“相似的内容”太过于“扎墩儿”出现。
 
今天同事分享了相似度算法中最简单的算法:MMR。接下来就仔细研究学习下。
 
MMR的全称为Maximal Marginal Relevance ,中文名字为最大边界相关法或者最大边缘相关。算法目的是减少排序结果的冗余,同时保证结果的相关性。最早应用于文本摘要提取和信息检索等领域。在推荐场景下体现在,给用户推荐相关商品的同时,保证推荐结果的多样性,即排序结果存在着相关性与多样性的权衡。

MMR的主要思路是:


• Use the query to retrieve a ranking R of documents
• Use MMR to rerank the top N documents (build a new ranking S)
– Select the 1st document based on how well it satisfies the query
– Select subsequent documents based on two criteria
» How well it satisfies the query
» How different it is from documents ranked above it


 
在MMR的公式是这样的:

MMR.png

 
R: The initial ranking
S: Documents already selected for the diverse ranking
– Documents ranked above this position
Sim(di, dj): Similarity metric
– E.g., vector space model or Jensen-Shannon Divergence
λ : 权重系数,调节推荐结果相关性与多样性。λ越大,推荐结果越相关; λ越小,推荐结果多样性越高。
 举个例子,假设λ=0.6λ=0.6,初始排名及其相关性分数如下:
Initial Ranking
d1, 0.80
d2, 0.78
d3, 0.76
d4, 0.74
d5, 0.72
d6, 0.70
 
第一步,选择与 query 最相关的文档 d1,并从 R 中移除 d1
Diversified Ranking
d1
计算剩余文档与 {d1} 的相似度和对应的多样性分数

step1.jpg

 
选择分数最高的文档作为多样性排名的第 2 篇文档,并从 R 中移除该文档
Diversified Ranking
d1
d5
分别计算剩余文档与已排序文档 {d1, d5} 的相似度,选相似度最大的值,计算 MMR 分数

step2.jpg

 
选择分数最高的文档作为多样性排名的第 3 篇文档,并从 R 中移除该文档
Diversified Ranking
d1
d5
d3
分别计算剩余文档与已排序文档 {d1, d5, d3} 的相似度,选相似度最大的值,计算 MMR 分数

step3.jpg

 
选择分数最高的文档作为多样性排名的第 4 篇文档,并从 R 中移除该文档
Diversified Ranking
d1
d5
d3
d6
分别计算剩余文档与已排序文档 d1, d5, d3, d6 的相似度,选相似度最大的值,计算 MMR 分数

step4.jpg

 
选择分数最高的文档作为多样性排名的第 5 篇文档,并从 R 中移除该文档
Diversified Ranking
d1
d5
d3
d6
d2
Repeat until all documents in the initial ranking are added to the diversified ranking

所以就有了最后的排名 {d1, d5, d3, d6, d2}

MMR 也会用于其它的任务如文本摘要,因为它是符合摘要的基本要求的,即相关性和多样性的权衡。摘要结果与原文的相关性越高,摘要就接近全文中心意思,而多样性则使摘要内容更加的全面。直观和简单是这种方法最大的优点。
 
参考文档:
http://www.shuang0420.com/2016/12/07/Search%20Engines%E7%AC%94%E8%AE%B0%20-%20Diversity/
文档相似性分数计算:
https://blog.csdn.net/yixianfe ... 17158

海量数据相似度计算算法:simhash和海明距离

架构思想zkbhj 发表了文章 • 0 个评论 • 1054 次浏览 • 2018-09-12 16:04 • 来自相关话题

通过 采集系统 我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析。分析前我们需要对这些数据去除重复,如何选择和设计文本的去重算法?常见的有余弦夹角算法、欧式距离、Jaccard相似度、最长公共子串、编辑距离等。这些算法对于待比较的文本数据不多时还比较好用,如果我们的爬虫每天采集的数据以千万计算,我们如何对于这些海量千万级的数据进行高效的合并去重。最简单的做法是拿着待比较的文本和数据库中所有的文本比较一遍如果是重复的数据就标示为重复。看起来很简单,我们来做个测试,就拿最简单的两个数据使用Apache提供的 Levenshtein for 循环100w次计算这两个数据的相似度。代码结果如下:
String s1 = "你妈妈喊你回家吃饭哦,回家罗回家罗" ;
String s2 = "你妈妈叫你回家吃饭啦,回家罗回家罗" ;

long t1 = System.currentTimeMillis();

for (int i = 0; i < 1000000; i++) {
int dis = StringUtils .getLevenshteinDistance(s1, s2);
}

long t2 = System.currentTimeMillis();

System. out .println(" 耗费时间: " + (t2 - t1) + " ms ");耗费时间: 4266 ms

大跌眼镜,居然计算耗费4秒。假设我们一天需要比较100w次,光是比较100w次的数据是否重复就需要4s,就算4s一个文档,单线程一分钟才处理15个文档,一个小时才900个,一天也才21600个文档,这个数字和一天100w相差甚远,需要多少机器和资源才能解决。

为此我们需要一种应对于海量数据场景的去重方案,经过研究发现有种叫 local sensitive hash 局部敏感哈希 的东西,据说这玩意可以把文档降维到hash数字,数字两两计算运算量要小很多。查找很多文档后看到google对于网页去重使用的是simhash,他们每天需要处理的文档在亿级别,大大超过了我们现在文档的水平。既然老大哥也有类似的应用,我们也赶紧尝试下。simhash是由 Charikar 在2002年提出来的,参考 《Similarity estimation techniques from rounding algorithms》 。 介绍下这个算法主要原理,为了便于理解尽量不使用数学公式,分为这几步:
 

1、分词,把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重,我们假设权重分为5个级别(1~5)。比如:“ 美国“51区”雇员称内部有9架飞碟,曾看见灰色外星人 ” ==> 分词后为 “ 美国(4) 51区(5) 雇员(3) 称(1) 内部(2) 有(1) 9架(3) 飞碟(5) 曾(1) 看见(3) 灰色(4) 外星人(5)”,括号里是代表单词在整个句子里重要程度,数字越大越重要。

2、hash,通过hash算法把每个词变成hash值,比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字,还记得文章开头说过的吗,要把文章变为数字计算才能提高相似度计算性能,现在是降维过程进行时。

3、加权,通过 2步骤的hash生成结果,需要按照单词的权重形成加权数字串,比如“美国”的hash值为“100101”,通过加权计算为“4 -4 -4 4 -4 4”;“51区”的hash值为“101011”,通过加权计算为 “ 5 -5 5 -5 5 5”。

4、合并,把上面各个单词算出来的序列值累加,变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”,“51区”的 “ 5 -5 5 -5 5 5”, 把每一位进行累加, “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的,真实计算需要把所有单词的序列串累加。

5、降维,把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串,形成我们最终的simhash签名。 如果每一位大于0 记为 1,小于0 记为 0。最后算出结果为:“1 0 1 0 1 1”。

 
整个过程图为:





 
大家可能会有疑问,经过这么多步骤搞这么麻烦,不就是为了得到个 0 1 字符串吗?我直接把这个文本作为字符串输入,用hash函数生成 0 1 值更简单。其实不是这样的,传统hash函数解决的是生成唯一值,比如 md5、hashmap等。md5是用于生成唯一签名串,只要稍微多加一个字符md5的两个数字看起来相差甚远;hashmap也是用于键值对查找,便于快速插入和查找的数据结构。不过我们主要解决的是文本相似度计算,要比较的是两个文章是否相识,当然我们降维生成了hashcode也是用于这个目的。看到这里估计大家就明白了,我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的,而传统的hashcode却不行。我们可以来做个测试,两个相差只有一个字符的文本串,“你妈妈喊你回家吃饭哦,回家罗回家罗” 和 “你妈妈叫你回家吃饭啦,回家罗回家罗”。

通过simhash计算结果为:

1000010010101101111111100000101011010001001111100001001011001011

1000010010101101011111100000101011010001001111100001101010001011

通过 hashcode计算为:

1111111111111111111111111111111110001000001100110100111011011110

1010010001111111110010110011101

大家可以看得出来,相似的文本只有部分 01 串变化了,而普通的hashcode却不能做到,这个就是局部敏感哈希的魅力。目前Broder提出的shingling算法和Charikar的simhash算法应该算是业界公认比较好的算法。在simhash的发明人Charikar的论文中并没有给出具体的simhash算法和证明,“量子图灵”得出的证明simhash是由随机超平面hash算法演变而来的。

现在通过这样的转换,我们把库里的文本都转换为simhash 代码,并转换为long类型存储,空间大大减少。现在我们虽然解决了空间,但是如何计算两个simhash的相似度呢?难道是比较两个simhash的01有多少个不同吗?对的,其实也就是这样,我们通过海明距离(Hamming distance)就可以计算出两个simhash到底相似不相似。两个simhash对应二进制(01串)取值不同的数量称为这两个simhash的海明距离。举例如下: 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同,则海明距离为3。对于二进制字符串的a和b,海明距离为等于在a XOR b运算结果中1的个数(普遍算法)。

为了高效比较,我们预先加载了库里存在文本并转换为simhash code 存储在内存空间。来一条文本先转换为 simhash code,然后和内存里的simhash code 进行比较,测试100w次计算在100ms。速度大大提升。

未完待续:

1、目前速度提升了但是数据是不断增量的,如果未来数据发展到一个小时100w,按现在一次100ms,一个线程处理一秒钟 10次,一分钟 60 * 10 次,一个小时 60*10 *60 次 = 36000次,一天 60*10*60*24 = 864000次。 我们目标是一天100w次,通过增加两个线程就可以完成。但是如果要一个小时100w次呢?则需要增加30个线程和相应的硬件资源保证速度能够达到,这样成本也上去了。能否有更好的办法,提高我们比较的效率?

2、通过大量测试,simhash用于比较大文本,比如500字以上效果都还蛮好,距离小于3的基本都是相似,误判率也比较低。但是如果我们处理的是微博信息,最多也就140个字,使用simhash的效果并不那么理想。看如下图,在距离为3时是一个比较折中的点,在距离为10时效果已经很差了,不过我们测试短文本很多看起来相似的距离确实为10。如果使用距离为3,短文本大量重复信息不会被过滤,如果使用距离为10,长文本的错误率也非常高,如何解决?




  查看全部
通过 采集系统 我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析。分析前我们需要对这些数据去除重复,如何选择和设计文本的去重算法?常见的有余弦夹角算法、欧式距离、Jaccard相似度、最长公共子串、编辑距离等。这些算法对于待比较的文本数据不多时还比较好用,如果我们的爬虫每天采集的数据以千万计算,我们如何对于这些海量千万级的数据进行高效的合并去重。最简单的做法是拿着待比较的文本和数据库中所有的文本比较一遍如果是重复的数据就标示为重复。看起来很简单,我们来做个测试,就拿最简单的两个数据使用Apache提供的 Levenshtein for 循环100w次计算这两个数据的相似度。代码结果如下:
String s1 = "你妈妈喊你回家吃饭哦,回家罗回家罗" ;
String s2 = "你妈妈叫你回家吃饭啦,回家罗回家罗" ;

long t1 = System.currentTimeMillis();

for (int i = 0; i < 1000000; i++) {
int dis = StringUtils .getLevenshteinDistance(s1, s2);
}

long t2 = System.currentTimeMillis();

System. out .println(" 耗费时间: " + (t2 - t1) + " ms ");
耗费时间: 4266 ms

大跌眼镜,居然计算耗费4秒。假设我们一天需要比较100w次,光是比较100w次的数据是否重复就需要4s,就算4s一个文档,单线程一分钟才处理15个文档,一个小时才900个,一天也才21600个文档,这个数字和一天100w相差甚远,需要多少机器和资源才能解决。

为此我们需要一种应对于海量数据场景的去重方案,经过研究发现有种叫 local sensitive hash 局部敏感哈希 的东西,据说这玩意可以把文档降维到hash数字,数字两两计算运算量要小很多。查找很多文档后看到google对于网页去重使用的是simhash,他们每天需要处理的文档在亿级别,大大超过了我们现在文档的水平。既然老大哥也有类似的应用,我们也赶紧尝试下。simhash是由 Charikar 在2002年提出来的,参考 《Similarity estimation techniques from rounding algorithms》 。 介绍下这个算法主要原理,为了便于理解尽量不使用数学公式,分为这几步:
 


1、分词,把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重,我们假设权重分为5个级别(1~5)。比如:“ 美国“51区”雇员称内部有9架飞碟,曾看见灰色外星人 ” ==> 分词后为 “ 美国(4) 51区(5) 雇员(3) 称(1) 内部(2) 有(1) 9架(3) 飞碟(5) 曾(1) 看见(3) 灰色(4) 外星人(5)”,括号里是代表单词在整个句子里重要程度,数字越大越重要。

2、hash,通过hash算法把每个词变成hash值,比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字,还记得文章开头说过的吗,要把文章变为数字计算才能提高相似度计算性能,现在是降维过程进行时。

3、加权,通过 2步骤的hash生成结果,需要按照单词的权重形成加权数字串,比如“美国”的hash值为“100101”,通过加权计算为“4 -4 -4 4 -4 4”;“51区”的hash值为“101011”,通过加权计算为 “ 5 -5 5 -5 5 5”。

4、合并,把上面各个单词算出来的序列值累加,变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”,“51区”的 “ 5 -5 5 -5 5 5”, 把每一位进行累加, “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的,真实计算需要把所有单词的序列串累加。

5、降维,把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串,形成我们最终的simhash签名。 如果每一位大于0 记为 1,小于0 记为 0。最后算出结果为:“1 0 1 0 1 1”。


 
整个过程图为:

simhash.png

 
大家可能会有疑问,经过这么多步骤搞这么麻烦,不就是为了得到个 0 1 字符串吗?我直接把这个文本作为字符串输入,用hash函数生成 0 1 值更简单。其实不是这样的,传统hash函数解决的是生成唯一值,比如 md5、hashmap等。md5是用于生成唯一签名串,只要稍微多加一个字符md5的两个数字看起来相差甚远;hashmap也是用于键值对查找,便于快速插入和查找的数据结构。不过我们主要解决的是文本相似度计算,要比较的是两个文章是否相识,当然我们降维生成了hashcode也是用于这个目的。看到这里估计大家就明白了,我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的,而传统的hashcode却不行。我们可以来做个测试,两个相差只有一个字符的文本串,“你妈妈喊你回家吃饭哦,回家罗回家罗” 和 “你妈妈叫你回家吃饭啦,回家罗回家罗”。

通过simhash计算结果为:

1000010010101101111111100000101011010001001111100001001011001011

1000010010101101011111100000101011010001001111100001101010001011

通过 hashcode计算为:

1111111111111111111111111111111110001000001100110100111011011110

1010010001111111110010110011101

大家可以看得出来,相似的文本只有部分 01 串变化了,而普通的hashcode却不能做到,这个就是局部敏感哈希的魅力。目前Broder提出的shingling算法和Charikar的simhash算法应该算是业界公认比较好的算法。在simhash的发明人Charikar的论文中并没有给出具体的simhash算法和证明,“量子图灵”得出的证明simhash是由随机超平面hash算法演变而来的。

现在通过这样的转换,我们把库里的文本都转换为simhash 代码,并转换为long类型存储,空间大大减少。现在我们虽然解决了空间,但是如何计算两个simhash的相似度呢?难道是比较两个simhash的01有多少个不同吗?对的,其实也就是这样,我们通过海明距离(Hamming distance)就可以计算出两个simhash到底相似不相似。两个simhash对应二进制(01串)取值不同的数量称为这两个simhash的海明距离。举例如下: 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同,则海明距离为3。对于二进制字符串的a和b,海明距离为等于在a XOR b运算结果中1的个数(普遍算法)。

为了高效比较,我们预先加载了库里存在文本并转换为simhash code 存储在内存空间。来一条文本先转换为 simhash code,然后和内存里的simhash code 进行比较,测试100w次计算在100ms。速度大大提升。

未完待续:

1、目前速度提升了但是数据是不断增量的,如果未来数据发展到一个小时100w,按现在一次100ms,一个线程处理一秒钟 10次,一分钟 60 * 10 次,一个小时 60*10 *60 次 = 36000次,一天 60*10*60*24 = 864000次。 我们目标是一天100w次,通过增加两个线程就可以完成。但是如果要一个小时100w次呢?则需要增加30个线程和相应的硬件资源保证速度能够达到,这样成本也上去了。能否有更好的办法,提高我们比较的效率?

2、通过大量测试,simhash用于比较大文本,比如500字以上效果都还蛮好,距离小于3的基本都是相似,误判率也比较低。但是如果我们处理的是微博信息,最多也就140个字,使用simhash的效果并不那么理想。看如下图,在距离为3时是一个比较折中的点,在距离为10时效果已经很差了,不过我们测试短文本很多看起来相似的距离确实为10。如果使用距离为3,短文本大量重复信息不会被过滤,如果使用距离为10,长文本的错误率也非常高,如何解决?
simhash2.png

 

相似文档查找算法之 simHash

专业名词zkbhj 发表了文章 • 0 个评论 • 1091 次浏览 • 2018-09-05 14:50 • 来自相关话题

简单易懂的理解什么是神经网络

专业名词zkbhj 发表了文章 • 0 个评论 • 976 次浏览 • 2018-06-24 11:57 • 来自相关话题

分类
神经网络最重要的用途是分类,为了让大家对分类有个直观的认识,咱们先看几个例子:
 
 
垃圾邮件识别:现在有一封电子邮件,把出现在里面的所有词汇提取出来,送进一个机器里,机器需要判断这封邮件是否是垃圾邮件。疾病判断:病人到医院去做了一大堆肝功、尿检测验,把测验结果送进一个机器里,机器需要判断这个病人是否得病,得的什么病。猫狗分类:有一大堆猫、狗照片,把每一张照片送进一个机器里,机器需要判断这幅照片里的东西是猫还是狗。

这种能自动对输入的东西进行分类的机器,就叫做分类器。
 
分类器的输入是一个数值向量,叫做特征(向量)。在第一个例子里,分类器的输入是一堆0、1值,表示字典里的每一个词是否在邮件中出现,比如向量(1,1,0,0,0......)就表示这封邮件里只出现了两个词abandon和abnormal;第二个例子里,分类器的输入是一堆化验指标;第三个例子里,分类器的输入是照片,假如每一张照片都是320*240像素的红绿蓝三通道彩色照片,那么分类器的输入就是一个长度为320*240*3=230400的向量。

分类器的输出也是数值。第一个例子中,输出1表示邮件是垃圾邮件,输出0则说明邮件是正常邮件;第二个例子中,输出0表示健康,输出1表示有甲肝,输出2表示有乙肝,输出3表示有饼干等等;第三个例子中,输出0表示图片中是狗,输出1表示是猫。

分类器的目标就是让正确分类的比例尽可能高。一般我们需要首先收集一些样本,人为标记上正确分类结果,然后用这些标记好的数据训练分类器,训练好的分类器就可以在新来的特征向量上工作了。

神经元

咱们假设分类器的输入是通过某种途径获得的两个值,输出是0和1,比如分别代表猫和狗。现在有一些样本:





 
大家想想,最简单地把这两组特征向量分开的方法是啥?当然是在两组数据中间画一条竖直线,直线左边是狗,右边是猫,分类器就完成了。以后来了新的向量,凡是落在直线左边的都是狗,落在右边的都是猫。

一条直线把平面一分为二,一个平面把三维空间一分为二,一个n-1维超平面把n维空间一分为二,两边分属不同的两类,这种分类器就叫做神经元。
 
大家都知道平面上的直线方程是 ax+by+c=0 。,等式左边大于零和小于零分别表示点  (x,y)在直线的一侧还是另一侧,把这个式子推广到n维空间里,直线的高维形式称为超平面,它的方程是:




神经元就是当h大于0时输出1,h小于0时输出0这么一个模型,它的实质就是把特征空间一切两半,认为两瓣分别属两个类。你恐怕再也想不到比这更简单的分类器了,它是McCulloch和Pitts在1943年想出来了。
这个模型有点像人脑中的神经元:从多个感受器接受电信号




,进行处理(加权相加再偏移一点,即判断输入是否在某条直线  h=0 的一侧),发出电信号(在正确的那侧发出1,否则不发信号,可以认为是发出0),这就是它叫神经元的原因。

当然,上面那幅图我们是开了上帝视角才知道“一条竖直线能分开两类”,在实际训练神经元时,我们并不知道特征是怎么抱团的。神经元模型的一种学习方法称为Hebb算法:
先随机选一条直线/平面/超平面,然后把样本一个个拿过来,如果这条直线分错了,说明这个点分错边了,就稍微把直线移动一点,让它靠近这个样本,争取跨过这个样本,让它跑到直线正确的一侧;如果直线分对了,它就暂时停下不动。因此训练神经元的过程就是这条直线不断在跳舞,最终跳到两个类之间的竖直线位置。 
神经网络
MP神经元有几个显著缺点。首先它把直线一侧变为0,另一侧变为1,这东西不可微,不利于数学分析。人们用一个和0-1阶跃函数类似但是更平滑的函数Sigmoid函数来代替它(Sigmoid函数自带一个尺度参数,可以控制神经元对离超平面距离不同的点的响应,这里忽略它),从此神经网络的训练就可以用梯度下降法来构造了,这就是有名的反向传播算法。

神经元的另一个缺点是:它只能切一刀!你给我说说一刀怎么能把下面这两类分开吧。





 
解决办法是多层神经网络,底层神经元的输出是高层神经元的输入。我们可以在中间横着砍一刀,竖着砍一刀,然后把左上和右下的部分合在一起,与右上的左下部分分开;也可以围着左上角的边沿砍10刀把这一部分先挖出来,然后和右下角合并。

每砍一刀,其实就是使用了一个神经元,把不同砍下的半平面做交、并等运算,就是把这些神经元的输出当作输入,后面再连接一个神经元。这个例子中特征的形状称为异或,这种情况一个神经元搞不定,但是两层神经元就能正确对其进行分类。

只要你能砍足够多刀,把结果拼在一起,什么奇怪形状的边界神经网络都能够表示,所以说神经网络在理论上可以表示很复杂的函数/空间分布。但是真实的神经网络是否能摆动到正确的位置还要看网络初始值设置、样本容量和分布。

神经网络神奇的地方在于它的每一个组件非常简单——把空间切一刀+某种激活函数(0-1阶跃、sigmoid、max-pooling),但是可以一层一层级联。输入向量连到许多神经元上,这些神经元的输出又连到一堆神经元上,这一过程可以重复很多次。这和人脑中的神经元很相似:每一个神经元都有一些神经元作为其输入,又是另一些神经元的输入,数值向量就像是电信号,在不同神经元之间传导,每一个神经元只有满足了某种条件才会发射信号到下一层神经元。当然,人脑比神经网络模型复杂很多:人工神经网络一般不存在环状结构;人脑神经元的电信号不仅有强弱,还有时间缓急之分,就像莫尔斯电码,在人工神经网络里没有这种复杂的信号模式。
 
神经网络的训练依靠反向传播算法:最开始输入层输入特征向量,网络层层计算获得输出,输出层发现输出和正确的类号不一样,这时它就让最后一层神经元进行参数调整,最后一层神经元不仅自己调整参数,还会勒令连接它的倒数第二层神经元调整,层层往回退着调整。经过调整的网络会在样本上继续测试,如果输出还是老分错,继续来一轮回退调整,直到网络输出满意为止。这很像中国的文艺体制,武媚娘传奇剧组就是网络中的一个神经元,最近刚刚调整了参数。

大型神经网络

我们不禁要想了,假如我们的这个网络有10层神经元,第8层第2015个神经元,它有什么含义呢?我们知道它把第七层的一大堆神经元的输出作为输入,第七层的神经元又是以第六层的一大堆神经元做为输入,那么这个特殊第八层的神经元,它会不会代表了某种抽象的概念?

就好比你的大脑里有一大堆负责处理声音、视觉、触觉信号的神经元,它们对于不同的信息会发出不同的信号,那么会不会有这么一个神经元(或者神经元小集团),它收集这些信号,分析其是否符合某个抽象的概念,和其他负责更具体和更抽象概念的神经元进行交互。

2012年多伦多大学的Krizhevsky等人构造了一个超大型卷积神经网络[1],有9层,共65万个神经元,6千万个参数。网络的输入是图片,输出是1000个类,比如小虫、美洲豹、救生船等等。这个模型的训练需要海量图片,它的分类准确率也完爆先前所有分类器。纽约大学的Zeiler和Fergusi[2]把这个网络中某些神经元挑出来,把在其上响应特别大的那些输入图像放在一起,看它们有什么共同点。他们发现中间层的神经元响应了某些十分抽象的特征。 
第一层神经元主要负责识别颜色和简单纹理第二层的一些神经元可以识别更加细化的纹理,比如布纹、刻度、叶纹。第三层的一些神经元负责感受黑夜里的黄色烛光、鸡蛋黄、高光。第四层的一些神经元负责识别萌狗的脸、七星瓢虫和一堆圆形物体的存在。第五层的一些神经元可以识别出花、圆形屋顶、键盘、鸟、黑眼圈动物。

这里面的概念并不是整个网络的输出,是网络中间层神经元的偏好,它们为后面的神经元服务。虽然每一个神经元都傻不拉几的(只会切一刀),但是65万个神经元能学到的东西还真是深邃呢。 查看全部
分类
神经网络最重要的用途是分类,为了让大家对分类有个直观的认识,咱们先看几个例子:
 
 
  1. 垃圾邮件识别:现在有一封电子邮件,把出现在里面的所有词汇提取出来,送进一个机器里,机器需要判断这封邮件是否是垃圾邮件。
  2. 疾病判断:病人到医院去做了一大堆肝功、尿检测验,把测验结果送进一个机器里,机器需要判断这个病人是否得病,得的什么病。
  3. 猫狗分类:有一大堆猫、狗照片,把每一张照片送进一个机器里,机器需要判断这幅照片里的东西是猫还是狗。


这种能自动对输入的东西进行分类的机器,就叫做分类器
 
分类器的输入是一个数值向量,叫做特征(向量)。在第一个例子里,分类器的输入是一堆0、1值,表示字典里的每一个词是否在邮件中出现,比如向量(1,1,0,0,0......)就表示这封邮件里只出现了两个词abandon和abnormal;第二个例子里,分类器的输入是一堆化验指标;第三个例子里,分类器的输入是照片,假如每一张照片都是320*240像素的红绿蓝三通道彩色照片,那么分类器的输入就是一个长度为320*240*3=230400的向量。

分类器的输出也是数值。第一个例子中,输出1表示邮件是垃圾邮件,输出0则说明邮件是正常邮件;第二个例子中,输出0表示健康,输出1表示有甲肝,输出2表示有乙肝,输出3表示有饼干等等;第三个例子中,输出0表示图片中是狗,输出1表示是猫。

分类器的目标就是让正确分类的比例尽可能高。一般我们需要首先收集一些样本,人为标记上正确分类结果,然后用这些标记好的数据训练分类器,训练好的分类器就可以在新来的特征向量上工作了。

神经元

咱们假设分类器的输入是通过某种途径获得的两个值,输出是0和1,比如分别代表猫和狗。现在有一些样本:

WX20180624-114555@2x.png

 
大家想想,最简单地把这两组特征向量分开的方法是啥?当然是在两组数据中间画一条竖直线,直线左边是狗,右边是猫,分类器就完成了。以后来了新的向量,凡是落在直线左边的都是狗,落在右边的都是猫。

一条直线把平面一分为二,一个平面把三维空间一分为二,一个n-1维超平面把n维空间一分为二,两边分属不同的两类,这种分类器就叫做神经元。
 
大家都知道平面上的直线方程是 ax+by+c=0 。,等式左边大于零和小于零分别表示点  (x,y)在直线的一侧还是另一侧,把这个式子推广到n维空间里,直线的高维形式称为超平面,它的方程是:
WX20180624-114754@2x.png

神经元就是当h大于0时输出1,h小于0时输出0这么一个模型,它的实质就是把特征空间一切两半,认为两瓣分别属两个类。你恐怕再也想不到比这更简单的分类器了,它是McCulloch和Pitts在1943年想出来了。
这个模型有点像人脑中的神经元:从多个感受器接受电信号
WX20180624-114835@2x.png

,进行处理(加权相加再偏移一点,即判断输入是否在某条直线  h=0 的一侧),发出电信号(在正确的那侧发出1,否则不发信号,可以认为是发出0),这就是它叫神经元的原因。

当然,上面那幅图我们是开了上帝视角才知道“一条竖直线能分开两类”,在实际训练神经元时,我们并不知道特征是怎么抱团的。神经元模型的一种学习方法称为Hebb算法:
先随机选一条直线/平面/超平面,然后把样本一个个拿过来,如果这条直线分错了,说明这个点分错边了,就稍微把直线移动一点,让它靠近这个样本,争取跨过这个样本,让它跑到直线正确的一侧;如果直线分对了,它就暂时停下不动。因此训练神经元的过程就是这条直线不断在跳舞,最终跳到两个类之间的竖直线位置。 
神经网络
MP神经元有几个显著缺点。首先它把直线一侧变为0,另一侧变为1,这东西不可微,不利于数学分析。人们用一个和0-1阶跃函数类似但是更平滑的函数Sigmoid函数来代替它(Sigmoid函数自带一个尺度参数,可以控制神经元对离超平面距离不同的点的响应,这里忽略它),从此神经网络的训练就可以用梯度下降法来构造了,这就是有名的反向传播算法。

神经元的另一个缺点是:它只能切一刀!你给我说说一刀怎么能把下面这两类分开吧。

WX20180624-115229@2x.png

 
解决办法是多层神经网络,底层神经元的输出是高层神经元的输入。我们可以在中间横着砍一刀,竖着砍一刀,然后把左上和右下的部分合在一起,与右上的左下部分分开;也可以围着左上角的边沿砍10刀把这一部分先挖出来,然后和右下角合并。

每砍一刀,其实就是使用了一个神经元,把不同砍下的半平面做交、并等运算,就是把这些神经元的输出当作输入,后面再连接一个神经元。这个例子中特征的形状称为异或,这种情况一个神经元搞不定,但是两层神经元就能正确对其进行分类。

只要你能砍足够多刀,把结果拼在一起,什么奇怪形状的边界神经网络都能够表示,所以说神经网络在理论上可以表示很复杂的函数/空间分布。但是真实的神经网络是否能摆动到正确的位置还要看网络初始值设置、样本容量和分布。

神经网络神奇的地方在于它的每一个组件非常简单——把空间切一刀+某种激活函数(0-1阶跃、sigmoid、max-pooling),但是可以一层一层级联。输入向量连到许多神经元上,这些神经元的输出又连到一堆神经元上,这一过程可以重复很多次。这和人脑中的神经元很相似:每一个神经元都有一些神经元作为其输入,又是另一些神经元的输入,数值向量就像是电信号,在不同神经元之间传导,每一个神经元只有满足了某种条件才会发射信号到下一层神经元。当然,人脑比神经网络模型复杂很多:人工神经网络一般不存在环状结构;人脑神经元的电信号不仅有强弱,还有时间缓急之分,就像莫尔斯电码,在人工神经网络里没有这种复杂的信号模式。
 
神经网络的训练依靠反向传播算法:最开始输入层输入特征向量,网络层层计算获得输出,输出层发现输出和正确的类号不一样,这时它就让最后一层神经元进行参数调整,最后一层神经元不仅自己调整参数,还会勒令连接它的倒数第二层神经元调整,层层往回退着调整。经过调整的网络会在样本上继续测试,如果输出还是老分错,继续来一轮回退调整,直到网络输出满意为止。这很像中国的文艺体制,武媚娘传奇剧组就是网络中的一个神经元,最近刚刚调整了参数。

大型神经网络

我们不禁要想了,假如我们的这个网络有10层神经元,第8层第2015个神经元,它有什么含义呢?我们知道它把第七层的一大堆神经元的输出作为输入,第七层的神经元又是以第六层的一大堆神经元做为输入,那么这个特殊第八层的神经元,它会不会代表了某种抽象的概念?

就好比你的大脑里有一大堆负责处理声音、视觉、触觉信号的神经元,它们对于不同的信息会发出不同的信号,那么会不会有这么一个神经元(或者神经元小集团),它收集这些信号,分析其是否符合某个抽象的概念,和其他负责更具体和更抽象概念的神经元进行交互。

2012年多伦多大学的Krizhevsky等人构造了一个超大型卷积神经网络[1],有9层,共65万个神经元,6千万个参数。网络的输入是图片,输出是1000个类,比如小虫、美洲豹、救生船等等。这个模型的训练需要海量图片,它的分类准确率也完爆先前所有分类器。纽约大学的Zeiler和Fergusi[2]把这个网络中某些神经元挑出来,把在其上响应特别大的那些输入图像放在一起,看它们有什么共同点。他们发现中间层的神经元响应了某些十分抽象的特征。 
  • 第一层神经元主要负责识别颜色和简单纹理
  • 第二层的一些神经元可以识别更加细化的纹理,比如布纹、刻度、叶纹。
  • 第三层的一些神经元负责感受黑夜里的黄色烛光、鸡蛋黄、高光。
  • 第四层的一些神经元负责识别萌狗的脸、七星瓢虫和一堆圆形物体的存在。
  • 第五层的一些神经元可以识别出花、圆形屋顶、键盘、鸟、黑眼圈动物。


这里面的概念并不是整个网络的输出,是网络中间层神经元的偏好,它们为后面的神经元服务。虽然每一个神经元都傻不拉几的(只会切一刀),但是65万个神经元能学到的东西还真是深邃呢。

Dijkstra算法(即单源最短路径)解析

架构思想zkbhj 发表了文章 • 0 个评论 • 967 次浏览 • 2017-12-04 15:58 • 来自相关话题

 单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前,必须弄清楚最短路径的最优子结构性质。

一.最短路径的最优子结构性质

   该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。

   假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离,那么必定存在另一条从k到s的最短路径P'(k,s),那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)<P(i,j)。则与P(i,j)是从i到j的最短路径相矛盾。因此该性质得证。

二.Dijkstra算法

   由上述性质可知,如果存在一条从i到j的最短路径(Vi.....Vk,Vj),Vk是Vj前面的一顶点。那么(Vi...Vk)也必定是从i到k的最短路径。为了求出最短路径,Dijkstra就提出了以最短路径长度递增,逐次生成最短路径的算法。譬如对于源顶点V0,首先选择其直接相邻的顶点中长度最短的顶点Vi,那么当前已知可得从V0到达Vj顶点的最短距离dist[j]=min{dist[j],dist+matrix[i][j]}。根据这种思路,

假设存在G=<V,E>,源顶点为V0,U={V0},dist[i]记录V0到i的最短距离,path[i]记录从V0到i路径上的i前面的一个顶点。

1.从V-U中选择使dist[i]值最小的顶点i,将i加入到U中;

2.更新与i直接相邻顶点的dist值。(dist[j]=min{dist[j],dist[i]+matrix[i][j]})

3.知道U=V,停止。[/i][/i][/i][/i][/i][/i]

伪代码实现如下:function Dijkstra(Graph, source):

dist[source] ← 0 // Distance from source to source
prev[source] ← undefined // Previous node in optimal path initialization

for each vertex v in Graph: // Initialization
if v ≠ source // Where v has not yet been removed from Q (unvisited nodes)
dist[v] ← infinity // Unknown distance function from source to v
prev[v] ← undefined // Previous node in optimal path from source
end if
add v to Q // All nodes initially in Q (unvisited nodes)
end for

while Q is not empty:
u ← vertex in Q with min dist[u] // Source node in first case
remove u from Q

for each neighbor v of u: // where v has not yet been removed from Q.
alt ← dist[u] + length(u, v)
if alt < dist[v]: // A shorter path to v has been found
dist[v] ← alt
prev[v] ← u
end if
end for
end while

return dist, prev

end function[/u][/u][u]例如,下面是一个包含 9 个顶点的图,每条边分别标识了距离。
 
源顶点 source = 0,初始时,[/u][u][u]sptSet = {false, false, false, false, false, false, false, false, false};
distSet = {0, INF, INF, INF, INF, INF, INF, INF, INF};[/u][/u]
[u]将 0 包含至 sptSet 中;[/u][u][u]sptSet = {true, false, false, false, false, false, false, false, false};[/u][/u]
[u]更新 0 至其邻接节点的距离;[/u][u][u]distSet = {0, 4, INF, INF, INF, INF, INF, 8, INF};[/u][/u]
[u]



 
选择不在 sptSet 中的 Min Distance 的顶点,为顶点 1,则将 1 包含至 sptSet;[/u][u][u]sptSet = {true, true, false, false, false, false, false, false, false};[/u][/u]
[u]更新 1 至其邻接节点的距离;[/u][u][u]distSet = {0, 4, 12, INF, INF, INF, INF, 8, INF};[/u][/u]
[u]



 
选择不在 sptSet 中的 Min Distance 的顶点,为顶点 7,则将 7 包含至 sptSet;[/u][u][u]sptSet = {true, true, false, false, false, false, false, true, false};[/u][/u]
[u]更新 7 至其邻接节点的距离;[/u][u][u]distSet = {0, 4, 12, INF, INF, INF, 9, 8, 15};[/u][/u]
[u]



 
选择不在 sptSet 中的 Min Distance 的顶点,为顶点 6,则将 6 包含至 sptSet;[/u][u][u]sptSet = {true, true, false, false, false, false, true, true, false};[/u][/u]
[u]更新 6 至其邻接节点的距离;[/u][u][u]distSet = {0, 4, 12, INF, INF, 11, 9, 8, 15};[/u][/u]
[u]



 
以此类推,直到遍历结束。[/u][u][u]sptSet = {true, true, true, true, true, true, true, true, true};
distSet = {0, 4, 12, 19, 21, 11, 9, 8, 14};[/u][/u]
[u]



 
最终结果为源顶点 0 至所有顶点的距离:[/u][u][u]Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14[/u][/u][u]参考文档:https://www.cnblogs.com/gaochu ... .html[/u] 查看全部
 单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前,必须弄清楚最短路径的最优子结构性质。

一.最短路径的最优子结构性质

   该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。

   假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离,那么必定存在另一条从k到s的最短路径P'(k,s),那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)<P(i,j)。则与P(i,j)是从i到j的最短路径相矛盾。因此该性质得证。

二.Dijkstra算法

   由上述性质可知,如果存在一条从i到j的最短路径(Vi.....Vk,Vj),Vk是Vj前面的一顶点。那么(Vi...Vk)也必定是从i到k的最短路径。为了求出最短路径,Dijkstra就提出了以最短路径长度递增,逐次生成最短路径的算法。譬如对于源顶点V0,首先选择其直接相邻的顶点中长度最短的顶点Vi,那么当前已知可得从V0到达Vj顶点的最短距离dist[j]=min{dist[j],dist+matrix[i][j]}。根据这种思路,

假设存在G=<V,E>,源顶点为V0,U={V0},dist[i]记录V0到i的最短距离,path[i]记录从V0到i路径上的i前面的一个顶点。

1.从V-U中选择使dist[i]值最小的顶点i,将i加入到U中;

2.更新与i直接相邻顶点的dist值。(dist[j]=min{dist[j],dist[i]+matrix[i][j]})

3.知道U=V,停止。
[/i][/i][/i][/i][/i][/i]

伪代码实现如下:
function Dijkstra(Graph, source):

dist[source] ← 0 // Distance from source to source
prev[source] ← undefined // Previous node in optimal path initialization

for each vertex v in Graph: // Initialization
if v ≠ source // Where v has not yet been removed from Q (unvisited nodes)
dist[v] ← infinity // Unknown distance function from source to v
prev[v] ← undefined // Previous node in optimal path from source
end if
add v to Q // All nodes initially in Q (unvisited nodes)
end for

while Q is not empty:
u ← vertex in Q with min dist[u] // Source node in first case
remove u from Q

for each neighbor v of u: // where v has not yet been removed from Q.
alt ← dist[u] + length(u, v)
if alt < dist[v]: // A shorter path to v has been found
dist[v] ← alt
prev[v] ← u
end if
end for
end while

return dist, prev

end function[/u][/u]
[u]例如,下面是一个包含 9 个顶点的图,每条边分别标识了距离。
 
源顶点 source = 0,初始时,
[/u]
[u][u]sptSet = {false, false, false, false, false, false, false, false, false};
distSet = {0, INF, INF, INF, INF, INF, INF, INF, INF};[/u][/u]

[u]将 0 包含至 sptSet 中;[/u]
[u][u]sptSet = {true, false, false, false, false, false, false, false, false};[/u][/u]

[u]更新 0 至其邻接节点的距离;[/u]
[u][u]distSet = {0, 4, INF, INF, INF, INF, INF, 8, INF};[/u][/u]

[u]
281631318781591.jpg

 
选择不在 sptSet 中的 Min Distance 的顶点,为顶点 1,则将 1 包含至 sptSet;
[/u]
[u][u]sptSet = {true, true, false, false, false, false, false, false, false};[/u][/u]

[u]更新 1 至其邻接节点的距离;[/u]
[u][u]distSet = {0, 4, 12, INF, INF, INF, INF, 8, INF};[/u][/u]

[u]
281635078621307.jpg

 
选择不在 sptSet 中的 Min Distance 的顶点,为顶点 7,则将 7 包含至 sptSet;
[/u]
[u][u]sptSet = {true, true, false, false, false, false, false, true, false};[/u][/u]

[u]更新 7 至其邻接节点的距离;[/u]
[u][u]distSet = {0, 4, 12, INF, INF, INF, 9, 8, 15};[/u][/u]

[u]
281637061284639.jpg

 
选择不在 sptSet 中的 Min Distance 的顶点,为顶点 6,则将 6 包含至 sptSet;
[/u]
[u][u]sptSet = {true, true, false, false, false, false, true, true, false};[/u][/u]

[u]更新 6 至其邻接节点的距离;[/u]
[u][u]distSet = {0, 4, 12, INF, INF, 11, 9, 8, 15};[/u][/u]

[u]
281638430509082.jpg

 
以此类推,直到遍历结束。
[/u]
[u][u]sptSet = {true, true, true, true, true, true, true, true, true};
distSet = {0, 4, 12, 19, 21, 11, 9, 8, 14};[/u][/u]

[u]
281640391919096.jpg

 
最终结果为源顶点 0 至所有顶点的距离:
[/u]
[u][u]Vertex   Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14[/u][/u]
[u]参考文档:https://www.cnblogs.com/gaochu ... .html[/u]

2017自如技术大赛研发组题目七:单源最短路径算法问题

PHPzkbhj 发表了文章 • 0 个评论 • 1087 次浏览 • 2017-12-04 00:08 • 来自相关话题

7. 自如今年年底就会拥有50W间房子,大家知道每间房房子都是需要配置完才能出租给自如客的,整个房租的配置过程是很复杂的,每天都需要大量的物流师傅将家电,家具等物品从仓库送到需要配置的每个房间。为了能在更多的时间配置更多的房子,我要不断的优化物流从仓库A到房间G的路径或者仓库B到房间E的距离,请写出一种算法给你任意图中两点,计算出两点之间的最短距离。
注:A B C D E F G H 都可能是仓库或者房间,点与点之间是距离
示例:






输入:AE 
输出:最短距离:22 
【PHP实现】<?php
/**
* Class Road
* 两点间最短路径计算类
* User: 郑凯
* Date: 2017/12/2
* Time: 19:48
* Dijkstra 算法,迪科斯彻算法(Dijkstra),又称为单源最短路径算法。
* Dijstra算法是运用贪心的策略,从源点开始,不断地通过相联通的点找出到其他点的最短距离。
*/

class Road {

//节点对应的字母名
public $pointName = array(
0 => "A",
1 => "B",
2 => "C",
3 => "D",
4 => "E",
5 => "F",
6 => "G",
7 => "H",

);

//地图上的点已经点之间的路径长度
public $points = array(
"A" => array(
"A" => 0,
"B" => 15,
"C" => 6,
"D" => 0,
"E" =>0,
"F" =>25,
"G" =>0,
"H" =>0
),
"B" => array(
"A" => 15,
"B" => 0,
"C" => 9,
"D" => 0,
"E" =>7,
"F" =>0,
"G" =>0,
"H" =>0
),
"C" => array(
"A" => 6,
"B" => 9,
"C" => 0,
"D" => 11,
"E" =>0,
"F" =>0,
"G" =>0,
"H" =>0
),
"D" => array(
"A" => 0,
"B" => 0,
"C" => 11,
"D" => 0,
"E" =>12,
"F" =>0,
"G" =>0,
"H" =>5
),
"E" => array(
"A" => 0,
"B" => 7,
"C" => 0,
"D" => 12,
"E" =>0,
"F" =>5,
"G" =>0,
"H" =>7
),
"F" => array(
"A" => 25,
"B" => 0,
"C" => 0,
"D" => 0,
"E" =>5,
"F" =>0,
"G" =>12,
"H" =>0
),
"G" => array(
"A" => 0,
"B" => 0,
"C" => 0,
"D" => 0,
"E" =>0,
"F" =>12,
"G" =>0,
"H" =>17
),
"H" => array(
"A" => 0,
"B" => 0,
"C" => 0,
"D" => 5,
"E" =>7,
"F" =>0,
"G" =>17,
"H" =>0
),
);

//有向图存储
private $graph = array(
array(0,15,6,0,0,25,0,0),
array(15,0,9,0,7,0,0,0),
array(6,9,0,11,0,0,0,0),
array(0,0,11,0,12,0,0,5),
array(0,7,6,12,0,5,0,7),
array(25,0,6,0,5,0,12,0),
array(0,0,0,0,0,12,0,17),
array(0,0,0,5,7,25,17,0)
);

//设置一个无穷大距离的数字
private $soBig = 999999;

private $path = array();


private function getOptimalPath($a, $b)
{

if($a == $b){
return "start and end could not be one point";
}


//读取已经选择的点
$idx = array_keys($this->points);
$a = array_search($a, $idx);
$b = array_search($b, $idx);

//存储路径上节点距离$a点的最小距离
$c = array();
$path = array();

//初始化距离起点最近的节点的最小距离
for($i=1;$i<8;$i++)
{
if($this->graph[$a][$i]>0)
{
$c[$i] = $this->graph[$a][$i];
$path[$i]['name'] = $this->pointName[$a];
$path[$i]['key'] = $a;
}
else
{
$c[$i] = $this->soBig;
}
}

//用于存储已经选择的节点
$selected = array($a);
$all = array(1,2,3,4,5,6,7);
unset($all[$a-1]);
$others = $all;

// n-1次循环完成转移节点任务
for($i=0;$i<count($this->graph)-1;$i++)
{
//查找剩余节点中距离起点最近的节点v
$current_min = $this->soBig;
$current_min_v = 0;
foreach($others as $k=>$v)
{
if($c[$v] < $current_min)
{

$current_min = $c[$v];
$current_min_v = $v;
}
}






//从$others更新顶点到$selected中
array_push($selected,$current_min_v);
array_splice($others,array_search($current_min_v,$others),1);


//更新最短路径
foreach($others as $k=>$u)
{

if($this->graph[$current_min_v][$u]!=0&&$c[$u]>$c[$current_min_v]+$this->graph[$current_min_v][$u])
{

$path[$u]['name'] = $this->pointName[$current_min_v];
$path[$u]['key'] = $current_min_v;
$c[$u] = $c[$current_min_v]+$this->graph[$current_min_v][$u];

}
}





}

$this->getRoadLine($path,$b,$a);
$finalPath = $this->pointName[$a];
foreach(array_reverse($this->path) as $x => $y){
$finalPath.=$y;
}
$finalPath.=$this->pointName[$b];

return $c[$b]." ".$finalPath;
}


//获取路径信息
public function getRoadLine($path,$b,$a)
{
if($path[$b]['key'] !== $a){
$this->path = $path[$b]['name'];
$this->getRoadLine($path,$path[$b]['key'],$a);
}

}

public function getResult($towPoint){

return $this->getOptimalPath(substr($towPoint,0,1),substr($towPoint, -1));

}


}

//获取输入变量
$params = trim(fgets(STDIN), " \t\n\r\0\x0B");
$road = new Road();
echo $road->getResult($params); 查看全部
7. 自如今年年底就会拥有50W间房子,大家知道每间房房子都是需要配置完才能出租给自如客的,整个房租的配置过程是很复杂的,每天都需要大量的物流师傅将家电,家具等物品从仓库送到需要配置的每个房间。为了能在更多的时间配置更多的房子,我要不断的优化物流从仓库A到房间G的路径或者仓库B到房间E的距离,请写出一种算法给你任意图中两点,计算出两点之间的最短距离。
注:A B C D E F G H 都可能是仓库或者房间,点与点之间是距离
示例:

QQ截图20171204000641.jpg


输入:AE 
输出:最短距离:22 
【PHP实现】
<?php
/**
* Class Road
* 两点间最短路径计算类
* User: 郑凯
* Date: 2017/12/2
* Time: 19:48
* Dijkstra 算法,迪科斯彻算法(Dijkstra),又称为单源最短路径算法。
* Dijstra算法是运用贪心的策略,从源点开始,不断地通过相联通的点找出到其他点的最短距离。
*/

class Road {

//节点对应的字母名
public $pointName = array(
0 => "A",
1 => "B",
2 => "C",
3 => "D",
4 => "E",
5 => "F",
6 => "G",
7 => "H",

);

//地图上的点已经点之间的路径长度
public $points = array(
"A" => array(
"A" => 0,
"B" => 15,
"C" => 6,
"D" => 0,
"E" =>0,
"F" =>25,
"G" =>0,
"H" =>0
),
"B" => array(
"A" => 15,
"B" => 0,
"C" => 9,
"D" => 0,
"E" =>7,
"F" =>0,
"G" =>0,
"H" =>0
),
"C" => array(
"A" => 6,
"B" => 9,
"C" => 0,
"D" => 11,
"E" =>0,
"F" =>0,
"G" =>0,
"H" =>0
),
"D" => array(
"A" => 0,
"B" => 0,
"C" => 11,
"D" => 0,
"E" =>12,
"F" =>0,
"G" =>0,
"H" =>5
),
"E" => array(
"A" => 0,
"B" => 7,
"C" => 0,
"D" => 12,
"E" =>0,
"F" =>5,
"G" =>0,
"H" =>7
),
"F" => array(
"A" => 25,
"B" => 0,
"C" => 0,
"D" => 0,
"E" =>5,
"F" =>0,
"G" =>12,
"H" =>0
),
"G" => array(
"A" => 0,
"B" => 0,
"C" => 0,
"D" => 0,
"E" =>0,
"F" =>12,
"G" =>0,
"H" =>17
),
"H" => array(
"A" => 0,
"B" => 0,
"C" => 0,
"D" => 5,
"E" =>7,
"F" =>0,
"G" =>17,
"H" =>0
),
);

//有向图存储
private $graph = array(
array(0,15,6,0,0,25,0,0),
array(15,0,9,0,7,0,0,0),
array(6,9,0,11,0,0,0,0),
array(0,0,11,0,12,0,0,5),
array(0,7,6,12,0,5,0,7),
array(25,0,6,0,5,0,12,0),
array(0,0,0,0,0,12,0,17),
array(0,0,0,5,7,25,17,0)
);

//设置一个无穷大距离的数字
private $soBig = 999999;

private $path = array();


private function getOptimalPath($a, $b)
{

if($a == $b){
return "start and end could not be one point";
}


//读取已经选择的点
$idx = array_keys($this->points);
$a = array_search($a, $idx);
$b = array_search($b, $idx);

//存储路径上节点距离$a点的最小距离
$c = array();
$path = array();

//初始化距离起点最近的节点的最小距离
for($i=1;$i<8;$i++)
{
if($this->graph[$a][$i]>0)
{
$c[$i] = $this->graph[$a][$i];
$path[$i]['name'] = $this->pointName[$a];
$path[$i]['key'] = $a;
}
else
{
$c[$i] = $this->soBig;
}
}

//用于存储已经选择的节点
$selected = array($a);
$all = array(1,2,3,4,5,6,7);
unset($all[$a-1]);
$others = $all;

// n-1次循环完成转移节点任务
for($i=0;$i<count($this->graph)-1;$i++)
{
//查找剩余节点中距离起点最近的节点v
$current_min = $this->soBig;
$current_min_v = 0;
foreach($others as $k=>$v)
{
if($c[$v] < $current_min)
{

$current_min = $c[$v];
$current_min_v = $v;
}
}






//从$others更新顶点到$selected中
array_push($selected,$current_min_v);
array_splice($others,array_search($current_min_v,$others),1);


//更新最短路径
foreach($others as $k=>$u)
{

if($this->graph[$current_min_v][$u]!=0&&$c[$u]>$c[$current_min_v]+$this->graph[$current_min_v][$u])
{

$path[$u]['name'] = $this->pointName[$current_min_v];
$path[$u]['key'] = $current_min_v;
$c[$u] = $c[$current_min_v]+$this->graph[$current_min_v][$u];

}
}





}

$this->getRoadLine($path,$b,$a);
$finalPath = $this->pointName[$a];
foreach(array_reverse($this->path) as $x => $y){
$finalPath.=$y;
}
$finalPath.=$this->pointName[$b];

return $c[$b]." ".$finalPath;
}


//获取路径信息
public function getRoadLine($path,$b,$a)
{
if($path[$b]['key'] !== $a){
$this->path = $path[$b]['name'];
$this->getRoadLine($path,$path[$b]['key'],$a);
}

}

public function getResult($towPoint){

return $this->getOptimalPath(substr($towPoint,0,1),substr($towPoint, -1));

}


}

//获取输入变量
$params = trim(fgets(STDIN), " \t\n\r\0\x0B");
$road = new Road();
echo $road->getResult($params);