我正在编写一个diff文本工具来比较两个类似的源代码文件.
周围有很多这样的"差异"工具,但是我的工具会有所改进:
如果它发现一组线在两侧都不匹配(即在两个文件中),它不仅要突出显示这些线,还要突出显示这些线中的各个变化(我在这里称之为线间比较).
我有点工作的解决方案的一个例子:
alt text http://files.tempel.org/tmp/diff_example.png
它目前所做的是采取一组不匹配的线条并再次通过差异运行它们的单个字符,产生粉红色突出显示.
然而,包含"原始2"的第二组不匹配需要更多工作:这里,添加了前两条右线("添加线a/b"),而第三条线是左侧的改变版本.我希望我的软件能够检测到可能的更改和可能的新行之间的这种差异.
看一下这个简单的例子,我可以很容易地发现这种情况:
使用像Levenshtein这样的算法,我可以在3到5的集合中找到所有正确的行,5行最好匹配左行3,因此我可以扣除右边的行3和4被添加,并执行inter左线3和右线5的线比较.
到现在为止还挺好.但我仍然坚持如何将此转换为更通用的算法.
在更复杂的情况下,一组不同的线可以在两侧添加线,其间具有一些紧密匹配的线.这变得非常复杂:
我不仅要匹配左边的第一行和右边的最好的一行,反之亦然,依此类推所有其他行.基本上,我必须匹配左边的每一行与右边的每一行.在最坏的情况下,这可能会产生偶数交叉,因此不再容易清楚哪些线路是新插入的,哪些线路只是被改变了(注意:我不想在这样的块中处理可能移动的线路,除非这实际上会简化算法).
当然,这永远不会是完美的,但我试图让它比现在更好.任何建议不是太神论但相当实用(我不是很好理解抽象算法),这是值得赞赏的.
更新
我必须承认,我甚至不了解LCS算法是如何工作的.我只是给它提供了两个字符串数组,然后列出了哪些序列不匹配.我基本上使用的是这里的代码:http://www.incava.org/projects/java/java-diff
查看代码,我找到一个函数equal(),负责告诉算法两行是否匹配.根据帕维尔的建议,我想知道这是否是我做出改变的地方.但是怎么样？此函数仅返回布尔值 - 而不是可以识别匹配质量的相对值.而且我不能简单地使用一个固定的Levenshtein比率来决定一条相似的线是否仍然被认为是相同的 - 我需要一些自我采用的东西来处理整个线路.
所以,我基本上说的是,我仍然不明白我在哪里应用与不完全匹配的线的相对相似性相关的模糊值.
下午好,
有没有人知道在.NET 中使用Levenshtein DFA(确定性有限自动机)的"开箱即用"实现(或者很容易翻译)？我有一个非常大的字典,有超过160000个不同的单词,我希望,给出一个内在的单词w,以高效的方式在Levenshtein距离中找到所有已知单词最多2个w.
当然,具有在编辑距离处计算所有可能编辑的功能,给定单词中的一个并将其再次应用于这些编辑中的每一个解决了该问题(并且以非常简单的方式).问题是效率刍议---给予7字母的单词,这已经可以采取超过1秒即可完成,而我需要的东西很多更有效的---如果可能的话,因为它与莱文斯坦的DFA,这需要O(解决方案| w |)步骤.
编辑:我知道我可以通过一些学习来构建我自己的问题方法,但目前我无法负担阅读Schulz和Mihov长达60页的文章.
非常感谢你.
.net performance automata finite-automata levenshtein-distance
我坐在这里为Java主程序编写一些算法(到目前为止第一个算法).我编写levenshtein算法就好了,这要归功于wiki对于newbeginners的假代码非常好以及一个很好的教程:D
然后我决定升级到Damerau并添加额外的线,但后来我读到它不是DL算法而是OptimalStringAlignmentDistance而不是.我尝试阅读actionscript代码,以了解我需要添加什么以使其成为DL但却感到困惑.我去过不同的地方,代码看起来与Java相似,但他们都使用了错误的伪代码.
花了半天后,我放弃了,决定在这里问.是否有人可以帮助我将此代码升级到Java中的Damerau-Levenshtein？
public class LevensteinDistance {
private static int Minimum(int a, int b, int c) {
return Math.min(Math.min(a, b), c);
}
private static int Minimum (int a, int b) {
return Math.min(a, b);
}
public static int computeLevensteinDistance(String s, String t){
int d[][];
int n; // length of s
int m; // length of t
int i; // iterates through s
int j; // iterates through t
char s_i; // ith character of s
char t_j; // jth character …我正在尝试用字典创建一个光学字符识别系统.
事实上我还没有实现的字典=)
我听说有基于Levenstein距离的简单度量,它考虑了不同符号之间的不同距离.例如,'N'和'H'彼此非常接近,d("剧院","TNEATRE")应该小于d("THEATRE","TOEATRE"),这是使用基本Levenstein距离不可能的.
请帮您点一下这个指标.
坦克引起注意.
我有一个MySQL数据库表,包含大约1000家商店的信息.现在我将通过上传Excel电子表格来导入更多商店,我正在努力避免重复.
但这是我的问题.
目前我正在将数据导入临时表.现在我想知道将进口商店与现有商店进行比较的最佳方法是什么.
我的计划是通过每一行并比较商店.
有没有人有这种数据比较的经验？
更新
感谢您的回答.
将用于比较的字段是:
我正在考虑以下几点:
选择name = Lavenshtein和country = country的行.
这样我只需要处理一个小清单.
然后我可以更彻底地比较姓名和地址.
我找到了一些代码来计算Levenshtein在答案和猜测之间的距离:
int CheckErrors(string Answer, string Guess)
{
int[,] d = new int[Answer.Length + 1, Guess.Length + 1];
for (int i = 0; i <= Answer.Length; i++)
d[i, 0] = i;
for (int j = 0; j <= Guess.Length; j++)
d[0, j] = j;
for (int j = 1; j <= Guess.Length; j++)
for (int i = 1; i <= Answer.Length; i++)
if (Answer[i - 1] == Guess[j - 1])
d[i, j] = d[i - 1, j …我想查找一个String在String[]该查询的最佳匹配.我听说过Levenshtein Distance.但我无法确定是否需要它.
假设,我有一个String query = "Examples"和
String[] arrayStr = new String[] {"The Examples String", "The Example String", "Example", "Examples String", "Example String", "Examplestring"};
现在,我希望Example从String[]最佳匹配中获得.
那么,我需要Levenshtein Distance来做吗？
或者,如果有人可以指出我快速实现Levenshtein Distance for Java,那就太棒了.我想检查它是否适用于我拥有的所有字符串.(基本上我有大约10k个字符串来匹配10k数组.)
假设我有数千个字符串,我需要识别最常见的组.
这是一个示例数据集:http://pastebin.com/XGijjsfE
此数据集的前10行代表我所追求的字符串类型.虽然在现实生活中,这些会与其他人混在一起.
一种策略是循环遍历每个字符串,并使用字符串比较工具将其与其他字符串进行比较,并跟踪高度相似性.这里有一些伪php代码来说明这一点:
<?php
$arr = explode("\n",http://pastebin.com/XGijjsfE); // I know. Just pseudocode here!
$winners = array(); // store close matches here
foreach ($arr as $k1 => $line1) {
foreach ($arr as $k2 => $line2) {
if ($k1 != $k2) {
$lev = levenshtein($line1, $line2);
if ($lev < 10) { // assume 10 is a reasonable start to learn and tune later
$winners[] = array($line1,$line2,$lev);
}
}
}
}
print_r($winners);
?>
但是在100k行乘以100k行时,这可能非常昂贵.
在更大的数据集中识别类似字符串的更有效方法是什么？
我在LAMP环境中,字符串当前在MySQL表中.但答案可以在Shell,PHP,Python,MySQL等中执行.
这是数据集:
Lorem ipsum …如何在Python中计算字符串的Levenshtein距离矩阵
str1 str2 str3 str4 ... strn
str1 0.8 0.4 0.6 0.1 ... 0.2
str2 0.4 0.7 0.5 0.1 ... 0.1
str3 0.6 0.5 0.6 0.1 ... 0.1
str4 0.1 0.1 0.1 0.5 ... 0.6
. . . . . ... .
. . . . . ... .
. . . . . ... .
strn 0.2 0.1 0.1 0.6 ... 0.7
使用Ditance函数，我们可以计算2个单词之间的距离。但是这里有1个包含n个字符串的列表。我想计算距离矩阵，然后再对单词进行聚类。
python string machine-learning text-mining levenshtein-distance
我的申请中有员工名单。每个员工都有名字和姓氏，所以我有一个元素列表，例如：
["Jim Carry", "Uma Turman", "Bill Gates", "John Skeet"]
我希望我的客户具有使用模糊搜索算法按名称搜索员工的功能。例如，如果用户输入“ Yuma Turmon”，则将返回最接近的元素“ Uma Turman”。我在这里找到Levenshtein距离算法。
static class LevenshteinDistance
{
/// <summary>
/// Compute the distance between two strings.
/// </summary>
public static int Compute(string s, string t)
{
int n = s.Length;
int m = t.Length;
int[,] d = new int[n + 1, m + 1];
// Step 1
if (n == 0)
{
return m;
}
if (m == 0)
{
return n;
}
// Step 2
for …