1

トライの次の構造の場合。

struct Trie {

  bool eow; //when a Trie field isWord = true, hence there is a word
  char letter;
  Trie *letters[27];

};

オートコンプリートプログラムの関数を作成しようとしています。この関数は、基本的に、特定の文字列プレフィックスを指定してトライ内の単語を出力します。

これが私が持っているものです：

int wordcheck( TrieNode &node )
  {
    if (node.isWord == 1) // you have found your word, so return true
      {
        return 1;
      }
    for (int i = 0; i < 26; i++)
      {
        if (node.letters[i] != NULL && wordcheck(*(node.letters[i])))
          {
            return 1;
          }
      }
    return 0;
  }



string find (TrieNode &node, const string &word, string acc)
{
   if (word.length() == 0)
    {
      string x = "";
      if (node.isWord == 1){
      x = " ";
      int check = 1;
      for(int i = 0; i < 26; i++)
        {
          if (node.letters[i] != NULL && wordcheck(*(node.letters[i])))
            {
              x = x + acc; check = 0; break;
            }
        }
      if(check == 1)
        { return x; }
      }
  for (int i = 0; i < 26; i++){
    if (node.letters[i] != NULL &&  wordcheck(*(node.letters[i])))
      {
        char let = (char)(i + (int)'a');
        if (x[x.length() - 1 ] == ' ')
          {
            x = x + acc;
          }
        x = x + node.letters[i]->letter 
              + find(*(node.letters[i]), word, acc + node.letters[i]->letter);
      }
  }
  return x;
    }
 else if (node.letters[word[0] - 'a'] == NULL)
   { return ""; }
 else {
   return word[0] + find(*(node.letters[ word[0] - 'a']), 
                         word.substr(1, word.length()-1), 
                         acc + word[0]);
 }
}

長いプレフィックスを付けると、プレフィックスより短い単語が出力されるという事実以外は機能しているようです。私は累積再帰を使用しましたが、これを行うためのより効率的な方法があると確信しています。私の質問は、誰かが正しい文字列を返すようにすることができるか、または可能であればより簡単なアルゴリズムを案内してくれるかどうかです。

4

1 に答える 1

0

オートコンプリートプログラムの関数を作成しようとしています。この関数は、基本的に、特定の文字列プレフィックスを指定してトライ内の単語を出力します。

私はあなたのプログラムを分析するつもりはありません-私にとってそれはあまりにも複雑です、例えば私は何wordcheckをすべきかわからないのですか？なぜそうではないのboolですintか？サブトライに単語が含まれていることを本当に確認する必要がありますか？単語が含まれていない空でないトライが本当にありますか？

まず、指定されたプレフィックスで始まるすべての単語を印刷するには、これらすべての単語が始まるノードに移動する必要があります。

TrieNode* TreeNode::get(std::string word)
{
   TreeNode* retVal = this;
   for (size_t i = 0; i < word.length(); ++i) {
     if (Words[i] < 'a' || words[i] > 'z')
        throw std::runtime_error("Wrong word");
     if (retVal->letters[word[i] - 'a'] != NULL)
         retVal = retVal->letters[word[i] - 'a'];
     else 
         return nullptr;
    }
    return retVal;
}

指定されたノードからすべての単語を出力する関数が必要です。

void TreeNode::printAll(std::ostream& os, std::string prefix)
{
   if (isWord)
     os << prefix << "\n";
   for (size_t i = 0; i < 26; ++i) {
     if (retVal->letters[i] != NULL)
         // this recursive call can be replaced with iterative solution with stack
         letters[i]->print(os, prefix + char('a' + i)); 
    }
}

そして、これらの機能を組み合わせることで、必要なものが得られます。

void TreeNode::printBeginWith(std::ostream& os, std::string prefix)
{
   TreeNode* node = get(prefix);
   if (node)
      node->printAll(os, prefix);
}
于 2012-10-20T11:24:40.670 に答える