Golang：过程耗时太长。实现拼写检查器

Question

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

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

奇怪的是，前三个调用正确地给了我所需的输出。

但是从第二个开始，它说“过程花费了太长时间”。

有人可以看看我的代码并告诉我出了什么问题吗？

这是可能出错的片段。

使用相同的英文代码，一切都完美无缺。

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)

}

Answer 1

玩弄你的代码，似乎是你KoreanKnownEdits2花了太长时间。在您的第四个示例（失败的一个）中，model.KoreanEdits1(input_word)is28197的长度和第一个的长度model.KoreanEdits1(elem1)is&nbsp;23499，这使得大约 662 百万个案例可以尝试。似乎程序在前 147 千之后失败了，因为它花费的时间太长（操场）。任何不需要调用的示例KoreanKnownEdits2似乎都可以工作，因此我怀疑您应该重写此函数以避免穷举搜索，或者如果您想在操场的时间限制下使用它，至少将其限制为更合理的大小。我还没有对你的代码进行足够详细的研究，无法 100% 确定这一点，但我怀疑 26 个西方字母使其在英文版本中易于管理，而扩展的韩文字母会使输入的大小太大而无法在操场的时间限制内处理，不管每个字符编码的字节数是多少。