文字列類似度 備忘録

文字列類似度

編集距離アルゴリズムを使った処理を作っているが
少し疲れてきたので気分転換にもっとお手軽に類似度を計算できる処理を少し考えてみたので
メモとして残しておく。

定義量少ないのを優先した実装であり、別に早くはないし、編集距離とはちょっと違う結果になるが
さくっと類似度を取得したいといった場面に有効かとおもう。

pythonの場合

from collections import Counter
def similar(a, b):
    lensum = float(len(a) + len(b))
    ca, cb = Counter(a), Counter(b)
    dist = sum(((cb - ca) + (ca - cb)).values())
    return (lensum - dist) / lensum

C++の場合

template <typename T, typename U>
double similar(T* a, std::size_t A, U* b, std::size_t B) {
    std::size_t dist, lensum, i, j;
    lensum = dist = A + B;

    std::unordered_multiset<U, through_hash> map;
    for(i = 0; i < B; i++)
        map.emplace(b[i]);

    for(j = 0; j < A; j++) {
        T key = a[j];
        if(map.count(key)) {
            map.erase(key);
            ----dist;
        }
    }
    return (double)(lensum - dist) / lensum;
}

もう一つのアプローチ

　ビットパラレルのアルゴリズムを学ぶ中で、思いついたもう一つのアプローチ。
　上のsimilarよりも5倍ぐらい速く、編集距離の結果に近い。
　Python3の整数ビット数に制限がないと初めて知った。fem
　Pythonだとちょい速くなったかもぐらいだけど、
　C++の生配列とlog2の部分を若干工夫してやるとメッチャ速かった。

import math
from collections import defaultdict

def similar2(a, b):
    A = len(a)
    B = len(b)
    if A > B:
        return distance(b, a)

    ## ここまで前裁き。
    fp = defaultdict(int) # 長い方の文字 bを検索のために保存しておくストレージ
    lensum = dist = A + B # 両方の文字合計からスタートし、一致を見つけたら減算し残ったものが編集距離
    
    i = j = 0
    for y, bi in enumerate(b):
        fp[bi] |= 1 << y ## myers1999のアルゴリズム、、

    while(i < A and j < B):
        ai = a[i]
        
        if(ai == b[j]): # 一致
            dist -= 2
        else: # 不一致なんだけど
            trb = fp[ai] >> j #前方に一致するものあったか
            if(trb):
                dist -= 2 # あったら先読みして一致
                j += int(math.log2(trb & -trb)) # 一致したところまで早送りして次の周回へ
        
        i += 1
        j += 1
    
    return (lensum - dist) / lensum