Come world to Record life

前言

捣鼓了半天，终于把用python写界面的一套玩意大体上搞清楚了。一开始一直在纠结用什么python IDE适合进行桌面程序开发，很多PyQt发布网站都推荐用Eric这个编辑器，然而我自己试了下发现界面很一般，而且搞不好还会在安装配置的过程中搞出很多麻烦。而实际上，稍微研究一下也能发现PyQt5也并不是和Eric绑定的东西，他其实就是一个python库，完全可以直接用任意的文本编辑器来写，因此我还是选择了比较方便的PyCharm。

环境安装

为了使用PyQt5，我们最好还是使用python3及以上的版本，虽说他(貌似)能够兼容python2.x，但是不管是从字符集、兼容性、还是未来的趋势来讲，用python3总没错。一般来说，在Ubuntu下，我们可以直接用类似下面的命令来安装python3以及python3对应的qt5库:

1
2
3

$sudo apt install python3
$sudo apt install python3-pyqt5*
$sudo apt install libqt5*

单独的PyQt5用法可以找到很多文档，也就是不拖控件直接写代码的那种，当然这样写相对麻烦，更快捷的方法就是用QtDesigner来设计界面生成.ui文件，再用pyuic5将他转换为.py的界面文件，最后实现其任务逻辑。当然，我们也可以把Qt Designer 和 pyuic5集成到pycharm的工具栏里，不过没啥卵用，本质上还是不同的软件。Qt Designer可以从Qt的官网上下到。

QtDesigner其实就是原先给C++版的Qt(Qt Creator)用的界面设计工具，不过他们之间采用的是松散耦合，也就是QtDesigner设计界面，然后生成*.ui的界面描述文件，接着再将这个文件转化为C++代码。这里的PyQt5也是一样，首先我们直接用Qt  Designer，编辑好界面(包括布局以及各种槽函数的配置)，然后在命令行下，用pyuic5 HelloWorld.ui -o HelloWorld.py命令生成一个布局类，然后在这个基础上进行后续操作。后续操作的具体方法可以参考官方文档的做法《PyQt—Using Qt Designer》。

因此，总而言之，我们需要用到的就是python3，pycharm，pyuic5(通常集成在Qt Designer里)，以及Qt Designer。

使用样例

下面稍微记录下一般的流程：

首先打开Qt Designer，随便编辑一个Widget窗口，并添加一个退出按钮，以及一个自定义按钮，为退出按钮绑定窗口退出的函数，为自定义按钮绑定一个自定义的函数（Qt Designer的使用不做介绍），保存到Test.ui：

生成的Test.ui是以xml格式描述的界面信息：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

<?xml version="1.0" encoding="UTF-8"?>
<ui version="4.0">
 <class>Form</class>
 <widget class="QWidget" name="Form">
  <property name="geometry">
   <rect>
    <x>0</x>
    <y>0</y>
    <width>400</width>
    <height>300</height>
   </rect>
  </property>
  <property name="windowTitle">
   <string>Form</string>
  </property>
  <widget class="QPushButton" name="pushButton">
   <property name="geometry">
    <rect>
     <x>140</x>
     <y>190</y>
     <width>99</width>
     <height>27</height>
    </rect>
   </property>
   <property name="text">
    <string>Exit</string>
   </property>
  </widget>
  <widget class="QPushButton" name="pushButton_2">
   <property name="geometry">
    <rect>
     <x>140</x>
     <y>110</y>
     <width>99</width>
     <height>27</height>
    </rect>
   </property>
   <property name="text">
    <string>Diy</string>
   </property>
  </widget>
 </widget>
 <resources/>
 <connections>
  <connection>
   <sender>pushButton</sender>
   <signal>clicked()</signal>
   <receiver>Form</receiver>
   <slot>close()</slot>
   <hints>
    <hint type="sourcelabel">
     <x>228</x>
     <y>207</y>
    </hint>
    <hint type="destinationlabel">
     <x>342</x>
     <y>248</y>
    </hint>
   </hints>
  </connection>
  <connection>
   <sender>pushButton_2</sender>
   <signal>clicked()</signal>
   <receiver>Form</receiver>
   <slot>slotDiy()</slot>
   <hints>
    <hint type="sourcelabel">
     <x>225</x>
     <y>119</y>
    </hint>
    <hint type="destinationlabel">
     <x>348</x>
     <y>167</y>
    </hint>
   </hints>
  </connection>
 </connections>
 <slots>
  <slot>slotDiy()</slot>
 </slots>
