디자인 모드가 있는 Trie 데이터 구조

소개하다.
이 문서에서는 Trie 데이터 구조를 위해 다양한 설계 원칙과 모델을 사용하는 방법을 보여 드리겠습니다.Trie 데이터 구조를 실현하고 서로 다른 알고리즘을 시도한 후에 이런 생각이 들었어요.
최종 결과는 서로 다른 디자인 모델과 원칙의 응용, 그리고 그것들을 사용하는 장점을 나타냈다.

비밀 번호
전체 코드는github에서 얻을 수 있습니다: Trie data structure

데이터 구조
Trie 데이터 구조도 접두사 트리라고도 부른다. 이 데이터 구조의 주요 목표는 간단한 방법을 제공하는 것이기 때문에 문자열의 문자에 따라 문자열을 하나씩 검색하고 기본적으로 접두사에 따라 검색한다.
이런 데이터 구조는 자동 완성과 맞춤법 검사 등 많은 응용이 있다.나는 이 예가 leetcodeTrie leetcode solution 해결 방안의 사용 가능성을 잘 설명한 것을 발견했다.
나는 알고리즘 자체의 실현에 중점을 두지 않을 것이다.당신은 기본적으로 어느 곳에서든 실현을 찾을 수 있습니다.만약 네가 스스로 하고 싶다면, 나는 Tushar Roy를 유튜브에 추천한다.나의 해결 방안은 그의 해석에 기초를 두고 있다.만약 네가 비교하고 싶다면, 너는 심지어 그의 실현을 볼 수 있을 것이다.

클래스 및 인터페이스
코드는 세 개의 다른 패키지로 나뉜다.

트리에

노드

알고리즘

trie 세트

ITrie 인터페이스
trie 데이터 구조는 인터페이스 ITrie 인터페이스를 사용하여 표시합니다.
이 인터페이스는 trie 데이터 구조의 기본 동작을 정의합니다.

voidsettrie 알고리즘(itrie 알고리즘trie 알고리즘);

ITrieAlgorithm GettrieAlgorium();

ITrieNode getRoot();

빈 삽입자(문자열자);

블로 삭제자(문자열자);

부울 값(문자열),

블컨테이너리픽스(문자열 접두사);

이러한 추상적인 방법은 Trie 역할을 하려는 모든 클래스에서 이루어져야 합니다.
처음 세 가지 방법은 Trie를 조합하여 Trie 알고리즘과 분리하는 방법을 제공합니다.
'setTrieAlgority' 방법은 실행할 때 Trie의 알고리즘을 변경할 수 있도록 합니다.

ITRI의 실현
ITrie 인터페이스에는

TrieArray: 배열 기반 노드 사용

TrieMap: 지도 기반 노드 사용

이러한 실현된 명칭은 그들이 특정한 유형의 세 노드를 사용하는 데서 비롯된다.예를 들어 TrieArray는 Trie 데이터 구조의 노드 유형으로 TrieNodeArray를 사용합니다.
이 노드들은 특정한 데이터 구조(예를 들어 수조와 맵)를 사용하여 각 노드의 서로 다른 문자를 저장한다.
ITrie 인터페이스는 실행할 때trie 알고리즘을 바꾸는 방법을 정의합니다.이것은 유형의 조합을 통해 실현된 것이다.trie 실현은 하나의trie 알고리즘으로 구성되어 있으며 이 알고리즘은 실제적으로 서로 다른 조작을 수행한다.
따라서 인터페이스에 행동을 제공하는 방법의 실현은 매우 간단하다.

 @Override
    public void insertWord(String word) {
        trieAlgorithm.insertWord(this, word);
    }

    @Override
    public boolean deleteWord(String word) {
        return trieAlgorithm.deleteWord(this, word);
    }

    @Override
    public boolean containsWord(String word) {
        return trieAlgorithm.containsWord(this, word);
    }

    @Override
    public boolean containsPrefix(String prefix) {
        return trieAlgorithm.containsPrefix(this, prefix);
    }

