与Python + Sqlite的字符串相似度（Levenshtein距离/编辑距离）

25-02-02 27

这篇文章主要围绕与Python+Sqlite的字符串相似度和Levenshtein距离/编辑距离展开，旨在为您提供一份详细的参考资料。我们将全面介绍与Python+Sqlite的字符串相似度的优缺点，

这篇文章主要围绕与Python + Sqlite的字符串相似度和Levenshtein距离/编辑距离展开，旨在为您提供一份详细的参考资料。我们将全面介绍与Python + Sqlite的字符串相似度的优缺点，解答Levenshtein距离/编辑距离的相关问题，同时也会为您带来c – 如何确定普通话的Levenshtein距离？、C#通过编辑距离算法实现字符串相似度比较、Damerau-Levenshtein距离实现、Java 比较两个字符串的相似度算法（Levenshtein Distance）的实用方法。

本文目录一览：

与Python + Sqlite的字符串相似度（Levenshtein距离/编辑距离）
c – 如何确定普通话的Levenshtein距离？
C#通过编辑距离算法实现字符串相似度比较
Damerau-Levenshtein距离实现
Java 比较两个字符串的相似度算法（Levenshtein Distance）

与Python + Sqlite的字符串相似度（Levenshtein距离/编辑距离）

在Python + Sqlite中是否有可用的字符串相似性度量，例如与sqlite3模块有关？

用例示例：

import sqlite3conn = sqlite3.connect('':memory:'')c = conn.cursor()c.execute(''CREATE TABLE mytable (id integer, description text)'')c.execute(''INSERT INTO mytable VALUES (1, "hello world, guys")'')c.execute(''INSERT INTO mytable VALUES (2, "hello there everybody")'')

此查询应匹配ID为1的行，但不匹配ID为2的行：

c.execute(''SELECT * FROM mytable WHERE dist(description, "He lo wrold gyus") < 6'')

如何在Sqlite + Python中做到这一点？

关于我到目前为止发现的注释：

该Levenshtein距离，即单字符编辑（插入，删除或替换）的最小数量需要改变一个字到另一个，可能是有用的，但我不知道是否SQLite中存在的正式实施（我看到一些自定义的实现，如这一个）
所述Damerau-的Levenshtein是相同的，除了它也允许两个相邻字符之间换位; 也称为编辑距离
我知道可以自己定义一个函数，但是实现这样的距离将是不容易的（对数据库进行超高效的自然语言处理比较确实是不容易的），这就是为什么我想查看Python / Sqlite是否已经具有这样的功能一个工具
Sqlite具有FTS（全文搜索）功能：FTS3，FTS4，FTS5
```
CREATE VIRTUAL TABLE enrondata1 USING fts3(content TEXT);     /* FTS3 table */
```
CREATE TABLE enrondata2(content TEXT); / Ordinary table /
SELECT count() FROM enrondata1 WHERE content MATCH ‘linux’; / 0.03 seconds /
SELECT count() FROM enrondata2 WHERE content LIKE ‘%linux%’; / 22.5 seconds /

但是我找不到具有这样的“相似距离”的字符串比较，FTS的功能，MATCH或者NEAR似乎没有字母变化的相似性度量等。

此外，此答案表明：

SQLite的FTS引擎基于令牌-搜索引擎尝试匹配的关键字。
可以使用多种令牌生成器，但是它们相对简单。“简单”令牌生成器仅将每个单词拆分并小写：例如，在字符串“快速的棕色狐狸跳过懒狗”中，单词“
jumps”将匹配，但不匹配“ jump”。“ porter”令牌生成器要先进一些，它去除了单词的共轭，因此“ jumps”和“
jumping”将匹配， 但是像“ jmups”这样的错字将不 匹配。

遗憾的是，后者（无法找到与“跳转”相似的“ jmups”事实）使它对我的用例不切实际。

答案1

小编典典

这是一个现成的示例test.py：