</ui>

下面生成python代码pyuic5 Test.ui -o Test.py ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# -*- coding: utf-8 -*-

# Form implementation generated from reading ui file 'Test.ui'
#
# Created by: PyQt5 UI code generator 5.7
#
# WARNING! All changes made in this file will be lost!

from PyQt5 import QtCore, QtGui, QtWidgets

class Ui_Form(object):
    def setupUi(self, Form):
        Form.setObjectName("Form")
        Form.resize(400, 300)
        self.pushButton = QtWidgets.QPushButton(Form)
        self.pushButton.setGeometry(QtCore.QRect(140, 190, 99, 27))
        self.pushButton.setObjectName("pushButton")
        self.pushButton_2 = QtWidgets.QPushButton(Form)
        self.pushButton_2.setGeometry(QtCore.QRect(140, 110, 99, 27))
        self.pushButton_2.setObjectName("pushButton_2")

        self.retranslateUi(Form)
        self.pushButton.clicked.connect(Form.close)
        self.pushButton_2.clicked.connect(Form.slotDiy)
        QtCore.QMetaObject.connectSlotsByName(Form)

    def retranslateUi(self, Form):
        _translate = QtCore.QCoreApplication.translate
        Form.setWindowTitle(_translate("Form", "Form"))
        self.pushButton.setText(_translate("Form", "Exit"))
        self.pushButton_2.setText(_translate("Form", "Diy"))

他是以Ui_Form类的形式来保存界面设置的信息，显然不能直接执行他，当然也不要直接编写他，否则万一重新修改了界面，还得重新写控制代码。我们可以看到在空行前面的是界面的设置，空行后面的是槽的设置，显然这就意味着传进去的Form 对象得有slotDiy函数来响应信号。

下面就用这个布局来写一个可执行的窗口，新建一个Main.py文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import sys
from  PyQt5 import QtWidgets
from Test import Ui_Form

class Main(QtWidgets.QWidget, Ui_Form):
    def __init__(self):
        super(Main, self).__init__()
        self.setupUi(self)
        self.show()
    def slotDiy(self):
        print("DiyBtn clicked")
app = QtWidgets.QApplication(sys.argv)
main = Main()
sys.exit(app.exec_())

执行python Main.py即可：

HSTS 是 HTTP Strict Transport Security （HTTP 严格安全传输）的缩写。开启了这项设置以后，大部分浏览器会强制性地使用 HTTPS 来请求资源，能够更加有效地保护网站和用户的数据安全。

我们都知道多线程可以提高程序运行的速度，但是至于能够提高多少却一直没有一个直观的印象，下面就用Linux C的多线程编程技术，简要分析下多线程的运行效率。

测试代码

下面就用1000*1000的矩阵之间的乘法来做一个实验，我们分别用单线程和多线程分别实现，算法都采用$O(n^3)$的朴素算法。测试代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include <sys/time.h>

#define LEN 1000
#define MAXNUM 1000
#define MAXTHREADNUM 16

long long matrix1[LEN][LEN]={0};
long long matrix2[LEN][LEN]={0};
long long sum[MAXTHREADNUM]={0};
long long ans=0;

long long getCurrentTime(){
   struct timeval tv;
   gettimeofday(&tv,NULL);
   return tv.tv\_sec * 1000 + tv.tv\_usec / 1000;
}
void genMatrix(char *file){
    FILE *fp=fopen(file,"w");
    srand(time(NULL));
    for(int i=0;i<LEN;i++){
        for(int j=0;j<LEN;j++){
            int random=rand()%MAXNUM;
            fprintf(fp,"\t%d",random);
        }
        fprintf(fp,"\n");
    }
    fclose(fp);
}

void getMatrix(long long matrix[LEN][LEN],char *file){
    FILE *fp=fopen(file,"r");
    for(int i=0;i<LEN;i++){
        for(int j=0;j<LEN;j++){
            fscanf(fp,"\t%lld",&matrix[i][j]);
        }
        char tmp;
        fscanf(fp,"%c",&tmp);
    }
    fclose(fp);
}

