中野智文のブログ

データ・マエショリストのメモ

BQで最長前方共通文字列を抽出する

背景

住所などで、前方一致する共通文字列を取り出したい。

方法

考え

前方部分文字列を1文字つずつ増やしながら生成して、同じ文字数で生成した文字列が何タイプあるか調べて、1以外なら共通していないので破棄する。(ここまでが前方共通文字列)

そのうち最長のものが欲しいわけだから、その文字数の最大値で、前方部分文字列を生成するとそれが最小共通文字列となる。

WITH
  data AS (
  SELECT
    x.latlon,
    x.address
  FROM
    UNNEST([
    STRUCT('東京都江東区有明1' AS address, 1 as latlon),
    STRUCT('東京都江東区有明2' AS address, 1 as latlon),
    STRUCT('東京都江東区東雲' AS address, 2 as latlon),
    STRUCT('東京都江東区東雲1' AS address, 2 as latlon),
    STRUCT('東京都江東区東雲2' AS address, 2 as latlon),
    STRUCT('東京都江東区豊洲4' AS address, 3 as latlon)
    ]) AS x),
  n_list AS (
  SELECT
    n
  FROM
    UNNEST(GENERATE_ARRAY(1, 30)) AS n ),
  substr_list AS (
  SELECT
    latlon,
    n,
    SUBSTR(address, 1, n) address
  FROM
    data
  CROSS JOIN
    n_list ),
  common_n_list AS (
  SELECT
    latlon,
    n,
    COUNT(DISTINCT address) type
  FROM
    substr_list
  GROUP BY
    latlon, n
  HAVING
    type = 1),
  max_common_n AS (
  SELECT
    latlon,
    MAX(n) n
  FROM
    common_n_list
  GROUP BY
    latlon ) --
  --
SELECT
  latlon,
  address,
  SUBSTR(address, 1, n) common_address
FROM
  data
JOIN
  max_common_n 
USING (latlon) 
Row latlon address common_address
1 1 東京都江東区有明1 東京都江東区有明
2 1 東京都江東区有明2 東京都江東区有明
3 2 東京都江東区東雲 東京都江東区東雲
4 2 東京都江東区東雲1 東京都江東区東雲
5 2 東京都江東区東雲2 東京都江東区東雲
6 3 東京都江東区豊洲4 東京都江東区豊洲4