はてな流大規模データなんたら

自然言語処理などは全然知らない世界だが、検索アルゴリズムにベクトル空間モデルというのがあるようでちょっと興味を持った。たとえば文書の単語の出現回数などをベクトル成分とみなし、ベクトル同士の角度が小さい（cosθが1に近い）ほど類似している文書であるとみなすらしい。

ためしに、みんなの嫌いなJava言語でアルファベットの出現回数をベクトル要素として文字列の類似度を推定させてみた。

public class VectorSearch {
    
    private static char[] ALPHABET = "abcdefghijklmnopqrstuvwxyz".toCharArray();
    
    private int[] frequency;
    
    VectorSearch(String other) {
        this.frequency = this.frequency(other);
    }
    
    public double getSimilarityTo(VectorSearch other) {
        return getInnerProduct(other) / (this.getVectorLength() * other.getVectorLength());
    }
    
    double getInnerProduct(VectorSearch other) {
        double result = 0;
        for (int i = 0; i < ALPHABET.length; i++) {
            result += this.frequency[i] * other.frequency[i];
        }
        return result;
    }
    
    double getVectorLength() {
        int sum = 0;
        for (int i: frequency) {
            sum += i * i;
        }
        return Math.sqrt(sum);
    }
    
    int[] frequency(String text) {
        int[] freq = new int[ALPHABET.length];
        for (int i = 0; i < freq.length; i++ ) {
            freq[i] = 0;
        }
        
        for (char c: text.toCharArray()) {
            for (int i = 0; i < ALPHABET.length; i++) {
                if (c == ALPHABET[i]) {
                    freq[i] += 1;
                }
            }   
        }
        return freq;
    }
}

で、実行

    public static void main(String[] args) {
        VectorSearch v1 = new VectorSearch("aaaaaaaafg aaaaaabbbbbbbbbbaaaaaaaa");
        VectorSearch v2 = new VectorSearch("grgsaeragerltlhooossssbbbbbbbblrhosrlmororr");
        VectorSearch v3 = new VectorSearch("aaaaaaaaaaigejiafjiaaaaaaaaaghui");
 
        System.out.println("v1 and v2 " + v1.getSimilarityTo(v2));
        System.out.println("v1 and v3 " + v1.getSimilarityTo(v3));
        System.out.println("v2 and v3 " + v2.getSimilarityTo(v3));
    }

これならv1とv3が近いはず、結果は

v1 and v2 0.33935633624513245
v1 and v3 0.884571685303832
v2 and v3 0.15633246269595452

確かにv1とv3が最も1に近い。なるほど。単純にアルファベットの出現回数だけで比較しているので類似した文字列を推定しているとは言いがたいが、だいたい雰囲気はわかった。