标签: levenshtein-distance

我正在用 php 编写一个工具来比较 HTML 文件并显示差异。现在我正在寻找一种有效的方法来计算两个 HTML 文件之间的百分比差异。这些文件可以是任意长的（我拥有的文件可以长达 300000 个字符）。

经过一番研究，我偶然发现了 Levensthein 距离，它是一种 O(n*m) 算法，需要空间 O(n*m)：php 版本最多只能支持 255 个字符，而我自己实现的 O(n) 空间，太慢了。之后，我尝试了php函数similar_text，但是该算法对于非常大的HTML文件来说也太慢了。

所以现在我正在寻找另一种更有效的算法来比较 HTML 文件。近似算法也很好。有人可以给我一些关于如何做到这一点的建议吗？

我正在寻找一种方法来计算任意两个提交内容之间的良好编辑距离。

我发现的最好的方法是从输出中得出一些东西

git diff <commit-ish> <commit-ish> --numstat

...但是我使用这种方法所能想到的任何东西都将是编辑距离的一个非常粗略的代理。

有更好的吗？

作为我自己对基因型网络研究的一部分，我有一段代码，我试图在其中从字符串列表构建一个单差网络。程序是这样的：

1. 迭代字符串的所有成对组合。
2. 如果字符串相差一个位置，则在网络中在它们之间绘制一条边。
3. 如果它们没有单一位置的不同，则通过。

我现在拥有的代码块是这样的：

from itertools import combinations
import Levenshtein as lev # a package that wraps a C-implemented levenshtein distance
import networkx as nx
strings = [...list of strings...]

G = nx.Graph()

for (s1, s2) in combinations(strings, 2):
    if s1 not in G.nodes():
        G.add_node(s1)
    if s2 not in G.nodes():
        G.add_node(s2)

    if lev.distance(s1, s2) == 1:
        G.add_edge(s1, s2)

显然没有办法提高图构建过程的计算复杂度——它总是O(n**2). 至少，以我有限的知识，这就是我的想法——也许我错了？

也就是说，考虑到我需要进行的比较数量的正常规模（约 2000-5000），如果我能获得几个数量级的加速，总体而言，那么实际计算时间仍然是可以接受的- 使用当前的 Python 实现，构建图形需要大约几天的时间。使用正确的导入（下面未说明），我尝试了下面的 Cython 实现，但无法弄清楚如何使其更快：

cpdef cython_genotype_network(sequences):

    G = nx.Graph()
    cdef:
        unicode s1
        unicode s2 …

我正在尝试安装 Levenshtein 模块，如您在此处看到的。

我能够setup.py通过 运行该文件python setup.py build。

python然后，当我通过从终端立即进入 python 时，在与文件夹相同的文件夹中Levenshtein，我尝试导入它：

import Levenshtein,

但我收到以下错误：

    >>> import Levenshtein
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "Levenshtein/__init__.py", line 1, in <module>
    from Levenshtein import _levenshtein
ImportError: cannot import name _levenshtein

并且，当我查看文件夹时Levenshtein，我看到两个与该名称相似的文件：

 _levenshtein.c   _levenshtein.h

这个导入有什么意义，我应该如何获取名称为 的文件_levenshtein？

根据对另一个问题的回答，在 sqlite 中，Levenshtein 距离是在名为editdist3. （也比较文档）

现在，当我尝试使用它时，我得到的只是它不存在的错误：

???> sqlite3
SQLite version 3.11.1 2016-03-03 16:17:53
Enter ".help" for usage hints.
Connected to a transient in-memory database.
Use ".open FILENAME" to reopen on a persistent database.
sqlite> CREATE TABLE test (col1 TEXT);
sqlite> INSERT INTO test VALUES ('foobar');
sqlite> SELECT * FROM test WHERE editdist3(col1, 'f00bar') < 3;
Error: no such function: editdist3

我在 Gentoo Linux 上使用 sqlite-3.11.1（默认） USE 标志icu，readline和secure-delete …

我在 Tensorflow 中编写了一些代码来计算一个字符串和一组字符串之间的编辑距离。我无法找出错误。

import tensorflow as tf
sess = tf.Session()

# Create input data
test_string = ['foo']
ref_strings = ['food', 'bar']

def create_sparse_vec(word_list):
    num_words = len(word_list)
    indices = [[xi, 0, yi] for xi,x in enumerate(word_list) for yi,y in enumerate(x)]
    chars = list(''.join(word_list))
    return(tf.SparseTensor(indices, chars, [num_words,1,1]))


