搜索里的相似度计算 最长公共子串

相似度计算的任务是根据两段输入文本的相似度返回从0到1之间的相似度值：完全不相似，则返回0,；完全相同，返回1.衡量两端文字距离的常用方法有：海明距离（Hamming distance），编辑距离，欧氏距离，文档向量的夹角余弦距离，最长公共字串。

##1. 余弦相似度

把两篇文档看作是词的向量，如果x,y为两篇文档的向量，则：Cos(x, y) = (x * y) / (   x   *   y   )

使用Hashmap可以很方便的把这个计算出来

##2. 最长公共字串(Longest Common Subsequence, LCS)

矩阵生成

假设有串s1 = {a,b,c,b,d,a,b}, s2={b,d,c,a,b,a}, s1和s2的最长公共字串应当有3个”bdab”,”bcab”,”bcba”。

这又是一个动态规划法的应用，思维过程就简单带过，生成一个s1.size + 1 X s2.size+1的矩阵，行和列分别是s1和s2的每个字母，填充矩阵，如果对应的两个字母相同，就把斜上角的元素+1，填充到当前矩阵位置，如果不同，取该位置相邻左边及上边的最大值，一直把矩阵填满，最右下角的矩阵值就是最长公共字串的长度。

                b       d       c       a       b       a      
        0       0       0       0       0       0       0      
a       0       0       0       0       1       1       1      
b       0       1       1       1       1       2       2      
c       0       1       1       2       2       2       2      
b       0       1       1       2       2       3       3      
d       0       1       2       2       2       3       3      
a       0       1       2       2       3       3       4      
b       0       1       2       2       3       4       4      

###回溯

得到最长公共字串的矩阵后，剩下的工作就是回溯。

  • 如果当前位置的s1字符和s2字符相同，则是相同的数值。

  • 如果不同，则要向上或向左移动，移动到大的一边，与填充矩阵的逻辑对应。

  • 如果是相同呢？

    如果只求其中一个公共字串，逻辑比较简单，随便想上或者向左

    如果要求所有的公共字串，则每一边都有可能，可以简单用递归解决。

好了。说这么多，奉上ruby写的代码。

#encoding:utf-8
require 'matrix'
class Matrix
  def []=(i, j, x)
    @rows[i][j] = x
  end
end

# 最长公共字串
 def start
   $s1 = 'abcbdab'
   $s2 = 'bdcaba'
   $num = Matrix.zero($s1.size + 1, $s2.size + 1)
   puts "Row = #{$num.row_size}, col = #{$num.column_size}"
 
   for i in 1..$s1.size
     for j in 1..$s2.size
       if $s1[i - 1] == $s2[j - 1]
         $num[i, j] = $num[i-1, j-1] + 1
       else
         $num[i, j] = [$num[i-1, j], $num[i, j-1]].max
       end
     end
   end
 
   puts "最长公共字串的长度是#{$num[$s1.size, $s2.size]}"
   $num.each_with_index { |val, row, col| print val,','; puts if (col + 1) % $num.column_size == 0}
 
   # 回溯路径
   $result = []
   $lcs_length = $num[$s1.size, $s2.size]
   s1position = $s1.size
   s2position = $s2.size
   loop_path(s1position, s2position, '')
   $result.each {|x| puts "lcs: #{x}"}
 
   puts "one path is: #{one_loop_path(s1position,s2position, '')}"
 end
 
 def one_loop_path(s1position, s2position, result)
   while s1position != 0 and s2position != 0
     if $s1[s1position - 1] == $s2[s2position - 1]
       result << $s1[s1position - 1]
       s2position -= 1
       s1position -= 1
       next
     end
 
     if $num[s1position, s2position - 1] >= $num[s1position - 1, s2position]
       s2position -= 1
     else
       s1position -= 1
     end
   end
   result
 end
 
 def loop_path(s1position, s2position, result)
   while s1position != 0 and s2position != 0
     if $s1[s1position - 1] == $s2[s2position - 1]
       result << $s1[s1position - 1]
       s2position -= 1
       s1position -= 1
       next
     end
 
     if $num[s1position, s2position - 1] > $num[s1position - 1, s2position]
       s2position -= 1
     elsif $num[s1position, s2position - 1] < $num[s1position - 1, s2position]
       s1position -= 1
     elsif $num[s1position, s2position - 1] == $num[s1position - 1, s2position]
       leftpath = result.clone
       uppath = result.clone
       loop_path(s1position, s2position - 1, leftpath)
       loop_path(s1position - 1, s2position, uppath)
       break
     end
   end
   $result << result.reverse! if result.size == $lcs_length
   # $result << result.reverse! if result.size == $lcs_length
 end
 
 start

Published: July 19 2014

blog comments powered by Disqus