地狱,
PHP有许多字符串函数,如levenshtein,similar_text和soundex,可以比较字符串的相似性. http://www.php.net/manual/en/function.levenshtein.php
哪种准确度和性能最佳？
首先,我想说我是python中的新手.我试图计算许多单词列表的Levenshtein距离.直到现在我成功编写了一对单词的代码,但是我在列表中遇到了一些问题.我只是有两个列表,其中一个在另一个之下,就像这样:carlos stiv peter
我想使用Levenshtein距离进行相似性处理.somebady可以告诉我如何加载列表然后使用函数计算距离？
我会感激的!
这是我的代码只有两个字符串:
#!/usr/bin/env python
# -*- coding=utf-8 -*-
def lev_dist(source, target):
if source == target:
return 0
#words = open(test_file.txt,'r').read().split();
# Prepare matrix
slen, tlen = len(source), len(target)
dist = [[0 for i in range(tlen+1)] for x in range(slen+1)]
for i in xrange(slen+1):
dist[i][0] = i
for j in xrange(tlen+1):
dist[0][j] = j
# Counting distance
for i in xrange(slen):
for j in xrange(tlen):
cost = 0 if source[i] == target[j] else 1
dist[i+1][j+1] = min( …是否有一种通用的方法来转换相似度量和距离度量？
考虑一个相似性度量,例如两个字符串共有的2克数.
2-grams('beta', 'delta') = 1
2-grams('apple', 'dappled') = 4
如果我需要将其提供给期望测量差异的优化算法,例如Levenshtein距离,该怎么办？
这只是一个例子......我正在寻找一个通用的解决方案,如果存在的话.比如如何从Levenshtein距离到相似度量？
我感谢您提供的任何指导.
我正在使用C++编写一个拼写检查程序,并且我已经陷入了实现中的某个步骤.
假设我们有一个包含正确拼写单词的文本文件和一个我们想要检查拼写错误的输入字符串.如果该字符串是拼写错误的单词,我可以通过检查文本文件中的所有单词并选择与其不同的单词和最少的字母来轻松找到其正确的表单.对于那种类型的输入,我实现了一个函数来计算2个字符串之间的Levenshtein编辑距离.到现在为止还挺好.
现在,困难的部分:如果输入的字符串是拼写错误的单词的组合怎么办？例如,"iloevcokies".考虑到"i","love"和"cookies"是可以在文本文件中找到的单词,我如何使用已经实现的Levenshtein函数来确定文件中哪些单词适合进行校正？另外,我如何在正确的位置插入空格？
欢迎任何想法:)
我最近在我们的搜索引擎数据库中实现了levenshtein算法,但是我们遇到了一个问题.
根据基本的levenshtein
Levenshtein('123456','12x456')与Levenshtein('123456','12345x')的值相同
通常这很好,但对于我的具体问题是不正确的.当有人使用我们的网站时,这是不正确的.电子元件制造商通常制造类似的产品,最后一个字母只有不同之处.如果第一个字母不同,它通常是完全不同的类别.因此,我需要一种算法,该算法认为在单词开头附近的匹配比在后面的那些更有价值,或者换句话说,在开头附近发生的不匹配应该比后面的那些应用更大的惩罚.
如果有人有任何想法,请告诉我.
可能重复:
计算将一个排列转换为另一个排列所需的交换
我正在寻找一种计算某种字符串距离的算法,其中只允许操作是两个相邻字符的转置.例如:
string1:"mother"
string2:"moterh"
距离:2(首先交换"h"与"e"并获得"motehr"然后"h"与"r"导致"moterh")
我知道Damerau -Levenshtein距离这个问题非常相似,但它需要大量的内存(我希望它可以在高达1 000 000个字符的单词上工作得非常快).我已经写过:
int amo = 0;
for (int i = 0; i < n; i++)
{
if (fromString[i] == toString[i])
continue;
char toWhat = toString[i];
int where = -1;
for (int j = i; j < n; j++)
{
if (fromString[j] == toWhat)
{
where = j;
break;
}
}
while (where != i)
{
char temp = fromString[where];
fromString[where] = fromString[where - 1];
fromString[where - 1] = temp;
where--;
amo++;
} …string algorithm edit-distance dynamic-programming levenshtein-distance
鉴于此数据(两种语言的相对字母频率):
spanish => 'e' => 13.72, 'a' => 11.72, 'o' => 8.44, 's' => 7.20, 'n' => 6.83,
english => 'e' => 12.60, 't' => 9.37, 'a' => 8.34, 'o' => 7.70, 'n' => 6.80,
然后计算字符串"这是一个测试"的字母频率给了我:
"t"=>21.43, "s"=>14.29, "i"=>7.14, "r"=>7.14, "y"=>7.14, "'"=>7.14, "h"=>7.14, "e"=>7.14, "l"=>7.14
那么,将给定的字符串字母频率与语言匹配(并尝试检测语言)的好方法是什么？我已经看过(并已经测试过)使用levenshtein距离的一些例子,它似乎工作正常,直到你添加更多的语言.
"this is a test" gives (shortest distance:) [:english, 13] ...
"esto es una prueba" gives (shortest distance:) [:spanish, 13] ...
我正在尝试使用 Levenshtein 距离算法（在 Python 中，如果它有任何区别的话）在两个公司名称列表之间进行模糊字符串比较。一个例子是列表 A 包含XYZ INDUSTRIAL SUPPLY但列表 B 可能会说XYZ INDUSTRIAL SUPPLY, INC.但它们仍然应该匹配。
现在，我的实施非常不准确。作为第二个例子，目前算法发现abc metal finishing和xyz's mach & metal finishing非常相似，因为它们的结局，但它们是完全不同的公司。我想提高这种准确性，我认为可以做到这一点的一种方法是以某种方式对字符串的开头进行加权。如果公司名称应该匹配，那么它们的开头很可能相似。看我的第一个例子，整个开头都是匹配的，只是在最后才发生变化。有办法做到这一点吗？我还没能解决。
谢谢！
编辑更多示例：
应匹配：
s west tool supply,southwest tool supply
abc indust inc,abc industries
icg usa,icg usa llc
不应该匹配（但目前匹配）：
ohio state university,iowa state university
m e gill corporation,s g corporation
更新：
已经取得了进展:)如果有人对这类事情感兴趣，我最终尝试了插入、删除和替换的成本。我的想法是加重字符串开头的权重，因此我根据矩阵中的当前位置来确定权重。但这造成的问题是，由于我的权重分配方式，所有内容都与几个非常短的名称相匹配。我通过在计算中包含长度来解决这个问题。例如，我的插入重量最终(1 if index<=2/3*len(target) else .1*(len(source)-index))总是source两根弦中较长的一个。我计划继续调整它并尝试其他值，但它已经显示出很大的改进。这绝不是一门精确的科学，但如果它有效，那才是最重要的！
有谁知道为什么PHP中的函数levenshtein有255个字符的限制？
我在 Python 中使用 Fuzzywuzzy 来匹配 2 个列表中的人名。但是，运行时间太长，因为一个列表包含 25000 个名称，另一个包含 39000 个名称。它已经运行了20个小时。
以前，我使用相同的代码来匹配具有 6000 和 3000 个名称的 2 个列表，运行时间为 1 小时。基于此，我当前工作的运行时间将需要 50 多个小时。
下面是我的代码：
names_array=[]
ratio_array=[]
def match_names(wrong_names,correct_names):
for row in wrong_names:
x=process.extractOne(row, correct_names, scorer=fuzz.token_set_ratio)
names_array.append(x[0])
ratio_array.append(x[1])
return names_array,ratio_array
df=pd.read_csv("wrong-country-names.csv",encoding="ISO-8859-1")
wrong_names=df['name'].dropna().values
choices_df=pd.read_csv("country-names.csv",encoding="ISO-8859-1")
correct_names=choices_df['name'].values
name_match,ratio_match=match_names(wrong_names,correct_names)
我fuzz.token_set_ratio根据我拥有的数据选择作为得分手来执行这场多对多比赛。
下面是示例数据：
wrong_names = ['Alberto Steve', 'David Lee']
correct_names = ['Alberto Lee Steve', 'David Steve Lee']
基本上，错误名称列表不包含中间名，为了忽略这一点并生成合理的匹配，我选择了fuzz.token_set_ratio.
通过在线研究，我找到了一个安装 python levenshtein 包的解决方案，以将运行时间加快 4-10 倍。但是，我的工作现在已经运行了 20 多个小时，我不想破坏当前的工作，所以我会在这之后尝试一下。
我想知道是否还有其他选择可以改善这一点。
提前致谢。