이러한 사용위탁을 실현하고 조작의 책임을 조합의trie 알고리즘에 전달한다.이것은 일리가 있는 것이다. 왜냐하면 실제 조작은 알고리즘에 달려 있기 때문이다.
trie 알고리즘은 구조 함수에 주입됩니다.

    public TrieArray(ITrieAlgorithm trieAlgorithm) {
        setTrieAlgorithm(trieAlgorithm);
        this.root = new TrieNodeArray();
    }

    @Override
    public void setTrieAlgorithm(ITrieAlgorithm trieAlgorithm) {
        this.trieAlgorithm = trieAlgorithm;
    }

이것은 TrieArray의 구조 함수로 TrieMap의 구조 함수와 유사하다.
구조 함수는 ITrie Algorithm 인터페이스 유형을 가진 알고리즘을 수신하고 그에 상응하는 방법으로 필드'Trie Agorithm'에 분배한다.
하나의 인터페이스를 알고리즘의 유형으로 사용하고 구조 함수에 그것을 분배하며 의존 주입을 허용하는 것은 의존 역치 원칙을 실현하는 메커니즘이다.우리는 또한 설계 원칙을 응용했다. "프로그램이 인터페이스에 들어가는 것이지 실현되는 것이 아니다."
이것은 Trie 데이터 구조를 알고리즘 내부의 세부 사항과 분리하는 방법을 제공한다.ITrie 인터페이스의 실현은 ITrie 알고리즘 인터페이스의 실현을 진정으로 이해하거나 관심을 가지지 않는다.Trie는 이러한 실현된 행동에만 관심을 갖는다.
너는 변화의 축에 따라 사물을 봉하고 조를 나누어 보아야 한다.너는 같은 원인으로 같은 속도로 변화하는 사물을 한데 조합해라.이런 상황에서 Trie 데이터 구조는 매우 안정적인 구성 요소로 인터페이스와 실현이 자주 변경될 수 없다.다른 한편, 우리는 서로 다른 알고리즘이 실현되어 자주 바뀔 수 있다.예를 들어, 귀하는 알고리즘의 내부 세부 사항을 변경하기로 결정했습니다. 예를 들어 귀속 호출이나 알고리즘에서 내부 데이터 구조를 사용하기로 결정했습니다.이러한 변경 사항은 Trie 데이터 구조에 영향을 주어서는 안 됩니다.
전략 모드
이 정의는 Head First Design Patterns라는 책에서 따온 것이다(우수한 책!):
"전략 모델은 일련의 알고리즘을 정의했다.
하나하나를 봉하여 교환할 수 있도록 하다.
정책은 알고리즘이
그것을 사용하는 고객."
이 예에서는 ITrie Algorithm 인터페이스를 사용하여 일련의 알고리즘을 정의했습니다.
서로 다른 실현: 교체, 귀속, 귀속 2는 서로 바꾸어 사용할 수 있다.너무 좋아요!우리는 변경된 부분을 특정한 인터페이스로 봉할 것이다.현재 클라이언트나 Trie 데이터 구조를 사용하는 모든 사람들은 특정한 실현에 의존하지 않는다.만약 네가 더욱 좋은 새로운 방법을 생각해 내서 알고리즘을 실현한다면, 너는 인터페이스만 실현하면 된다.새 알고리즘을 사용하여 setter 메소드를 대체할 수 있습니다.Trie 클래스의 어떤 내용도 변경할 필요가 없습니다!

ITRIE 알고리즘 인터페이스
이 인터페이스는 Trie 알고리즘에 적용되어야 하는 일반적인 동작을 정의합니다.

public interface ITrieAlgorithm {

    void insertWord(ITrie trie, String word);

    boolean deleteWord(ITrie trie, String word);

    boolean containsWord(ITrie trie, String word);

    boolean containsPrefix(ITrie trie, String prefix);
}

메소드 서명에서 주의해야 할 중요한 사항은 ITrie 매개 변수입니다.이러한 알고리즘은 Trie 데이터 구조가 실현되는 실제 세부 사항을 알거나 관심을 가질 필요가 없다. ITrie 인터페이스만 실현하고, 더욱 구체적으로 말하면 getRoot 방법에 실현을 제공할 것이다. 우리는 다음 절에서 볼 수 있다.

ITRIE 알고리즘의 실현
ITrie 인터페이스에는

교체 알고리즘

귀속 알고리즘

3차 귀속 알고리즘 2

