草庐IT

arrays - Golang : process took too long. 实现拼写检查

coder 2023-06-26 原文

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)
}

英文的在下面。 这是完美的工作。

//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)
}

添加:有序参数，现在我有三样东西在工作。

韩语字母中没有一个字符丢失。

无论如何我可以更具体地看到错误？我就是想不通。

最佳答案

研究您的代码，似乎是您的 KoreanKnownEdits2 花费了太长时间。在你的第四个例子(失败的那个)中， model.KoreanEdits1(input_word) 的长度是 28197 而第一个 model.KoreanEdits1(elem1) 的长度 是 23499，这使得大约有 6.62 亿个案例需要尝试。程序似乎在前 147,000 次后失败，因为它花费的时间太长 ( playground )。

任何不需要调用 KoreanKnownEdits2 的例子似乎都有效，所以我怀疑你应该重写这个函数以避免穷举搜索，或者至少将它限制在一个更合理的大小，如果你想在 Playground 的时间限制下使用它。我还没有足够详细地研究你的代码，无法 100% 确定这一点，但我怀疑西方字母表的 26 个字母使其易于管理英文版本，而扩展的韩文字母表使你的输入量太大而无法使用在 playground 的时间限制内处理，无论每个字符编码的字节数如何。

关于arrays - Golang : process took too long. 实现拼写检查，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19806628/

拼写processtotal_setelemtotalarraysalgorithmmemory-managementgo

有关arrays - Golang : process took too long. 实现拼写检查的更多相关文章

  1. ruby - 在 Ruby 中实现 `call_user_func_array` - 2

    我怎样才能完成http://php.net/manual/en/function.call-user-func-array.php在ruby中？所以我可以这样做:classAppdeffoo(a,b)putsa+benddefbarargs=[1,2]App.send(:foo,args)#doesn'tworkApp.send(:foo,args[0],args[1])#doeswork,butdoesnotscaleendend 最佳答案 尝试分解数组App.send(:foo,*args)

  2. ruby - 检查 "command"的输出应该包含 NilClass 的意外崩溃 - 2

    为了将Cucumber用于命令行脚本，我按照提供的说明安装了arubagem。它在我的Gemfile中，我可以验证是否安装了正确的版本并且我已经包含了require'aruba/cucumber'在'features/env.rb'中为了确保它能正常工作，我写了以下场景:@announceScenario:Testingcucumber/arubaGivenablankslateThentheoutputfrom"ls-la"shouldcontain"drw"假设事情应该失败。它确实失败了，但失败的原因是错误的:@announceScenario:Testingcucumber/ar

  3. Ruby Koans about_array_assignment - 非平行与平行分配歧视 - 2

    通过ruby​​koans.com，我在about_array_assignment.rb中遇到了这两段代码你怎么知道第一个是非并行赋值，第二个是一个变量的并行赋值？在我看来，除了命名差异之外，代码几乎完全相同。4deftest_non_parallel_assignment5names=["John","Smith"]6assert_equal["John","Smith"],names7end45deftest_parallel_assignment_with_one_variable46first_name,=["John","Smith"]47assert_equal'John

  4. ruby - 检查数组是否在增加 - 2

    这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife

  5. ruby - 检查方法参数的类型 - 2

    我不确定传递给方法的对象的类型是否正确。我可能会将一个字符串传递给一个只能处理整数的函数。某种运行时保证怎么样？我看不到比以下更好的选择:defsomeFixNumMangler(input)raise"wrongtype:integerrequired"unlessinput.class==FixNumother_stuffend有更好的选择吗？ 最佳答案 使用Kernel#Integer在使用之前转换输入的方法。当无法以任何合理的方式将输入转换为整数时，它将引发ArgumentError。defmy_method(number)

  6. ruby - 如何根据特征实现 FactoryGirl 的条件行为 - 2

    我有一个用户工厂。我希望默认情况下确认用户。但是鉴于unconfirmed特征，我不希望它们被确认。虽然我有一个基于实现细节而不是抽象的工作实现，但我想知道如何正确地做到这一点。factory:userdoafter(:create)do|user,evaluator|#unwantedimplementationdetailshereunlessFactoryGirl.factories[:user].defined_traits.map(&:name).include?(:unconfirmed)user.confirm!endendtrait:unconfirmeddoenden

  7. ruby - 检查字符串是否包含散列中的任何键并返回它包含的键的值 - 2

    我有一个包含多个键的散列和一个字符串，该字符串不包含散列中的任何键或包含一个键。h={"k1"=>"v1","k2"=>"v2","k3"=>"v3"}s="thisisanexamplestringthatmightoccurwithakeysomewhereinthestringk1(withspecialcharacterslike(^&*$#@!^&&*))"检查s是否包含h中的任何键的最佳方法是什么，如果包含，则返回它包含的键的值？例如，对于上面的h和s的例子，输出应该是v1。编辑:只有字符串是用户定义的。哈希将始终相同。 最佳答案

  8. ruby-on-rails - Ruby 检查日期时间是否为 iso8601 并保存 - 2

    我需要检查DateTime是否采用有效的ISO8601格式。喜欢:#iso8601?我检查了ruby​​是否有特定方法，但没有找到。目前我正在使用date.iso8601==date来检查这个。有什么好的方法吗？编辑解释我的环境，并改变问题的范围。因此，我的项目将使用jsapiFullCalendar，这就是我需要iso8601字符串格式的原因。我想知道更好或正确的方法是什么，以正确的格式将日期保存在数据库中，或者让ActiveRecord完成它们的工作并在我需要时间信息时对其进行操作。 最佳答案 我不太明白你的问题。我假设您想检查

  9. ruby - 检查日期是否在过去 7 天内 - 2

    我的日期格式如下:"%d-%m-%Y"(例如，今天的日期为07-09-2015)，我想看看是不是在过去的七天内。谁能推荐一种方法？ 最佳答案 你可以这样做:require"date"Date.today-7 关于ruby-检查日期是否在过去7天内，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/32438063/

  10. arrays - 这是 Ruby 中 Array.fill 方法的错误吗？ - 2

    这个问题在这里已经有了答案:Arraysmisbehaving(1个回答)关闭6年前。是否应该这样，即我误解了，还是错误？a=Array.new(3,Array.new(3))a[1].fill('g')=>[["g","g","g"],["g","g","g"],["g","g","g"]]它不应该导致:=>[[nil,nil,nil],["g","g","g"],[nil,nil,nil]]

随机推荐