Mining Words Without a Dictionary
以前、小規模だが検索エンジンを開発していたことがある。日本語の検索には形態素解析が要る。テキストを単語に分割して、索引に載せる。当時はChaSenが標準だった。整形されたテキストなら正確に動く。インターネットのテキストは整形されていない。
新しいアイドルグループの名前、発売されたばかりの商品名、SNSで生まれた動詞。辞書にない単語は形態素解析器にとって存在しない。索引に正しく載らない。ユーザーが検索しても見つからない。
Rosette（当時Basis Technology社、現在はBabel Street傘下）というエンタープライズ向けの形態素解析エンジンがあった。Googleを含む主要な検索エンジンを顧客に持っていたと言われている。当時ライセンスを問い合わせたが、相手にされなかった。大手向けの製品だった。
辞書を大きくすればカバー率は上がるが、インターネットは辞書より速く新語を生む。辞書を更新し続けるのは終わりのない作業だ。そこで考えた。辞書なしで、テキストの統計的パターンだけから「これは単語だろう」と推定できないか。
PMI——文字の共起が単語を暗示する
PMI（Pointwise Mutual Information、自己相互情報量）は、2つの事象が一緒に起きる確率が、独立に起きる確率と比べてどれだけ高いかを測る指標だ。
たとえば「東」と「京」。日本語のテキストで「東」の後に「京」が来る確率は、両者が独立にランダムに出現する場合よりはるかに高い。PMIはその「はるかに」を数値化する。
PMI(x, y) = log₂( P(x, y) / (P(x) × P(y)) )PMIの直感的な理解
「東」が全文字の0.3%、「京」が全文字の0.2%の確率で出現するとする。もし両者が無関係なら「東京」というバイグラムは 0.003 × 0.002 = 0.0006% の確率で出現するはずだ。実際には「東京」はそれよりはるかに高い頻度で出現する。この「期待値からのずれ」がPMIの値になる。PMIが高いほど、その文字列が偶然ではなく意味のある単位——つまり単語——である可能性が高い。
大量のテキストから文字バイグラム（2文字組）やトライグラム（3文字組）を抽出し、PMIスコアを計算する。スコアが高いペアは単語の一部である可能性が高い。これが基本的なアイデアだ。
PMIの限界
PMIには弱点がある。低頻度のバイグラムでスコアが異常に高くなる問題だ。コーパス全体で1回だけ出現する珍しい文字の組み合わせは、期待値が極端に低いためPMIが跳ね上がる。実際にはノイズでしかない。
対策は最低頻度のフィルタリング（出現回数N回以上のバイグラムだけを対象にする）と、NPMIへの正規化だ。NPMI（Normalized PMI）はPMI値を -1〜+1 の範囲に正規化し、低頻度バイアスを緩和する。
Bloom filter——10億行の重複を捨てる
大規模コーパスの前処理で最初にぶつかるのは重複だ。Webクロールしたテキストには同じ文が大量に含まれている。重複をそのままPMI計算に流すと、頻度が歪む。
素朴な重複排除はHashMapにすべての行を入れることだが、10億行のテキストでは数十GBのメモリを食う。
Bloom filterとは
要素が集合に含まれるかどうかを高速に判定するデータ構造。ビット配列と複数のハッシュ関数で構成される。要素を追加するときは、複数のハッシュ関数で計算した位置のビットを立てる。判定するときは、同じ位置のビットがすべて立っているかを確認する。すべて立っていれば「たぶんある」、一つでも立っていなければ「確実にない」。ビットの衝突により偽陽性は起きるが、偽陰性は構造的に起きない。1970年にBurton Howard Bloomが提案した。
Bloom filterは確率的データ構造で、「確実にない」か「たぶんある」を答える。偽陰性がなく、偽陽性だけがある。つまり、見たことのない文を「見た」と間違えることはあるが、見たことのある文を「見ていない」と間違えることはない。重複排除にはこれで十分だ。
メモリ効率は劇的に違う。1000万件のユニーク文字列に対して、偽陽性率1%のBloom filterは約12MBで済む。HashMapなら160MB以上必要だ。99%の重複チェックをBloom filterの定数時間で処理し、残り1%だけHashMapで検証する。
Bloom filterのパラメータ設計
ビット数 m = -n × ln(p) / ln(2)² で計算する。n=1000万、p=0.01（偽陽性率1%）なら約9600万ビット＝12MB。ハッシュ関数の数は k = (m/n) × ln(2) で6〜8個が最適。ハッシュにはxxHash64を使い、ダブルハッシング（h(i) = hash1 + i × hash2）で複数のハッシュ値を生成する。
Accessor Variety——単語の境界を統計で推定する
PMIは文字の共起を測るが、単語の長さが可変であることに対応しにくい。「東京」は2文字、「東京タワー」は5文字。バイグラムPMIだけでは可変長の単語を丸ごと抽出できない。
Accessor Variety（AV）は別のアプローチだ。ある文字列の前後にどれだけ多様な文字が来るかを数える。
「東京」の左隣には「は」「の」「大」など多様な文字が来る。右隣にも「タ」「駅」「都」など多様な文字が来る。左右のAVがどちらも高い。一方、「京タ」の左隣はほぼ「東」だけ、右隣はほぼ「ワ」だけ。AVが低い。これは単語の内部であって境界ではない。
AVの計算にはSuffix Array（接尾辞配列）を使う。SA-ISアルゴリズムでO(n)時間で構築でき、任意の部分文字列の出現位置と前後文脈を高速に取得できる。
suzume-feedmillで実装した
これらの技術を組み合わせて、コーパスから未知語候補を抽出するパイプラインツールをC++で実装した。
パイプラインの各段階
正規化: ICUライブラリでUnicode NFKC正規化をかける。全角英数字を半角に、異体字を統一する。この段階でBloom filterとHashMapによる重複排除も行う。
Suffix Array構築: 正規化済みテキスト全体からSA-ISアルゴリズムでSuffix Arrayを構築する。LCP（Longest Common Prefix）配列も同時に計算し、部分文字列の出現回数を高速に数えられるようにする。
Accessor Variety計算: Suffix Arrayを使って、各部分文字列の左右のユニーク文字数を数える。AVが閾値（デフォルト5）以上の部分文字列を単語候補として残す。
スコアリング: NPMIスコア（重み0.4）、出現頻度（重み0.3）、Accessor Variety（重み0.3）の加重和で最終スコアを計算する。上位K件をmin-heapで抽出する。
結果
理論的には美しかった。実際の出力は使いものにならなかった。
抽出された「単語候補」の大半は、単語の一部だったり、助詞を含んだフレーズだったり、意味のない文字の並びだったりした。パラメータ（AV閾値、最低頻度、スコアの重み配分）を調整すれば改善する余地はあるが、コーパスごとにチューニングが必要で、汎用的な「辞書なし未知語抽出ツール」にはなり得なかった。
| 期待したもの | 実際に出てきたもの |
|---|---|
| 新語（アイドル名、商品名） | 単語の一部（「ンライン」「ックス」） |
| 複合語（東京タワー） | 助詞付きフレーズ（「東京の」「タワーに」） |
| 専門用語 | 高頻度だが意味のないバイグラム |
PMIもAccessor Varietyも、学術論文では中国語のセグメンテーションで良好な結果が報告されている（Feng et al., 2004）。ただし整形されたコーパスでの評価だ。Webクロールしたノイズまみれの日本語テキストでは、ノイズがそのままスコアに反映される。
その後
並行して開発していたSuzume（日本語トークナイザー）の設計が文法ベースに振ったことも大きい。Suzumeは辞書を最小化する代わりに、日本語の活用規則や接続規則をコードに埋め込むアプローチを取った。「辞書にない単語をコーパスから見つける」必要自体が薄れた。未知語に出会ったら、文法規則で推定する方が安定したからだ。
PMIは死んだか
suzume-feedmillは「思ったより使えなかった」プロジェクトだが、PMIとAccessor Varietyの組み合わせ自体が無価値だとは思わない。
問題は適用範囲だった。ノイズの多いWebテキストから直接未知語を抽出するのは、前処理のコストが高すぎた。もっと限定されたドメイン——特定ジャンルの掲示板、特定企業の社内文書——なら、ノイズが少ないぶん精度は上がる可能性がある。
PMI + Accessor Varietyをスタンドアロンのコマンドラインツールとして実装した既存のプロダクトは、調べた限り見つからなかった。学術論文は多いが、再利用可能なツールにまで仕上げた例はない。ニッチだが、空白地帯ではある。
コードはGitHubに公開してある。C++ 24,000行、テスト付き、Docker対応。使いたい人がいれば使ってほしいが、パラメータ調整には覚悟がいる。