Trie - 가능한 모든 문장 찾기

Question

다음 작업을 수행 중입니다 (C#에서). 우리는 문자 그룹과 영어 사전을 가지고 있습니다. 제공된 문자에서 생성 된 단어의 가능한 모든 조합을 찾습니다. 그렇게하기 위해, 나는 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; 
     } 
    } 

Answer 1

당신은 아호-corasick 알고리즘을 시도 할 수 있습니다 :

편집 이것은 내가 준비 예제 코드입니다. 그것은 trie와 접미사 및 대체 트라이 데이터 구조를 사용합니다.