import sqlite3db = sqlite3.connect('':memory:'')db.enable_load_extension(True)db.load_extension(''./spellfix'')                 # for Linux#db.load_extension(''./spellfix.dll'')            # <-- UNCOMMENT HERE FOR WINDOWSdb.enable_load_extension(False)c = db.cursor()c.execute(''CREATE TABLE mytable (id integer, description text)'')c.execute(''INSERT INTO mytable VALUES (1, "hello world, guys")'')c.execute(''INSERT INTO mytable VALUES (2, "hello there everybody")'')c.execute(''SELECT * FROM mytable WHERE editdist3(description, "hel o wrold guy") < 600'')print c.fetchall()# Output: [(1, u''hello world, guys'')]

重要说明：距离editdist3已标准化，因此

值100用于插入和删除，值150用于替换

这是在Windows上首先要执行的操作：

下载https://sqlite.org/2016/sqlite-src-3110100.zip，https://sqlite.org/2016/sqlite-amalgamation-3110100.zip和解压他们
从此处替换C:\Python27\DLLs\sqlite3.dll为新的sqlite3.dll。如果跳过此步骤，您将在以后得到sqlite3.OperationalError: The specified procedure could not be found

跑：

call "C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\vcvarsall.bat"

要么

    call "C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\vcvarsall.bat" x64cl /I sqlite-amalgamation-3110100/ sqlite-src-3110100/ext/misc/spellfix.c /link /DLL /OUT:spellfix.dllpython test.py

（使用MinGW，这将是：gcc -g -shared spellfix.c -I ~/sqlite-amalgation-3230100/ -ospellfix.dll）

这是在Linux Debian上的方法：

apt-get -y install unzip build-essential libsqlite3-devwget https://sqlite.org/2016/sqlite-src-3110100.zipunzip sqlite-src-3110100.zipgcc -shared -fPIC -Wall -Isqlite-src-3110100 sqlite-src-3110100/ext/misc/spellfix.c -o spellfix.sopython test.py

以下是在具有旧Python版本的Linux Debian上执行此操作的方法：

如果您的发行版的Python有点旧，它将需要另一种方法。由于sqlite3模块是内置在Python中的，因此对其进行升级似乎并不容易（pipinstall --upgradepysqlite仅升级pysqlite模块，而不升级底层SQLite库）。因此，此方法例如在ifimportsqlite3; print sqlite3.sqlite_version为3.8.2的情况下有效：

wget https://www.sqlite.org/src/tarball/27392118/SQLite-27392118.tar.gztar xvfz SQLite-27392118.tar.gzcd SQLite-27392118 ; sh configure ; make sqlite3.c ; cd ..gcc -g -fPIC -shared SQLite-27392118/ext/misc/spellfix.c -I SQLite-27392118/src/ -o spellfix.sopython test.py   # [(1, u''hello world, guys'')]

c – 如何确定普通话的Levenshtein距离？

我们正在开发一个使用UTF-8,UTF-16和UTF-32 Unicode字符标准对超过50种国际语言进行模糊匹配的系统.到目前为止,我们已经能够使用Levenshtein距离来检测德语Unicode扩展字符词的拼写错误.

我们想扩展这个系统来处理以Unicode表示的普通话中文表意文字.我们如何在类似汉字之间执行Levenshtein距离计算？

解决方法

首先,只是为了澄清：汉字不像德文或英文一样.大多数你认为是文字的东西(使用“单词”的语义或句法定义)由1-3个字符组成.通过将Levenshtein距离表示为UCS-2或UCS-4码点的序列,可以直接应用Levenshtein距离.由于大多数单词很短(特别是长度为1或2个字符的单词),可能是有限的使用.

但是,由于您的问题具体涉及个人角色之间的编辑距离,我认为需要采用不同的方法,确实可能非常困难.

首先,您必须将每个字符表示为组成的组件/笔画的顺序.有两个问题：

