LoginSignup
1
0
@Kazu_Project

Mozc の辞書を使ってかな漢字変換する [Kotlin]

Last updated at Posted at 2024-05-02

はじめに

Android で使える連文節かな漢字変換器を Kotlin で実装した。かな漢字変換の辞書を構築するために Mozc の辞書を使用した。この記事では、Mozc の辞書を利用したかな漢字変換の実装方法について述べる。

どのようにかな漢字変換を実現するか

  1. ひらがなの文字列をひと文字ずつずらしながら読みの trie で common prefix search をして読みの node id  のリストを取得する
  2. 読みの trie で得た node id を index として Token 配列から単語の node id のリストを取得する
  3. Token 配列で得た node id から単語の trie で親ノードをたどり単語を取得する
  4. 単語の trie で得た単語を使いグラフを作成する
  5. Viterbi アルゴリズムを使って最短経路をたどって漢字まじりの文字列を取得する

参考: 辞書と言語モデルの効率のよい圧縮とかな漢字変換への応用 [C4-2]

必要なもの

  • 読みの trie
    • LOUDS
    • dictionary00.txt ~ dictionary09.txt から作成する
  • 単語の trie
    • LOUDS
    • dictionary00.txt ~ dictionary09.txt から作成する
  • Token 配列
    • 単語の node id、品詞の情報、単語のコストの集合を読みの node id を index として保存した配列
    • dictionary00.txt ~ dictionary09.txt から作成する
    • var tokenArray: List<List<Node>> と同等である
  • 言語モデル
    • グラフを作成する際、重みをつけるのに必要
    • connection_single_column.txt を圧縮して保存する

かな漢字変換のためのデータ構造

LOUDS

かな漢字変換で使用する LOUDS の条件

  • 子ノードの id から親ノードを参照できる
  • 親ノードの id から子ノードの集合を取得できる

参考: 日本語入力を支える技術　～変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus)

LOUDS の作成手順

  1. 木構造 (Prefix Tree) に文字列を登録する
  2. 文字列が登録された Prefix Tree を以下の手順で LOUDS に変換する
    • LOUDS を表現するためのビット列 List<Boolean>、 文字のリスト List<Char>、文字列の終わりを保存したビット列 List<Boolean> を用意する
    • Prefix Tree の root node から子ノードを参照して LOUDS に変換する
    • List<Boolean> で表現されたビット列を BitSet に変換する

LOUDS のための完備辞書

LOUDS を表現するのに完備辞書 (完結ビットベクトル) が必要となる
完備辞書を表現するため BitSet を拡張して使用した

List から BitSet に変換
/** List<Boolean> => BitSet **/
fun List<Boolean>.toBitSet(): BitSet {
    val bitSet = BitSet(this.size)
    this.forEachIndexed { index, value ->
        if (value) {
            bitSet.set(index,true)
        }
    }
    return bitSet
}

/** BitSet => List<Boolean> **/
fun  BitSet.toBooleanList():List<Boolean>{
    return (0 until this.size()).map { this[it] }
}
BitSet の拡張

fun BitSet.rank0(index: Int): Int {
    var count = 0
    for (i in 0..index) {
        if (!this[i]) {
            count++
        }
    }
    return count
}

fun BitSet.rank1(index: Int): Int {
    return index + 1 - rank0(index)
}

fun BitSet.select0(nodeId: Int): Int {
    var count = 0
    for (i in 0 until size()) {
        if (!this[i]) {
            count++
            if (count == nodeId) {
                return i
            }
        }
    }
    return -1 // Not found
}

fun BitSet.select1(nodeId: Int): Int {
    var count = 0
    for (i in 0 until size()) {
        if (this[i]) {
            count++
            if (count == nodeId) {
                return i
            }
        }
    }
    return -1 // Not found
}
Common Prefix Search

