Golang:过程花了太长时间.实施拼写检查

Question

http://play.golang.org/p/H5E0ExL85d

我用Go实现了一些Peter Norvig的拼写检查算法.

奇怪的是,FIRST THREE调用工作正确,给我所需的输出.

但从第二个方面来看,它说的是"过程花了太长时间".

任何人都可以查看我的代码并告诉我出了什么问题？

这是可能出错的片段.

使用英文版的相同代码,一切都很完美.

UNICODE格式和边界根据语言而改变,因为英语每个字母包含1个字节,在这种情况下亚洲语言包含每个字符3个字节.

这是尝试运行与英语完全相同的算法.但这不起作用.

total_set := []string{}
for _, elem := range splits {

    if len(elem.str2) > 3 {
        //deletion
        total_set = append(total_set, elem.str1+elem.str2[3:])

        //replace
        for i:=0; i<len(koreanletter)/3; i++ {
            total_set = append(total_set, elem.str1+string(koreanletter[3*i:3*(i+1)])+elem.str2[3:])
        }

        //transpose
        if len(elem.str2) > 9 {
            total_set = append(total_set, elem.str1+string(elem.str2[3:6])+string(elem.str2[:3])+elem.str2[9:])
        }

    } else {
        //deletion
        total_set = append(total_set, elem.str1)
    }

    //insertion
    for _, c := range koreanletter {
        total_set = append(total_set, elem.str1+string(c)+elem.str2)
    }
    return RemoveDuplicateStringArrayForKorean(total_set)
}

---

英语的下面是.这是完美的.

//Edits1 is to measure the distance between strings.
func (model *Model) Edits1(word string) []string {
  const alphabet = "abcdefghijklmnopqrstuvwxyz"

  splits := []Pair{}
  for i := 0; i <= len(word); i++ {
    splits = append(splits, Pair{word[:i], word[i:]})
  }

  total_set := []string{}
  for _, elem := range splits {

    if len(elem.str2) > 0 {
      //deletion
      total_set = append(total_set, elem.str1+elem.str2[1:])

      //replace
      for _, c := range alphabet {
        total_set = append(total_set, elem.str1+string(c)+elem.str2[1:])
      }

      //transpose
      if len(elem.str2) > 1 {
        total_set = append(total_set, elem.str1+string(elem.str2[1])+string(elem.str2[0])+elem.str2[2:])
      }

    } else {
      //deletion
      total_set = append(total_set, elem.str1)
    }

    //insertion
    for _, c := range alphabet {
      total_set = append(total_set, elem.str1+string(c)+elem.str2)
    }
  }
  return RemoveDuplicateStringArrayLowerCase(total_set)
}

增加:有序的论点,现在我有三件事在起作用.

韩国通讯中没有遗漏任何字符.

反正我是否可以更具体地看到错误？我只是想不通.

Answer 1

玩弄你的代码,似乎是你KoreanKnownEdits2花了太长时间.在你的第四个例子(一个失败的),长度model.KoreanEdits1(input_word)就是28197和第一的长度model.KoreanEdits1(elem1)是23499,这使得周围662百万情况下尝试.似乎该计划在第一批147,000之后失败,因为它需要太长时间(游乐场).

任何不需要调用的示例KoreanKnownEdits2似乎都有效,所以我怀疑你应该重写这个函数以避免穷举搜索,或者至少将它限制在更合理的大小,如果你想在游乐场的时间限制内使用它.我没有足够的细节研究你的代码,以确保100%确定,但我怀疑西方字母的26个字母使其可以管理英文版,而扩展的韩文字母使你的输入的大小太大而不能无论每个字符编码的字节数,都在操场的时间限制内处理.