谷歌BigQuery中有一种测量字符串相似度的方法吗？

Question

我想知道是否有一种在BigQuery中测量字符串相似度的方法。

看起来这将是一个很棒的函数。

我的情况是，我需要比较两个URL的相似性，以确保它们指的是同一篇文章。

我可以找到使用JavaScript的示例，所以可能UDF是一个好方法，但我从未使用过UDF（或JavaScript）。

只是想知道是否有使用现有正则表达式函数的方法，或者是否有人能够帮助我将JavaScript示例转换为UDF。

非常感谢任何帮助。

编辑：添加一些示例代码

如果我定义了一个UDF：

// distance function

function levenshteinDistance (row, emit) {

  //if (row.inputA.length <= 0 ) {var myresult = row.inputB.length};
  if (typeof row.inputA === 'undefined') {var myresult = 1};
  if (typeof row.inputB === 'undefined') {var myresult = 1};
  //if (row.inputB.length <= 0 ) {var myresult = row.inputA.length};

    var myresult = Math.min(
        levenshteinDistance(row.inputA.substr(1), row.inputB) + 1,
        levenshteinDistance(row.inputB.substr(1), row.inputA) + 1,
        levenshteinDistance(row.inputA.substr(1), row.inputB.substr(1)) + (row.inputA[0] !== row.inputB[0] ? 1 : 0)
    ) + 1;

  emit({outputA: myresult})

}

bigquery.defineFunction(
  'levenshteinDistance',                           // Name of the function exported to SQL
  ['inputA', 'inputB'],                    // Names of input columns
  [{'name': 'outputA', 'type': 'integer'}],  // Output schema
  levenshteinDistance                       // Reference to JavaScript UDF
);

// make a test function to test individual parts

function test(row, emit) {
  if (row.inputA.length <= 0) { var x = row.inputB.length} else { var x = row.inputA.length};
  emit({outputA: x});
}

bigquery.defineFunction(
  'test',                           // Name of the function exported to SQL
  ['inputA', 'inputB'],                    // Names of input columns
  [{'name': 'outputA', 'type': 'integer'}],  // Output schema
  test                       // Reference to JavaScript UDF
);

任何我尝试的测试都带有这样的查询：

SELECT outputA FROM (levenshteinDistance(SELECT "abc" AS inputA, "abd" AS inputB))

我遇到了错误：

错误：TypeError: 无法读取未定义的属性 'substr'，位于第11行，38-39列 错误位置：用户定义函数

看起来可能是row.inputA不是字符串，或者由于某种原因字符串函数无法在其上工作。不确定这是否是类型问题，或者UDF默认可以使用哪些有趣的utils。

再次感谢任何帮助，谢谢。

- andrewm4894

---

请您能否分享至少5个例子，以便更好地为您提供正则表达式或JS解决方案的建议。 - Pentium10

Answer 1

准备好使用共享UDF - Levenshtein距离:

SELECT fhoffa.x.levenshtein('felipe', 'hoffa')
 , fhoffa.x.levenshtein('googgle', 'goggles')
 , fhoffa.x.levenshtein('is this the', 'Is This The')

6  2  0

Soundex:

(Note: This is already in Chinese. It says "Soundex.")

SELECT fhoffa.x.soundex('felipe')
 , fhoffa.x.soundex('googgle')
 , fhoffa.x.soundex('guugle')

F410  G240  G240

模糊选择一个：

SELECT fhoffa.x.fuzzy_extract_one('jony' 
  , (SELECT ARRAY_AGG(name) 
   FROM `fh-bigquery.popular_names.gender_probabilities`) 
  #, ['john', 'johnny', 'jonathan', 'jonas']
)

johnny

如何操作:

• https://medium.com/@hoffa/new-in-bigquery-persistent-udfs-c9ea4100fd83

- Felipe Hoffa

---

我尝试了 fuzzy_extract_one 但是出现了 Invalid choices at gs://fh-bigquery/js/fuzzball.umd.min.js line 1, columns 5895-5896 的错误，但我无法弄清原因。 - luisvenezian

哦，@luisvenezian，我现在为Snowflake工作，所以我将无法修复我的旧查询。但是如果你有兴趣的话，Snowflake有本地的Levenhstein https://docs.snowflake.com/en/sql-reference/functions/editdistance.html - Felipe Hoffa

Answer 2

如果您熟悉Python，可以使用从GCS加载的外部库在BigQuery中使用fuzzywuzzy定义的函数。

步骤:

1. 下载fuzzywuzzy的javascript版本(fuzzball) 2. 取出库的编译文件：dist/fuzzball.umd.min.js并将其重命名为更清晰的名称(如fuzzball) 3. 将其上传到Google Cloud存储桶 4. 创建一个临时函数来在查询中使用该库(在OPTIONS中设置路径)

CREATE TEMP FUNCTION token_set_ratio(a STRING, b STRING)
RETURNS FLOAT64
LANGUAGE js AS """
  return fuzzball.token_set_ratio(a, b);
"""
OPTIONS (
  library="gs://my-bucket/fuzzball.js");

