[Javascript]Trie - 자동완성 기능 만들기

반응형

✔️Trie란?

• 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조이다. 
• 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어 있는 자료 구조이다. 
• 특히, Trie 자동완성은 검색 엔진, 텍스트 에디터 및 자동완성 기능을 구현하는 데 자주 사용되는 중요한 개념이다.

✔️Trie 자동완성 구현 코드

다음은 전위순회를 이용한 코드이다. 

• insert메서드 : 트라이에 문자열을 삽입한다.
• has메서드 : 문자열의 존재 여부를 확인힌다.
• autoComplete메서드 : 문자열을 자동 완성할 수 있다.
• 자동완성을 위해 Trie를 순회를 한다.
• insert 된 단어만 출력할 수 있도록 Node 클래스에 inserted 속성을 추가했다.

class Node {
    constructor(value = "") {
        this.value = value;
        this.children = new Map();
        this.inserted = false; 
    }
}

class Trie {
    constructor() {
        this.root = new Node();
    }

    insert(string) {
        let currentNode = this.root;

        for (const char of string) {
            if (!currentNode.children.has(char)) {
                currentNode.children.set(
                    char,
                    new Node(currentNode.value + char)
                );
            }
            currentNode = currentNode.children.get(char);
        }

         //insert된 단어인지 판별하기 위한 플래그 추가
         currentNode.inserted = true;
    }

    //자동완성 함수 
    autoComplete(string) {
        let currentNode = this.root;
        let result = [];

        if(!string){
            return "입력이 없습니다.";
        }

        // string 문자열까지 노드 이동
        for (const char of string) {
            if (!currentNode.children.has(char)) {
                return "추천 검색어가 없습니다.";
            } else {
                currentNode = currentNode.children.get(char);
            }
        }

        //순회 함수
        const preorder = (node) => {

            //insert되어있는 단어라면 result에 추가 
            if ( node.inserted) {
                result.push(node.value);
            }

            // 자식 노드를 순회
            for (const childNode of node.children.values()) {
                preorder(childNode);
            }
        };

        preorder(currentNode); 

      

        return result;
    }

    has(string) {
        let currentNode = this.root;

        for (const char of string) {
            if (!currentNode.children.has(char)) {
                return false;
            }
            currentNode = currentNode.children.get(char);
        }
        return true;
    }
}

const trie = new Trie();
trie.insert("cat");
trie.insert("can");
trie.insert("par");
trie.insert("p");
trie.insert("party");
trie.insert("pan");
trie.insert("peek");

console.log(trie.has("par"));
console.log(trie.has("can"));
console.log(trie.has("cap"));

console.log(trie.autoComplete("p")); //['p', 'par', 'party', 'pan', 'peek']
console.log(trie.autoComplete("ca")); //['cat', 'can']

 

 

✔️코드 작성 과정 중 발생한 오류

0. 처음에 다음과 같은 조건일 경우 result에 단어를 포함하도록 했다.  

 // 현재 노드가 단어의 끝인 경우 결과에 추가
if (node.children.size==0) {
      result.push(node.value);
}

발생한 오류:

처음에 잘 나오는 줄 알았으나 p를 자동완성 검색한 결과 'p'와 'pa'를 제외한 ['party', 'pan']만 나오면서 잘못된 결과가 나오는 것을 확인할 수 있었다. 

 

원인:  

preorder 함수 내에서 노드가 단어의 끝인 경우에만 결과에 추가되기 때문이었다.

par의 경우 party까지 끝까지 이동한 후에 result에 포함되는 식이었기에  p나 par과 같이 다른 단어에 포함된 경우 result에 들어가지 않았던 것이다. 

 

해결: 

-조건을 삭제한다. 

조건을 삭제함으로써 Insert 된 다른 단어와 겹쳐도 자동완성 result에 포함될 수 있도록 한다. 다만, insert 되지 않은 단어가 result에 들어가는 것을 막을 방안이 필요하다. 

 

-노드에 inserted속성을 추가한다. 

단어의 끝에 도달했을 때 해당 노드에 inserted 플래그를 True로 설정하도록 한다. 

insert 메서드로 추가된 단어만이 autoComplete 함수에서 출력된다.

 

 

+해결과정에서 추가로 알게 된 것 

노드 클래스에 inserted속성을 초기화하지 않은 상태에서 currentNode.inserted = true;라는 코드를 작성했음에도 오류가 발생하지 않았다.

이유:

JavaScript는 속성을 초기화하지 않은 경우 해당 속성을 undefined로 간주하지 않고 그냥 무시한다. 따라서 초기화하지 않은 속성을 사용할 때 오류가 발생하지 않을 수 있다. 그러나 안전하고 명확한 코드를 작성하기 위해 항상 속성을 초기화하는 것이 좋다. (by chat GPT)

 

 

➕추가 코드

BFS활용한 코드 이다. 

class Node {
    constructor(value = "") {
        this.value = value;
        this.children = new Map();
        this.inserted = false; 
    }
}

class Trie {
    constructor() {
        this.root = new Node();
    }

    insert(string) {
        let currentNode = this.root;

        for(const char of string){
            if(!currentNode.children.has(char)) {
                currentNode.children.set(
                    char,
                    new Node(currentNode.value + char)
                );
            }
            currentNode = currentNode.children.get(char);
        }

        //insert된 단어인지 판별하기 위한 플래그 추가
        currentNode.inserted = true;
    }




    autoComplete(string) {
        let currentNode = this.root;
        let result = [];

        if(!string){
            return; 
        }

        // 주어진 단어와 일치하는 부분까지 이동
        for (const char of string) {
            if (!currentNode.children.has(char)) {
                return "추천 검색어가 없습니다.";
            } else {
                currentNode = currentNode.children.get(char);
            }
        }
        
        const queue = [currentNode];

        while (queue.length > 0) {
            const node = queue.shift();
            
            // 현재 노드가 단어의 끝인 경우 결과에 단어 추가
            if ( node.inserted) {
                result.push(node.value);
            }

            // 자식 노드들을 큐에 추가
            for (const childNode of node.children.values()) {
                queue.push(childNode);
                
            }
        }

        return result;
    }

    has(string) {
        let currentNode = this.root;

        for (const char of string) {
            if(!currentNode.children.has(char)){
                return false;
            }
            currentNode = currentNode.children.get(char);
        }
        return true;
    }



}

const trie = new Trie();
trie.insert("cat");
trie.insert("can");
trie.insert("p");
trie.insert("party");
trie.insert("pan");
trie.insert("peek");
console.log(trie.has("cat"));
console.log(trie.has("can"));
console.log(trie.has("cap"));

console.log(trie.autoComplete("p"));