int threadNum;
void* runner(void *p){
    int pid=*(int*)p;
    long long sumT=0;
    for(int i=pid;i<LEN;i+=threadNum){
        for(int j=0;j<LEN;j++){
            for(int k=0;k<LEN;k++){
                sumT+=matrix1[i][k]*matrix2[k][j];
            }
        }
    }
    sum[pid]=sumT;
    free((int *)p);
    pthread_exit(NULL);
}

void multiThread(int num){
    threadNum=num;
    long long clock1=clock();
    long long time1=getCurrentTime();
    pthread_t id[MAXTHREADNUM];
    for(int i=0;i<threadNum;i++){
        int *p=(int *)malloc(sizeof(int));
        *p=i;
        pthread_create(&id[i],NULL,runner,p);
    }
    ans=0;
    for(int i=0;i<threadNum;i++){
        pthread_join(id[i],NULL);
        ans+=sum[i];
    }
    long long clock2=clock();
    long long time2=getCurrentTime();
    printf("Multi Thread %d:\n",num);
    printf("Ans =\t%lld\nClock time =\t%lldms\nUnix time =\t%lldms\n\n",ans,(clock2-clock1)/1000,time2-time1);
}

int main(){
    char name1[50]="matrix1.txt";
    char name2[50]="matrix2.txt";

    FILE *fp=fopen(name1,"r");
    if(fp==NULL){
        genMatrix(name1);
    }else{
        fclose(fp);
    }
    fp=fopen(name2,"r");
    if(fp==NULL){
        genMatrix(name2);
    }else{
        fclose(fp);
    }

    getMatrix(matrix1,name1);
    getMatrix(matrix2,name2);

    for(int i=1;i<=16;i++){
        multiThread(i);
    }
}

程序简要分析

注：为了方便验证结果的正确性，我计算了$\sum x_{ij}$来进行对比。

单线程的部分自不必说，多线程的部分我采用的并不是通用的线程池，也不是对每一个任务都创建一个线程，而是根据行数模线程数的值来分配给不同的线程。这样总线程数一直不变，相对简化了线程创建的开销，以及代码量。

关于pthread库的使用也是很讲究的。

对于pthread_create 来说，为了保证能够兼容不同的回调函数，他在创建进程的时候将回调函数的参数和返回值都定义为void*。那么如果想传入自己的参数就要用一个指针来传入数据并强制转换为void *，然后在回调函数里强制类型转换为实际的类型。如果要传入多个参数，就要自己写一个结构体来传，还是非常麻烦的。而且这里还要注意一点，就是不能把临时变量的引用当做参数传给回调函数，因为临时变量是会在循环结束后立即被释放的，这样会导致回调函数得不到正确的值。正确的做法应该是malloc一块内存，并用指针把这块内存传给回调函数，回调函数在执行完任务逻辑后再自行释放。

对于pthread_exit 和pthread_join 来说，我们要知道的是，pthread_exit才是真正传递回调函数返回值的地方。我们将需要返回的值传递给他，然后再用pthread_join 的第二个参数来接受这个参数。不过通常为了简单起见都会开一个全局数组来接受不同线程的计算结果。

当然，多线程最怕的就是不同线程对同一数据的修改，如果必须修改，那么就得对这块代码块加锁。

关于程序的逻辑，我们需要注意的就是计算结果可能会过大导致数据溢出，因此我们要小心控制下数据的大小。

还有一个小细节，就是如何用Linux C来获取Unix 时间戳，一开始以为是clock()函数，不过后来才发现，clock()函数是cpu时间，不是真正的时间。比如说我的cpu有四个核，这四个核同时工作了1s，那么用clock()函数做差可以发现结果是接近4s。因此，正确的做法是重写一个getCurrentTime函数，这样就能得到真正的Unix时间戳。

最后需要注意的就是程序在编译时需要加上-lpthread 参数。

运行结果分析

对于一个四核的电脑，我们运行的结果是：

对于一个九十六核的服务器，我们运行的结果是：

我们可以发现，对于九十六核的服务器而言，UNIX时间*线程数近似等于CPU时间，而CPU时间近似保持不变，多线程的特性发挥的很完美。而对于四核的电脑来说，当线程数大于四的时候，我们就发现程序的执行时间就开始发生波动，执行效率并没有随着线程数增加而有所提高。

利用minivtun实现点对点非公网NAT穿透，在学校轻松访问家里的路由器。需要一个中心化公网服务器（VPS）作为打洞实现内网访问。