with data as (select "my_test_string" as a, "my_other_string" as b)

SELECT  a, b, token_set_ratio(a, b) from data

- Colin Le Nost

---

这是一个很好的想法，但我无法让它运行起来。返回SyntaxError: Invalid regular expression: <huge list of characters like -¾٠-٩۰-۹߀-߉०-९০-৯৴-৹ etc.>: Range out of order in character class at gs://test-udfs/fuzzball.js line 4, columns 9575-9576。 - tw0000

我刚刚重新下载了文件并重试了一次，对我来说仍然有效。你使用的是标准SQL吗？在哪些字符串上？ - Colin Le Nost

Answer 3

使用JS中的Levenshtein算法是可行的。您可以使用该算法获取绝对字符串距离，或通过计算 abs(strlen - distance / strlen) 将其转换为百分比相似度。

最简单的实现方式是定义一个Levenshtein UDF，它需要两个输入a和b，并计算它们之间的距离。该函数可以返回a、b和距离。

要调用它，您需要将两个URL作为列传递，并将其别名为'a'和'b'：

SELECT a, b, distance
FROM
  Levenshtein(
     SELECT
       some_url AS a, other_url AS b
     FROM
       your_table
  )

- thomaspark

---

谢谢 - 这正是我想要使用它的方式，但是我链接的JS解决方案似乎不能直接在BQ UDF中实现，我不确定我做错了什么。 - andrewm4894

嗨，这里有一个您可以使用的Levenshtein实现：https://storage.googleapis.com/thomaspark-sandbox/udf-examples/pataky.js（引用为“gs://thomaspark-sandbox/udf-examples/pataky.js”）。我为维基百科的一个示例编写了它，因此它绑定到输入列“target”和“title”。它返回绝对编辑数字距离。 - thomaspark

谢谢 - 我肯定自己想不出来。我会用它来学习和玩耍的。谢谢，非常感谢。 - andrewm4894

很高兴能帮忙！我们将来会发布一张JS函数目录，用户可以在他们的查询中调用这些函数；我们肯定可以包含Levenshtein。 - thomaspark

这是一个很好的想法，如果我们能够在某个地方看到代码、进行调试，然后再做出贡献，那将是一个很好的学习起点。干杯！ - andrewm4894

Answer 4

使用 WITH OFFSET 而不是 ROW_NUMBER() OVER()，可以得到更简单的汉明距离版本。

#standardSQL
WITH Input AS (
  SELECT 'abcdef' AS strings UNION ALL
  SELECT 'defdef' UNION ALL
  SELECT '1bcdef' UNION ALL
  SELECT '1bcde4' UNION ALL
  SELECT '123de4' UNION ALL
  SELECT 'abc123'
)
SELECT 'abcdef' AS target, strings, 
  (SELECT COUNT(1) 
    FROM UNNEST(SPLIT('abcdef', '')) a WITH OFFSET x
    JOIN UNNEST(SPLIT(strings, '')) b WITH OFFSET y
    ON x = y AND a != b) hamming_distance
FROM Input

- Mikhail Berlyant

Answer 5

我找不到直接的答案，因此我提出了这个标准SQL解决方案。

#standardSQL
CREATE TEMP FUNCTION HammingDistance(a STRING, b STRING) AS (
  (
  SELECT
    SUM(counter) AS diff
  FROM (
    SELECT
      CASE
        WHEN X.value != Y.value THEN 1
        ELSE 0
      END AS counter
    FROM (
      SELECT
        value,
        ROW_NUMBER() OVER() AS row
      FROM
        UNNEST(SPLIT(a, "")) AS value ) X
    JOIN (
      SELECT
        value,
        ROW_NUMBER() OVER() AS row
      FROM
        UNNEST(SPLIT(b, "")) AS value ) Y
    ON
      X.row = Y.row )
   )
);

WITH Input AS (
  SELECT 'abcdef' AS strings UNION ALL
  SELECT 'defdef' UNION ALL
  SELECT '1bcdef' UNION ALL
  SELECT '1bcde4' UNION ALL
  SELECT '123de4' UNION ALL
  SELECT 'abc123'
)

SELECT strings, 'abcdef' as target, HammingDistance('abcdef', strings) as hamming_distance
FROM Input;

与其他解决方案（比如这个）相比，它需要两个字符串（长度相同，遵循汉明距离的定义），并输出预期的距离。 BigQuery 相似度 标准SQL 汉明距离

- jquinter

---

喜欢在标准 SQL 中使用函数的想法——这个想法我之前没有想到过。谢谢。 - andrewm4894

Answer 6

我是这样做的：

CREATE TEMP FUNCTION trigram_similarity(a STRING, b STRING) AS (
  (
    WITH a_trigrams AS (
      SELECT
        DISTINCT tri_a
      FROM
        unnest(ML.NGRAMS(SPLIT(LOWER(a), ''), [3,3])) AS tri_a
    ),
    b_trigrams AS (
      SELECT
        DISTINCT tri_b
      FROM
        unnest(ML.NGRAMS(SPLIT(LOWER(b), ''), [3,3])) AS tri_b
    )
    SELECT
      COUNTIF(tri_b IS NOT NULL) / COUNT(*)
    FROM
      a_trigrams
      LEFT JOIN b_trigrams ON tri_a = tri_b
  )
);

