Trie - 查找所有可能的句子

-1

我正在做以下任務（在C＃中）：我們有一組字母和一個英文字典。根據提供的字母查找所有可能的單詞組合。爲此，我使用trie數據結構 - 我從剩餘的字母中搜索單詞和所有可能的附加單詞（遞歸操作）。但是，該操作非常耗費時間/空間。任何想法如何更有效地處理它？Trie - 查找所有可能的句子

編輯這是示例代碼我準備：

class Trie 
    { 
     private Node root = new Node(null); 

     public void AddWord(string word) 
     { 
      root.Add(word, 0); 
     } 

     public void GetCandidates(string input) 
     { 
      var results = new List<Result>() 
      { 
       new Result() {Rest = input} 
      }; 

      Get(results); 
     } 

     private void Get(List<Result> results) 
     { 
      foreach (var result in results.Where(r => !string.IsNullOrEmpty(r.Rest)).ToList()) 
      { 
       var pattern = result.Rest.Replace(" ", string.Empty); 

       var allWords = new List<Result>(); 
       root.GetWord(string.Empty, allWords, pattern); 
       result.OhterWords = allWords; 

       Get(allWords); 
      } 


     } 
    } 

    class Node 
    { 
     protected Dictionary<char,Node> children = new Dictionary<char, Node>(); 

     public bool End { get; private set; } 

     public char? Key { get; private set; } 

     public Node(char? key) 
     { 
      Key = key; 
     } 

     public void Add(string word, int index) 
     { 
      var letter = word[index]; 
      if (!children.ContainsKey(letter)) 
      { 
       children.Add(letter, new Node(letter)); 

      } 

      var nextIndex = index + 1; 
      if (nextIndex < word.Length) 
      { 
       children[letter].Add(word, nextIndex); 
      } 
      else 
      { 
       children[letter].End = true; 
      } 
     } 

     public virtual void GetWord(string current, List<Result> allWords, string availableLetters) 
     { 
      var newCurrent = string.Concat(current, Key); 
      if (End) 
      { 
       var result = new Result() 
       { 
        Rest = availableLetters, 
        Word = newCurrent, 
       }; 


       if (!allWords.Contains(result)) 
       { 
        allWords.Add(result); 
       } 
      } 

      foreach (var letter in availableLetters) 
      { 
       if (children.ContainsKey(letter)) 
       { 
        var index = availableLetters.IndexOf(letter); 
        var tempAvailableString = availableLetters.Remove(index, 1); 
        children[letter].GetWord(newCurrent, allWords, tempAvailableString); 
       } 
      } 
     } 
    } 

    class Result 
    { 
     public List<Result> OhterWords { get; set; } 

     public string Word { get; set; } 

     public string Rest { get; set; } 

     public override bool Equals(object obj) 
     { 
      var r = obj as Result; 
      if (r == null) 
      { 
       return false; 
      } 

      return r.Word == Word && r.Rest == Rest; 
     } 
    }

來源

2015-01-31 macpak

你能否提供一些示例代碼來告訴我們你目前有什麼？ – kevin 2015-01-31 17:58:42

你應該發佈你的代碼或至少解釋你使用的算法更清楚一點。我們不知道爲什麼手術需要時間/空間，直到我們瞭解您如何執行手術。 – Jacob 2015-01-31 17:58:45

另外，你提到空間消耗;你能告訴我們你是如何存儲trie的嗎？ – Jacob 2015-01-31 18:08:33

您可以嘗試阿霍 - corasick算法。它使用一個trie，也是後綴和替代trie數據結構。

來源

2015-02-02 17:51:49 Bytemain

Trie - 查找所有可能的句子

回答

相關問題