var LBS: BitSet = BitSet()

    fun commonPrefixSearch(str: String): MutableList<String> {
        val resultTemp: MutableList<Char> = mutableListOf()
        val result: MutableList<String> = mutableListOf()
        var n = 0
        str.forEachIndexed { _, c ->
            n = traverse(n, c)
            val index = LBS.rank1(n)
            if (n == -1) return@forEachIndexed
            if (index >= labels.size) return result
            resultTemp.add(labels[index])
            if (isLeaf[n]){
                val tempStr = resultTemp.joinToString("")
                if (result.size >= 1){
                    val resultStr = result[0] + tempStr
                    result.add(resultStr)
                }else {
                    result.add(tempStr)
                    resultTemp.clear()
                }
            }
        }
        return result
    }

    private fun firstChild(pos: Int): Int {
        LBS.apply {
            val y = select0(rank1(pos)) + 1
            return if (!this[y]) -1 else y
        }
    }

    private fun traverse(pos: Int, c: Char): Int {
        var childPos = firstChild(pos)
        if (childPos == -1) return -1
        while (LBS[childPos]){
            if (c == labels[LBS.rank1(childPos)]) {
                return childPos
            }
            childPos += 1
        }
        return -1
    }
子ノードの id から親ノードをたどり文字列を取得する

var LBS: BitSet = BitSet()

fun getLetter(nodeIndex: Int): String {
        val list = mutableListOf<Char>()
        val firstNodeId = LBS.rank1(nodeIndex)
        val firstChar = labels[firstNodeId]
        list.add(firstChar)
        var parentNodeIndex = LBS.select1(LBS.rank0(nodeIndex))
        while (parentNodeIndex != 0){
            val parentNodeId = LBS.rank1(parentNodeIndex)
            val pair = labels[parentNodeId]
            list.add(pair)
            parentNodeIndex = LBS.select1(LBS.rank0(parentNodeIndex))
            if (parentNodeId == 0) return ""
        }
        return list.toList().reversed().joinToString("")
    }

参考: 日本語入力を支える技術　～変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus)

Token 配列

Token 配列に完備辞書を使用する。ひらがなの文字列は複数の変換候補を持ちそれを表現するためにデータそのものを保存する配列と、各データの長さを保持する配列を用意する。後者に完備辞書を使用する。
データそのものを保存する配列に対応する index は rank1(select0(nodeId)) と rank1(select0(nodeId + 1)) の差分から求めることができる

例
"わたし" = [私、渡し、ワタシ]
"わたす" = [渡す、ワタス、わたす]
"わたせ" = [渡瀬、渡せ、渡世]

以下つづく。。。

/** "わたし"の読みノード id == 1 **/
val yomiNodeId1 = yomiTrie.getNodeId("わたし")
/** "わたす"の読みノード id == 2 **/
val yomiNodeId2 = yomiTrie.getNodeId("わたす")
/** "わたせ"の読みノード id == 3 **/
val yomiNodeId3 = yomiTrie.getNodeId("わたせ")
データそのものを保存する配列と各データの長さを保持する配列

val tangoList: List<String> = [私,渡し,ワタシ,渡す,ワタス,わたす,渡瀬,渡せ,渡世]

val bitVector: BitSet = [0,1,1,1,0,1,1,1,0,1,1,1]
変換候補を Token 配列から取得する例
/** わたしの変換候補を取得する **/

val nodeId = 1

bitVector.apply{
    val startPos = rank1(select0(nodeId)) // 0
    val endPos = rank1(select0(nodeId + 1)) // 3
    val result: MutableList<String> = mutableListOf()
    
    for (i in startPos < endPos){
        val word = tangoList[i]
        result.add(word)
    }
    
    /** 私,渡し,ワタシ  **/
    println(result)
}

参考: 日本語入力を支える技術　～変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus)

言語モデルの圧縮

Mozc の言語モデルは2,6621のクラスがあり connection_single_column.txt に7,086,244 (2662*2662) のコストが記載されている。List<Short> で表現すると約14 MB になる。このリストを圧縮して保存し、プログラムの起動時に解凍して展開する方法を採用した。

List から ByteArray に変換

