问题标签 [fuzzy]

我对两个单词列表的函数感兴趣，它将返回它们之间的顺序不可知的编辑距离。

也就是说，参数将是两个（假设用空格分隔）单词列表，返回值将是列表中单词的编辑（或 Levenshtein）距离的最小总和。

"cat rat bat"和之间的距离"rat bat cat"为0。和之间的距离与和"cat rat bat"之间"fat had bad"的距离相同，4。如果列表中的单词数不相同，则较短的列表将用长度为0的单词填充。"rat bat cat""had fat bad"

我的直觉（没有通过计算机科学课程培养）除了使用蛮力之外没有找到任何其他解决方案：

从第一行开始，选择一列并转到下一行，而无需重新访问您已经访问过的列。一遍又一遍地这样做，直到你尝试了所有的组合。

对我来说，这听起来有点像旅行商问题。是吗，您将如何解决我的特定问题？

Lucene 模糊匹配使用基本的editDistance 算法来实现模糊匹配。Lucene 是否还有其他使用其他相似性度量的模糊匹配实现？他们也应该识别同音字。还请比较 lucene 的各种模糊匹配方法。

我目前正在尝试为一组观察自动生成一组模糊规则，其中每个观察包含四个值，其中每个观察将对应于一个状态（一个很好的例子是 Fisher 的虹膜数据）。

在 Matlab 中，我正在创建一个四维规则表，其中单个单元格 (a,b,c,d) 将包含相应的状态。为了减少表格，我遵循了行列相似性检查的Hong 和 Lee方法，但我很难理解如何处理第三维和第四维的行和列。从方法来看，我的理解是每个维度都是单独处理的，如果规则是真的，表格就会被简化。合并规则如下：

1. 如果相邻列或行中的所有单元格都相同。
2. 如果两个单元格相同，或者相邻
   列或行中的任何一个为空，并且两者中至少有一个单元格不为空。
3. 如果一列或一行中的所有单元格都是空的，并且如果它的两个
   相邻列或行中的单元格相同，则合并三个。
4. 如果一列或一行中的所有单元格都是空的，并且如果它的两个
   相邻列或行中的单元格相同或其中一个为空，则合并三个。
5. 如果一列或一行中的所有单元格都是空的，并且如果
   其左侧的列或行中的所有非空单元格具有相同的区域，并且其右侧的列或行中的所有非空单元格具有相同的区域，但与前面提到的区域不同，将这三列合并为两部分。

现在是令人困惑的一点。简单地检查整个行/列是否与相邻的（规则 1）相同似乎很简单：

这个对吗？

但是要检查行/列中的元素是否匹配，或者是否为零（规则 2 和 4），我有点迷茫。会不会是这样的：

对于第三维和第四维：

甚至对四维数组的任何帮助都会很有用，因为我对超过三个的想法感到非常困惑！我建议您查看论文以理解我的意思-他们自己使用了 Iris 数据，但仅给出了 2D 表格的示例。

假设我有一组对象，S. 有一种算法f，给定一个集合在其上S构建一定的数据结构D：f(S) = D. 如果S很大和/或包含非常不同的对象，则会D变得很大，以至于无法使用（即不适合分配的内存）。为了克服这个问题，我分成S几个不相交的子集：S = S1 + S2 + ... + Sn并为每个子集构建Di。使用n结构比使用结构效率低，但至少这样我可以适应内存限制。由于大小的f(S)增长速度比S自身快，组合大小Di远小于大小D。

然而，仍然希望减少n，即子集的数量；或减小 的组合大小Di。为此，我需要以S每个Si包含“相似”对象的方式进行拆分，因为f如果输入对象彼此“足够相似”，则会产生较小的输出结构。

问题是，虽然对象的“相似性”S和 do 的大小f(S)相关，但除了评估之外，没有办法计算后者f(S)，而且f速度不是很快。

我目前拥有的算法是迭代地将每个下一个对象从 中添加S到其中一个中Si，这样就可以尽可能少地（在这个阶段）增加组合Di大小：