>某些组件由更小的组件组成,所以如何将角色分解为“原子”组件并不是唯一定义的.如果你做到单个笔画的水平,你需要描述每一个笔画(角色,形状,方向等等).我不认为任何人都这样做(如果有人告诉我,我会最感兴趣的).
>您需要将笔画或组件放在一个顺序中.明显的候选人是字典的规范笔画顺序,在词典中有描述,甚至有字典网站都有动画笔画顺序图.然而,我知道的数据源(对于日语),生成这些动画作为位图图形的序列;我从来没有看到适用于编辑距离计算的表单中的人物或机器可读代码来代表笔画序列(甚至单个笔画的名称).

可以尝试一个最后一件事是渲染字符字形,并根据需要改变多少个像素(或向量)将一个字符转换为另一个字符来计算编辑距离.我曾经在OCR修正后的背景下做了拉丁字符和字符组合(以像素为单位),结果相当令人鼓舞.

对larsmans的一个快速回答如下：Unicode标准定义了两个相关概念(下面我参考6.0 version,chapter 12)：

>基于激进和中风计数的指标.每个汉字由几个组成部分组成,其中一个是激进的.激进/笔触计数索引是由根基(即,共享相同基团组合在一起的所有字符)排序的字符列表,并且每个激进特定组在内部根据字符的其余部分中使用的笔画数进行排序.不幸的是,即使这并不是唯一的定义 – 有不同传统词汇定义不同的字符,笔画计数也很难.以下是Unicode标准的内容：

To expedite locating specific Han ideographic characters in the code charts,radical-stroke indices are provided on the Unicode web site. […]
The most influential authority for radical-stroke information is the eighteenth-century
KangXi dictionary,which contains 214 radicals. The main problem in using KangXi radicals today is that many simplified characters are difficult to classify under any of the 214
KangXi radicals. As a result,varIoUs modern radical sets have been introduced. None,however,is in general use,and the 214 KangXi radicals remain the best kNown. […]
The Unicode radical-stroke charts are based on the KangXi radicals. The Unicode Standard
follows a number of different sources for radical-stroke classification. Where two sources
are at odds as to radical or stroke count for a given character,the character is shown in both positions in the radical-stroke charts.

注意,即使我们假设激进/中风指数是明确和正确的,它不足以将字符转换成一个组件序列的信息源,因为完全描述的字符的唯一组件是激进.
>表意描述序列(第12.2节)：Unicode定义了字符的基本组件的代码点(大多数可以自己被用作独立字符),并且有一些代码点用于将它们粘合在一起以形成描述的组件序列组成更复杂的人物.所以这样做的方式类似于组合字符,但有重要的区别：

>组件的顺序不是唯一定义的
>这种序列的渲染机制没有定义
>没有从普通字符到对应的表意描述序列的映射(虽然标准提到这种映射在某种程度上存在于用于编译汉字符集的源中).

标准表明,表意描述序列用于描述没有由任何现有代码点表示的复杂或罕见的特征;但是它明确地阻止使用描述序列代替普通字符：

In particular,Ideographic Description Sequences should not be used to provide alternative graphic representations of encoded ideographs in data interchange. Searching,collation,and other content-based text operations would then fail.

C#通过编辑距离算法实现字符串相似度比较

下面是小编 jb51.cc 通过网络收集整理的代码片段。

小编小编现在分享给大家，也给大家做个参考。

C#通过编辑距离算法实现字符串相似度比较
编辑距离：通过插入、删除、替换一个字符(和交换相邻字符)的操作，使得字符串A和字符串B相同，而最少的操作次数就是编辑距离。
如字符串abcd和aca的距离是2

