Upgrade to Pro — share decks privately, control downloads, hide ads and more …

[DEIM2022] 高速な単語分割器VaporettoとパターンマッチングマシンDaacho...

[DEIM2022] 高速な単語分割器VaporettoとパターンマッチングマシンDaachorseの紹介

DEIM2022にて,LegalForce Researchで開発するOSSについて紹介した資料です。

More Decks by LegalOn Technologies, Inc

Other Decks in Technology

Transcript

  1. 2 株式会社LegalForce 全ての契約リスクを制御可能にする。 レビュー支援ソフトウェア AI契約管理システム   代表: 角田 望   設立: 2017年4月21日

    従業員等: 338名※1(役員含) 資本金等: 41.9億円※2(資本準備金等含) ※1: 2022年1月時点 ※2: 2021年2月時点 契約・法令情報メディア
  2. 6 単語分割手法 系列予測法 ソフトウェア: MeCab, Kuromoji, Sudachi, など 単語の境界か? 文字列

    素性 点予測法 ソフトウェア: KyTea, Vaporetto, など 点予測法の利点 ❏ 入力文長に線形時間で動作(系列予測法は二乗時間) ❏ 柔軟なコーパス設計(部分的アノテーションコーパスや品詞なしコーパス)
  3. 7 入力文の各文字境界について単語境界か否かを二値線形分 類問題として判定 固定長窓に含まれる文字列素性を利用してモデルを学習 ❏ 文字 n-gram 素性(e.g., 世界, 界の,

    の国民) ❏ 文字種 n-gram 素性(e.g., ひらがな, カタカナ, 漢字) ❏ 辞書単語素性(e.g., UniDic, IPADIC) 以下の3ステップで単語分割 1. 入力文に含まれる素性を列挙 2. 素性に紐づくスコアを加算 3. 合計スコアから各文字境界が単語境界かを判別 点予測に基づく単語分割 [森ら, 2011] 単語の境界か? Step1. 素性列挙 Step2. スコア加算 Vaporettoでは各ステップを高速に設計 参考文献: 森 信介, 中田 陽介, Neubig Graham, 河原 達也, 点予測による形態素解析, 自然言語処理, 2011
  4. 8 ステップ1:素性列挙(複数パターン検索) 入力文に含まれる素性(パターン)を列挙する Vaporettoでは Aho-Corasick (AC) 法を採用 ❏ 時間計算量がテキスト長と解の個数に線形 ❏

    スコア加算の高速化テクとの親和性 LegalForce Researchでは、高速・省メモリなAC法のRustライブラリ Daachorse を開発 ❏ ダブル配列を用いたAC法の実装 ❏ Rustで最も有名なAC法ライブラリと比べて45%のメモリ使用量で5.5倍高速 ❏ 最長一致分解などのトリッキーな検索もサポート 発表の後半で
  5. 9 ステップ2:素性のスコア加算 AC法で列挙した素性が持つスコア配列を合計し、各文 字境界のスコアを計算 ➔ 合計スコアが非負なら単語境界と判定 Vaporettoでは以下の3つの素性を使用 ❏ 文字 n-gram

    素性(e.g., 世界, 界の, の国民) ❏ 文字種 n-gram 素性(e.g., ひらがな, 漢字) ❏ 辞書単語素性(e.g., UniDic, IPADIC) 素性の特性に合わせた高速化技法を提案! 1. 文字 n-gram 素性スコアの事前加算 2. 辞書単語素性の併合 3. 文字種 n-gram 素性スコアのキャッシュ … は 、 全 世 界 の 国 民 … 世界 -2 2 -4 3 1 全世界 4 -3 -5 4 … 2 -1 -9 7 1 … 文字n-gram素性 合計スコア
  6. 10 オートマトンの同じ状態 s に紐づく素性は必ず同時にテキストに出現する ➔ それら素性のスコア配列は必ず合計される ➔ 状態 s のスコア配列として予め足し合わせておく

    実験結果 ❏ 文字n-gram素性でのスコア加算回数を47%削減! 高速化技法1:文字n-gram素性のスコア配列の事前加算 -2 2 -4 3 1 4 -3 -5 4 2 -1 -9 7 1 世界 全世界 s s 世界、全世界 世界、全世界
  7. 12 高速化技法3:文字種n-gramのスコアをキャッシュ 境界スコアは窓内の文字種の組合せによって一意に決まる ➔ 全通りの結果を記憶しておけば瞬時にスコアが計算できる 文字種は高々 6 通りしかない(ひらがな, 漢字, etc)

    ➔ 全通りの計算結果は高々1MiBで保存できる 窓をズラしながら結果を取り出すことで高速にスコア計算! ➔ ACマシンの素性列挙すら必要ない! 実験結果 ❏ ACマシンを使う場合と比べて6.1倍高速!
  8. 13 モデル(点予測法) ❏ コンパクトSVMモデル from KyTea ❏ BCCWJ & UniDic

    辞書(MeCab, Kuromoji, Lindera) ❏ IPA辞書 辞書(Sudachi, sudachi.rs) ❏ SudachiDict Core 解析テキスト ❏ 吾輩は猫である from 青空文庫 ベンチマーク: 分割速度 2.6倍高速 8.25倍高速 点予測法 系列予測法 実験コード: https://github.com/legalforce-research/tokenizer-speed-bench
  9. 15 LegalForce Researchで開発しているAC法のRustライブラリ ❏ 高速な複数パターン検索をサポート 特徴 ❏ ダブル配列による高い時間効率とメモリ効率 ❏ シンプルなAPI

    ❏ マルチバイト文字に特化したオプション 豊富な検索機能 ❏ オーバーラップマッチ ❏ 非オーバーラップマッチ ❏ 最短マッチ ❏ 最長マッチ ❏ 追加順序優先マッチ 応用例 ❏ 単語分割器や形態素解析器 ❏ 正規表現エンジン Daachorse: Double-Array Aho-Corasick
  10. 16 効率化の工夫 出力集合の併合保存 ❏ ACマシンで保持する出力の集合は同じエントリを含み冗長 ❏ Daachorseでは集合を併合して保存することでメモリ効率化 ❏ 単語集合ではエントリ数を20–40%程度削減 マルチバイト文字に特化したオプション

    ❏ ダブル配列ではマルチバイト文字はバイトに区切って処理するのが一般的 ❏ Pros: 構築が容易、文字のエンコードに依存しない ❏ Cons: 遷移数が増えて検索が低速化 ❏ DaachorseではUnicodeのコードポイント値から構築するオプションも実装 キャッシュ・メモリ効率を意識したデザイン ❏ 配列の要素圧縮 ❏ 状態の構造化、など
  11. 18 LegalForce Researchで開発しているRust製ライブラリを紹介 ❏ Vaporetto: 点予測に基づく高速な単語分割器 ❏ Daachorse: ダブル配列による高速なAC法 詳細な解説がLegalForce

    Enginnering Blogにあります! https://tech.legalforce.co.jp/ Vaporettoについては3月の言語処理学会でも発表します! まとめ PR LegalForce Research ではソフトウェアエンジニアとリサーチエンジニアを募集しています 興味を持たれた方は是非お声がけください! ❏ リサーチエンジニア(自然言語処理・画像処理・機械学習など) ❏ ソフトウェアエンジニア(自然言語処理・画像処理・機械学習など) ❏ ソフトウェアエンジニア(検索システム) 各リンクは弊社特設ページにあります!