트라이 알고리즘 || Javascript를 이용한 자동완성 기능

소개

접두사 트리라고도 알려진 Trie는 효율적인 정보 검색에 사용되는 특수한 트리 기반 데이터 구조입니다.

문자열 내에서 검색 및 접두사 일치와 관련된 사용 사례에 특히 유용합니다.

1. Trie 알고리즘에 대해 말하면 여러분은 이 알고리즘에 관심이 있을 수도 있고 없을 수도 있습니다

2. 하지만 이것을 사용하면 자동 완성 알고리즘을 만들 수 있습니다. 이 내용을 배우면 더욱 흥미로울 것입니다.

이 알고리즘의 사용 사례

1. 자동완성:

아. 시도는 자동 완성 기능을 구현하기 위해 검색 엔진이나 텍스트 편집기에서 자주 사용됩니다.
비. 입력을 시작하면 애플리케이션은 입력한 접두어를 기반으로 가능한 완성을 제안합니다.

2. 맞춤법 검사기:

아. 맞춤법 검사기를 구현하는 데 시도를 사용할 수 있습니다. 단어가 트라이에 없으면 철자가 틀렸을 가능성이 높습니다.
비. 트리는 유사한 단어를 찾아 수정 사항을 제안할 수도 있습니다.

3. IP 라우팅:

아. 트라이는 라우터에서 라우팅 테이블을 저장하는 데 사용됩니다.
비. 라우터는 가장 긴 접두사와 일치하는 트리를 사용하여 패킷의 다음 홉을 결정합니다.

4. 효율적인 문자열 저장 및 검색:

아. 공유 접두사가 많은 문자열 데이터세트가 있는 경우 trie는 개별적으로 저장하는 것보다 적은 공간을 사용하여 이러한 문자열을 저장할 수 있습니다.
비. 검색 작업은 검색하는 문자열의 길이에 비례하여 시간 복잡도가 높아 효율적입니다.

class Node {
    constructor() {
        this.end = false;
        this.children = {}
    }
}

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

    insert(word) {
        let head = this.root;

        for (let i = 0; i< word.length; i++) {
            if (!head.children[word[i]]) {
                head.children[word[i]] = new Node();
            }
            head = head.children[word[i]];
        }
        head.end = true;
    }

    search(word){
        let current = this.root;

        for (let i = 0; i < word.length; i++) {
            if (!current.children[word[i]]) {
                return false;
            }
            current = current.children[word[i]]
        }

        return true;
    }

    autoComplete(word) {
        let current = this.root;

        for (let i = 0; i< word.length; i++) {
            if (!current.children[word[i]]) {
                return false;
            }
            current = current.children[word[i]];
        }
        if (Object.keys(current.children).length === 1) {
            console.log('Please Type More...');
            return;
        }
        console.log('children =---> ', current.children);

        console.log('Possible Auto Complete Values are --->');
        for (let key in current.children) {
            console.log('---> ', word+key);
        }
    }
}

const test = new Trie();
test.insert('ant');
test.insert('any');
console.log(test.search('ant'));
console.log(test.search('any'));
console.log(test.search('anj'));
test.autoComplete('an')
/*
true
true
false
children =--->  {
  t: Node { end: true, children: {} },
  y: Node { end: true, children: {} }
}
Possible Auto Complete Values are --->
--->  ant
--->  any
*/

우려사항이나 문의사항이 있으면 언제든지 문의해 주세요.

위 내용은 트라이 알고리즘 || Javascript를 이용한 자동완성 기능의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!