唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

BigQuery の SQL で類似文字列検索をする

BigQuery自体には類似文字列検索の機能はないので、文字n-gramのコサイン類似度を求めるSQLを書いて似ている文字列の検索をします
ちなみに単純にある文字列が別の文字列に含まれているかどうかをみたいならWHEREにカラム名`LIKE '%探したい文字列%'のような条件を書いたりStandard SQLならSTRPOS(カラム名, '探したい文字列') != 0、Legacy SQLならカラム名 CONTAINS '探したい文字列'のように書けばよいはずです

文字n-gramのコサイン類似度による類似文字列検索

方針としては文字列同士を、文字n-gramのベクトルとみなしてコサイン類似度を計算します

文字n-gram

文字n-gramは連続したn文字のことで、これをカウントしたものをベクトルの要素とみなします

例えば文字bigram(2文字のn-gram)のベクトルを「BigQuery」について考えると、「Bi」「ig」「gQ」「Qu」「ue」「er」「ry」がそれぞれ1回出現するので、それらに対応した要素が1でその他が0のベクトルとなります

コサイン類似度

コサイン類似度はベクトルの角度を計算して類似度とみなしたもので、2つベクトルの内積をそれぞれのベクトルの大きさで割ったものです
\(x, y\)を2つのベクトルとした時コサイン類似度は以下のような式になります
$$\frac{x \cdot y}{|x|\,|y|} = \frac{\sum_i x_i y_i}{\sqrt{\sum_i x_i^2}\sqrt{\sum_i y_i^2}}$$ついでに紹介しておくと昔以下の記事で基本的な類似度について説明しました

SQL

というわけで後はSQLでこれを書くだけです
GENERATE_ARRAY(1, 100)で1から十分な長さまでの配列を作って、今回はbigramなので2文字ずつSUBSTR()で抜き出します

SELECT
  word
  , SUBSTR(word, i , 2) AS ngram
  , COUNT(*) AS count
FROM words, UNNEST(GENERATE_ARRAY(1, 100)) AS i
WHERE LENGTH(SUBSTR(word, i , 2)) = 2
GROUP BY word, ngram

内積の部分はJOINしてかけ合わせて総和を求めるだけです

SELECT
  a.word AS word1
  , b.word AS word2
  , SUM(a.count * b.count) AS inner_product
FROM ngram AS a
JOIN ngram AS b
ON a.ngram = b.ngram
AND a.word < b.word
GROUP BY word1, word2

ベクトルの大きさをもとめる部分は二乗して足し合わせるだけ

SELECT
  word
  , SQRT(sum) AS norm
FROM
  (
    SELECT
      word
      , SUM(count * count) AS sum
    FROM ngram
    GROUP BY word
  )

結果

というわけで適当なデータで試します
小説家になろうの作品(500件)に付いているキーワード(タグ)同士で類似文字列を調べました
結果が多少面白くなるように、どちらか片方に完全に包含されてしまうキーワード同士は除外しました

以下にコサイン類似度上位10件を出しました
微妙に表現が違ったり語順が入れ替わっているキーワードを取ってくることができました

word1 word2 cosine
2回OVL大賞応募作 3回OVL大賞応募作 0.88
ログアウト不可 ログアウト不能 0.83
tueee 銃tuee 0.81
ネット小説大賞五 ネット小説大賞感想 0.80
王道ファンタジー 王道？ファンタジー 0.80
ネット小説大賞五 ネット小説大賞受賞 0.80
ご都合主義？ 超ご都合主義 0.79
主人公最強化 主人公最強？ 0.79
主人公最強系 最強系主人公 0.79
半デスゲーム 非デスゲーム 0.79

まとめ

文字n-gramのベクトルのコサイン類似度を計算することで、BigQueryのSQLでも類似文字列検索を行うことができました
用途によってはUDFで編集距離(レーベンシュタイン距離など)の計算までやればもっといい感じのペアが取れるかもしれません
ちなみに大量のデータで試すときはn-gramのnの数を適当に大きめにしておかないと長い時間がかかるようになるので注意が必要です(もしかしたらBilling Tierの最大値の設定もしたほうがよいかも)

クエリ例

#StandardSQL
WITH words AS (
    SELECT
      word
    FROM
      (
      SELECT
        SPLIT(keywords, ' ') AS words
      FROM `text_data.narou_keywords`
      )
      , UNNEST(words) AS word
    GROUP BY word
  )
  , ngram AS (
    SELECT
      word
      , SUBSTR(word, i , 2) AS ngram
      , COUNT(*) AS count
    FROM words, UNNEST(GENERATE_ARRAY(1, 100)) AS i
    WHERE LENGTH(SUBSTR(word, i , 2)) = 2
    GROUP BY word, ngram
  )
  , inner_product AS (
    SELECT
      a.word AS word1
      , b.word AS word2
      , SUM(a.count * b.count) AS inner_product
    FROM ngram AS a
    JOIN ngram AS b
    ON a.ngram = b.ngram
    AND a.word < b.word
    GROUP BY word1, word2
  )
  , l2_norm AS (
    SELECT
      word
      , SQRT(sum) AS norm
    FROM
      (
        SELECT
          word
          , SUM(count * count) AS sum
        FROM ngram
        GROUP BY word
      )
  )

SELECT
  p.word1
  , p.word2
  , p.inner_product / n1.norm / n2.norm AS cosine
FROM inner_product AS p
JOIN l2_norm AS n1
ON p.word1 = n1.word
JOIN l2_norm AS n2
ON p.word2 = n2.word
WHERE STRPOS(word1, word2) = 0 AND STRPOS(word2, word1) = 0
ORDER BY cosine DESC
LIMIT 100000