はじめに
Android で使える連文節かな漢字変換器を Kotlin で実装した。かな漢字変換の辞書を構築するために Mozc の辞書を使用した。この記事では、Mozc の辞書を利用したかな漢字変換の実装方法について述べる。
どのようにかな漢字変換を実現するか
- ひらがなの文字列をひと文字ずつずらしながら読みの trie で common prefix search をして読みの node id のリストを取得する
- 読みの trie で得た node id を index として Token 配列から単語の node id のリストを取得する
- Token 配列で得た node id から単語の trie で親ノードをたどり単語を取得する
- 単語の trie で得た単語を使いグラフを作成する
- 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 の作成手順
- 木構造 (Prefix Tree) に文字列を登録する
- 文字列が登録された Prefix Tree を以下の手順で LOUDS に変換する
- LOUDS を表現するためのビット列
List<Boolean>、 文字のリストList<Char>、文字列の終わりを保存したビット列List<Boolean>を用意する - Prefix Tree の root node から子ノードを参照して LOUDS に変換する
-
List<Boolean>で表現されたビット列をBitSetに変換する
- LOUDS を表現するためのビット列
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)
}
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
グラフ構造
グラフ構造とは以下の画像のようなものである。
かな漢字変換におけるグラフ構造の作成の手順
- ノードを保持するリストを準備する
- リストのはじめに
BOSのノードを、リストの終わりにEOSのノードを追加する - 一文字ずつずらしながら common prefix search をしてその結果をリストに追加する
- かな漢字変換におけるグラフは 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
参考資料
-
辞書と言語モデルの効率のよい圧縮とかな漢字変換への応用 [C4-2]
-
Mozc - a Japanese Input Method Editor designed for multi-platform
-
version [2.29.5374.102]. 2024年5月1日 ↩