全ての部分文字列を考慮した文書分類

岡野原 大輔,辻井 潤一
全ての部分文字列を考慮した文書分類
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$


極大部分文字列

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

が与えられたとき,と定義する.

2つの部分文字列が,であり(は空文字を含む部分文字列),を満たすときと定義する.

中に出現する全ての部分文字列はの関係によりいくつかの集合に分割される.

この各集合に属する部分文字列の中で一番長い文字列を極大部分文字列と呼ぶ.

接尾辞木と対応させて考える(直接接尾辞木を扱うには作業容量が大きくなる)
極大部分文字列の必要十分条件
その部分文字列が内部節点に対応し,かつ,その節点に対応するBWT配列が2種類以上の異なる文字を持つ場合

「文献紹介」に戻る
Comments