11月3日是个特别的日子。1957年11月3日，前苏联发射了 Sputnik-2 号卫星，这是第二颗进入地球轨道的人造卫星，也是人类发射的第一颗载有活物的卫星。消息发布后，西方世界一片哗然，在美国小得可怜的首枚人造卫星发射之前，苏联的举动彻底夯实了其航天第一强国的地位。美国中情局对此作了大量分析，纠结于苏联卫星究竟是否带了活物之间。在确信苏联发射了活狗，原已令西方震惊，但这只狗的结局，更成为后来数十年的科学悬案。
那只随 Sputnik-2 升空的三岁流浪雌性混血萨摩耶犬名叫莱卡。作为第一只进入太空的地球生物，莱卡名垂青史，但它的结局却着实悲惨。从一开始，苏联人就没打算让它回来。10月4日苏联发射首枚人造卫星后一星期后，赫鲁晓夫就建议再次发射更为复杂的卫星，作为伟大十月革命40周年献礼，这意味着工程技术人员只有3周时间来设计和制造新的火箭及卫星。这次苏联决定发射生物上天。
一切为了进度， Sputnik-2 使用了 Sputnik-1 的部分备件，为了最大限度提高载荷能力，火箭的部分设备甚至也被拆除。科罗廖夫的助手鲍里斯·切尔托克在回忆中这样写道，“一切火箭技术开发的传统都被抛弃，第二颗卫星的开发根本未经详细设计，或者说根本没有设计。”卫星的大部分部件都是赶工制造的，工程师们甚至被派到工厂协助工人赶工，许多部件甚至省略了蓝图环节。紧张的工期甚至不允许工程师设计出可靠的生命保障系统，更不消说为莱卡铺就一条回家的路。

发射升空过程中，监测系统显示莱卡的心率达到了每分钟 260 次，比平时高 3 倍，呼吸频率也超出正常水平 4～5 倍，但顽强的莱卡还是活了下来，成功进入轨道。入轨后，载荷舱头锥成功分离，但有些部件却分离失败。造成的一个恶劣后果就是，热控制系统无法正常工作。此外，一些隔热材料被撕裂，舱内温度很快升至 40 度以上。据信在死于焦躁和高热之前，莱卡顶多活了两天，西方人甚至认为只有几个小时，根本不像苏联人宣布的那样长。莱卡用自己的生命告诉人类科学家，通过合理的防护措施，人类能够在太空环境下生存。这个代价对人类而言不大，但对莱卡而言不小。
莱卡的悲惨结局，固然可以归结为当时尚不成熟的返回卫星技术，但更为重要的原因，是美苏当时心急火燎的太空竞赛，而竞赛背后，是东西方阵营意识形态的激烈冲突。但无论如何，我们起码可以给莱卡更有尊严的死亡方式，一支安乐死制剂就足以实现。遗憾的是，1957年11月3日的那次发射，这些都没有被详尽计划。
每每看到关于莱卡的记述，我都会对身边动物平添几分敬意，提醒自己善待它们。为了人类的文明征程，它们已经付出了太多，我们不能与此同时再让他们成为我们野蛮举止的牺牲。
莱卡，回家吧。

虽说用Ubuntu的目的就是不喜欢windows大而杂的作风，但是由于office这类的工具实在是太流行，导致即使在ubuntu下工作还是要经常使用office套件。可是问题来了，无论是ubuntu自带的liboffice套件还是Apache的Openoffice，他们都实在是不好用，不仅界面丑，而且各种工具也经常找不到，更重要的是他不能跟ms office很好的兼容，尤其是word中的表格一类的东西。比方说一个挺好的实验报告，在这里看到的却是下面的效果：

啥玩意都乱了，十分丑陋。

不过还好，在网上找了半天，竟然惊奇的发现wps制作了兼容Linux的office套件（下载地址），不得不说，wps还是相当有职业道德的。。。

下载deb包，dpkg安装就行了，打开后发现界面跟ms office真的差不多:

表格的排版也是很不错的，用起来也很符合office的习惯，重点是。。。不要钱。

不过，默认的wps是支持IBus的输入法，是不能输入中文的，最典型的问题就是即使装了sogou中文输入法也无法输入中文。问题的解决也很简单，就是在他的启动脚本/usr/bin/wps 和/usr/bin/et 里添加两个环境变量即可：（参照这里）

1
2
3
4

...
export XMODIFIERS="@im=fcitx"
export QT_IM_MODULE="fcitx"
...

