어떻게 Swift 에서 사전 트 리 를 사용 합 니까?

A Trie in Swift 원문 날짜: 2015 / 08 / 11
대장장이 Linus 교정: numbbbb 원고: numbbbb
(이 글 의 코드 는 여기에서 다운로드 할 수 있 습 니 다) Google 에서 '멋 진 데이터 구조' 를 검색 하면 이 결 과 를 먼저 볼 수 있 습 니 다.그 중에서 주로 stackoverflow 의 문제 입 니 다. "우리 가 잘 모 르 지만 유용 한 데이터 구조 가 무엇 입 니까?"'좋아요' 를 가장 많이 누 른 답 은 이번 주 주제 인 사전 트 리 다.읽 어 보 니 멋 진 것 이 사전 트 리 의 용도 에 관 한 것 이 많 았 다.그리고 나 서 나 는 플레이 그라운드 를 열 고 이 글 을 쓰기 시작 했다.
사전 나 무 는 접두사 나무의 일종 이다.이것 은 재 귀적 인 데이터 구조 입 니 다. 모든 사전 트 리 는 하위 사전 트 리 를 포함 하고 하위 사전 트 리 는 접 두 사 를 통 해 식별 합 니 다.
사전 트 리 라 는 데이터 구 조 는 광범 위 하 게 사 용 될 뿐만 아니 라 유용 한 응용 도 있다.그것 도 set 와 같은 조작 이 있다. 예 를 들 어 삽입 과 검색 은 모두 O(n) 복잡 도 이 고 그 중에서 n 은 검색 서열 의 길이 이다.현재 set 는 해시 화 (hashable) 와 요소 가 무질서 화 되 는 가장 좋 은 방법 이다.그러나 찾 으 려 는 시퀀스 의 요소 가 해시 화 되 어 있다 면 사전 트 리 가 적합 합 니 다.(한 가지 주의해 야 할 것 은 Set 자체 가 해시 화 되 어 있 기 때문에 저장 할 순서 가 무질서 하 다 면 Set 의 집합 이 더욱 적합 할 것 입 니 다)
A trie for keys “A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, and “inn”.
Swift 에서 우 리 는 사전 트 리 에 일련의 접두사 와 하위 사전 트 리 를 포함 하여 실현 할 수 있 습 니 다.코드 는 다음 과 같 습 니 다:

public struct Trie {
  private var children: [Element:Trie]
}

사전 트 리 에 사전 트 리 를 직접 저장 하 는 것 이 아니 라 하위 사전 트 리 를 참조 하 는 사전 형식 을 저장 합 니 다.이 사전에 서 접 두 사 를 키 로 삼 아 라.그럼 어떻게 초기 화 할 까요?목록 처럼 생 성기 의 분해 속성 을 사용 할 수 있 습 니 다.

extension Trie {
  private init(var gen: G) {
    if let head = gen.next() {
      children = [head:Trie(gen:gen)]
    } else {
      children = [:]
    }
  }
  public init
    
    (_ seq: S) {
      self.init(gen: seq.generate())
  }
}

그것 으로 는 턱 없 이 부족 하 다.우 리 는 하나의 서열 을 저장 해 야 할 뿐만 아니 라 insert 조작 도 필요 하 다.

extension Trie {
  private mutating func insert
    
    (var gen: G) {
      if let head = gen.next() {
        children[head]?.insert(gen) ?? {children[head] = Trie(gen: gen)}()
      }
  }
  public mutating func insert
    
    (seq: S) {
      insert(seq.generate())
  }
}

위 에 코드 가 이상 하 게 보 입 니 다.

children[head]?.insert(gen) ?? {children[head] = Trie(gen: gen)}()

솔직히 나 도 이런 문법 을 별로 좋아 하지 않 는 다.선택 가능 한 체인 의 가 변 방법 (mutating methods) 을 호출 할 수 있 습 니 다.이 예 에서 호출 할 때 선택 할 수 있 는 값 은 사전 에서 찾 아서 되 돌려 줍 니 다. 만약 우리 가 삽입 작업 을 할 때 이 값 이 존재 한다 면 우 리 는 이 값 을 수정 할 것 입 니 다.
존재 하지 않 는 다 면 이 추가 동작 을 처리 해 야 합 니 다.우 리 는 사전 나 무 를 뽑 아 볼 수 있다. 이렇게:

if let head = gen.next() {
  if var child = children[head] {
    child.insert(gen)
  } else {
    children[head] = Trie(gen: gen)
  }
}

