如何在Python中获得字符串与另一个字符串类似的概率？
我想获得像0.9(意味着90%)等十进制值.最好使用标准的Python和库.
例如
similar("Apple","Appel") #would have a high prob.
similar("Apple","Mango") #would have a lower prob.
我想使用Locality敏感哈希来大致匹配字符串.我有很多字符串> 10M可能包含错别字.对于每个String,我想与所有其他字符串进行比较,并根据某个阈值选择具有编辑距离的字符串.
也就是说,天真的解决方案需要O(n ^ 2)个比较.为了避免这个问题,我正在考虑使用Locality Sensitive Hashing.然后接近相似的字符串会产生相同的桶,我只需要在桶搜索中进行.所以它是O(n*C),其中C是桶大小.
但是,我不明白如何表示字符串.如果是文本,我将在向量空间中表示.我的主要问题是,如果使用LSH这是易处理的,然后是字符串的适当矢量表示.
我可以使用已经实现的库来执行此任务吗？或者这取决于我的问题,所以我必须自己实施？是否有任何python包执行此操作？
以下代码用作最小示例。它在文本中搜索一个不匹配的正则表达式（后来是一个大的 DNA 文件）。
awk 'BEGIN{print match("CTGGGTCATTAAATCGTTAGC...", /.ATC|A.TC|AA.C|AAT./)}'
后来我对找到正则表达式的位置感兴趣。因此 awk 命令更复杂。就像这里解决了一样
如果我想搜索更多的不匹配和更长的字符串，我会想出很长的正则表达式：
example: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" with 3 mismatches "." allowed:
/
...AAAAAAAAAAAAAAAAAAAAAAAAAAA|
..A.AAAAAAAAAAAAAAAAAAAAAAAAAA|
..AA.AAAAAAAAAAAAAAAAAAAAAAAAA|
-
- and so on. (actually 4060 possibilities)
/
我的解决方案的问题是：
我的问题是：
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 距离？
我有以下两个字符串：
a = 'bjork gudmundsdottir'
b = 'b. gudmundsson gunnar'
两者之间的 Levenshtein 距离是12。当我使用以下公式计算 Levenshtein 距离时，我得到了0.01与python-Levenshtein库的差异：
>>> Ldist / max(len( a ), len( b ))
>>> float(12)/21
0.5714285714285714
# python-Levenshtein
Levenshtein.ratio(a,b)
0.5853658536585366
# difflib
>>> seq=difflib.SequenceMatcher(a=a,b=b)
>>> seq.ratio()
0.5853658536585366
造成这种差异的原因是什么？我在计算中做错了什么。请注意，我已经回顾了这个How python-Levenshtein.ratio 计算类似的问题，它并没有完全回答我的问题。
有人可以解释一下用于计算上述比率的公式吗？