相关疑难解决方法(0)

我一直在寻找一种先进的levenshtein距离算法,到目前为止我发现的最好的是O(n*m),其中n和m是两个弦的长度.算法处于这种规模的原因是因为空间而不是时间,创建了两个字符串的矩阵,例如:

是否有一个公开的levenshtein算法,它比O(n*m)更好？我并不反对看高级计算机科学论文和研究,但却找不到任何东西.我找到了一家名为Exorbyte的公司,该公司据称已经建立了超级先进且超快的Levenshtein算法,但当然这是商业秘密.我正在构建一个iPhone应用程序,我想使用Levenshtein距离计算.有一个Objective-c实现可用,但由于iPod和iPhone上的内存有限,我想找到一个更好的算法,如果可能的话.

我正在使用Python编写拼写检查程序.我有一个有效单词列表(字典),我需要从这个字典中输出一个单词列表,它与给定的无效单词的编辑距离为2.

我知道我需要从无效单词生成一个编辑距离为1的列表开始(然后再对所有生成的单词再次运行).我有三个方法,插入(...),删除(...)和更改(...)应输出编辑距离为1的单词列表,其中插入输出所有有效单词多于一个字母的单词给定的单词,删除输出所有有效单词少一个字母,并更改输出所有有效单词和一个不同的字母.

我查了很多地方,但我似乎无法找到描述这个过程的算法.我提出的所有想法都涉及多次遍历字典列表,这将非常耗时.如果有人能提供一些见解,我将非常感激.

我刚刚实现了一个最佳匹配文件搜索算法,以找到与字典中字符串最接近的匹配.在分析我的代码之后,我发现绝大部分时间花在计算查询和可能结果之间的距离上.我目前正在使用2-D数组实现算法来计算Levenshtein距离,这使得实现成为O(n ^ 2)运算.我希望有人可以建议更快的方式做同样的事情.

这是我的实现:

public int calculate(String root, String query)
{
  int arr[][] = new int[root.length() + 2][query.length() + 2];

  for (int i = 2; i < root.length() + 2; i++)
  {
    arr[i][0] = (int) root.charAt(i - 2);
    arr[i][1] = (i - 1);
  }

  for (int i = 2; i < query.length() + 2; i++)
  {
    arr[0][i] = (int) query.charAt(i - 2);
    arr[1][i] = (i - 1);
  }

  for (int i = 2; i < root.length() + 2; i++)
  { …

我正在进行模糊搜索实现,作为实现的一部分,我们使用的是Apache的StringUtils.getLevenshteinDistance.目前,我们正在寻找模糊搜索的特定最大平均响应时间.经过各种改进和一些剖析后,花费最多时间的地方是计算Levenshtein距离.它占搜索字符串总时间的大约80-90%三个字母或更多.

现在,我知道在这里可以做些什么有一些限制,但我已经读过以前的SO问题和LD的维基百科链接,如果有人愿意将阈值限制在设定的最大距离,这可能有助于遏制花在算法上的时间,但我不确定如何准确地做到这一点.

如果我们仅对距离感兴趣,如果它小于阈值k,那么在矩阵中计算宽度为2k + 1的对角条纹就足够了.这样,算法可以在O(kl)时间内运行,其中l是最短字符串的长度.[3]

下面你将看到StringUtils的原始LH代码.之后是我的修改.我试图基本上计算设定长度与i,j对角线的距离(因此,在我的例子中,i,j对角线上方和下方的两个对角线).但是,这是不正确的,因为我已经这样做了.例如,在最高的对角线上,它总是会直接在上面选择单元格值,这将是0.如果有人能告诉我如何使这个功能如我所描述的那样,或者如何使它成为如此的一般建议, 这将不胜感激.

public static int getLevenshteinDistance(String s, String t) {
        if (s == null || t == null) {
            throw new IllegalArgumentException("Strings must not be null");
        }

        int n = s.length(); // length of s
        int m = t.length(); // length of t

        if (n == 0) {
            return m;
        } else if (m == 0) {
            return n;
        }

        if (n > m) {
            // swap the input strings to consume less memory
            String …

如果我有一些我不想超过的距离。示例 = 2. 我是否可以在知道最小允许距离的情况下在完全完成之前中断算法？

也许有类似的算法可以完成。

我有必要减少工作计划的时间。