그러나 코드 에 있 는 하위 사전 트 리 는 우리 가 수정 하고 자 하 는 진정한 하위 사전 트 리 의 복사 일 뿐이다.우 리 는 나중에 그것 을 사전 에 넣 을 것 이다. 비록 지금 은 헛 된 일 을 하고 있 는 것 처럼 보이 지만.
우 리 는 반환 값 이 없어 보 이 는 함수 들 이 사실은 특수 한 값 을 되 돌려 주 는 것 을 알 고 있다. Void 또는 () 이 라 고 한다.본 논문 에서 ()? (또는 Optional 도 이런 유형 에 속한다.우 리 는 관심 이 없다 void 자체 가 분명 하 다. 우 리 는 옳 고 그 름 에 만 관심 이 있다 nil.그래서 우 리 는 이렇게 할 수 있다.

if let _ = children[head]?.insert(gen) { return }
children[head] = Trie(gen: gen)

또는 사용 guard:

guard let _ = children[head]?.insert(gen) else { children[head] = Trie(gen: gen) }

그러나 나 는 nil coalescing 연산 자 를 사용 하 는 것 이 더 좋 고 let 또는 _ 이해 에 대한 방 해 를 줄 일 수 있다 고 생각한다.
사전 트 리 라 는 데이터 구조 가 상식 적 으로 나 오지 않 는 것 같 습 니 다.처음에는 변이 방법 으로 사전 트 리 를 쉽게 되 돌 릴 수 있 었 다.그 밖 에 기본적으로 모든 방법 이 사전 트 리 전 체 를 포함 하기 때문에 타성 로드 는 거의 불가능 하 다.(누가 타성 로드 를 실현 하 는 효과 적 인 방법 을 생각해 낼 수 있다 면 알려 주세요.)
사전 트 리 에서 가장 중요 한 contains 함 수 는 다음 과 같 습 니 다.

extension Trie {
  private func contains
    
    (var gen: G) -> Bool {
      return gen.next().map{self.children[$0]?.contains(gen) ?? false} ?? true
  }
  public func contains
    
    (seq: S) -> Bool {
      return contains(seq.generate())
  }
}

이곳 에는 많은 생 성 기 를 사용 했다.생 성기 가 비어 있 으 면 gen.next() 되 돌아 오기 nil 사전 트 리 는 현재 요소 만 있 기 때문에 서열 을 포함 합 니 다.map() 생 성기 에서 다음 요 소 를 찾 아 되 돌려 줍 니 다.돌아 오 는 것 이 nil 이 라면 사전 트 리 는 이 서열 을 포함 하지 않 습 니 다.마지막 으로 나머지 생 성 기 를 포함 하 는 하위 사전 나 무 를 되 돌려 줍 니 다. 있 으 면 true 이 고 없 으 면 false 입 니 다.밤 을 들다

var jo = Trie([1, 2, 3])
jo.insert([4, 5, 6])
jo.insert([7, 8, 9])
 
jo.contains([4, 5, 6]) // true
jo.contains([2, 1, 3]) // false

여기 작은 문제 가 있 습 니 다.contains 방법 은 우리 가 상상 하 는 것 처럼 다음 코드 를 실행 할 수 없다.

jo.contains([1, 2]) // true

생 성기 에 데이터 가 없 으 면 되 돌아 오기 true 때문에 사전 트 리 는 삽 입 된 시퀀스 마다 접 두 사 를 '포함' 합 니 다.이것 은 결코 우리 가 원 하 는 것 이 아니다.하나의 해결 방안 은 마지막 사전 트 리 에 하위 노드 가 없 을 때 만 되 돌아 오 는 것 이다 true.수정 후 다음 과 같 습 니 다:

extension Trie {
  private func contains
    
    (var gen: G) -> Bool {
      return gen.next().map{self.children[$0]?.contains(gen) ?? false} ?? children.isEmpty
  }
}

하지만 이 건 소 용이 없 는 것 같 습 니 다.우리 가 호출 jo.insert([1, 2]) 하면 어떻게 될 까?우 리 는 반환 값 이 false 이 고 사전 트 리 는 포함 되 어 있 지 않다 는 것 을 발견 했다 [1, 2].
이러한 상황 에 대해 서 는 사전 트 리 가 시퀀스 의 끝 에 있 는 지 여 부 를 표시 하기 위해 서 추가 불 변수 가 필요 합 니 다.

public struct Trie {
  private var children: [Element:Trie]
  private var endHere : Bool
}

우리 도 생 성기 가 되 돌아 올 때 insert 초기 화 init 할 수 있 도록 우리 nil 와 endHere 방법 을 수정 해 야 한다.

extension Trie {
  private init(var gen: G) {
    if let head = gen.next() {
      (children, endHere) = ([head:Trie(gen:gen)], false)
    } else {
      (children, endHere) = ([:], true)
    }
  }
}
 
extension Trie {
  private mutating func insert
    
    (var gen: G) {
      if let head = gen.next() {
        children[head]?.insert(gen) ?? {children[head] = Trie(gen: gen)}()
      } else {
        endHere = true
      }
  }
}

이 동시에 true 방법 은 contains 변 수 를 되 돌려 주 고 더 이상 endHere 이 아니다.

public extension Trie {
  private func contains
    
    (var gen: G) -> Bool {
      return gen.next().map{self.children[$0]?.contains(gen) ?? false} ?? endHere
  }
}

우리 가 최적화 true 방법 을 사용 할 때 contains 코드 의 가 독성 을 증가 시 킬 수 있다.

public extension Trie {
  private func contains<
    G : GeneratorType where G.Element == Element
    >(var gen: G) -> Bool {
      guard let head = gen.next() else { return endHere }
      return children[head]?.contains(gen) ?? false
  }
}

Chris Eidhof 는 나 에 게 다음 과 같은 건 의 를 했다.
This is how Swift 2 improves our Functional Data Structures chapter in @FunctionalSwift : pic.twitter.com/LgwCBm7zA6 — Chris Eidhof (@chriseidhof) August 6, 2015
(분명히 이것 은 그의 Functional Programming in Swift 의 사전 트 리 가 이 루어 진 것 입 니 다. 저 는 본 적 이 없습니다. 지금 보 러 가 려 고 합 니 다. Advanced Swift 가 전 자 를 뛰 어 넘 을 수 있다 면 재 미 있 을 것 입 니 다.)
우 리 는 사전 트 리 가 Set 처럼 모든 집합, 교 집합 방법 을 사용 할 수 있 기 를 바란다.반면 guard, insert 와 init 방법 은 이미 실현 되 었 고 contains 방법 은 실현 되 지 않 았 다.remove 방법 이 좀 어려워 보 여요.당신 은 서열 의 끝 에서 삭제 한 후에 remove 를 endHere 에서 true 로 바 꿀 수 있 습 니 다. 사실은 이것 은 아무 소 용이 없습니다.내 말 은 작업 을 삭제 한 후에 도 같은 정 보 를 저장 하 겠 다 는 것 이다.당신 이 진정 으로 필요 로 하 는 작업 은 더 이상 사용 하지 않 는 가 지 를 삭제 하 는 것 입 니 다.
말하자면 이 일 은 좀 복잡 하 다.삭제 하고 싶 은 것 만 찾 은 후에 모든 하위 노드 를 삭제 합 니 다.다른 입구 점 (entries) 을 삭제 할 수 있 기 때문에 이렇게 하면 안 됩 니 다.하위 노드 만 있 는 사전 트 리 를 삭제 할 수 없습니다. 하위 노드 가 나중에 연 장 될 수 있 기 때문에 삭제 하고 싶 은 시퀀스 의 접두사 도 포함 할 수 있 습 니 다.
중요 한 것 은 주어진 입 구 를 삭제 할 수 있 는 지 없 는 지 에 대한 모든 정 보 는 사전 트 리 의 하위 노드 에서 나온다.그래서 나 는 재 귀적 으로 변이 방법 을 호출 하여 실현 하기 로 결 정 했 고 이 방법 은 중요 한 값 을 되 돌려 줄 것 이다.이러한 상황 에서 이 중요 한 값 은 불 형식 으로 사전 트 리 가 삭 제 될 수 있 는 지 를 나타 낸다.저 는 개인 적 인 방법 으로 생 성 기 를 만 들 고 공유 포장 방법 으로 서열 을 처리 하기 때문에 공공 방법 에서 불 유형 을 되 돌려 삭제 할 수 있 는 지 없 는 지 를 표시 합 니 다.
계속 합 시다.

private mutating func remove<
  G : GeneratorType where G.Element == Element
  >(var g: G) -> Bool { 

지금까지 이것 은 다른 방법 과 별 차이 가 없다.이 어 생 성기 의 머리 를 처리 합 니 다.

if let head = g.next() {

이 false 코드 블록 은 구체 적 인 논리 적 절차 입 니 다. 우 리 는 먼저 그것 을 건 너 뛰 어 처리 if 하고 g.next() 로 돌아 갈 때의 상황 을 처리 합 니 다.

private mutating func remove<
  G : GeneratorType where G.Element == Element
  >(var g: G) -> Bool {
    if let head = g.next() {...}
    endHere = false
    return children.isEmpty
}

여기까지 만 하면 시퀀스 삭제 작업 이 끝 납 니 다.지금 은 어느 사전 나무 든 nil 을 endHere 로 설정 해 야 한 다 는 뜻 이다.사전 트 리 사용자 에 게 지금부터 false 방법 으로 그 서열 을 매개 변수 로 입력 하면 되 돌아 갑 니 다 contains.
그러나 데이터 자 체 를 삭제 할 수 있다 면 false 의 값 을 되 돌려 줍 니 다.현재 사전 트 리 에 하위 노드 가 없다 면 삭제 할 수 있 습 니 다.이제 다시 children.isEmpty 코드 블록 으로 돌아 가 구체 적 인 실현:

guard children[head]?.remove(g) == true else { return false }
children.removeValueForKey(head)
return !endHere && children.isEmpty

하위 사전 트 리 에 대응 하 는 if 을 삭제 하기 위해 호출 remove.head 문 구 는 두 가지 상황 으로 false 를 되 돌려 줍 니 다. 하 나 는 guard 포함 되 지 않 은 경우 children 이 고, 다른 하 나 는 삭제 할 sequence 는 현재 사전 트 리 에 없습니다.삭제 되 거나 변이 되 지 않 았 기 때문에 이 방법 은 되 돌아 갑 니 다 head.false 에 children 이 포함 되 어 있 지만 되 돌아 오 는 것 이 head 이 라면 하위 노드 는 삭제 할 수 없 기 때문에 되 돌아 오 는 것 이다 false.그렇지 않 으 면 삭제 에 성공 합 니 다 false.
이 어 사전 트 리 children.removeValueForKey(head) 를 통 해 자신 이 삭제 할 수 있 는 지 아 닌 지 를 알 게 된다.만약 return !endHere && children.isEmpty 이 endHere 와 같다 면 sequence 말단 에 있다 는 것 을 나타 내 는 것 은 삭제 할 수 없 는 것 이다.하위 노드 가 없 으 면 삭제 할 수 있 습 니 다.완전한 방법 은 다음 과 같다.

extension Trie {
  private mutating func remove<
    G : GeneratorType where G.Element == Element
    >(var g: G) -> Bool { // Return value signifies whether or not it can be removed
      if let head = g.next() {
        guard children[head]?.remove(g) == true else { return false }
        children.removeValueForKey(head)
        return !endHere && children.isEmpty
      }
      endHere = false
      return children.isEmpty
  }
  public mutating func remove<
    S : SequenceType where S.Generator.Element == Element
    >(seq: S) {
      remove(seq.generate())
  }
}

이 코드 는 못 생기 고 길 어 요. true 속성 으로 간소화 하 세 요.

extension Trie {
  public var count: Int {
    return children.values.reduce(endHere ? 1 : 0) { $0 + $1.count }
  }
}

count 속성 기록 count 을 통 해 몇 번 endHere 이 있 습 니까?현재 사전 트 리 가 끝 에 있 으 면 true 1 count 을 추가 하 는 동시에 모든 아이들 노드 의 총화 에 도 추가 합 니 다.
다음 처리 (endHere ? 1 : 0).Getting tree - like structures to conform to SequenceType is a bit of a pain 글 에서 나무 구조 가 따라 야 한다 고 생각 하 는 SequenceType 골 치 아 픈 이 유 는 주로 재 귀 때문이다.선형 (비 재 귀) 으로 표시 하면 쉬 울 것 입 니 다.

extension Trie {
  public var contents: [[Element]] {
    return children.flatMap {
      (head: Element, child: Trie) -> [[Element]] in
      child.contents.map { [head] + $0 } + (child.endHere ? [[head]] : [])
    }
  }
}

그리고 이것 은 당연히 사전 트 리 의 생 성 방법 으로 도 쓸 수 있다.이것 은 보기에 좀 적합 하지 않다. 마치 옮 겨 다 니 는 방식 만으로 하나의 데이터 구 조 를 다른 데이터 구조 로 바 꾸 는 것 같다.우리 가 진정 으로 필요 로 하 는 것 은 필요 에 따라 모든 원 소 를 생 성 하 는 것 이다.
그러나 가끔 은 손 으로 쓰 는 것 이 좋 지 않 은 코드 이지 만 trick (예 를 들 어 폐쇄) 도 사용 해 야 한다.어쨌든 코드 를 보 세 요.

public struct TrieGenerator : GeneratorType {
  private var children: DictionaryGenerator>
  private var curHead : Element?
  private var curEnd  : Bool = false
  private var innerGen: (() -> [Element]?)?
  private mutating func update() {
    guard let (head, child) = children.next() else { innerGen = nil; return }
    curHead = head
    var g = child.generate()
    innerGen = {g.next()}
    curEnd = child.endHere
  }
  public mutating func next() -> [Element]? {
    for ; innerGen != nil; update() {
      if let next = innerGen!() {
        return [curHead!] + next
      } else if curEnd {
        curEnd = false
        return [curHead!]
      }
    }
    return nil
  }
  private init(_ from: Trie) {
    children = from.children.generate()
    update()
  }
}

이곳 은 이전에 사 용 했 던 SequenceType 논리 와 유사 하 다.
playground 버 전의 코드 는 여기 서 다운로드 할 수 있 습 니 다. Swift Sequence 에 테스트 가 있 습 니 다. 코드 는 여기 있 습 니 다.