Rust研究：Bag of Words、テキストの類似度

（コードに一部誤りがあったので再掲です）

Rust で BoW (Bag of Words) を実装してみました。
BoW に関する基本的な型を紹介し、最後にニュース記事の中の単語を形態素解析で抽出し、その出現回数と、ニュース記事同士の類似度を計算してみます。

# BoW

BoW はテキスト内の単語ごとの出現回数を保持する。

```rust
// 単語IDは usize で表現する。
pub type WordID = usize;

// Bag of Words の型。以降、"BoW" と表記する。
// BoW には単語IDごとの出現回数を保持する。
#[derive(Debug, Clone)]
pub struct BoW {
    // 単語IDから出現回数への対応
    // 出現回数の型を f32 としたが、usize でもかまわない
    data: HashMap<WordID, f32>,
}

impl BoW {
    pub fn new () -> Self {
        BoW {
            data: HashMap::new (),
        }
    }

    // add_wid は単語IDを登録する。
    // すでに登録済みの場合はその出現回数をインクリメントする。
    pub fn add_wid(&mut self, wid:WordID) {
        self.data.insert(wid, match self.data.get(&wid) {
            Some(n) => *n + 1.0,
            None => 1.0,
        });
    }

    // 指定された単語IDの出現回数を返す。
    // 未知の単語IDの場合は 0 を返す。
    pub fn frequency (&self, wid: WordID) -> f32 {
        match self.data.get(&wid) {
            Some(n) => *n,
            None => 0.0,
        }
    }

```

BoW の基本機能はここまでですが、続いて、他の BoW との類似度を算出する部分です。
類似度として BoW をベクトルとしてみた場合の二つのベクトル間の「角度」に注目します。
ただし角度そのものを算出するのではなく、コサインの値を求めます。

ベクトル間の角度が 0° のときもっとも似ていると考えます。したがってコサインの値は 1 となります。
逆に 180°のときはまったく似ていないと考え、コサインの値は -1 となります。

つまり、コサイン類似度は 1 に近いほど類似性は高く、-1 に近いほど類似性は低いということを意味します。

コサインの計算には、内積 (inner_product) とノルム (norm) の計算が必要となります。

```rust
    // similarity は他の BoW とのコサイン類似度を計算する。
    // 結果は -1 以上 1 以下となり、1 が最も類似性が高いことをあらわし、
    // -1 がもっとも類似性が低いことをあらわす。
    pub fn similarity(&self, x: &BoW) -> f32 {
        self.inner_product(x) / (self.norm() * x.norm())
    }

    // inner_product は他の BoW との内積を計算する。
    pub fn inner_product(&self, x: &BoW) -> f32 {

        // 両方の BoW が保持する単語IDリストの和集合をとる。
        let mut wids = self.wids();
        for wid in x.wids() {
            if !wids.contains(&wid) {
                wids.push(wid);
            }
        }

        // それぞれの BoW における単語の出現回数の積の和を計算する。
        let mut product:f32 = 0.0;
        for wid in wids {
            product += self.frequency(wid) * x.frequency(wid);
        }

        product
    }

    // wids は保持する単語IDのリストを返す。
    pub fn wids (&self) -> Vec<WordID> {
        let mut result:Vec<WordID> = vec![];
        for (wid, _) in &self.data {
            result.push(*wid);
        }
        result
    }

    // norm はノルムを計算する。
    pub fn norm (&self) -> f32 {
        let mut r:f32 = 0.0;
        for (_, v) in &self.data {
            r += v*v // すべての要素の平方の和を求め、
        }
        r.sqrt () // 平方根を求める
    }
}
```

# Vocabulary

Vocabulary（語彙）は出現したすべての単語を保持する。

```rust
// Vocabulary (語彙)はすべてテキストに出現したすべての単語を保持する
#[derive(Debug, Clone)]
pub struct Vocabulary {

    // words はこれまで出現したすべての単語リスト。あるいは、単語IDから単語への変換
    words: Vec<String>,

    // ids は単語から単語IDへの変換
    ids: HashMap<String, WordID>,
}

impl Vocabulary {

    pub fn new () -> Self {
        Vocabulary {
            words: vec![],
            ids: HashMap::new(),
        }
    }

    // len は保持している単語の個数を返す
    pub fn len (&self) -> usize {
        self.words.len()
    }

    // wid は与えられた単語に対応する単語IDを返す。
    // 新しい単語のときは新しい単語IDが返る。
    pub fn wid (&mut self, word: String) -> WordID {
        if let Some(n) = self.ids.get(&word) {
            *n
        } else {
            let wid = self.words.len();
            self.words.push(String::from(&word));
            self.ids.insert(word, wid);
            wid
        }
    }

    // word は与えられた単語IDに対応する単語を返す。未知の単語IDのときはエラーとなる。
    pub fn word (&self, wid: WordID) -> Result<String> {
        if wid < self.words.len() {
            Ok(self.words[wid].clone())
        } else {
            Err(Error::UnknownWord)
        }
    }

}
```