test_string_sparse = create_sparse_vec(test_string*len(ref_strings))
ref_string_sparse = create_sparse_vec(ref_strings)

sess.run(tf.edit_distance(test_string_sparse, ref_string_sparse, normalize=True))

该代码有效，运行时会产生输出：

array([[ 0.25],
       [ 1.  ]], dtype=float32)

但是，当我尝试通过稀疏占位符输入稀疏张量来执行此操作时，出现错误。

array([[ 0.25],
       [ 1.  ]], dtype=float32)

这是错误回溯：

Traceback (most recent call last):

  File "<ipython-input-29-4e06de0b7af3>", line 1, in <module> …

我想检查一个关键字字符串是否包含在一个文本字符串中。这一定是一个模糊的包含。

我的第一次尝试是使用库blurwuzzy。当使用部分比率时字符串差异很大时，这似乎具有产生高匹配值的意外行为。

我试过使用 levenshtein 的距离，它可以将一个字符串与另一个字符串进行比较，但不能用于查找字符串是否包含关键字。
我尝试过的一个想法是将文本拆分为单个单词，然后遍历它们，计算距离以查看是否匹配。问题是关键字中可能有空格，这意味着它不会使用此方法找到任何匹配项。

我现在已经尝试使用 Bitap 算法来查找关键字是否在文本中，但是当关键字和文本非常不同时，这又是正确的。该算法可以在这里找到。

final String keyword = "br0wn foxes very nice and hfhjdfgdfgdfgfvffdbdffgjfjfhjgjfdghfghghfg".toLowerCase();
final String text = "The Quick Brown Fox Jumps Over the Lazy Dog".toLowerCase();

final Bitap bitap = new Bitap(keyword, alphabet);   
bitap.within(text, 20);    // Returns true

我已经研究过使用 Lucene。这样做的问题是，很多都是基于从所有数据创建索引然后执行搜索。在我的情况下，这是无法完成的，因为它需要是一种分别采用关键字和文本的方法。如果有任何资源可以在不使用 Lucene 索引的情况下执行模糊包含，这将非常有用。

最好的方法是什么？

Fuzzywuzzy是一个非常流行的字符串匹配库。根据库的文档，提到它使用 Levenshtein 距离来计算序列之间的差异。但是仔细检查后，我发现它实际上使用SequenceMatcher了difflib库中的函数。根据文档，此函数使用 Ratcliff/Obershelp 模式匹配算法。

根据定义，Levenshtein 距离是将一个字符串转换为另一个字符串所需的最小编辑次数，Ratcliff/Obershelp 模式匹配算法计算匹配字符的两倍数除以两个字符串中的字符总数。比较两者的密切相关帖子。

当我运行一个例子时，我得到了 Fuzzywuzzy 中 SequenceMatcher 和 ratio 函数的相同结果。

from difflib import SequenceMatcher
from fuzzywuzzy import fuzz
s = SequenceMatcher(None, "abcd", "bcde")
s.ratio()
# 0.75
fuzz.ratio("abcd", "bcde")
# 75

如果我手动计算两个字符串之间的 Levenshtein 距离，我想它只会是 2。在这种情况下，它如何像贡献者在文档中所写的那样使用 Levenshtein 距离？

当我使用fuzzystrmatch levenshtein函数与变音符号一起使用时，它返回错误/多字节无知的结果：

select levenshtein(\'a\xcc\xa8\', \'x\');\nlevenshtein \n-------------\n       2\n

（注意：第一个字符是一个“a”，下面有一个变音符号，我复制到这里后它没有正确呈现）

fuzzystrmatch文档（https://www.postgresql.org/docs/9.1/fuzzystrmatch.html）警告：

\n

目前，soundex、metaphone、dmetaphone 和 dmetaphone_alt 函数不能很好地处理多字节编码（例如 UTF-8）。

\n

但由于它没有命名levenshtein函数，我想知道是否有 levenshtein的多字节感知版本的多字节感知版本。

我知道我可以使用非重音函数作为解决方法，但我需要保留变音符号。

我需要检查 python 中两个字符串之间的字符串距离（测量最小更改数量 - 字符删除、添加和转置）是否大于 1。

我可以自己实现它，但我打赌现有的软件包可以让我免于自己实现它。我无法找到任何我可以识别为常用的此类包。有吗？