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

Question

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

用例示例：

import sqlite3
conn = 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”事实）使它对我的用例不切实际。

Answer 1

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

import sqlite3
db = sqlite3.connect(':memory:')
db.enable_load_extension(True)
db.load_extension('./spellfix')                 # for Linux
#db.load_extension('./spellfix.dll')            # <-- UNCOMMENT HERE FOR WINDOWS
db.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上首先要执行的操作：

1. 下载https://sqlite.org/2016/sqlite-src-3110100.zip，https://sqlite.org/2016/sqlite-amalgamation-3110100.zip和解压他们

2. 从此处替换C:\Python27\DLLs\sqlite3.dll为新的sqlite3.dll。如果跳过此步骤，您将在以后得到sqlite3.OperationalError: The specified procedure could not be found

3. 跑：

   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" x64
cl /I sqlite-amalgamation-3110100/ sqlite-src-3110100/ext/misc/spellfix.c /link /DLL /OUT:spellfix.dll
python test.py

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

这是在Linux Debian上的方法：

apt-get -y install unzip build-essential libsqlite3-dev
wget https://sqlite.org/2016/sqlite-src-3110100.zip
unzip sqlite-src-3110100.zip
gcc -shared -fPIC -Wall -Isqlite-src-3110100 sqlite-src-3110100/ext/misc/spellfix.c -o spellfix.so
python test.py

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

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

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