public class Levenshteindistance
    {
 
        private static Levenshteindistance _instance=null;
        public static Levenshteindistance Instance
        {
            get
            {
                if (_instance == null)
                {
                    return new Levenshteindistance();
                }
                return _instance;
            }
        }
     
 
        /// <summary>
        /// 取最小的一位数
        /// </summary>
        /// <param name="first"></param>
        /// <param name="second"></param>
        /// <param name="third"></param>
        /// <returns></returns>
        public int LowerOfThree(int first,int second,int third)
        {
            int min = first;
            if (second < min)
                min = second;
            if (third < min)
                min = third;
            return min;
        }
 
        public int Levenshtein_distance(string str1,string str2)
        {
            int[,] Matrix;
            int n=str1.Length;
            int m=str2.Length;
 
            int temp = 0;
            char ch1;
            char ch2;
            int i = 0;
            int j = 0;
            if (n ==0)
            {
                return m;
            }
            if (m == 0)
            {
 
                return n;
            }
            Matrix=new int[n+1,m+1];
 
            for (i = 0; i <= n; i++)
            {
                //初始化第一列
                Matrix[i,0] = i;
            }
 
            for (j = 0; j <= m; j++)
            {
                //初始化第一行
                Matrix[0,j] = j;
            }
 
            for (i = 1; i <= n; i++)
            {
                ch1 = str1[i-1];
                for (j = 1; j <= m; j++)
                {
                    ch2 = str2[j-1];
                    if (ch1.Equals(ch2))
                    {
                        temp = 0;
                    }
                    else
                    {
                        temp = 1;
                    }
                    Matrix[i,j] = LowerOfThree(Matrix[i - 1,j] + 1,Matrix[i,j - 1] + 1,Matrix[i - 1,j - 1] + temp);
 
 
                }
            }
 
            for (i = 0; i <= n; i++)
            {
                for (j = 0; j <= m; j++)
                {
                    Console.Write(" {0} ",j]);
                }
                Console.WriteLine("");
            }
            return Matrix[n,m];
 
        }
 
        /// <summary>
        /// 计算字符串相似度
        /// </summary>
        /// <param name="str1"></param>
        /// <param name="str2"></param>
        /// <returns></returns>
        public decimal LevenshteindistancePercent(string str1,string str2)
        {
            int maxLenth = str1.Length > str2.Length ? str1.Length : str2.Length;
            int val = Levenshtein_distance(str1,str2);
            return 1 - (decimal)val / maxLenth;
        }
    }
 
    class Program
    {
 
 
        static void Main(string[] args)
        {
            string str1 = "你好蒂蒂";
            string str2="你好蒂芬";
            Console.WriteLine("字符串1 {0}",str1);
 
            Console.WriteLine("字符串2 {0}",str2);
 
            Console.WriteLine("相似度 {0} %",Levenshteindistance.Instance.LevenshteindistancePercent(str1,str2)*100);
            Console.ReadLine();
        }
    }

以上是小编(jb51.cc)为你收集整理的全部代码内容，希望文章能够帮你解决所遇到的程序开发问题。

如果觉得小编网站内容还不错，欢迎将小编网站推荐给程序员好友。

Damerau-Levenshtein距离实现

我正在尝试在JS中创建damerau-levenshtein距离函数。

我在WIkipedia上找到了关于该算法的描述，但是他们没有实现它。它说：

要设计适当的算法来计算不受限制的Damerau–Levenshtein距离，请注意，始终存在最佳的编辑操作序列，在此之后，一旦转置的字母就永远不会被修改。因此，我们只需要考虑两种以上修改子串的对称方式：（1）转置字母并在它们之间插入任意数量的字符，或者（2）删除一系列字符并转置在删除后变为相邻的字母。这个想法的直接实现给出了三次复杂度的算法：O
\ left（M \ cdot N \ cdot \ max（M，N）\
right），其中M和N是字符串长度。利用Lowrance和Wagner的思想，[7]在最坏的情况下，可以将这种幼稚算法改进为O \ left（M \
cdot N \ right）。有趣的是，可以修改bitap算法以处理换位。有关此类修改的示例，请参见[1]的信息检索部分。
https://zh.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance

[1]部分指向http://acl.ldc.upenn.edu/P/P00/P00-1037.pdf，这对我来说更加复杂。

