useTrie 문자열 자동 완성 hook

• Select 컴포넌트를 만들다가 자동완성 기능이 필요했다.
• 자동완성을 위한 알고즘이 어떤것이 있을까 하다가 Trie DS를 이용하여 간단하게 구현할 수 있을 것 같아서 구현을 하게 되었다.

Trie란?

• 문자열의 접두어 기준으로 트리 형태로 저장하는 자료구조
• dictionary 타입으로 이루어진 트리 형태가 된다.

• Prefix - dictionary의 key
• isWord - 해당 노드가 마지막 깊이의 노드인지, 즉 문자열의 끝인지 여부를 가짐, boolean type
• word - 해당 노드가 마지막 깊이의 노드일 경우 prefix로 시작하는 전체 문자열을 저장
• next - 다음 노드를 가리키는 참조자

기능

• 필요한 모든 문자열을 Trie DS로 생성한다.
  • 같은 문자열이 여러개가 올 수 있으며,
  • 문자열에 대한 추가적인 옵션도 저장할 수 있도록 한다.
• 한글도 자동완성이 되어야 하며, 이를 위해 한글이 입력되면 음소로 쪼개어 저장한다.
• input으로 입력받은 문자가 포함된 모든 문자열이 리스트에 출력되도록 한다.

구현

• class를 이용하여 구현해보았다.
• 먼저 Trie Node를 정의하며 각각의 노드가 다음의 노드를 가리키는 형태가 된다

  class TrieNode {
    public isWord: boolean;
  
    public next: { [key: string]: TrieNode };
  
    public info: Array<TrieData> | null;
  
    constructor() {
      this.isWord = false;
  
      this.next = {};
  
      this.info = null;
    }
  }

• 멤버 변수 info의 타입인 TrieData는 같은 문자열에 대한 구분을 위해 key 그리고 추가적인 데이터를 위한 option도 포함하는 타입이다.

  type TrieData = {
    label: string;
    key: string | number;
    options?: { [key: string]: any };
  };

• 입력받은 문자열을 포함하는 데이터를 모두 찾아서 배열로 반환한다.

  private extractStr = (str: string) => {
    const cur = [];
    for (let i = 0; i < str.length; i++) {
      const c = str[i];
      if (Hangul.isHangul(c)) {
        const extract = Hangul.make(str[i]);
        cur.push(...extract.split(''));
      } else {
        cur.push(str[i]);
      }
    }
  
    return cur;
  };
  
  public containList = (input: string): TrieData[] => {
    if (!input || input.length === 0) return [];
    const containList: TrieData[] = [];
    const extractInput = this.extractStr(input).join('');
  
    const recursion = (node: TrieNode) => {
      if (node === undefined) return;
      if (node.isWord && node.info) {
        node.info.forEach((val: TrieData) => {
          const extractLabel = this.extractStr(val.label).join('');
          if (extractLabel.includes(extractInput)) {
            containList.push(val);
          }
        });
      }
      Object.values(node.next).forEach((n) => {
        recursion(n);
      });
    };
  
    recursion(this.root);
  
    return containList;
  };

• extractStr을 이용하여 문자(음소)를 배열 형태로 추출하고 추출된 문자를 trie에서 찾는다.
• 찾은 문자를 리스트로 반환한다.

useTrie

• useTrie 코드는 다음과 같다.

  import { useMemo, useEffect } from 'react';
  
  import Trie from './Trie';
  import Hangul from './Hangul';
  
  import type { TrieData } from './types';
  
  /**
   * trie Data structure를 생성
   * @param dictionary trie 생성 데이터
   * @param isBuildTrie trie 생성 여부
   * @returns
   */
  function useTrie(dictionary: Array<TrieData>, isBuildTrie: boolean = true) {
    const trie = useMemo(() => new Trie(), []);
  
    useEffect(() => {
      if (isBuildTrie && trie.isDiff(dictionary)) {
        trie.initialize();
        dictionary.forEach((val: TrieData) => {
          const extract = Hangul.make(val.label);
          trie.insert(extract, val);
        });
      }
    }, [trie, dictionary, isBuildTrie]);
  
    return trie;
  }
  
  export default useTrie;

• Trie class를 이용하여 trie를 생성하며 생성된 trie를 반환한다.

사용

const trie = useTrie(
    [
			{
				key: 0,
				label: '하나',
			},
			{
				key: 1,
				label: '하나',
			},
			{
				key: 2,
				label: '한다',
			},
			{
				key: 3,
				label: '한글',
			},
		]
  );