trie는 효과적인 데이터 구조로 문제를 해결하는 도구 상자에 잘 추가할 수 있다.Trie의 사용이 표준set이나 맵보다 어떤 면에서 더 적용되는지 보여 줍니다.너는 또 그것을 사용하면 어떤 이익을 얻을 수 있느냐.

식욕을 돋우는 술

접두사 트리나 숫자 트리보다 트리라는 이름을 더 좋아합니다. 비록 접두사 트리가 가장 정확한 정의임에도 불구하고.trie라는 이름은retrieval에서 왔지만 발음은 "try"이지 "tree"가 아닙니다.이 생각은 나무와 나무를 구분하기 위한 것이다.
트리가 뭔지 알아맞혀 봐.나는 네 가지 단어로 트리를 구축했다. 사과, 바나나, 사생아, 금지령:

나는 a visualization tool from the University of San Franciscotrie를 사용하는 것을 강력히 건의합니다.
Trie는 시퀀스(일반적으로 문자열)로 표현된 키를 컴팩트하게 저장합니다.그 다음에 키를 조회하기 위해 집합이나 해시 맵으로 사용할 수 있습니다.이외에도 키 접두사를 통해 키와 값을 조회할 수 있습니다.

순진한 실현

나는 최상의 알고리즘에 관심을 두지 않는다.본문의 목적은trie를 익히고 언제 사용할 수 있는지를 익히는 것입니다.
필요한 API를 설계합니다.

// Trie represents a Trie data structure.
//
// https://en.wikipedia.org/wiki/Trie
type Trie interface {
    // Insert inserts a word into the trie and returns true
    // if the word already exists.
    Insert(word string) bool
    // Contains returns true if an exact match of the word is found, otherwise false.
    Contains(word string) bool
    // SearchByPrefix finds and returns words by prefix.
    SearchByPrefix(prefix string) []string
    // StartsWith returns true if there is any word in the trie that starts
    // with the given prefix.
    StartsWith(prefix string) bool
    // Size returns the number of keys in the tree.
    Size() int
}

이 두 가지 기능을 실현하면 충분하다. 바로 Insert와 Contains이다. 이 생각을 이해하기 위해서다.이것은 다음과 같은 개선의 합리적인 기초가 될 것이다.
나는 통용 룬trie를 실현하기 시작했다.In Go rune은 ASCII의 하이퍼집합으로, 유니코드 코드 코드 점을 나타냅니다.Java 또는 C에서는 문자 유형으로 볼 수 있지만 유니코드에서는 그렇습니다.
따라서 삽입 함수는 최적화되지 않고 첫 번째 간단한 실현일 뿐이다.

// runeTrie is a rune-wise trie implementation.
type runeTrie struct {
    root *runeNode
    size int
}

type runeNode struct {
    children map[rune]*runeNode
    last     bool
}

// NewRuneTrie creates a rune-wise new trie.
func NewRuneTrie() Trie {
    return &runeTrie{root: &runeNode{make(map[rune]*runeNode), false}}
}

// Insert inserts a word into the trie and returns true
// if the word already exists.
func (t *runeTrie) Insert(word string) bool {
    exists := true
    current := t.root
    for _, letter := range word {
        n, ok := current.children[letter]
        if !ok {
            exists = false

            n = &runeNode{make(map[rune]*runeNode), false}
            current.children[letter] = n
        }

        current = n
    }
    current.last = true

    if !exists {
        t.size++
    }

    return exists
}

알고리즘은 간단합니다.

현재 노드 값을 루트로 설정합니다.

단어의 각 자모:

현재 노드에 문자가 포함되어 있는지 확인하고 없으면 문자에 새 노드를 만들어 현재 노드에 추가합니다.

그러나 문자가 포함된 경우 해당 문자 아래의 노드를 가져와 현재 노드로 설정합니다.돌아가다

마지막 처리된 노드를 단어의 끝으로 표시합니다.

Contains 함수는 훨씬 간단하고 간단해 보입니다.

// Contains returns true if an exact match of the word is found, otherwise false.
func (t *runeTrie) Contains(word string) bool {
    n, _ := t.nodeByPrefix(word)

    return n != nil && n.last
}

func (t *runeTrie) nodeByPrefix(prefix string) (*runeNode, rune) {
    current := t.root
    var r rune
    for _, letter := range prefix {
        n, ok := current.children[letter]
        if !ok {
            return nil, 0
        }

        current = n
        r = letter
    }

    return current, r
}

