cannaのバイナリ辞書の形式

$Id: dic.txt,v 1.4 2003/08/31 14:15:17 aida_s Exp $


cannaの辞書には自立語辞書と付属語辞書があり、それぞれMWD,SWDというコードで
識別される。このほか、内部ではPRE辞書、SUC辞書というものが定義されており、
それぞれ接頭語、接尾語の辞書になっているようだが、現在のところ使われておらず、
動作するかどうかも不明である。

また、辞書の形式はテキスト形式とバイナリ形式がある。テキスト辞書は、単語登録が
可能であり、学習によっても内容が変化する。そのかわりマウントに空間的・時間的
コストがかかるため、ユーザー辞書や専門用語辞書に使われる。また、保持できる
学習情報は、単語の優先順位と、前回使われてからの仮想的時間(tick)だけである。
なお、付属語辞書のうち、fuzokugo.cbdは、語彙データの他に文法データを持つため、
テキスト形式にはできない。

バイナリ辞書は、サーバとともにインストールされ、そのまま内容が変化しない。
単語登録はできず、学習情報は別に作られた学習ファイル(.cld)に保存される。
検索に適した木構造をあらかじめ持っているので、マウント時に新しく管理情報を
生成する必要がなく、mmap()だけでアクセスすることも可能になっている。
また、1つの.cbdの中にバイナリ辞書を複数格納することも可能である。これは
単に複数のバイナリ辞書をcatでつなげただけの形式である。.cbd全体と区別
するため、.cbd内の個々の辞書を以下辞書メンバ(DM)と呼ぶ。

学習ファイルが頻度辞書とも呼ばれるなど、辞書という語はいろいろな意味で
使われるので、特に自立語辞書や付属語辞書の語彙部分をあわせて、「語彙辞書」と
呼ぶことにする。また、学習ファイルは語彙辞書と関係が深いので、これも併せて
解説する。

3.7devel2からは、より高い拡張性と互換性のため、辞書のヘッダの形式が多少
改められた。これはまだ開発バージョンであるため、従来の辞書についての記述も
残してある。

凡例：
BOOL	0または1
CARDnn	nnビットの符号無し整数、MSB first
CHAR	文字
WCHAR	ワイド文字
ZSTR	0終端文字列

1. 語彙辞書

1.1 Wrec

バイナリ辞書の基本単位は、読みと漢字、品詞をまとめたWrecというレコードである。
これはRK内部でバイトデータのまま保持され、かな漢字変換するたびに解析される。
形式は次の通りである。

WREC: WREC_HEADER2|WREC_HEADER4 LEFTYOMI(WCHAR*leftylen) CANDIDATE*ncand
WREC_HEADER2: 0(BOOL) LEFTYLEN(CARD6) WRECLEN(CARD6) NCAND(CARD3)
WREC_HEADER4: 1(BOOL) LEFTYLEN(CARD6) WRECLEN1(CARD6) NCAND1(CARD3) \
	      WRECLEN2(CARD7) NCAND2(CARD9)
CANDIDATE: KANJILEN(CARD7) HINSHIID(CARD9) KANJI(WCHAR*kanjilen)

候補が8個以上あるか、Wrecの大きさが64バイト以上になるときは、4バイトのヘッダが
使われる。また、読みはディレクトリとWrecに分断されて入っており、Wrecを一意に
識別できるのに必要な分だけディレクトリに、残りがWrecにLEFTYOMIとして入る。

1.2 全体構造

DMHEADER
    HD_RECORDS: HD_RECORD*n
	HD_RECORD: TAG(CHAR*4) LENGTH(CARD32) OFFSET(CARD32)|VALUE(CARD32)
	    LENGTHが0のときは、値は4バイト整数として直接書き込まれる。
	    LENGTHが1以上のときは、値はVALUESの領域に書き込まれ、OFFSETによって
	    間接参照される。OFFSETの基準はHEADERの先頭である。
    ENDTAG: '\0'*4
    VALUES

TOPDIR: DIRNODE_BROTHERS*n
    DIRNODE_BROTHERS: NBROTHERS(CARD16) 0(CARD24) DIRNODE*nbrothers
	DIRNODE: KEY(WCHAR) WORD_NODE(BOOL) NODEOFF(CARD23)|WRECOFF(CARD23)
	    NODEOFF,WRECOFFとも、辞書メンバのヘッダからのオフセットである。

