逆序对
在计算机科学和离散数学中，一个序列的逆序（inversion）对，是失去自然次序的元素对。 定義 逆序 設\ \pi \ 為一個排列，如果\ i 而且 \ \pi(i) > \pi(j) \ ， 這個位置（有称为“序位”）对 \ (i, j) \ ，或者這个元素对 \ \bigl(\pi(i), \pi(j)\bigr) \ ，被稱為是 \ \pi \ 的一個逆序。 逆序集是所有逆序的集合。一個排列 \ \pi \ 的使用基于位置表示法…
标签：#字符串相似性度量
共 8 篇文章
李距离
李距离（Lee distance）是编码理论裡的一種距离函數。两个使用包含 q 個字母的字母表 {0, 1, …, q − 1}（q ≥ 2）且长度为 n 的字符串x_1 x_2 \dotsb x_n和y_1 y_2 \dotsb y_n之间的李氏距离被定义为 : \sum_{i=1}^n min(|x_i-y_i|,q-|x_i-y_i|) 当q=2或者q=3，李距离等价于汉明距离。 由李距离所长产生的度量空间是一个类似于离散的椭圆几…
萊文斯坦距離
莱文斯坦距离（）是编辑距离的一种。指两个字串之間，由一个转成另一个所需的最少编辑操作次数。 允许的编辑操作包括： 将一个字符替换成另一个字符 插入一个字符 刪除一个字符 俄羅斯科學家弗拉基米尔·莱文斯坦在1965年提出這個概念。 定义 如果分别用 |a| 和 |b| 表示 a, b 两个字符串的长度，那么它们的列文斯坦距离为 \operatorname{lev}_{a,b}(|a|,|b|)，它符合： :\qquad\operatorn…
雅卡尔指数
雅卡尔指数（），又称为交并比（）、雅卡尔相似系数（），是用于比较样本集的相似性与多样性的统计量。雅卡尔系数能够量度有限样本集合的相似度，其定义为两个集合交集大小与并集大小之间的比例： : J(A,B) = {\over} = {\over}. 如果A与B完全重合，则定义J(A,B) = 1。于是有 : 0\le J(A,B)\le 1. 雅卡尔距离（）则用于量度样本集之间的不相似度，其定义为1减去雅卡尔系数，即 : d_J(A,B) =…
简单匹配系数
简单匹配系数（，缩写），又称为兰德相似系数（），是用于比较样本信合之间相似性与多样性的统计量。 假设两个对象A与B分别有n个二值属性，则SMC的定义为： : \begin{align} \text{SMC} & = \frac{\text{匹 配 属 性 数 量}}{\text{属 性 总 数}} \\[8pt] & = \frac{M_{00}+M_{11}}{M_{00}+M_{01}+M_{10}+M_{11}} \end{ali…
汉明距离
在信息论中，两个等长字符串之间的汉明距离（）是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。 汉明重量是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个数：对于二进制字符串来说，就是1的个数，所以11101的汉明重量是4。 範例 例如： 1011101与1001001之间的汉明距离是2。 2143896与2233796之间的汉明距离是3。 "tone…
編輯距離
編輯距離是針對二個字符串（例如英文字）的差異程度的量化量測，量測方式是看至少需要多少次的處理才能將一個字符串變成另一個字符串。編輯距離可以用在自然语言处理中，例如拼寫檢查可以根據一個拼錯的字和其他正確的字的編輯距離，判斷哪一個（或哪幾個）是比較可能的字。DNA也可以視為用A、C、G和T組成的字符串，因此編輯距離也用在生物信息学中，判斷二個DNA的類似程度。Unix 下的 diff 及 patch 即是利用编辑距离来进行文本编辑对比的例子…
Dice系数
戴斯系数（Dice coefficient），也称索倫森-戴斯系数（Sørensen–Dice coefficient），取名於和，是一种集合相似度度量函数，通常用于计算两个样本的相似度： :s = \frac{2 | X \cap Y |} 它在形式上和Jaccard指数没多大区别，但是有些不同的性质。 和Jaccard类似，它的范围为0到1。 与Jaccard不同的是，相应的差异函数 :d = 1 - \frac{2 | X \ca…