우리는 마지막 노드까지 자모를 통해 나무를 두루 돌아다녔다.
이 실현에 대해 기준 테스트를 진행합시다.Go에는 간단한 벤치마크 테스트를 작성하는 도구가 있습니다.

func BenchmarkRuneTrieInsert(b *testing.B) {
    var r bool
    for i := 0; i < b.N; i++ {
        t := NewRuneTrie()
        for _, w := range words {
            r = t.Insert(w)
        }
    }

    benchmarkResult = r
}

그런 다음 벤치마크 테스트를 실행합니다.

$ go test -bench=. -benchmem -benchtime=1000x
goos: darwin
goarch: amd64
op         0 allocs/op
BenchmarkRuneTrieInsert-8               1000          7196 ns/op        6984 B/op        129 allocs/op
BenchmarkRuneTrieContains-8             1000           517 ns/op           0 B/op          0 allocs/op
BenchmarkWordHashSetInsert-8            1000          1406 ns/op        1100 B/op          4 allocs/op
BenchmarkWordHashSetContains-8          1000           178 ns/op           0 B/op          0 allocs/op
PASS

Go bench 도구는 창고 분배를 계산하지 않기 때문에Contains 함수에 더미 분배가 포함되지 않는 것을 보았습니다. 이것은 매우 좋습니다.
Trie Fabric을 사용하면 일반적인 해시 매핑에 사용할 수 없는 함수인 SearchByPrefix를 추가할 수 있습니다.

// Finds and returns words by prefix.
func (t *runeTrie) SearchByPrefix(prefix string) []string {
    node, r := t.nodeByPrefix(prefix)

    return search(node, r, []rune(prefix[:len(prefix)-1]))
}

func (t *runeTrie) nodeByPrefix(prefix string) (*runeNode, rune) {
    current := t.root
    var r rune
    for _, letter := range prefix {
        n, ok := current.children[letter]
        if !ok {
            return nil, 0
        }

        current = n
        r = letter
    }

    return current, r
}

func search(currentNode *runeNode, currentRune rune, prefix []rune) []string {
    words := []string{}
    if currentNode == nil {
        return words
    }

    newPrefix := append(prefix, currentRune)
    if currentNode.last {
        words = append(words, string(newPrefix))
    }

    for letter, node := range currentNode.children {
        newWords := search(node, letter, newPrefix)
        words = append(words, newWords...)
    }

    return words
}

함수는 최적화를 거치지 않았지만, 이것은 가능하다는 것을 보여 주었고, 그리 복잡하지도 않다.이것은 앞에서 정의한 함수 nodeByPrefix 를 호출합니다.

응용 프로그램

자동 완성

trie는 접두사에 따라 단어를 검색할 수 있기 때문에 자동 보완 알고리즘의 좋은 후보자입니다.

경로

fasthttp library for Gotrie를 루트의 내부로 사용한다.그것은 루트가 가장 빨리 실현될 수 있을 뿐만 아니라, 어떠한 쓰레기도 생기지 않을 것이다.
네가 원한다면 할 수 있다can dive deeper.

기타 선택

필요한 경우:

찾기 집합을 접두사에 따라 실행해야 할 수도 있습니다.

비슷한 양의 데이터를 컴팩트하게 저장합니다.

구조를 구축하고 조회를 진행한다.

최는 아마도 너의 좋은 인선일 것이다.
예를 들어 프로그램이 시작될 때 메모리의 하위 필드를 포함하는 그룹을 만들고 그것만 조회합니다.너는 이 임무를 위해 테스트를 한 번 하는 것을 고려할 수 있다.
그러나 어쨌든 당신의 성능 가설을 반드시 기준으로 검사해야 한다.
접두사에 따라 찾을 필요가 없고 데이터 구조가 크게 바뀌고 있다면, 해시 맵이나 해시 집합이 더 좋은 선택입니다.

알려진 Trie 구현

나는 Trie의 예시적인 실현을 가진 두 개의 감동적인 라이브러리를 발견했다.

https://github.com/siongui/go-succinct-data-structure-trie

https://github.com/celzero/gotrie

사용 가능mine하지만 학습 목적으로 최적화 및 제작된 것은 아닙니다.