5

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

Go を使用して、Peter Norvig のスペル チェック アルゴリズムをいくつか実装しました。

FIRST THREEの呼び出しが正しく機能し、目的の出力が得られるのは奇妙です。

しかし、2 番目から、「処理に時間がかかりすぎました」と表示されます。

誰かが私のコードを見て、何が問題なのか教えてもらえますか?

これは、おそらく間違っているスニペットです。

英語版の同じコードですべてが完璧に機能します。

英語はアルファベットあたり 1 バイト、この場合のアジア言語は 1 文字あたり 3 バイトであるため、UNICODE の形式と境界は言語によって異なります。

これは、完璧に機能していた英語用のアルゴリズムと同じアルゴリズムを実行しようとしています。しかし、これは機能していません。

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

追加: 順序付けされた引数で、現在 3 つのことが機能しています。

韓国語の手紙に欠落している文字はありません。

エラーをより具体的に見ることができる方法はありますか? 私は理解できません。

4

1 に答える 1

5

コードをいじってみると、KoreanKnownEdits2時間がかかりすぎているようです。4 番目の例 (失敗した例) では、 is の長さと最初のmodel.KoreanEdits1(input_word)is28197の長さがあり、model.KoreanEdits1(elem1)約234996 億 6,200 万のケースが試行されます。時間がかかりすぎるため、プログラムは最初の 147 千回後に失敗しているようです (遊び場)。

呼び出しを必要としない例はすべて機能しているようにKoreanKnownEdits2見えるので、徹底的な検索を避けるためにこの関数を書き直すか、プレイグラウンドの時間制限で使用したい場合は少なくともより適切なサイズに制限する必要があると思います。あなたのコードを 100% 確信できるほど詳細に調べたわけではありませんが、西洋のアルファベットの 26 文字は英語版で扱いやすいと思いますが、拡張された韓国語のアルファベットは入力のサイズを大きくしすぎます。各文字がエンコードされているバイト数に関係なく、プレイグラウンドの時間制限で処理されます。

于 2013-11-06T11:46:24.490 に答える