# Context

Context はテキスト処理の文脈として、語彙と現在処理中の BoW を保持する。

```rust
// Context はテキスト処理の文脈として、語彙と現在の BoW を保持する。
#[derive(Debug, Clone)]
pub struct Context {
    vocabulary: Vocabulary,
    bow: BoW,
}

impl Context {
    pub fn new () -> Self {
        Context {
            vocabulary: Vocabulary::new(),
            bow: BoW::new(),
        }
    }

    // reset_bow は現在の BoW を空にする（オブジェクトとしても別になる）
    pub fn reset_bow (&mut self) {
        self.bow = BoW::new();
    }

    // add_word は単語を登録する
    pub fn add_word (&mut self, word: String) {

        // 単語の単語IDを取得
        let wid = self.vocabulary.wid(word);

        // bow に単語IDを登録
        self.bow.add_wid(wid);
    }

    pub fn wid (&mut self, word: String) -> WordID {
        self.vocabulary.wid(word)
    }

    pub fn word (&self, wid: WordID) -> Result<String> {
        self.vocabulary.word(wid)
    }

    pub fn bow(&self) -> BoW {
        self.bow.clone()
    }

    // print_bow は指定された BoW を表示する。
    // verbose = true の場合は語彙のすべての単語について表示する。
    // verbose = false の場合は BoW に出現するものだけを表示する。
    pub fn print_bow(&self, bow: &BoW, verbose: bool) {
        for wid in 0..self.vocabulary.len() {
            if let Ok (word) = self.word(wid) {
                if verbose {
                    print!("{}:{},", word, bow.frequency(wid))
                } else {
                    let freq = bow.frequency(wid);
                    if freq > 0.0 {
                        print!("{}:{},", word, freq)
                    }
                }
            }
        }
        println!("");
    }
}
```

# 形態素解析、BoW 作成、類似度の算出

三つのニュース記事ごとの BoW を作成する例を示す。
ここでは形態素解析に vibrato クレートを使用。