fun List<Short>.toByteArrayFromListShort(): ByteArray {
    val byteArray = ByteArray(this.size * 2)
    for (i in this.indices) {
        val shortValue = this[i]
        byteArray[i * 2] = (shortValue.toInt() shr 8).toByte()
        byteArray[i * 2 + 1] = shortValue.toByte()
    }
    return byteArray
}
ByteArray の圧縮と展開

fun ByteArray.deflate(): ByteArray{
    val rawData: ByteArray = this
    val compressedData = ByteArray(rawData.size)
    val compressor = Deflater()
    compressor.apply {
        setInput(rawData)
        finish()
    }
    val compressedDataLength = compressor.deflate(compressedData)
    return compressedData.copyOfRange(0, compressedDataLength)
}

fun ByteArray.inflate(size: Int): ByteArray{
    val compressedData: ByteArray = this
    val originalData = ByteArray(size)
    val inflater = Inflater()
    inflater.apply {
        setInput(compressedData)
        finished()
    }
    val originalDataLength = inflater.inflate(originalData)
    return originalData.copyOfRange(0, originalDataLength)
}

参考: Kotlinでバイト配列を圧縮・展開する

Mozc の辞書と圧縮後の辞書

以下の Mozc の辞書を使用した

  • dictionary00.txt ~ dictionary09.txt
    • 読み、単語、品詞の情報
    • 1,543,677 エントリー
    • 74.1 MB
  • connection_single_column.txt
    • 言語モデル
    • 36.2 MB
  • 合計 110.3 MB

圧縮後

  • yomi.dat
    • 読みの trie
    • 12 MB
  • tango.dat
    • 単語の trie
    • 7.3 MB
  • token.dat
    • Token 配列
    • 6.9 MB
  • connectionIds.dat
    • 圧縮後の言語モデル
    • 1.9 MB
  • 合計 28.1 MB

グラフ構造

グラフ構造とは以下の画像のようなものである。

graph.png

かな漢字変換におけるグラフ構造の作成の手順

  1. ノードを保持するリストを準備する
  2. リストのはじめに BOS のノードを、リストの終わりに EOS のノードを追加する
  3. 一文字ずつずらしながら common prefix search をしてその結果をリストに追加する
  4. かな漢字変換におけるグラフは n 文字目で終わる単語のリストを作成することで再現できる2
グラフ作成の疑似コード

fun constructGraph(): List<List<Node>>{

    val str: String = "わたしのなまえ"
    var graph: MutableList<List<Node>> = mutableListOf()

    /** initialize mutableList **/
    for (i in 0 .. str.length + 1){
        when(i){
            0 -> graph.add(BOS)
            str.length + 1 -> graph.add(EOS)
            else -> graph.add(null)
        }
    }

    for (i in str.indices){
            val subStr = str.substring(i, str.length)
            val commonPrefixSearch = commonPrefixSearch(subStr)
            commonPrefixSearch.forEachIndexed { strList, index ->
                graph[index] = strList
            }
        }
        return graph.toList()
}
結果

graph = [[BOS],[わ],[わた],[私,たし,し],[の],[な],[生],[名前,前,え],[EOS]]

index:
0 => [BOS]
1 => [わ]
2 => [わた]
3 => [私,たし,し]
4 => [の]
5 => [な]
6 => [生]
7 => [名前,前,え]
8 => [EOS]

最短経路を求めるアルゴリズム

ビタビアルゴリズムで最短経路を求める。
日本語入力を支える技術　～変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus) で紹介されていた ruby の疑似コードを Kotlin で実装した。

その他

Mozc の辞書のエントリーは以下のように構成されている

表面層（読み）     左id     右id     単語のコスト     単語
   String       Short    Short      Short       String

左 id と右 id の組み合わせのテーブルを作成しその index を使う事でサイズの削減をした

Github

参考資料

  1. version [2.29.5374.102]. 2024年5月1日 ↩

  2. 参考: 日本語入力を支える技術　～変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus) ↩

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0