개요

사람들은 인생에서 트리를 몇 번 쓴다고 한다. 그래서 몇 번째 트리에서 슈다치의 다츠-클론을 복제해 보았다. 트리의 기사가 많아서 여기서 Go에 이식해서 발견한 것들을 몇 가지 공유하고 싶다.
이번 결과: https://github.com/ikawaha/dartsclone

darts-clone

원소재는 이쪽.Java 버전과 Python 버전이 있습니다.

https://github.com/WorksApplications/Sudachi/tree/develop/src/main/java/com/worksap/nlp/dartsclone

https://github.com/WorksApplications/SudachiPy/tree/develop/sudachipy/dartsclone

본가https://github.com/s-yata/darts-clone입니다. 자세한 설명도 많으니 구글을 시도해 보세요.

아무튼 해보겠습니다.

작업 원리와 구조를 고려하지 않고 복제를 시도했다. 이후 GO처럼 재구성했다. 자바 버전과 Python 버전의 코드를 왜 Go에 떨어뜨렸는지 흥미롭다.

재구성

사실 Darts-clone의 Go 버전이 이미 있습니다. 제작 후에야 알아차렸습니다.
https://github.com/euclidr/darts
이것은 마치 본가의 C++ 버전의 clone인 것 같아서 이것과 비교하였다.
벤치에서 찾아봤는데byte수조에서 쌍수조를 처리할 때와 unit32수조에서 쌍수조를 처리할 때 같은 처리를 하기 위해 두 가지 측면에서 함수를 정리했습니다.이 함수의 호출이 느려서 그런 것 같습니다. 이것을 여러 상황에서 가득 쓴 함수로 바꾸어 호출을 줄이면 속도가 대체적으로 같습니다.
변경 전:

func (a MmapedDoubleArray) ExactMatchSearch(key string) (id, size int, err error) {
    return exactMatchSearch(a, key) // ← 共通処理でまとめてた
}

변경 후: 손으로 변경

func (a MmapedDoubleArray) ExactMatchSearch(key string) (id, size int, err error) {
    nodePos := uint32(0)
    unit, err := a.at(nodePos)
    if err != nil {
        return -1, -1, err
    }
    for i := 0; i < len(key); i++ {
        nodePos ^= unit.offset() ^ uint32(key[i])
        unit, err = a.at(nodePos)
        if err != nil {
            return -1, -1, err
        }
        if unit.label() != key[i] {
            return -1, 0, nil
        }
    }
    if !unit.hasLeaf() {
        return -1, 0, nil
    }
    unit, err = a.at(nodePos ^ unit.offset())
    if err != nil {
        return -1, -1, err
    }
    return int(unit.value()), len(key), nil
}

이렇게 하면 비교 프로그램과 같은 성능을 가지지만, 비교 프로그램은 배열된 색인 검사 등 잘못된 검사를 생략하기 때문에 좀 빠르다. 하지만,오차 범위이기 때문에 오류 검사를 넣기로 했습니다. 패닉에서 멈추는 것은 미묘합니다.

mmap 지원

sudachi는 mmap에서 사전을 공유하고 메모리를 절약하는 데 사용할 수 있습니다. 따라서 sudachi에서 사용하는 darts-clone은 mmap를 지원합니다. GO에서도 mmap를 지원합니다. linux계와 윈도우즈의 대응이 바뀌기 때문에 테스트 등이 좀 번거롭습니다.darts-clone의 쌍수조 자체는byte열이기 때문에 솔직하게 대응하면 됩니다.
하지만 아무리 mmap로 읽을 때의 속도(1/10 정도)도 없다.
mmap를 사용하지 않는 상황에서 uint32의 배열로 두 배열을 나타냅니다. mmap를 사용할 때 이것은 작은 단자 순서의byte 배열입니다. 여기서 unit32의 값을 꺼냅니다.
처음에 쓴 코드는 Reader를 사용하여 위치를 지정한 후 Read() 읽은 것입니다.

    var ret uint32
    if err := binary.Read(r, binary.LittleEndian, &ret); err != nil {
        return 0, fmt.Errorf("read error, %v", err)
    }

이 부분은 느린 것 같습니다. 이 배열을 직접 지정하고,

    if int(i+1)*unitSize > len(a.raw) {
        return 0, fmt.Errorf("index out of bounds")
    }
    ret := binary.LittleEndian.Uint32(a.raw[i*unitSize : (i+1)*unitSize])

읽은 후, mmap 버전도 동등한 성능을 나타냈다.
그나저나 binary.LittleEndian.Uint32()의 내용은,

func (littleEndian) Uint32(b []byte) uint32 {
    _ = b[3] // bounds check hint to compiler; see golang.org/issue/14808
    return uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
}

그렇군요. 간단합니다.
아, 그리고 syscall은 deprecated, golang입니다.org/x/sys 사용.

총결산

수다치에 해당하는darts-clonegithub.com/ikawaha/darts-clone을 발표했습니다. 이렇게 하면 사전을 찾는 기초 위에서 준비가 될 수 있기 때문에botchbotch와sudachi를 이식하고 싶습니다.
그나저나 작년부터 개발을 가로막았던 그거랑 이거랑 다 S로 갔는데 거기서 못 하는 벽에 부딪혀서 빼야 할 것 같지 않나. 이게 없으면 개발할 것 같은 느낌도 든다(^^`灬.
지난해부터 개발을 가로막고 있는 이것저것 → Happy hacking!