http://blog.sina.com.cn/s/blog_1777542730102xuqz.html
上面这个是中文的一个解释。
这里我并不是为了要进行某种相似度函数的解释，而是说，怎么来解决我一直困扰的问题。n^2问题。
就是要获取全部的对比样本，我应该怎么做，在大数据环境下，如果上千上万个样本，这玩意就更难弄了。
我这里出现的问题就是，我前面在做这个二进制程序的比较，然后发现了这么一个问题，我使用ssdeep获取了这个程序的哈希数值，但是我要获取其中相似度最高的对，也就是说要进行相似度比较，那么比较简答的方法就是两两相比，就是这么简单嘛。
但是这种方式的复杂度是多少呢，是n(n-1)/2，C n 2问题。算法的时间复杂度就是o(n^2)问题。
因为使用的是mysql数据库，我当前没有对每行记录进行标记，是否这个样本已经做了比较（其实这个逻辑好像不难，但是也有点麻烦，得仔细设计）。然后最后图简单就是直接重新全部跑，虽然数据可能插不进去，但是每次都是把所有的数据都跑了一边。
（如果有批量查询就好了，应该有吧，就是批量查询是否这些主键是否存在）
然后这样的结果当然是非常不尽人意，最开始的单线程操作，之后又是多线程操作，改为多线程的时候，速度明显提升了，但是后来数据量上去了之后，就发现出现的bug是说，数据库连接太多的错误好像。反正就是不太对。
那么这里的问题就很明显了，到底应该怎么来弄这个东西呢？
之前看过的一些内容的就是利用局部哈希的方法来做，但其实我对这个东西看了很多遍之后，反而模糊了。
因为有的文章是说将minhash和LSH组合在一起，但是本身来说，minhash不就是LSH吗？
所有这里我非常疑惑。
而且实际情况是，我本身要做的是二进制程序的程序的相似度比较，我已经通过ssdeep的方法，将这部分内容给凝练出来了。这就非常尴尬了。他最后的，已经是一个数值了，是不是说这种方法之后还是需要进一步进行操作呢？
（这里还有一个问题，ssdeep进行比较的时候是怎么比较的，我是利用了这个东西的py库进行比较，并不是非常清楚具体的内容，这里也是一个可以改进的地方）
好了，说了这么多，基本上问题也就大致上清楚了。
- LSH和ssdeep，minhash这些东西是什么关系，是否可以结合。
- 是否存在其他的解决方案。
[1]https://towardsdatascience.com/a-practitioners-guide-to-similarity-scoring-part-2-the-n%C2%B2-problem-af707461276a
[2]https://medium.com/@rizvihasan/large-scale-document-similarity-search-with-lsh-and-minhash-b8ddfc4affe
这两篇是我看到的比较好的，然后我通过similarity large dataset这些关键词搜索，发现全部都是论文，这两篇网页的文章还是好不容易找到的。
文章2是专门解释LSM和minhash的，解释的较为基础且全面，而且他也提到了《海量数据挖掘》这本书。
文章[1]就不是从这个LSM来说了，他更多的是直接来说明这个n ^ 2问题。
他提出了两个类别的解决方案。
- 通过桶的方式，先选择某些列，然后进行相似度检测
- 如果数据是向量，通过ANN 我自己翻译是，接近K紧邻。
首先文章[1]在前文中就提出，一般而言相似度比较有两种方式，一种是离线检测，也就是说将全部的数据进行两两比较，另一种是在线检测，已经有一批数据了，来一个新的数据，将这个数据跟这些老的数据进行检测。
然后他提出了一个比较好的出发点，那就是排序算法。从整体来说，排序算法的复杂度也是n^2，那么通过一些手段是可以将这个复杂度将为nlogn。就是从这个认知为出发点，来研究某种算法。
但是这里依然要说明，这些算法并不能得到准确的一个相似度（某个函数），他们是想办法给你一个大致的数值，而这个数值，你可以去作为参考，然后如果你想得到具体的相似度，你还要进行这个过程。但是你要明白，这种方式就已经将那种肯定不相似的给过滤掉了。
那么其实意义就是，我是要做那种大致的比较，然后能够节省人力。
网友评论