川幡太一 1  「漢字の構造」の表現  Ideographic Description Sequenceの略  ISO/IEC 10646:2003 Annex Fにて用法を規定構 ⿰ 木 ⿰木冓冓 ⿰木⿱𠀎冉 ⿱ 𠀎冉 ⿱𠀎冉 2  漢字構造情報の電子的表現  漢字字形の定義・検索に利用可能。  漢字が７万文字を超えると、従来の方法では検索は困難に。  異体字の照合や判定・フォント合成・文字認識・OCR等にも応用可能。  IDSの問題同じ漢字を複数の方法で表現できる。  同じ符号で包摂可能な漢字を異なる符号で表現できる。  3 http://kanjidatabase.sourceforge.net/  様々な漢字情報を収集／整理  漢字字形はIDSでデータ化  UCS漢字  GB 7589/7590 の漢字  チュノム  拡張漢字E候補漢字  日本の国字（和製漢字の辞典）   ある「漢字」が符号化されているか、または上記データにあるかをIDSで判別できるか？ 4 必ずしも漢字部品の全てが、符号化されているとは限らない  I.  例：乌 → ⿹乌一（乌は符号文字にない）  この問題については、台湾 CDP (Chinese Document Processing) の作成した「漢字部品外字フォント」が豊富な部品バリエーションがあり、多くの漢字の分解に利用可。特定の漢字符号に対して、IDSは必ずしもユニークにならない  II.  → 「正規化」による「比較可能性」が必要 5  分割点によるIDSの相違例傾傾傾 ⿰ ⿰ ⿲ 亻頃化頁亻匕頁 ⿰亻頃 ⿰化頁 ⿲亻匕頁 6  分割レベルによるIDSの相違例：峠峠 ⿰ ⿰ 山𠧗山 ⿱ 上下 ⿰山𠧗 ⿰山⿱上下 7  垂／繞のかかる範囲の違い ⿰ ⿺ 麥面麥面 ⿰麥面 ⿺麥面 ⿸ ⿱ 鹿射鹿射 ⿸鹿射 ⿱鹿射 8  統合可能な字形の違い ⿰ ⿰ 忄青忄靑 ⿱ ⿱ 衛心衞心同じ符号が異なるIDSで表記できる場合の他にも、同じIDSが複数の符号に対応する、「重複符号化」の問題もある。 9  「意味的」IDSと「表示的」IDSの違い旗 ⿸ 㫃其 VS. 旗街 ⿰ ⿴ 方 ⿱ 𠂉其行圭街 VS. ⿲ 彳圭亍説文解字などを重視して意味的に漢字を分解しよう、という意識が働くとき、実際の物理的な分解方法とは異なるIDSが構成される可能性がある。 10 現実のIDSは、上記の５つの問題が複雑に絡み合い、「同一性」の判定をIDS文字列の単純な比較だけで行うのは困難。  解決に向けての４つの手段  IDS入力ルールの明確化  IDCの統合  IDS木構造の「正規化」  統合可能な漢字部品 (DC)の「正規化」または「同一視化」   過去に、IRG N1154として分解アルゴリズムを提案したことがあったが、処理が重すぎた。 11  入力時のルールを、Annex F.3 に追加。重ね合わせIDSは極力避ける  「意味論的」ではなく「表現的」なIDSのみ   例：辧（説文「判也。从刀。辡聲。」）は「⿴辡刀」とせず「⿲辛刀辛」とする。辧辧 ⿴ ⿰ 辡刀辛刀辛 12  IDSの比較の際、⿵⿸⿹は⿱に、⿺⿶⿷は ⿰に統合し、また⿶はノードの左右を入れ替えて、⿱に統合する。凶凶 ⿶ ⿱ 凵㐅㐅凵 13  IDSの「⿲／⿳」と「⿰／⿱」の曖昧さを避けるため、⿲ABCは⿰A⿰BC等に置き換える。傾傾 ⿲ ⿰ 亻匕頁亻 ⿰ 匕頁 14  IDSの「分割点」の曖昧さを避けるため、木のノードのIDCと、その左枝のIDCが同じ場合は、当該IDCを右側に移動する。儲儲 ⿰ ⿰ ⿰ 亻言者亻 ⿰ 言者 15  前ページのルールは、ノードのIDCの左下の漢字が、当該ノードのIDCと同じIDCで分解可能な場合にも、分解して適用する。（儲）（儲）（儲） ⿰ ⿰ ⿰ 信者「信」は「⿰亻言」と展開でき、右上ノードとIDCが一致する。 ⿰ 亻言者亻 ⿰ 言者 16  IDSの縮約  IDS木の正規化後、IDS木の葉が符号化漢字(DC) の場合は、ノードのIDSをデータベースから検索、該当漢字があれば置換を行う。（儲）（儲）（儲） ⿰ ⿰ 儲亻 ⿰ 亻諸言者 17  IDS木構造の正規化例（１） ⿰ ⿲ ⿰ A B ⿰ ⿰ C ⿰ A1 A2 A3 B C A1 ⿰ B A2 ⿲ A1 A2 A3 処理ノードのIDCが横方向に分解でき、かつその左側の文字Aが、IDSデータベース上は ⿲A1A2A3と横方向に分解できる場合、Aはいったん、正規化のために分解する。 ⿰ ⿰ C A3 ノード左の漢字をIDS木構造に分解した場合は、そのノードに対しても正規化処理を再帰反復実行する。 18  IDS木構造の正規化例（２）一致 ⿰ ⿰ ⿰ A1 ⿰ B A2 ⿰ ⿰ A1 ⿰ A2 A3 ⿰ A1 ⿰ ⿰ C A3 一致 A2 B C ⿰ ⿰ A3 B 処理ノードの左側が同じIDCの場合、当該IDCの左側を処理ノードの左側（A1)に、右側を新設した処理ノード右側ノードの左側に、処理ノード右側を新設ノードの右側に移動する。 C 移動後、処理ノードを右側ノードに移動し、同様の処理を再帰反復する。 19  IDS木構造の正規化例（３） ⿰ A1 ⿰ ⿰ A2 A1 ⿰ B ⿰ A2 ⿰ A3 ⿰ A3 A1 ⿰ ⿰ A2 X ⿰BC C 処理ノードの左右がDCの場合、IDCとの組み合わせで、IDSのデータベース（ハッシュまたはトライ木）を検索する。該当漢字が検索できない場合は文字列を上ノードに返す。 ⿰BCがIDSデータベースに存在していなくても、⿰A3⿰BCに対して、Xがデータベースに存在する場合がある。 20 漢字の構成部品として「同等」と考えられるものが存在する。  異符号を持つ同等な部品の判定には２つの方法がある。  1. IDSデータの格納時に「片寄せ」正規化   2. メリット：単純／高速デメリット：硬直的／片寄せ処理の無限ループ化を防止する方法が必要 IDSデータ比較時に全「同等パターン」組み合わせを生成、全比較   メリット：柔軟性／応用性が高いデメリット：比較処理が複雑で遅くなる。 21  片寄せ時の無限ループ問題  「犬／大」のような部品は、同等とみなして「犬」に寄せると、「大」と「丶」に分解され、分解がループする。臭犬分解分解 ⿱ 自大片寄せ正規化大  片寄せ正規化 ⿺ 丶無限ループ化対策として、同等と考えられる部品のうち、「画数がもっとも小さいもの」に寄せる。  「漢字画数データベース」を整備 22  IDS木構造の最上位ノードから正規化処理を行う       対象ノードのIDCが⿵⿶⿷⿸⿹⿺／⿲⿳ならばIDCを正規化する。対象ノードのIDCと、左側IDCが一致したら、木の組み替えを行う。（⿰⿰ABC → ⿰A⿰BC) 対象ノードのIDCと、左側文字の潜在IDCが同じならば、左側ノード文字のIDS分解と正規化を行う。対象ノードの左側DCを（片寄せの場合は）正規化し、右側ノードを対象ノードにして再起的に処理を行う。左右のノードがDCのノードに到達したら終了。 IDS木構造の最上位ノードから文字合成処理を行う。  対象ノードの全子ノードがDC/IDSならば、ノード全体でIDSを構築してIDSデータベースを検索する。     符号化漢字がヒットしたらその文字列を返す。符号化漢字がヒットしない場合は、IDSをそのまま返す。対象ノードの子ノードが木構造なら再帰処理を行う処理終了時には正規化IDSが完成 23  アルゴリズムが単純（全分解して、可能性のある全パターンを検索する方法※に比較した場合）  再帰を使えば非常に短いコードで記述可能。  高速動作  低メモリ消費 ※ IRG N1154で発表し、IRGにおける重複漢字チェックに使用したアルゴリズム 24 IDSは漢字構造を記述。（部品としてはCDP 外字が便利）  IDSは漢字の検索／照合／フォント合成／ OCRなど、様々な応用が考えられる。  IDSによる照合処理には正規化が必要。  IDSの正規化には、「意味的 vs. 表示的 IDS」「分割点」「IDCの正規化」「DCの正規化」の問題がある。  本発表で提案するアルゴリズムは、上記の課題を高速・低メモリで解決することを可能にする。  25