这给出了实际有用的结果，但肯定远非最佳（即最小可能的组合大小）。另外，这很慢。为了加快速度，我只计算size(f(Si + {x})) - size(f(Si))那些i与.xSi

这类问题有什么标准方法吗？

我知道分支和边界算法系列，但它不能在这里应用，因为它会非常慢。我的猜测是，根本不可能在合理的时间内计算S出in 的最佳分布。Si但是有一些常见的迭代改进算法吗？

编辑：

正如评论所指出的，我从未定义过“相似性”。事实上，我想要的只是分割成Si组合大小Di = f(Si)最小或至少足够小的子集。“相似度”仅被定义为这一点，不幸的是，它根本无法轻松计算。我确实有一个简单的近似值，但仅此而已——一个近似值。

所以，我需要的是一个（可能是启发式的）算法，sum f(Si)考虑到没有简单的方法来计算后者——我只需要一个近似值来丢弃不太可能给出好的结果的情况。

是否有用于在图中搜索结构的 levenshtein 距离的概括？

有人知道在 Unicode 中查找与 ASCII 字符相似的字符的简单方法吗？一个例子是“西里尔小写字母DZE (ѕ)”。我想搜索并替换相似的字符。类似的意思是人类可读的。你看不出来有什么区别。

我最近一直在为一家公司开发一个网站，它有一个完整的管理前端/CMS。在管理前端，很遗憾，出于安全原因，我无法向您显示，有一个范围列表、集合列表和设计列表。我想让这些链接与 JQuery 一起工作，因此单击“范围”会将范围列表带到前面并淡出当前活动的列表，同时使其变得模糊。我想让 Range 列表默认位于其他列表的前面，不透明度约为 50%（疯狂猜测）。但是，如果不透明度为 50%，您仍然可以看到它后面的文本（在其他列表中）。我希望背景中的文本（“后面”列表）是灰色和模糊的，就像我刚刚注意到的效果一样，如果您在 Windows Live Mail 前面有一个 Windows 照片查看器窗口 - Windows Live Mail 右下角的状态文本是模糊的，在后面的窗口上很明显）。我还希望前景中的文本是黑色的并且是焦点。更改文本颜色很容易（peezy lemon squeezy！）。我在“JQuery 模糊”和类似术语上做了一个快速的谷歌搜索，但一无所获。

谁能告诉我是否有办法做到这一点（最好像 $(selector).fuzz(50%); 一样简单）？

提前致谢。

问候，

理查德

我同时使用 Daitch-Mokotoff soundexing 和 Damerau-Levenshtein 来确定应用程序中的用户条目和值是否“相同”。

Levenshtein 距离是否应该用作绝对值？如果我有一个 20 个字母的单词，那么 4 的距离还不错。如果单词有4个字母...

我现在正在做的是获取距离/长度以获得更好地反映单词已更改百分比的距离。

这是一种有效/经过验证的方法吗？还是单纯的愚蠢？

对于说荷兰语的人来说，两个字符“ij”被认为是一个很容易与“y”交换的字母。

对于我正在从事的项目，我希望有一个Damerau-Levenshtein 距离的变体，它将“ij”和“y”之间的距离计算为 1，而不是当前值 2。

我自己一直在尝试，但失败了。我的问题是我不知道如何处理两个文本长度不同的事实。有没有人有关于如何解决这个问题的建议/代码片段？

谢谢。

我在 vim 中将 FuzzyFinder 与 MiniBufExplorer 一起使用（在我的 .vimrc 中使用此设置：g:miniBufExplorerMoreThanOne = 1）。

我在覆盖文件模式下使用 FuzzyFinder（据我了解，它的工作方式与 command-t 非常相似）。

问题是，每当我使用 FuzzyFinder 打开一个新文件时，它不是在我打开的当前窗口中打开它，而是创建一个新的、微小的垂直分割窗口。

有没有办法改变这种行为？

编辑：这只发生在新的、修改后的 minibuffer 版本（从 vim 脚本页面链接到）。不知道我能做些什么。