文字列からベクトルを生成する方法

文字列からベクトルを生成する方法のメモ。

# やりたいこと
* 次元を指定して文字列からベクトルを生成　←　文字列の長さによらず、同じ次元のベクトルを生成
* （比較的）高速にベクトルを生成
* 同じ文字列から同じベクトルを生成　←　ランダムではない
* 同じような文字列であれば似たようなベクトルを生成　→　類似度を計算すると類似度が高くなる


# 文字列からのベクトル生成
以下の方法で文字列からベクトルを生成します。
* N次元の零ベクトルを生成
* 文字列を指定の長さの ngram に分解
* ngram の各文字列について以下を実行
  * ngram からベクトルの n 番目の要素を決定
  * n 番目の要素の値をインクリメント


# ngram の文字列からベクトルの n 番目の要素を決定する方法
ここでは、ngram の文字列からベクトルの n 番目の要素を以下の方法で決定します。
* 各文字の文字コードを取得（例. a: 0x61 = 97）
* 文字コードをベクトルの長さで割った余りの値を n 番目の要素とする（例. 10次元ベクトルの場合 a: 97 % 10 = 7）


# 文字列からのベクトル生成例
## 例1. ベクトルの次元 = 10、ngram = 1 の場合
* 文字列: abcd
  * ngram(unigram): a, b, c, d
  * ベクトル: [1. 0. 0. 0. 0. 0. 0. 1. 1. 1.]
* 文字列: bcde
  * ngram(unigram): b, c, d, e
  * ベクトル: [1. 1. 0. 0. 0. 0. 0. 0. 1. 1.]
* コサイン類似度
  * 類似度: 0.75

## 例2. ベクトルの次元 = 20、ngram = 2 の場合
* 文字列: abcabc
  * ngram: {'\ta': 1, 'ab': 2, 'bc': 2, 'ca': 1, 'c\t': 1}
  * ベクトル: [0. 0. 0. 0. 0. 0. 1. 0. 1. 0. 0. 0. 0. 0. 0. 2. 1. 2. 0. 0.]
* 文字列: bcdbcd
  * ngram: {'\tb': 1, 'bc': 2, 'cd': 2, 'db': 1, 'd\t': 1}
  * ベクトル: [0. 0. 0. 0. 0. 0. 0. 1. 0. 1. 0. 0. 0. 0. 0. 0. 0. 2. 1. 2.]
* コサイン類似度
  * 類似度: 0.36363636363636365


# プログラム例
## ベクトル生成
```javascript:string_ngram_vector_creator.py
#
# String Ngram Vector Creator
#

import numpy as np


class StringNgramVectorCreator:
    BOS = '\t'
    EOS = '\t'


    def __init__(self, dim, ngram=1):
        self.dim = dim
        self.ngram = ngram


    def ngrams(self, str):
        cls = type(self)
        ngs = {}
        n = self.ngram
        str = (cls.BOS * (n-1)) + str + (cls.EOS * (n-1))

        for i in range(0, len(str)-(n-1)):
            ng = str[i:i+n]
            cnt = ngs.get(ng, 0)
            ngs[ng] = cnt + 1

        return ngs


    def nth_component(self, str):
        nth = sum([ord(c) for c in str]) % self.dim
        return nth


    def vector(self, str):
        v = np.zeros(self.dim)
        ngs = self.ngrams(str)

        for key, val in ngs.items():
            idx = self.nth_component(key)
            v[idx] = val

        return v
```

## ベクトル生成・類似度計算の例1
```javascript:
import numpy as np
from string_ngram_vector_creator import StringNgramVectorCreator


vector_creator = StringNgramVectorCreator(10, 1)

str1 = 'abcd'
str2 = 'bcde'

ngram1 = vector_creator.ngrams(str1)
ngram2 = vector_creator.ngrams(str2)

print(f"ngram1: {ngram1}")
print(f"ngram2: {ngram2}")

v1 = vector_creator.vector(str1)
v2 = vector_creator.vector(str2)

print(f"vector1: {v1}")
print(f"vector2: {v2}")

# 内積での類似度
s1_1 = np.dot(v1, v1) / (np.linalg.norm(v1) * np.linalg.norm(v1))
s1_2 = np.dot(v1, v2) / (np.linalg.norm(v1) * np.linalg.norm(v2))

print(f"similarity v1-v1: {s1_1}")
print(f"similarity v1-v2: {s1_2}")
```

実行結果
```
ngram1: {'a': 1, 'b': 1, 'c': 1, 'd': 1}
ngram2: {'b': 1, 'c': 1, 'd': 1, 'e': 1}
vector1: [1. 0. 0. 0. 0. 0. 0. 1. 1. 1.]
vector2: [1. 1. 0. 0. 0. 0. 0. 0. 1. 1.]
similarity v1-v1: 1.0
similarity v1-v2: 0.75
```

## ベクトル生成・類似度計算の例2
```javascript:
import numpy as np
from string_ngram_vector_creator import StringNgramVectorCreator


vector_creator = StringNgramVectorCreator(20, 2)

str1 = 'abcabc'
str2 = 'bcdbcd'

ngram1 = vector_creator.ngrams(str1)
ngram2 = vector_creator.ngrams(str2)

print(f"ngram1: {ngram1}")
print(f"ngram2: {ngram2}")

v1 = vector_creator.vector(str1)
v2 = vector_creator.vector(str2)

print(f"vector1: {v1}")
print(f"vector2: {v2}")

# 内積での類似度
print(np.dot(v1, v2))

s1_1 = np.dot(v1, v1) / (np.linalg.norm(v1) * np.linalg.norm(v1))
s1_2 = np.dot(v1, v2) / (np.linalg.norm(v1) * np.linalg.norm(v2))

print(f"similarity v1-v1: {s1_1}")
print(f"similarity v1-v2: {s1_2}")
```

実行結果
```text:
ngram1: {'a': 1, 'b': 1, 'c': 1, 'd': 1}
ngram2: {'b': 1, 'c': 1, 'd': 1, 'e': 1}
vector1: [1. 0. 0. 0. 0. 0. 0. 1. 1. 1.]
vector2: [1. 1. 0. 0. 0. 0. 0. 0. 1. 1.]
similarity v1-v1: 1.0
similarity v1-v2: 0.75
```