[Self Study] : 문자열 자동 완성 기능

Trie는 흔히 Prefix Tree 혹은 Radix Tree라고 불리우는 정렬된 트리 구조로서
문자열 자동 완성이나 스펠링 체크 기능 등에 사용되는 자료구조이다.
Trie는 retrieval이라는 단어 중간 부분을 따온 것으로 Tree와 구분되게 '트라이'라고 발음한다.

Trie는 주로 문자열을 키로 사용하며, 문자열 안에 문자 하나 하나가 노드의 링크로 표현된다.
예를 들어, "cat"이라는 단어의 경우,
루트 노드에서 "c"를 가리키는 자식 노드에 연결되고(루트 -> c),
다시 "c"노드에서 "a"를 가리키는 자식 노드에 연결되고(루트 -> c -> a),
마지막으로 "a"노드에서 "t"를 가리키는 자식 노드에 연결된다(루트 -> c -> a -> t).

즉, 일반적인 이진 탐색 트리는 한 노드에 "cat"이라는 문자열을 저장하지만,
Trie는 빈 노드인 루트를 포함하여 4개의 노드에 걸쳐 "c", "a", "t"를 저장하는 것이다.

Trie에서 문자열은 루트부터 리프 노드까지 연결되어 표현된다.
그런데 "tea"와 같이 특정 문자열("team") 중간에 문자열이 완성되는 경우도 있다.
따라서 어떤 노드가 문자열의 끝인지를 표현하기 위해
Trie 노드에서 완성된 문자열인지를 표현하는 필드를 두거나
노드에 완성된 문자열 자체를 저장하는 등의 방법을 사용할 수 있다.

아래 코드는 해시테이블을 사용한 Trie 클래스이다.
새로운 문자열을 Trie에 추가하는 Insert() 메소드와
특정 문자열이 Trie 트리에 존재하는지 검색하는 Find() 메소드가 주요 메소드이다.

public class Trie
{
	private class Node
    {
		public Dictionary<char, Node> Children
      	{
			get; private set;
        }
      	public bool EndOfWord { get; set; }
      	public Node()
      	{
			Children = new Dictionary<char, Node>();
      	}
    }
	
	// 루트 노드
	private Node root = new Node();
	
	// Insert() 메소드
	public void Insert(string str)
    {
		Node node = root;
      	
      	foreach (var ch in str)
      	{
			if (!node.Children.ContainsKey(ch))
            {
				node.Children[ch] = new Node();
            }
          	node = node.Children[ch];
        }
      	
      	node.EndOfWord = true;
    }

	// Find() 메소드
	public bool Find(string str)
    {
		Node node = root;
      	
      	foreach (var ch in str)
      	{
			if (!node.Children.ContainsKey(ch))
            {
				return false;
            }
          	node = node.Children[ch];
        }
      	
      	return node != null && node.EndOfWord;
    }
}

Trie를 기반으로 문자열 자동 완성 기능을 구현해보았다.
문자열 자동 완성 기능은 사용자가 지금까지 입력한 내용을 기반으로
사전이나 데이터베이스에서 그 문자열로 시작하는 단어들을 보여주는 기능이다.

자동 완성 기능을 구현하기 위해서 AutoComplete()라는 메소드를 작성하였다.
해당 메소드는 prefix라는 문자열을 입력 받아, 단어 리스트를 반환하는 메소드이다.
기본 로직은 루트 노드로부터 prefix 문자열까지의 노드로 이동한 후,
해당 노드의 서브 트리를 전위 순회하면서 단어 끝으로 표시된 노드를 결과 리스트에 저장한다.

public class Trie
{
	// 앞서 구현한 내용 생략
  	public List<string> AutoComplete(string prefix)
	{
		var node = root;
		foreach (var ch in prefix)
		{
			if (!node.Children.ContainsKey(ch))
			{
				return null;
			}
			node = node.Children[ch];
		}
		
		var result = new List<string>();
		
		Preorder(node, prefix, result);
		
		return result;
	}
	
	private void Preorder(Node node, string nodeStr, List<string> result)
	{
		if (node == null)
		{
			return;
		}
		
		if (node.EndOfWord)
		{
			result.Add(nodeStr);
		}
		
		foreach (var key in node.Children.Keys)
		{
			Preorder(node.Children[key], nodeStr + key, result);
		}
	}
}

상기 구현에서는 노드간 링크들로부터 단어를 조합한다.
그런데 단어가 끝나는 노드에 실제 그 단어를 넣어 두면 조금 더 편리하다.
이를 위해 아래와 같이 코드를 수정하였다.

public class Trie
{
	private class Node
    {
		public Dictionary<char, Node> Children
      	{
			get; private set;
        }
      	public string Word { get; set; }
      	public Node()
      	{
			Children = new Dictionary<char, Node>();
      	}
    }

	private Node root = new Node();
	
	public void Insert(string str)
    {
		Node node = root;
      	
      	foreach (var ch in str)
      	{
			if (!node.Children.ContainsKey(ch))
            {
				node.Children[ch] = new Node();
            }
          	node = node.Children[ch];
        }
      	
      	node.Word = str;
    }

	public bool Find(string str)
    {
		Node node = root;
      	
      	foreach (var ch in str)
      	{
			if (!node.Children.ContainsKey(ch))
            {
				return false;
            }
          	node = node.Children[ch];
        }
      	
      	return node != null && node.Word != null;
    }
	
	public List<string> AutoComplete(string prefix)
	{
		var node = root;
		foreach (var ch in prefix)
		{
			if (!node.Children.ContainsKey(ch))
			{
				return null;
			}
			node = node.Children[ch];
		}
		
		var result = new List<string>();
		
		Preorder(node, result);
		
		return result;
	}
	
	private void Preorder(Node node, List<string> result)
	{
		if (node == null)
		{
			return;
		}
		
		if (node.Word != null)
		{
			result.Add(node.Word);
		}
		
		foreach (var key in node.Children.Keys)
		{
			Preorder(node.Children[key], result);
		}
	}
}