曾经一直由于windows太卡，导致在windows下安装的虚拟机性能都很不好，这就导致我曾经一直以为虚拟机都是巨卡无比。不过这次在ubuntu下面用了虚拟机才发现原来虚拟机技术本身并不会对系统本身带来太多的负面影响，至少在我的ubuntu下面用起来还是挺流畅的。

VirtualBox

virtualBox是一个非常有名的开源虚拟机软件，曾经由Sun公司用Qt开发，当然现在归Oracle了。他据说被称为最强的免费虚拟机软件，支持现存绝大多数操作系统，支持快照、共享文件、承载不同系统架构等等很不错的特性。

安装使用

在使用virtualbox之前，首先得确认你的电脑支持cpu虚拟化技术(其实就是提高硬件支持)。在BIOS里面可以看到类似的选项，默认是关闭的，我们把他开开就好。

当然，并不是所有的虚拟机软件都必须要开启cpu虚拟化的，只是开启了这个选项后会使虚拟机运行更流畅。

对于具体的安装而言，ubuntu下安装当然是很简单的了，$sudo apt install virtualbox 即可。

然后打开他，按照要求选择需要的操作系统和版本，然后开启虚拟机，选择下载好的镜像。

这样就会进入镜像的安装程序，跟普通U盘启动装机差不多，如下图所示：

接下来就是很傻瓜的操作了，完成后就会显示我们熟悉的界面了。

这样就可以正常使用虚拟机了。

共享文件

虽然有了虚拟机，但是如果需要主机能够和虚拟机进行通信的话则还要另外下载一个iso扩展包。不过好在这个东西也可以很方便的用$ sudo apt install virtualbox-guest-additions-iso来下载。

我们来看看他把东西放在哪里了：

1
2
3
4
5
6
7
8
9
10

$ dpkg -L virtualbox-guest-additions-iso 
/.
/usr
/usr/share
/usr/share/virtualbox
/usr/share/virtualbox/VBoxGuestAdditions.iso
/usr/share/doc
/usr/share/doc/virtualbox-guest-additions-iso
/usr/share/doc/virtualbox-guest-additions-iso/copyright
/usr/share/doc/virtualbox-guest-additions-iso/changelog.Debian.gz

找到那个VBoxGuestAdditions.iso文件，这就是我们需要的。

接着，对于需要进行文件共享的虚拟机系统，我们在他的Storage设置里添加上面这个镜像文件，替代之前安装时的镜像文件：

然后我们在Shared Folders设置里添加一个本机中的文件夹作为共享文件夹，设置为自动挂载（共享文件分为Transient Folder和Permanent Folder，一般用永远共享就好）。

接着打开虚拟机，如果是windows虚拟机的话，他会提示你安装下驱动程序，然后他会提示你有新媒体被发现，也就是以一个网络位置的形式呈现在下面，而这个其实就是和主系统公用的共享文件夹。

如果是ubuntu虚拟机的话，他会默认把共享文件夹挂载在/media下，其实我们可以直接把他看成个文件夹了。

关于Android虚拟机

其实virtualbox也能支持模拟安卓机子，不过一般的ROM是不能直接用的。不过还好，有个叫android-x86的项目，把很多安卓ROM搞成了适合电脑直接安装的iso镜像，这样就可以直接装了。镜像的下载地址在这里。

有两个具体介绍的博客1，博客2，详细介绍了安卓虚拟机的安装细节，讲的还是不错的，照着弄基本就没问题了。

在对向量进行相似度计算的时候经常需要纠结的是用什么测度来衡量相似度。经常听到的距离测度无非是欧氏距离、曼哈顿距离、切比雪夫距离、闵科夫斯基距离、海明距离、编辑距离、余弦距离、杰卡德距离这么几个，稍微生僻点的再加上什么标准化欧氏距离、卡方距离、马哈拉诺比斯距离、巴塔恰里雅距离、皮尔逊距离。前面说的那些距离大都是一回事，掌握了初中左右的知识基本都能理解，而后面说的这些距离就相对复杂很多了，得有离散统计线性代数这类的扎实功底才能吃透。。。这里就稍微介绍下概念上距离测度的定义，以及简单的距离测度。

距离测度的定义

感觉实距离测度本没有标准的定义，只是人们用多了，也就有了这么个定义。