이 이름들은 스스로 묘사한 것이다.우리는 순환하는 교체 방법을 사용하는 알고리즘이 있다.다른 하나는 귀속 방법을 사용한다.
"insertWord"접근 방식을 살펴보겠습니다.

    /**
     * Insert a word in the trie
     *
     * @param trie The Trie where the word will be inserted
     * @param word The word to insert
     */
    @Override
    public void insertWord(ITrie trie, String word) {
        insertWord(trie.getRoot(), word);
    }

    /**
     * Helper method that inserts the word in the Trie.
     * This algorithm sets the "isEndOfWord" flag to the trieNode that the last character points.
     *
     * @param trieNode The trieNode to insert the character
     * @param word     The word to insert
     */
    private void insertWord(ITrieNode trieNode, String word) {
        char currentChar;
        for (int i = 0; i < word.length(); i++) {
            currentChar = word.charAt(i);
            if (!trieNode.containsCharacter(currentChar)) {
                trieNode.addCharacter(currentChar);
            }
            trieNode = trieNode.getTrieNodeForChar(currentChar);
        }
        trieNode.setEndOfWord(true);
    }

insertWord 방법은 trie를 ITrie 유형의 매개 변수로 수신합니다.이 알고리즘은 내부 실현에 무관심하고 getRoot 방법을 통해 루트 노드를 가져와 계속 조작한다.
이제 helper 방법을 살펴보자.이 수신 인터페이스 유형은 ITrieNode의 노드입니다.마찬가지로 이 알고리즘은 노드의 실제 실현 방식에 진정으로 관심이 없다.배열을 사용하든 스티커를 사용하든 알고리즘은 똑같다.이 알고리즘이 Trie와 노드의 완전한 결합을 이루기 때문에 매우 중요한 세부 사항이다.그것은 어떠한 실현에서도 운행할 수 있다.이는 동일한 알고리즘을 서로 다른 Trie 구현 인스턴스에 적용할 수 있음을 의미합니다.

디자인 모델과 응용 원칙 개술

각종 변화: 알고리즘의 실제 실현을 요약했다.

계승이 아닌 조합을 지원한다.Trie 데이터 구조는'조합'알고리즘을 사용하는데 이 알고리즘은 구조 함수에서 전달된다.

프로그램이 인터페이스에 도착하는 것이지 실현이 아니다. ITrie, ITrieNode와 ITrie 알고리즘은 서로 다른 실현에서 사용하는 인터페이스이다.특정한 실현에 대한 인용이나 의존이 없다.이것은 서로 다른 구성 요소가 결합되어 독립적으로 수정할 수 있다는 것을 의미한다.

개방/폐쇄 원칙: 알고리즘이 변할 때마다 Trie 데이터 구조는 진정으로 관심을 가지지 않는다. 실현에 의존하지 않기 때문에 당신은 새로운 알고리즘을 수정하거나 만들 수 있고 Trie 데이터 구조 클래스의 어떤 내용도 변경할 필요가 없다!반대로 해도 마찬가지다.Trie에서 새로운 Trie에 적용되는 데이터 구조를 변경할 수 있습니다.분명히 모든 것은 종류별로 정의된 인터페이스를 통해 이루어질 수 있다.이 계약들을 준수하기만 한다면 모든 것이 좋아야 한다.

추상에 의존한다.특정 클래스에 의존하지 마십시오. 우리는 의존 역치 원칙을 적용하여 원본 코드를 Trie에서 구체적인 알고리즘에 의존합니다.이제 Trie와 알고리즘은 모두 추상에 의존한다.Trie는 이 알고리즘의 어떤 구체적인 실현도 모르고 인터페이스만 사용한다.알고리즘도 마찬가지다.알고리즘의 어떠한 실현도 Trie/trieode의 구체적인 실현에 의존하지 않고 추상적, ITrie, ITrieNode에만 의존한다.

마지막 말
이것은 간단한 예로 어떻게 서로 다른 디자인 원칙과 모델을 흔한 임무에 응용하는지, 예를 들어 정의된 데이터 구조에 따라 자신의 알고리즘을 만들어 실현하는지를 설명한다.서로 다른 디자인 원칙을 응용하면 본고에서 기술한 많은 장점을 제공할 수 있다.