岡野原　大輔，辻井　潤一
全ての部分文字列を考慮した文書分類
IPSJ SIG Notes 2008(90), 59-64, 2008-09-17

---

全ての部分文字列が素性として利用する文書分類モデル，及びその効率的な学習，推定手法の提案．

部分文字列の種類数 ∝ 文書長の2乗

テキスト長に比例する個数のみ存在する極大部分文字列に関する統計量を扱い，有効な部分文字列を漏れ無く求める．
拡張接尾辞配列を用いることで，全文書長に比例した時間で学習ができる．

BOWの問題点
・単語に変換する際のエラー
・単語の定義が困難な場合（塩基配列，ログ情報など）
・処理単位
　形態素単位では映画のタイトル，メールの署名，テンプレートの情報を使えない

部分文字列を素性とする
→計算量が膨大に

拡張接尾辞配列
入力文字列
の接尾辞
入力文字列の接尾辞を辞書順にソートしたときの添字を並べた配列
・入力文字列の末尾には，入力中に出現しない，辞書順で最も小さい文字であるとする（文献中では$と表記）

最長共通接頭辞配列
（との共通な接頭辞の長さ）

Burrows Wheeler's 変換（BWT）
BWT変換後の文字列

但し，のとき

例）
入力文字列 = "abracadabra$"
拡張接尾辞配列 = [12, 11, 8, 1, 4, 6, 9, 2, 5, 7, 10, 3]
最長接頭辞配列 = [0, 1, 4, 1, 1, 0, 3, 0, 0, 0, 2, 0]
BWT後の文字列 = "ard$rcaaaabb"

i	SA	L	B	suffix
1	12	0	a	$
2	11	1	r	a$
3	8	4	d	abra$
4	1	1	$	abracadabra$
5	4	1	r	acadabra$
6	6	0	c	adabra$
7	9	3	a	bra$
8	2	0	a	bracadabra$
9	5	0	a	cadabra$
10	7	0	a	dabra$
11	10	2	b	ra$
12	3	0	b	racadabrra$

極大部分文字列

定義：
入力と，部分文字列が与えられたとき，の中の出現頻度を，の中の出現位置の集合をと定義する．