所谓距离测度(Similarity Measure)就是指一个函数$d(x,y)$，用空间中的两个点$x,y$作为参数，输出一个实数值，这个值能够反应这两个点的距离关系。这个函数一般要满足下面的准则：

1、$d(x,y)\geq 0$（非负性）

2、$x=y$当且仅当$d(x,y)=0$（自反性）

3、$d(x,y)=d(y,x)$（对称性）

4、$d(x,y)\geq d(x,z)+d(z,y)$(三角不等式)

前三个都很好理解，只是为什么一定要满足三角不等式呢？我想应该是为了保证距离一定得是所有同类路径中最短的那条轨迹。

闵可夫斯基距离类

在n维空间中，两个n维向量$x=(x_1,x_2,x_3,…,x_n),y=(y_1,y_2,y_3,…,y_n)$之间的闵可夫斯基距离(Minkowski Distance)定义为：

$$d(x,y)=(\overset{n}{\underset{i=1}{\sum}}|x_i-y_i|^p)^{\frac 1p}$$

闵科夫斯基距离实际上就是Lp norm里的距离(p根据需要确定)。可以很容易的证明当p>=1的时候，这个距离都是满足距离测度的定义的。不过当$p<0$时，他就不满足三角不等式了，也就不算是标准的距离测度了。

当$p=1$时，闵科夫斯基距离就变曼哈顿距离成了：

$$d(x,y)=\overset{n}{\underset{i=1}{\sum}}|x_i-y_i|$$

曼哈顿距离，又叫出租车距离，直观的理解就是向量在各个维度上差的绝对值之和。

当$p=2$时，就是我们最常见的欧氏距离了：

$$d(x,y)=(\overset{n}{\underset{i=1}{\sum}}(x_i-y_i)^2)^{\frac 12}$$

当$p\to\infty$时，闵科夫斯基距离就变成了切比雪夫距离：

$$d(x,y)=MAX(|x_i-y_i|)$$

也就是向量在各个维度上差的绝对值的最大值。

可以很容易证明，当$p\geq 1$时，闵科夫斯基距离是满足距离测度的所有要求的。

海明距离

海明距离的定义也很简单，对于两个向量，他们之间的海明距离就是定义为这两个向量中不同分量的个数。仔细想想这个距离定义好像很没有用，不过事实上他通常应用在布尔向量(比如00101和01111的海明距离就是2)或者相似度要求比较高的场景中。

他的特点在于计算速度巨快，通过计算机基础的异或操作就能比较布尔向量的距离，因此在数据量巨大、追求效率的场景中用处还是非常广的。

编辑距离

编辑距离也是很简单的，主要用于两个字符串之间的距离计算。定义就是将一个字符串用最少的删除、插入操作变成另一个字符串所需要的操作个数。比如$x=abcde,y=acfdeg$，他们的编辑距离就是3。具体的实现方法就用$dp$做就好了，复杂度就是两个字符串长度之积。他的值跟这两个字符串的LCS还有一定的关系，即编辑距离等于x和y的长度之和减去他们LCS长度的两倍。

当然，有些定义的编辑距离还会支持“替换”或者“交换”之类的操作，其实意思也都差不多了。

余弦距离

余弦距离就是字面上的意思了，也就是求两个向量夹角的余弦值。具体的计算方法也就是用两个向量的内积除以两个向量的$l_2\ \ norm$：

$$d(x,y)=\frac{\sum x_iy_i}{(\sum(x_i-y_i)^2)^{\frac 12}}$$

余弦距离在某些情况下特别管用，谁用谁知道。

杰卡德距离

Jaccard距离实际上就是1-Jaccard相似度，即：

$$d(x,y)=1-SIM(x,y)$$

在文档相似度处理时，杰卡德距离和杰卡德相似度都常常被提及。

上面这些距离测度其实都很好理解，在这里归纳一下主要是为了以后遇到类似距离计算的问题时能够多几种思考的角度。

LSH

我们知道最小哈希签名能够把一篇较大的文档压缩成一个较短的签名并且不影响文档间的Jaccard相似度。很多情况下，我们用最小哈希签名的目的就是为了方便的对文档进行存储，并且对于给定的文档，能在大量的文档中快速的查找相似的文章。现在我们能做到快速的对两篇文章进行相似度比较，但是当总的文档数目比较大的时候，比较所有文档的最小哈希签名仍然是一个非常耗时耗力的事。而我们知道，对于给定的文档而言，文档库中的绝大多数文档其实都没有比较的意义，如果能有一个方法能过滤掉不需要比较的大量文档，那么显然就能加快整个查找的过程。这个思路其实可以称为”Filter and Refine”，”先过滤，后提纯”。而实现这个的方法，就是LSH(Locality-Sensitive Hashing 局部敏感哈希)。