PAGES: PAGE*npages
    PAGE
	PAGEHEADER: PAGENUMBER(CARD16) N_PAGENODES(CARD16) NWREC(CARD16) \
		    0(CARD8) FIRST_LVO(CARD24) FIRST_CSN(CARD24) 0(CARD8)
	PAGEDIR: PAGENODE*n_pagenodes
	    PAGENODE: KEY(WCHAR) WORD_NODE(BOOL) LAST_NODE(BOOL) \
		      NODEOFF(CARD14)|WRECOFF(CARD14)
		NODEOFF,WRECOFFともページの先頭からのオフセットである。
	LINKTABLE: LINK*nwrec
	    LINK: WRECOFF(CARD14) LVO_IN_PAGE(CARD15) CSN_IN_PAGE(CARD11)
	WORDS: WREC*nwrec

[GRAMMER]
    自立語辞書の場合はここは空である。3.7devel1までのバイナリ付属語辞書の場合、
    ここに文法データが必要である。実装を見る限り、文法を持たないバイナリ辞書を
    作りたい場合は、4バイトの0を書いておけば、RKを「だまして」動作させることが
    できるようである。3.7devel2以降は、HD_GRAMレコードを省略するか、HD_GRSZを
    0にすれば、文法の無い辞書を作ることができる。

辞書はページという単位に分かれている。資源が限られていた時代には、ページを
個別に解放したり、ページ単位でmmapしたりすることで、メモリを節約していたようで
ある。Wrecは全てページの中にあり、辞書木はページとディレクトリ領域に分かれて
入っている。

1.3 ヘッダ

ヘッダは拡張性が高いように見えるが、3.6までの実装では、RKが知らないTAGがあると、
その時点でエラーになってしまう。そのため、レコードを新設すると、古いRKでは
読めなくなってしまった。

3.7devel2からは、RKが知らないレコードは無視するようになっており、任意のデータを
追加できる。また、バージョンを表すレコードは実際には使われていなかった上、
互換性を詳しく示せるようにはなっていなかったので、HD_VERを廃止して、辞書の
実際のバージョンを示すHD_CURVと、互換性のある最も古いバージョンを示すHD_CMPV
を設けた。このほか、ヘッダのサイズの制限をなくすため、重要な5つのレコードは
常に先頭に配置することにした。

現在のレコードは次の通りである。

1.3.1 最初に、この順で現れねばならないもの(3.7devel2より前では場所は任意)