如果我正确理解了这一点，那么创建一个实现就不那么容易了。

这是我当前使用的levenshtein实现：

levenshtein=function (s1, s2) {  //       discuss at: http://phpjs.org/functions/levenshtein/  //      original by: Carlos R. L. Rodrigues (http://www.jsfromhell.com)  //      bugfixed by: Onno Marsman  //       revised by: Andrea Giammarchi (http://webreflection.blogspot.com)  // reimplemented by: Brett Zamir (http://brett-zamir.me)  // reimplemented by: Alexander M Beedie  //        example 1: levenshtein(''Kevin van Zonneveld'', ''Kevin van Sommeveld'');  //        returns 1: 3  if (s1 == s2) {    return 0;  }  var s1_len = s1.length;  var s2_len = s2.length;  if (s1_len === 0) {    return s2_len;  }  if (s2_len === 0) {    return s1_len;  }  // BEGIN STATIC  var split = false;  try {    split = !(''0'')[0];  } catch (e) {    // Earlier IE may not support access by string index    split = true;  }  // END STATIC  if (split) {    s1 = s1.split('''');    s2 = s2.split('''');  }  var v0 = new Array(s1_len + 1);  var v1 = new Array(s1_len + 1);  var s1_idx = 0,    s2_idx = 0,    cost = 0;  for (s1_idx = 0; s1_idx < s1_len + 1; s1_idx++) {    v0[s1_idx] = s1_idx;  }  var char_s1 = '''',    char_s2 = '''';  for (s2_idx = 1; s2_idx <= s2_len; s2_idx++) {    v1[0] = s2_idx;    char_s2 = s2[s2_idx - 1];    for (s1_idx = 0; s1_idx < s1_len; s1_idx++) {      char_s1 = s1[s1_idx];      cost = (char_s1 == char_s2) ? 0 : 1;      var m_min = v0[s1_idx + 1] + 1;      var b = v1[s1_idx] + 1;      var c = v0[s1_idx] + cost;      if (b < m_min) {        m_min = b;      }      if (c < m_min) {        m_min = c;      }      v1[s1_idx + 1] = m_min;    }    var v_tmp = v0;    v0 = v1;    v1 = v_tmp;  }  return v0[s1_len];}

构建这种算法的想法是什么，如果您认为它太复杂了，那么我该怎么做才能使“ l”（L小写）和“ I”（i大写）之间没有区别。

答案1

小编典典

要点@doukremt给出了：https
://gist.github.com/doukremt/9473228

在Javascript中提供以下内容。

您可以在加权对象中更改操作的权重。

var levenshteinWeighted= function(seq1,seq2){    var len1=seq1.length;    var len2=seq2.length;    var i, j;    var dist;    var ic, dc, rc;    var last, old, column;    var weighter={        insert:function(c) { return 1.; },        delete:function(c) { return 0.5; },        replace:function(c, d) { return 0.3; }    };    /* don''t swap the sequences, or this is gonna be painful */    if (len1 == 0 || len2 == 0) {        dist = 0;        while (len1)            dist += weighter.delete(seq1[--len1]);        while (len2)            dist += weighter.insert(seq2[--len2]);        return dist;    }    column = []; // malloc((len2 + 1) * sizeof(double));    //if (!column) return -1;    column[0] = 0;    for (j = 1; j <= len2; ++j)        column[j] = column[j - 1] + weighter.insert(seq2[j - 1]);    for (i = 1; i <= len1; ++i) {        last = column[0]; /* m[i-1][0] */        column[0] += weighter.delete(seq1[i - 1]); /* m[i][0] */        for (j = 1; j <= len2; ++j) {            old = column[j];            if (seq1[i - 1] == seq2[j - 1]) {                column[j] = last; /* m[i-1][j-1] */            } else {                ic = column[j - 1] + weighter.insert(seq2[j - 1]);      /* m[i][j-1] */                dc = column[j] + weighter.delete(seq1[i - 1]);          /* m[i-1][j] */                rc = last + weighter.replace(seq1[i - 1], seq2[j - 1]); /* m[i-1][j-1] */                column[j] = ic < dc ? ic : (dc < rc ? dc : rc);            }            last = old;        }    }    dist = column[len2];    return dist;}

Java 比较两个字符串的相似度算法（Levenshtein Distance）

转载自： https://blog.csdn.net/JavaReact/article/details/82144732

算法简介：

Levenshtein Distance，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。

许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫Levenshtein Distance。

/**
* 比较两个字符串的相识度
* 核心算法：用一个二维数组记录每个字符串是否相同，如果相同记为0，不相同记为1，每行每列相同个数累加
* 则数组最后一个数为不相同的总数，从而判断这两个字符的相识度
*
* @param str
* @param target
* @return
*/
private static int compare(String str, String target) {
int d[][]; // 矩阵
int n = str.length();
int m = target.length();
int i; // 遍历str的
int j; // 遍历target的
char ch1; // str的
char ch2; // target的
int temp; // 记录相同字符,在某个矩阵位置值的增量,不是0就是1
if (n == 0) {
return m;
}
if (m == 0) {
return n;
}
d = new int[n + 1][m + 1];
// 初始化第一列
for (i = 0; i <= n; i++) {
d[i][ 0] = i;
}
// 初始化第一行
for (j = 0; j <= m; j++) {
d[ 0][j] = j;
}
for (i = 1; i <= n; i++) {
// 遍历str
ch1 = str.charAt(i - 1);
// 去匹配target
for (j = 1; j <= m; j++) {
ch2 = target.charAt(j - 1);
if (ch1 == ch2 || ch1 == ch2 + 32 || ch1 + 32 == ch2) {
temp = 0;
} else {
temp = 1;
}
// 左边+1,上边+1, 左上角+temp取最小
d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + temp);
}
}
return d[n][m];
}
/**
* 获取最小的值
*/
private static int min(int one, int two, int three) {
return (one = one < two ? one : two) < three ? one : three;
}
/**
* 获取两字符串的相似度
*/
public static float getSimilarityRatio(String str, String target) {
int max = Math.max(str.length(), target.length());
return 1 - (float) compare(str, target) / max;
}

public static void main(String[] args) {
String a= "Steel";
String b = "Steel Pipe";
System.out.println( "相似度："+getSimilarityRatio(a,b));
}

算法原理：

该算法的解决是基于动态规划的思想，具体如下：
设 s 的长度为 n，t 的长度为 m。如果 n = 0，则返回 m 并退出；如果 m=0，则返回 n 并退出。否则构建一个数组 d[0..m, 0..n]。
将第0行初始化为 0..n，第0列初始化为0..m。
依次检查 s 的每个字母(i=1..n)。
依次检查 t 的每个字母(j=1..m)。
如果 s[i]=t[j]，则 cost=0；如果 s[i]!=t[j]，则 cost=1。将 d[i,j] 设置为以下三个值中的最小值：
紧邻当前格上方的格的值加一，即 d[i-1,j]+1
紧邻当前格左方的格的值加一，即 d[i,j-1]+1
当前格左上方的格的值加cost，即 d[i-1,j-1]+cost
重复3-6步直到循环结束。d[n,m]即为莱茵斯坦距离。

参考链接：

http://wdhdmx.iteye.com/blog/1343856

https://www.cnblogs.com/ymind/archive/2012/03/27/fast-memory-efficient-Levenshtein-algorithm.html

https://blog.csdn.net/u013035314/article/details/50340443

今天关于与Python + Sqlite的字符串相似度和Levenshtein距离/编辑距离的分享就到这里，希望大家有所收获，若想了解更多关于c – 如何确定普通话的Levenshtein距离？、C#通过编辑距离算法实现字符串相似度比较、Damerau-Levenshtein距离实现、Java 比较两个字符串的相似度算法（Levenshtein Distance）等相关知识，可以在本站进行查询。

本文标签：