mirror of
https://github.com/mii443/AzooKeyKanaKanjiConverter.git
synced 2025-08-22 15:05:26 +00:00
227 lines
17 KiB
Markdown
227 lines
17 KiB
Markdown
# Conversion Algorithms
|
||
|
||
AzooKeyKanaKanjiConverter内部で用いられている複雑な実装を大まかに説明します。
|
||
|
||
## かな漢字変換
|
||
|
||
変換処理では基盤としてViterbiアルゴリズムを用いています。
|
||
|
||
入力中には「1文字追加する」「1文字消す」「1文字置き換える」など、差分を利用しやすい場面が多いため、それぞれの場面に最適化したアルゴリズムを選択出来るようになっています。
|
||
|
||
アルゴリズムに特徴的な点として、文節単位に分割したあと、「内容語バイグラム」とでもいうべき追加のコストを計算します。このコスト計算により、「共起しやすい語」が共起している場合により評価が高く、「共起しづらい語」が共起している場合に評価が低くなります。
|
||
|
||
## 入力管理（Input Management）
|
||
|
||
入力管理とは、ユーザのキー入力の履歴を管理し、それに応じてローマ字かな変換などの適用を行う仕組みです。入力管理は簡単に見えて非常に複雑な問題です。AzooKeyKanaKanjiConverterではおもに`ComposingText`の内部で管理されています。
|
||
|
||
典型的なエッジケースは「ローマ字入力中に英語キーボードに切り替えて英字を打ち、日本語キーボードに戻って入力を続ける」という操作です。つまり、次の2つは区別できなければいけません。
|
||
|
||
```
|
||
入力 k (日本語) // →k
|
||
入力 a (日本語) // →か
|
||
```
|
||
|
||
```
|
||
入力 k (英語) // →k
|
||
入力 a (日本語) // →kあ
|
||
```
|
||
|
||
AzooKeyKanaKanjiConverterの`ComposingText`は、次のような構造になっています。このように`input`を持つことによって、この問題に対処しています。
|
||
|
||
```swift
|
||
struct ComposingText {
|
||
// 入力の記録
|
||
var input: [InputElement]
|
||
// ローマ字変換などを施した結果の文字列
|
||
var convertTarget: String
|
||
// 結果文字列内のカーソル位置(一番左にある場合、0)
|
||
var convertTargetCursorPosition: Int
|
||
}
|
||
|
||
struct InputElement {
|
||
// 入力した文字
|
||
var character: Character
|
||
// 入力方式
|
||
var inputStyle: InputStyle
|
||
}
|
||
|
||
enum InputStyle {
|
||
// 直接入力
|
||
case direct
|
||
// ローマ字入力
|
||
case roman2kana
|
||
}
|
||
```
|
||
|
||
しかし、カーソルを考慮すると、問題はさらに複雑になります。これは、UIの表面からは想像もつかないほど複雑です！
|
||
|
||
例えば、以下の状態を考えます。
|
||
|
||
```swift
|
||
ComposingText(
|
||
input: [
|
||
InputElement("j", .roman2kana),
|
||
InputElement("a", .roman2kana),
|
||
],
|
||
convertTarget: "じゃ",
|
||
// 重要: カーソルの位置は「じ|ゃ」となっている。
|
||
convertTargetCursorPosition: 1
|
||
)
|
||
```
|
||
|
||
ここで、「u」をローマ字入力した場合、どういう挙動になるでしょうか。ここにはデザインスペースがあります。
|
||
|
||
1. じうゃ
|
||
1. じゃう
|
||
1. じゅあ
|
||
1. 諦めて編集状態を解除する
|
||
|
||
1は最も直感的で、AzooKeyKanaKanjiConverterはこの方式をとっています。この場合、`input`を修正する必要があります。AzooKeyKanaKanjiConverterでは、「u」をローマ字入力した場合に`ComposingText`が次のように変化します。
|
||
|
||
```swift
|
||
ComposingText(
|
||
input: [
|
||
InputElement("じ", .direct),
|
||
InputElement("u", .roman2kana),
|
||
InputElement("ゃ", .direct),
|
||
],
|
||
convertTarget: "じうゃ",
|
||
convertTargetCursorPosition: 2
|
||
)
|
||
```
|
||
|
||
一方でiOSの標準ローマ字入力では、「2」が選ばれています。これはある意味で綺麗な方法で、ローマ字入力時に「一度に」入力された単位は不可侵にしてしまう、という方法で上記の変化を無くしています。もしAzooKeyKanaKanjiConverterがこの方式をとっているのであれば、以下のように変化することになります。しかし、このような挙動は非直感的でもあります。
|
||
|
||
```swift
|
||
ComposingText(
|
||
input: [
|
||
InputElement("j", .roman2kana),
|
||
InputElement("a", .roman2kana),
|
||
InputElement("u", .roman2kana),
|
||
],
|
||
convertTarget: "じゃう",
|
||
convertTargetCursorPosition: 3
|
||
)
|
||
```
|
||
|
||
「3」の「じゅあ」を選んでいるシステムは知る限りありません。この方式は「ja / じゃ」の間に「u」を入れる場合はうまくいきますが、「cha / ちゃ」の「ち」と「ゃ」の間に「u」を入れる場合は入れる位置をどのように決定するのかという問題が残ります。（chua、とすることになるのでしょうか）
|
||
|
||
「4」はある意味素直な立場で、「そんなんどうでもええやろ」な実装はしばしばこういう形になっています。合理的です。AzooKeyKanaKanjiConverterも、ライブ変換中はカーソル移動を諦めているため、このように実装しています。
|
||
|
||
このように、入力にはさまざまなエッジケースがあります。こうした複雑なケースに対応していくため、入力の管理は複雑にならざるを得ないのです。
|
||
|
||
## 誤り訂正（Typo Correction）
|
||
|
||
AzooKeyKanaKanjiConverterの誤り訂正は、`ComposingText.input`に対する置換として実装されています。つまり、例えば「ts」というシーケンスが存在した場合、一定のペナルティを課した上でこれを「ts」と読み替えたり、「た」というシーケンスが存在した場合、一定のペナルティを課した上でこれを「だ」と読み替えたり、といった具合です。これらのルールは事前にソースコードレベルで定義されています。
|
||
|
||
誤り訂正をナイーブに実装した場合、訂正候補の組み合わせ爆発が課題となります。例えば、入力が「たたたたたたたたたた」であるような場合、それぞれの「た」についてルールを適用するか否かで1024通りの候補が生じてしまいます。
|
||
|
||
このような問題に対処するため、AzooKeyKanaKanjiConverterでは効率的な誤り訂正のための工夫を導入しています。ペナルティは置換を適用するたびに蓄積するので、このペナルティには上限が設けられており、それを超えた場合は列挙の対象から外れます。これにより、パターンを大きく減らすことができます。
|
||
|
||
さらに、v0.9系以降のAzooKeyKanaKanjiConverterでは誤り訂正と辞書検索が並行して行われます。Trie木を用いた辞書検索では、特定の文字列に対応するノードがなかった場合、その文字列をプレフィックスに持ついかなる文字列も辞書登録されていないことがわかります。この性質を利用し、ありえない候補を生み出すような誤り訂正は早期に枝刈りされ、列挙のコストを大幅に削減することができています。
|
||
|
||
## 二重インデックスラティス (Dual-Indexed Lattice)
|
||
|
||
v0.9系以降のAzooKeyKanaKanjiConverterではかな漢字変換のためのラティス構造に大きな変更を加え、「二重インデックスラティス」と呼ぶ構造を導入しました。
|
||
|
||
従来のかな漢字変換用のラティスは、`ComposingText.input`のインデックスに対応する二重配列として表現されていました。二重配列の各ノード配列要素は、対応する`input`の位置から始まり、特定の`input`の位置で終わるようなノードを格納しています。この方法では、例えば「ittai」という入力に対して`[[i, it, itta, itta, ittai], [tt, tta, ttai], [ta, tai], [a, ai], [i]]`のような形で部分入力文字列が作られ、それぞれについて辞書引きが行われて実際のラティスノードが作られます。
|
||
|
||
このような実装は大筋で問題なく動作しますが、例外的なケースで問題が発生します。具体的には、「イッ」のような文字列に対応する入力を作ることができません。なぜなら、「ittai」というローマ字入力列のうち、「イッ」に過不足なく対応するような部分文字列が存在しないからです。「it」はそれ単体では「イt」、「itt」はそれ単体では「イッt」です。しかし、辞書においては「行った」の「行っ」など、「イッ」で検索をかけなければ作れない単語が数多くあります。
|
||
|
||
この問題に対処するため、AzooKeyKanaKanjiConverterでは「表層文字列レベルのインデックス」つまり「イッタイ」という文字列ベースのインデックスと、「内部文字列レベルのインデックス」つまり「ittai」という履歴ベースのインデックスを混在させる構造を導入しました。通常の変換には常に表層文字列レベルのインデックスを利用しつつ、誤り訂正については内部文字列ベースのインデックスを利用し、両者の間の対応関係を適切に取り扱うことにより、上記の問題を解決しています。
|
||
|
||
## 学習（Learning）
|
||
|
||
学習は、「一時記憶（キーボードを開く〜閉じるの間）」と「長期記憶（半永続）」の2つのデータを用いて行います。一時記憶は揮発性メモリ上にのみ存在し、長期記憶はファイルとして非揮発性のストレージに保存します。
|
||
|
||
辞書検索においては、一時記憶と長期記憶の両方を検索します。通常利用の際には一時記憶のみを更新します。そして、キーボードを閉じる際に一時記憶の内容を長期記憶にマージします。長期記憶へのマージは一時記憶の更新に比べて負荷の大きな処理であるため、キーボードを閉じる際にのみ実施することで使用感を向上させています。
|
||
|
||
### 学習のアルゴリズム
|
||
|
||
学習においては、選択された候補に対応する`[DicdataElement]`に対して、以下を学習します。
|
||
|
||
1. 学習が必要な単語に対して、その単語
|
||
1. 文節
|
||
1. 候補全体
|
||
|
||
例えば「この本を本屋で買った」の場合、「本」「本屋」「買っ」などが1の結果として学習されます。また、2の結果として「この本を」「本屋で」「買った」などが学習されます。また、3の結果として「この本を本屋で買った」全体が学習されます。
|
||
|
||
学習された表現は、ユーザ辞書と同じ仕組みで記録されます。元の単語とは別の表現として新たな辞書項目を追加し、計算時にそちらが優先的に選ばれるようコストを調整します。コストは「使用回数」などに応じて計算します。
|
||
|
||
#### 学習の減衰
|
||
|
||
学習したデータは時間が経つにつれ減衰します。具体的には、「使用回数」が32日おきに半減します。「使用回数」が0になった単語は学習から削除するため、1度使って学習された単語は32日間記憶されたのち、削除されます。2度使えば64日、4度使えば128日は維持されます。ただし学習には上限数があるため、上限に達した場合は古いものから削除されます。
|
||
|
||
#### 学習のリセット
|
||
|
||
変換候補を長押しすることで「この候補の学習をリセット」することができます。この際、候補に含まれる`[DicdataElement]`に対して、それと同じものを一時記憶・長期記憶から削除します。
|
||
|
||
### 学習データファイルの更新
|
||
|
||
学習は「学習した内容」を示すファイル(`memory.louds`, `memory.loudschars2`, `memory.loudstxt3`など)を内部的に保存することで実現しています。この更新処理を安全に行うため、以下のような処理をしています。
|
||
|
||
1. 更新を反映した各ファイルを`memory.louds.2`のように書き出す
|
||
1. `.pause`を書き出す
|
||
1. それぞれの`.2`を元ファイルの位置にコピーする（`.2`ファイル自体は削除しない）
|
||
1. `.pause`を削除する
|
||
|
||
このとき、読み出し側では
|
||
|
||
* `.pause`がない場合、`.2`のつかないファイルを読み出す。
|
||
* `.pause`がある場合、適当なタイミングで上記ステップの`3`以降を再実行する。また、`.pause`がある場合、学習機能を停止する。
|
||
|
||
上記手順では`.pause`がない間は`.2`のつかないファイルが整合性を保っており、`.pause`がある場合は`.2`のつくファイルが整合性を保っています。
|
||
|
||
例えば1と2のステップの実行中にエラーが生じた場合、一時記憶は失われますが、次回キーボードを開いた際は単に更新前のファイルを使うことができます。
|
||
|
||
3のステップの実行中にエラーが生じた場合、`.pause`があるため、次回キーボードを開いた際は学習を停止状態にします。ついで適切なタイミングで再度ステップ3を実行することで、安全に全てのファイルを更新することができます。
|
||
|
||
AzooKeyKanaKanjiConverter では、変換器を開いた際に `.pause` ファイルが残っている場合、自動的に空の一時記憶とマージを試みて `.pause` を削除し、学習機能を復旧します。
|
||
|
||
## 変換候補の並び順（Candidate Ordering）
|
||
|
||
変換候補の並び順の決定はとても難しい問題です。AzooKeyKanaKanjiConverterではおおよそ以下のようになっています。`Converter.swift`が並び順を決めていますが、とても複雑な実装になっているため、改善したいと思っています。
|
||
|
||
```
|
||
最初の5件: 完全一致または予測変換またはローマ字英語変換（ただし上位3件までに最低1つは完全一致が含まれる）
|
||
そこから5件: 文節単位変換
|
||
そこから: 全部ひらがな、全部カタカナ、全部大文字などの変換と前方一致で長い順・高評価順に辞書データを表示（5番目あたりでUnicode変換、西暦和暦変換、メアド変換、装飾文字などの特殊変換を挿入する）
|
||
```
|
||
|
||
## ライブ変換（Live Conversion）
|
||
|
||
ライブ変換はかなり単純なアイデアで実現しています。ライブ変換のない場合と同様に変換候補をリクエストし、「（予測変換ではなく）完全一致変換の中で最も順位が高いもの」をディスプレイします。
|
||
|
||
## 予測変換（Prediction）
|
||
|
||
予測変換は「入力中（mid composition）」と「確定後（post composition）」で実装が異なります。
|
||
|
||
### 入力中の予測変換
|
||
|
||
入力中の予測変換は以下のような手順で実行されます。
|
||
|
||
1. 最後の数文字をクエリとして辞書で前方一致検索を実施
|
||
2. 発見された単語で候補を追加し、コスト的に問題なければ追加
|
||
|
||
ただし、「1文字しかクエリがない場合」の予測変換はコストが非常に高いため、辞書の生成時点で「あ」から始まる予測変換候補を列挙しておく、といった工夫を行なっています。このデータは`p/p_あ.csv`のようなファイルに配置しています。こうすることで短いクエリでも適切な予測を実施できます。
|
||
|
||
また、ローマ字入力中は「r」などローマ字のみの入力でも予測変換を行うようにしています。この場合は「ら・り・る・れ・ろ」でそれぞれ予測変換を行なっています。
|
||
|
||
### 確定後の予測変換
|
||
|
||
確定後の予測変換が入力中の予測変換と異なる点は、ユーザによる明示的なクエリが少ないことです。全く入力のない状態から予測しなければならないため、一般に困難です。
|
||
|
||
そこで確定後の予測変換では以下のような変換を混ぜ合わせてこれを実現しています。
|
||
|
||
1. 末尾の品詞に基づく予測変換
|
||
|
||
辞書には`p/pi_1285.csv`のようなデータがあります。これは品詞idが1285の単語の後にきやすい単語を列挙したデータです。このデータを用いて確定後の予測変換を実施します。1285は名詞なので、「が」とか「は」といった単語が予測されます。
|
||
|
||
2. 末尾の単語からの予測変換
|
||
|
||
辞書には複合語が含まれます。例えば「内閣」と「内閣総理大臣」の両方が辞書に登録されています。そこで「内閣」で確定した場合、「ナイカク」をクエリとして辞書で前方一致検索を実施します。これによって発見された候補のうち単語表記のprefixが「内閣」のものを選び、残りの部分を予測変換候補として表示します。結果的に「総理大臣」が予測されることになります。
|
||
|
||
3. 絵文字などの予測変換
|
||
|
||
「ほんと悲しいな……」などで確定した場合、この候補の中には「悲しい」が含まれます。このとき「悲しい」をクエリに絵文字を検索し、「😭」がヒットした場合「😭」を予測変換候補として提示します。
|