现在先不精确定义LSH，只要知道LSH是一种对大量数据进行过滤的方法即可。

面向最小哈希签名的LSH

对于最小哈希签名来说，我们可以通过一种叫“行条化策略”的方法，对最小哈希签名再进行一次哈希。怎么做呢？

对于$n$个长度为$k$的最小哈希签名的集合$S_1,S_2,S_3,…,S_n$、以及生成他们的的$k$个哈希函数来说，我们用下面的签名矩阵来表示他们：
$$
\begin{matrix}&S_1&S_2&S_3&…&S_n\\h_1&x&x&x&x&x\\h_2&x&x&x&x&x\\h_3&x&x&x&x&x\\…&x&x&x&x&x\\h_k&x&x&x&x&x\\\end{matrix}
$$

其中一列就表示一个最小哈希签名。

接着，我们把这个矩阵平均划分成$b$个行条，每个行条有$r$行(显然$r*b=k$)。这相当于我们把每一个签名分成了$b$段，每一段有$r$个数。然后我们再分别对每一段进行一次哈希，将该段相同的哈希签名放在一个桶中，该段不同的放在不同的桶中(当然，不同行条的桶互不影响）。这就相当于把一个长度为$k$的最小哈希签名映射到了$b$个桶中。

这样一来，我们如果我们需要对某个最小哈希签名进行相似查找，我们只要对这$b$个桶中的那些东西进行比较即可，省去了很多不必要的比较。

行条化策略分析

那么用行条化策略后会不会影响我们查询的准确性呢？答案是—当然会。

所谓影响正确性，无非就两种，一种是伪正例(false positive)，一种是伪反例(false negative)。

所谓伪正例，就是指我们把不相似的签名加到了进一步比较的列表中。对于伪正例而言，我们显然不用担心，因为下一步直接比较的目的就是去除伪正例，只是会害我们多比较几次，因此我们主要关注的是伪反例。

所谓伪反例，就是指我们把相似度很高的签名给漏掉了。这就很尴尬了，因为漏掉的话以后就再也不会考虑到他了。这是我们需要极力避免的。

那么伪反例的比例到底是怎么样的呢？

我们知道在两个签名的Jaccard相似度为$s$的情况下，这两个签名的某一个位相等的概率就是$s$，那么在某一行相等的概率就是$s^r$，那么在任意一行都不相等的概率就是$(1-s^r)^b$，那么他们最终成为候选对的概率就是$(1-(1-s^r)^b)$。也就是说两个签名最终会被放在一起作为进行比较的概率$P=1-(1-s^r)^b$。

也就是说，对于给定的$s\ r\ b$，伪反例的比例就是$1-P$。假设$s=0.8,b=20,r=5$，这时伪反例的比例就是0.000356，还是相当低的，而且随着b的增大，这个值还会变得更小。

接下来我们就分析以下如何根据我们需要的$s$来确定参数$r,b$。不管$r,b$的取值是什么，$P$关于$s$的函数图像基本是这样的：

注意到$s$的取值在0到1之间，这个函数图像和sigmoid还是有点像的，虽然突变的部分不是很明显，但是还是两端的差距还是很明显的。通过调节这个函数的参数，我们就可以控制只把相似度大于一定阈值$s_{thresh}$的签名以很高的概率纳为候选对，而相似度低的签名以很低的概率不纳为候选对。通常情况下我们会通过调节$r,b$，使这个阈值$s_{thresh}$对应到概率为0.5的地方，这个时候就有$s_{thresh}=(1-2^{-\frac 1b})^{\frac 1r}$。不过有时候为了方便，也为了更准确，这个$s_{thresh}$会设置为$(\frac 1b)^{\frac 1r}$。当$s=(\frac 1b)^{\frac 1r}$时，我们可以算出来，概率$Q=1-(1-\frac 1b)^b$。显然$\underset{b\to \infty}{Q}\to 1-\frac1e\approx 0.632$。也就是说这个值会比0.5稍大，不过实际上效果可能更好。