```rust
fn run() -> Result<()>  {

    // 形態素解析のトークナイザの作成
    let tokenizer = make_tokenizer("system.dic.zst")?;
    let mut worker = tokenizer.new_worker();

    // コンテクストオブジェクトの作成
    let mut ctx = Context::new();

    // ニュース記事1
    process_sentense(&mut ctx, &mut worker, "第５回ＷＢＣで２００９年の第２回大会以来３大会ぶりの優勝を狙う侍ジャパンは、１次ラウンド（Ｒ）３戦目でチェコを下し、無傷の３連勝となった。日本は１２日のオーストラリア戦に勝利すれば、Ｂ組１位となり１位で準々決勝に進む。デーゲームで行われる試合で、現在１勝１敗のチェコが２敗の韓国に敗れると、その時点で日本の２位以内が確定し、準々決勝進出が決まる。
    　日本に敗れて１勝１敗となったチェコ代表のハジム監督は、４万人超が集まった東京ドームでプレーし「満員の会場でプレーできたこと、この大会で試合ができたことが感激の感情以外ない。選手にとって、こんな満席のスタジアムでプレーすること以上の喜びはない」と感慨に浸った。
    　ほとんどの選手が野球以外の職業と兼務し、監督自身も神経科医として働いている。ＳＮＳでトレンドワードに「チェコの選手」などチェコ関連のワードが上位に入るなど、奮闘ぶりは日本のファンの心をつかんだ。指揮官は「日本で野球は重要な意味を持っている。しっかり見ているファンの温かい視線、励ましが素晴らしく、私たちもそれを感じて頑張った。（日本の）野球ファンのレベル、質も世界一だと思う」と思いを受け止めている。
    　チェコ国内の野球の人気は高いとはいえないが、初出場しているＷＢＣでの躍進に「チェコ全体で大きな興味を持っている。野球人気は数段上がると思う」と国内の反響も大きいようだ。準々決勝進出の望みは残っている。１２日の韓国戦へ「存分に力いっぱい戦ってきます」と話していた。
    ")?;

    // BoW をコンテクストオブジェクトから取得
    let news1 = ctx.bow();

    // コンテクストオブジェクト内の BoW をリセット
    ctx.reset_bow();

    // ニュース記事2
    process_sentense(&mut ctx, &mut worker, "【ＷＢＣ】韓国代表が３大会連続１次ラウンド敗退決定…オーストラリアがチェコ破り確定
    これまで２勝１敗だったオーストラリアがチェコに勝利し、３勝１敗となったため、同日の中国戦前まで１勝２敗の韓国代表の敗退が決定。準優勝した２００９年以来３大会ぶりの１次ラウンド突破とはならなかった。
    　韓国は９日の初戦・オーストラリア戦、１０日の日本戦で敗戦。１２日のチェコ戦で今大会初勝利をつかみ、１勝２敗だった。この日、オーストラリアが敗れ、ナイターゲームで韓国が２勝目を挙げれば２勝２敗で並ぶため、準々決勝進出の可能性が残っていた。
    　１２日の試合後、イ・ガンチョル監督は「この後の試合の結果を見守りたい」と話していたが、悔しくも涙をのむこととなった。"
    )?;


    // BoW をコンテクストオブジェクトから取得
    let news2 = ctx.bow();

        // コンテクストオブジェクト内の BoW をリセット
    ctx.reset_bow();

    // ニュース記事3
    process_sentense(&mut ctx, &mut worker, "ウクライナ陸軍「反攻遠くない」　バフムト防衛で時間稼ぎ
    　【キーウ共同】ウクライナのシルスキー陸軍司令官は11日、ロシアとの激戦が続く東部ドネツク州バフムトを防衛するため、近く反転攻勢を目指す考えを示唆した。「兵員を集めて反攻開始まで時間を稼ぐ必要がある。そう遠くない」と述べた。陸軍が発表した。
    　ウクライナ軍参謀本部は、バフムトでロシア側が絶え間なく攻撃を続けたが、ウクライナ軍は多くを撃退したと発表。ロシアは全域制圧を目指すドネツク、ルガンスク両州の境界線に向けドネツク州のリマンやアブデーフカ、マリンカ方面に猛攻をかけている。
    　ロシアの民間軍事会社ワグネル創設者プリゴジン氏は、バフムトでの戦闘に月1万トン、5億ドル（約674億円）相当の弾薬を含め、戦車やミサイルなど計10億ドル分が必要だと主張。供給が不十分だとしてロシア政府を通信アプリで批判した。
    ")?;

    // BoW をコンテクストオブジェクトから取得
    let news3 = ctx.bow();

    // BoW の表示
    println!("----------------------------");
    println!("news1:");
    ctx.print_bow(&news1, false);
    println!("----------------------------");
    println!("news2:");
    ctx.print_bow(&news2, false);
    println!("----------------------------");
    println!("news3:");
    ctx.print_bow(&news3, false);

    // 類似度の表示
    println!("----------------------------");
    // news1 と news1 の類似度。1になるはず。
    println!("similarity among news1 and news1 = {}", news1.similarity(&news1));

    // news1 と news2 の類似度
    println!("similarity among news1 and news2 = {}", news1.similarity(&news2));
    // news2 と news3 の類似度
    println!("similarity among news2 and news3 = {}", news2.similarity(&news3));
    // news3 と news1 の類似度
    println!("similarity among news3 and news1 = {}", news3.similarity(&news1));

    Ok(())
}

// make_tokenizer は vibrato のトークナイザを作成する
fn make_tokenizer(dic_zst_file: &str) -> Result<Tokenizer> {

    // 辞書データの読み込み
    eprint!("loading...");
    let reader = zstd::Decoder::new(File::open(dic_zst_file)?)?;
    let dict = Dictionary::read(reader)?;
    eprintln!("done");

    // トークナイザの生成
    Ok(vibrato::Tokenizer::new(dict).ignore_space(true)?)
}

// process_sentense はセンテンス単位で処理する。
fn process_sentense (ctx:&mut Context, worker: &mut Worker<'_>, sentense: &str) -> Result<()> {

    worker.reset_sentence(sentense);
    worker.tokenize();
    for token in worker.token_iter() {
        let token = MyToken::from(token);
        //println!("# {:?}", token);
        if &token.class == "名詞" { // 「名詞」以外は無視する
            //println!("{}", token.word);
            ctx.add_word(token.word);
        }    
    }

    Ok(())
}

// vibrato トークンを必要な部分だけを切り出したトークン
#[derive(Debug, PartialEq)]
struct MyToken {
    word: String, // 単語
    class: String, // 品詞
}

impl std::convert::From<vibrato::token::Token<'_, '_>> for MyToken {

    fn from(token: vibrato::token::Token) -> Self {
        // feature をカンマで区切ってベクタ化
        let f:Vec<&str> = token.feature().split(',').collect();
        MyToken {
            word: String::from(token.surface()),
            class: String::from(f[0]), // featureのうち「品詞」だけを取り出す
        }
    }
}
```