这里是与Postgres的pg_trgm的比较：

select trigram_similarity('saemus', 'seamus');
-- 0.25 vs. pg_trgm 0.272727

select trigram_similarity('shamus', 'seamus');
-- 0.5 vs. pg_trgm 0.4

我在如何在Google BigQuery中执行三元组操作？上给出了相同的答案。

- Seamus Abshere

Answer 7

当我在寻找Felipe的答案时，我自己也做了一个查询，并得到了两个版本，一个被称为字符串近似，另一个是字符串相似度。第一个是查找源字符串和测试字符串之间最短距离，并返回0到1之间的分数，其中1表示完全匹配。它总是基于两者中最长的字符串进行评分。结果发现其返回类似于Levensthein距离的结果。

#standardSql
CREATE OR REPLACE FUNCTION `myproject.func.stringApproximation`(sourceString STRING, testString STRING) AS (
(select avg(best_result) from (
                              select if(length(testString)<length(sourceString), sourceoffset, testoffset) as ref, 
                              case 
                                when min(result) is null then 0
                                else 1 / (min(result) + 1) 
                              end as best_result,
                              from (
                                       select *,
                                              if(source = test, abs(sourceoffset - (testoffset)),
                                              greatest(length(testString),length(sourceString))) as result
                                       from unnest(split(lower(sourceString),'')) as source with offset sourceoffset
                                                cross join
                                            (select *
                                             from unnest(split(lower(testString),'')) as test with offset as testoffset)
                                       ) as results
                              group  by ref
                                 )
        )
);

第二种方法是第一种方法的变体，它将查看匹配距离序列，因此与其前面或后面的字符相等距离处匹配的字符将计为一个点。这种方法效果相当不错，比字符串近似好，但还不如我想象的那么好（请参见下面的示例输出）。

    #standarSql
    CREATE OR REPLACE FUNCTION `myproject.func.stringResemblance`(sourceString STRING, testString STRING) AS (
(
select avg(sequence)
from (
      select ref,
             if(array_length(array(select * from comparison.collection intersect distinct
                                   (select * from comparison.before))) > 0
                    or array_length(array(select * from comparison.collection intersect distinct
                                          (select * from comparison.after))) > 0
                 , 1, 0) as sequence

      from (
               select ref,
                      collection,
                      lag(collection) over (order by ref)  as before,
                      lead(collection) over (order by ref) as after
               from (
                     select if(length(testString) < length(sourceString), sourceoffset, testoffset) as ref,
                            array_agg(result ignore nulls)                                          as collection
                     from (
                              select *,
                                     if(source = test, abs(sourceoffset - (testoffset)), null) as result
                              from unnest(split(lower(sourceString),'')) as source with offset sourceoffset
                                       cross join
                                   (select *
                                    from unnest(split(lower(testString),'')) as test with offset as testoffset)
                              ) as results
                     group by ref
                        )
               ) as comparison
      )

)
);

现在这里是一个结果的样例：

#standardSQL
with test_subjects as (
  select 'benji' as name union all
  select 'benjamin' union all
  select 'benjamin alan artis' union all
  select 'ben artis' union all
  select 'artis benjamin' 
)

select name, quick.stringApproximation('benjamin artis', name) as approxiamtion, quick.stringResemblance('benjamin artis', name) as resemblance
from test_subjects

order by resemblance desc

This returns

+---------------------+--------------------+--------------------+
| name                | approximation      | resemblance        |
+---------------------+--------------------+--------------------+
| artis benjamin      | 0.2653061224489796 | 0.8947368421052629 |
+---------------------+--------------------+--------------------+
| benjamin alan artis | 0.6078947368421053 | 0.8947368421052629 |
+---------------------+--------------------+--------------------+
| ben artis           | 0.4142857142857142 | 0.7142857142857143 |
+---------------------+--------------------+--------------------+
| benjamin            | 0.6125850340136053 | 0.5714285714285714 |
+---------------------+--------------------+--------------------+
| benji               | 0.36269841269841263| 0.28571428571428575|
+----------------------------------------------------------------

编辑：更新相似度算法以改善结果。

- neydroydrec

Answer 8

试试 Flookup 用于 Google Sheets... 它绝对比 Levenshtein 距离更快，并且可以直接计算百分比相似度。

你可能会发现一个有用的 Flookup 函数是：

FUZZYMATCH (string1, string2)

参数详情

1. string1：与 string2 进行比较。
2. string2：与 string1 进行比较。

然后根据这些比较计算百分比相似度。两个参数都可以是范围。

我目前正在尝试为大型数据集进行优化，所以您的反馈将非常受欢迎。

编辑：我是 Flookup 的创建者。

- user9937931

---

请添加一份声明，以便在帖子中清楚地表明这是您的产品。 - elixenide