HD_MAG	(MAG#): "CDIC"をCARD32と見た値
HD_SIZ	(#SIZ): 辞書メンバの大きさ、3.7devel2からは文法データの大きさを含む
HD_HSZ	(#HSZ): ヘッダの大きさ
HD_CURV	(CURV): 辞書形式のバージョン、現在は0x300702L
HD_CMPV	(CMPV): 互換性のある辞書形式のバージョン、現在は0x300702L

1.3.2 順序は任意で、3.7devel2より前の辞書に存在するもの

HD_VER	(VER#): "R3.0"をCARD32と見た値、チェックされていない、3.7devel2で廃止
HD_TIME	(TIME): 作成時刻
HD_REC	(#REC): Wrecの総数
HD_CAN	(#CAN): 候補の総数
HD_L2P	(L2P#):	log2(ページの大きさ)、crxdicで作った場合13=8KB
HD_L2C	(L2C#):	log2(ページあたりの最大候補数)、crxdicで作った場合11=2048個
HD_PAG	(#PAG): ページの総数
HD_LND	(#LND): TOPDIRに含まれる節点の数
HD_SND	(#SND): PAGEDIRに含まれる節点の数
HD_DROF	(DROF): TOPDIRの位置、通常HD_HSZと同じでありRK内部でも混同されている
HD_PGOF	(PGOF): 最初のページの位置
HD_DMNM	(DMNM): 辞書メンバの名前
HD_CODM	(CODM): 0、学習ファイルでは対応する辞書メンバの名前
HD_LANG	(LANG): "japan"
HD_WWID	(WWID): 2(ワイド文字の幅?)
HD_WTYP	(WTYP): "W16 "をCARD32と見た値
HD_COPY	((C) ): 0(著作権者?)
HD_NOTE	(NOTE): 0(著作権表示?)
HD_TYPE	(TYPE): "jmwd"をCARD32と見た値

1.3.3 3.7devel1で登場し、3.6系の辞書には存在してはいけないもの

HD_CRC	(#CRC):	TOPDIRとPAGEを合わせた領域のISO/IEC 8802-3:1989 CRC

1.3.4 3.7devel2以降に登場し、3.7devel1までの辞書には存在してはいけないもの

HD_GRAM	(GRAM): 文法データの位置
HD_GRSZ	(GRSZ): 文法データの大きさ

1.4 辞書木の構造

Wrecは読みの1文字を1つの節点とする木構造で検索される。葉にはWORD_NODEフラグが
立っており、WRECOFFでWrecを指し示す。節点は全体のディレクトリ(TOPDIR)と
ページ内ディレクトリ(PAGEDIR)に分かれて入っている。節点がどちらに属するかは、
次のアルゴリズムで決められる。

a.頂点をxとする。頂点はTOPDIRに入れる。
b.xから下の部分木(x自身を除く)をすべてページ内に納めると仮定して、節点と、
  葉が指し示すWrec、およびWrecを指すリンク(後述)を合わせた大きさを求める。
c.部分木が全て収まるページを最初のページから順に探す。見付かればそのページに
  全て納めてしまう。節点はPAGEDIRに、リンクはLINKTABLEに、WrecはWORDSに納める。
d.どのページにも収まらないときは、xの直接の子供をTOPDIRに格納し、子供たちを
  再びxとして手順b以下を繰り返す。

一見効率が低いように見えるが、使用率が半分を切るページは高々1つであり、使用率
の最小値をmとすると、他のページの使用率は1-m以上であるから、悪いとはいえない。

TOPDIRとPAGEDIRに入れるときで、節点の形式、格納法が違っている。形式については
図1.2で十分であろう。格納するときは、どちらの場合も兄弟にあたる節点をかためて
記録するのだが、TOPDIRに入れるときは、兄弟が読みの1文字をキーとするハッシュ
テーブルをなしているのに対し、PAGEDIRに入れるときは、単に読みの順に格納する。
また、TOPDIRではハッシュテーブルの大きさがテーブルの先頭に書かれているのに対し、
PAGEDIRでは兄弟の最後の節点にLAST_NODEフラグが立っている。

「あい、あいあん、あいお・・・」のように、読みに他の語との不一致が出ないまま
終わる語(この場合は「あい」)がある場合は、読みの最後に0が加わったかのように
扱われる。この場合であれば、「あい」の子供は「0、あ、お・・・」となる。

1.5 リンク領域

ページにはリンクと呼ばれる情報も記録されている。リンクは、固定長でWrecと一対一
に対応しており、Wrecの番号でインディックスアクセスすることができる。主に学習
に使われている。リンクは次の内容を持つ。

WRECOFF:
  ページの先頭から測ったWrecの位置。
LVO:
  学習ファイルで、候補の順序を記録する場所を指す。実際には、最初のWrecのLVO
  がFIRST_LVOとしてページのヘッダに書かれ、リンク領域には、LVOとFIRST_LVO
  の差の形で記録される。
CSN:
  辞書に含まれる全候補の通し番号。これもページの最初の候補のCSNがFIRST_CSN
  として書かれ、リンク領域にはFIRST_CSNとの差が書かれる。ただし、3.6p3までは、
  CSN_IN_PAGEの計算が間違っていた。CSNは「候補が最後に使われてからの時間
  (tick)」を管理するためだけに使われていたので、実害は優先度が相互干渉して
  多少狂うだけだったようである。


2. 文法ファイル

2.1 全体構造

GRAMMER_SIZE(CARD32)
    GRAMMER_SIZEレコード自体の大きさ(4byte)を除き、N_HINSHIレコードの大きさ
    は含む。
N_HINSHI(CARD32)
CONJ_MATRIX
HINSHIMEI_TABLE: HINSHIMEI(ZSTR)*n_hinshi
    BB,K5r,k5u,Fkosoといった品詞名が、単に品詞番号の順に0終端文字列で
    入っている。
[NEG_CONJ_TABLE]
    NUMNEG(CARD32)
    NEG_CONJ*numneg
	NEG_CONJ: 0(CARD4) HINSHIID1(CARD9) HINSHIID2(CARD9) \
		  HINSHIID3(CARD9) NEG_FLAG(BOOL)
0(CARD8)

LOGIC_HACKを有効にするとNEG_CONJ_TABLEが付く。

RKはGRAMMER_SIZEが文法データ全体の大きさを指すことを仮定しているが、現在の
crxgramの実装では、NEG_CONJ_TABLEと最後の0の大きさが含まれてない。このため、
3.7devel2より前の辞書で、文法データの後に別の辞書メンバが続いた場合、正しく
アクセスできない。特に、NEG_CONJ_TABLEの有無は曖昧であり、単なるRKの修正では
済まない、形式自体の欠陥になっていた。

3.7devel2の辞書では、文法データのサイズはDMHEADERに含まれているので、この問題
は生じない。3.7devel2でも、文法ファイル本体の形式は一切変更していないため、
GRAMMER_SIZEはNEG_CONJ_TABLEと最後の0を含まないままである。


2.2 接続行列

ある品詞iの後に品詞jが続くかどうかは、ビットの行列で表される。i行j列が1なら
接続し、0なら接続しない。品詞の種類が8の倍数でないと、ビットの端数が出るが、
端数は行毎に切り上げられる。したがって、行の先頭(品詞0、これはBBである)は常に
バイト境界に揃えられている。

2.3 打ち消し接続テーブル

NEG_CONJは、3つの品詞の品詞番号と、接続を切る(NEG_FLAG=0)か優先度を下げる
(NEG_FLAG=1)かをまとめて、32ビットにしたものである。これが辞書順に並んでいる。
RKはこのテーブルをそのまま二分探索するので、必ず辞書順でなければならない。


3. 学習ファイル

3.1 全体構造

DMHEADER
    語彙辞書のヘッダとまったく同じである。ほとんどのレコードは、対応する
    語彙辞書のレコードのコピーであり、新たに設定されるのはHD_DMNM,HD_CODM,
    HD_HSZだけである。HD_SIZなどは意味を持たない。
PERM_TABLE_SIZE(CARD32)
PERM_TABLE: PERMUTATION*nwrec PADDING
    PERMUTATION: CANDNUM(CARDn)*ncand_in_wrec
RUC_TABLE
    RUC_TABLE_SIZE(CARD32)
	RUC_TABLE_BODYの空の部分を含めたエントリ数。
    N_RUC(CARD32)
	RUC_TABLEのうち実際に使われているエントリ数。
    FIRST_RUC(CARD32)
	最初に(つまり最も古く)使われた候補の番号。N_RUC<RUT_SIZEの場合はゴミ
	(通常0)が入っている。
    TM(CARD32)
	不明。現在のところ常に0が入っているようである。
    RUC_TABLE_BODY: RUC_ENTRY*n_ruc EMPTY_RUC_ENTRY*(ruc_table_size-n_ruc)
	RUC_ENTRY: CSN(CARD20) AGE(CARD20)
NV_AREA
    NV_SIZE(CARD32)
	NV_AREA_BODYの空の部分を含めたエントリ数。
    NV_COUNT(CARD32)
	NV_AREAのうち実際に使われているエントリ数。
    NV_HASHTABLE_SIZE(CARD32)
	RKが内部で使うハッシュテーブルの大きさをここで指定する。crfreqで作ると
	32になる。
    0(CARD32)
    NV_AREA_BODY: NV_ENTRY*nv_size EMPTY_NV_ENTRY*(nv_size-nv_count)
	NV_ENTRY: YOMILEN(CARD8) SPLITPOS(CARD8) YOMI(WCHAR*yomilen)

3.2 順序テーブル

1つの読みに対応する候補の順序は次のように記録される。候補数がncand=6個とする。
最も最近使われた候補が3番、続いて0番、2番、4番、5番、1番であったとする。
このとき、候補の番号を2倍して、
6 0 4 8 10 2
という数列を作る。そして、0以上ncand*2以下(未満ではない)の数を記録できる最小の
ビット数で、この6個の数字を表現し、順に詰め込んでいく。最初の数字(ここでは6)の
位置(ビット単位で数える)は、語彙辞書のリンク領域のLVOフィールドに書く。

削除した候補がある場合、候補数を合わせるため、ncand*2で埋める。上の例で5番目の
候補を削除した場合、
6 0 4 8 12 2
のようにする。ただし12の位置は不定であり、通常長く使っている間に数列の最後の
方に移動していく。

半端なビットが出た場合、バイト境界に合うように、テーブルの一番最後に0を埋める。

3.3 RUCテーブル

最近使用した候補を記録しておく。一つのエントリは、候補の通し番号CSNと、最後に
使われてからの時間(tick)の組になっている。1.5で述べたように、CSNの計算が狂って
いたため、このテーブルの内容がおかしくなっていて、矛盾はないものの、誤った
学習が生じていた。

3.4 NV領域

文節区切り長学習のための領域である。一つのエントリは、文節の読みと、文節を切る
位置の組み合わせであり、読みは生のWCHARテキストで記録する。


4. 主な制限値

DMHEADERの大きさ: 1024バイト以下(3.7devel1まで)、無制限(3.7devel2以降)
1つの辞書メンバの大きさ: 8MB(=2^23)未満
1つのページの大きさ: 16KB(=2^14)未満、crxdicで作った場合は8KBになる
ページあたりの候補数: 2048(=2^11)未満、ページの大きさの制限の方が常に強い
ページあたりの順序テーブルの消費量: 32Kbit(=2^15)未満、候補数の制限の方が強い
読みの長さ: 64(=2^6)文字未満
候補の漢字の長さ: 128(=2^7)文字未満
品詞の種類: 512(=2^9)種類未満、BBなどを除くともう少し少なくなる
Wrecの大きさ: 8KB(=2^13)バイト未満