# 処理結果

上の run() を実行した結果を示す。

```
loading...done
----------------------------
news1:
５:1,回:2,ＷＢＣ:2,２:6,０:2,９:1,年:1,大会:3,以来:1,３:3,ぶり:2,優勝:1,侍:1,ジャパン:1,１:9,次:1,ラウンド:1,戦:3,目:1, チェコ:7,無傷:1,連勝:1,日本:6,日:2,オーストラリア:1,勝利:1,組:1,位:3,決勝:3,デーゲーム:1,試合:2,現在:1,勝:2,敗:3,韓国:2,時点:1,以内:1,確定:1,進出:2,代表:1,ハジム:1,監督:2,４:1,万:1,人:1,超:1,東京ドーム:1,プレー:3,満員:1,会場:1,こと:3,感激:1,感情:1,以外:2,選手:3,満席:1,スタジアム:1,以上:1,喜び:1,感慨:1,野球:5,職業:1,兼務:1,自身:1,神経:1,科:1,医:1,ＳＮＳ:1,ト レンド:1,ワード:2,関連:1,上位:1,奮闘:1,ファン:3,心:1,指揮:1,官:1,重要:1,意味:1,視線:1,私:1,たち:1,それ:1,レベル:1,質:1, 世界一:1,思い:1,国内:2,人気:2,出場:1,躍進:1,全体:1,興味:1,数:1,段:1,反響:1,よう:1,望み:1,存分:1,
----------------------------
news2:
ＷＢＣ:1,２:9,０:3,９:2,年:1,大会:3,以来:1,３:3,ぶり:1,優勝:1,１:9,次:2,ラウンド:2,戦:3,目:1,チェコ:3,日本:1,日:5,オーストラリア:4,勝利:2,決勝:1,試合:2,勝:6,敗:5,韓国:4,確定:1,進出:1,代表:2,監督:1,こと:1,連続:1,敗退:2,決定:2,破り:1,これ:1, ため:2,同日:1,中国:1,戦前:1,突破:1,初戦:1,敗戦:1,ナイター:1,ゲーム:1,可能:1,性:1,後:2,イ・ガンチョル:1,結果:1,涙:1,
----------------------------
news3:
日:1,万:1,官:1,ため:1,ウクライナ:4,陸軍:3,反攻:2,バフムト:4,防衛:2,時間:2,稼ぎ:1,キーウ:1,共同:1,シル:1,スキー:1,司令:1,11:1,ロシア:5,激戦:1,東部:1,ドネツク:3,州:3,近く:1,反転:1,攻勢:1,考え:1,示唆:1,兵員:1,開始:1,必要:2,発表:2,軍:2,参謀:1, 本部:1,側:1,絶え間:1,攻撃:1,多く:1,撃退:1,全域:1,制圧:1,ルガンスク:1,境界:1,線:1,リマン:1,アブデーフカ:1,マリンカ:1,方面:1,猛攻:1,民間:1,軍事:1,会社:1,ワグネル:1,創設:1,者:1,プリゴジン:1,氏:1,戦闘:1,月:1,1:1,トン:1,5:1,億:3,ドル:2,674:1,円:1,相当:1,弾薬:1,戦車:1,ミサイル:1,10:1,分:1,主張:1,供給:1,不十分:1,政府:1,通信:1,アプリ:1,批判:1,
----------------------------
similarity among news1 and news1 = 1
similarity among news1 and news2 = 0.66386783
similarity among news2 and news3 = 0.025890788
similarity among news3 and news1 = 0.01393483
```


ニュース記事１とニュース記事２はWBCの記事なので類似性は高いが、ニュース記事３はウクライナの記事のためニュース記事１・２との類似性が低いことが定量的に示された。

（一応、同じ記事同士で類似性が1になることも確認した）