sparql - 使用 iSPARQL 通过相似性度量来比较值

Question

我有一个问题要问你。

我想编写一个查询，检索与给定字符串“Londn”相似的值(给定相似度函数，例如 Lev)，以便与谓词“RDFS:label”进行比较DBP百科。例如，在输出中，我想获取“London”的值。 我读到，一种可用的方法可能是使用 iSPARQL(“不精确的 SPARQL”)，尽管它在文献中并未得到广泛使用。

我可以使用 iSPARQL 还是有某种 SPARQL 方法来执行相同的操作？

Answer 1

简短版本 - 您可以在纯 SPARQL 中执行其中一些操作

您可以使用这样的查询来查找名称类似于“Londn”的城市，并按(一种衡量)相似度对它们进行排序。答案的其余部分解释了它是如何工作的:

select ?city ?percent where {
  ?city a dbpedia-owl:City ;
        rdfs:label ?label .
  filter langMatches( lang(?label), 'en' )

  bind( replace( concat( 'x', str(?label) ), "^x[^Londn]*([L]?)[^ondn]*([o]?)[^ndn]*([n]?)[^dn]*([d]?)[^n]*([n]?).*$", '$1$2$3$4$5' ) as ?match )
  bind( xsd:float(strlen(?match))/strlen(str(?label)) as ?percent )
}
order by desc(?percent)
limit 100

SPARQL results

city                                  percent
----------------------------------------------
http://dbpedia.org/resource/London    0.833333
http://dbpedia.org/resource/Bonn      0.75
http://dbpedia.org/resource/Loudi     0.6
http://dbpedia.org/resource/Ladnu     0.6
http://dbpedia.org/resource/Lonar     0.6
http://dbpedia.org/resource/Longnan   0.571429
http://dbpedia.org/resource/Longyan   0.571429
http://dbpedia.org/resource/Luoding   0.571429
http://dbpedia.org/resource/Lodhran   0.571429
http://dbpedia.org/resource/Lom%C3%A9 0.5
http://dbpedia.org/resource/Andong    0.5

计算字符串相似度指标

Note: the code in this part of this answer works in Apache Jena. There's actually an edge case that causes this to (correctly) fail in Virtuoso. The update at the end addresses this issue.

SPARQL 中没有内置任何内容来计算字符串匹配距离，但您可以使用 SPARQL 中的正则表达式替换机制来完成其中一些操作。假设您要匹配某些字符串中的序列“cat”。然后，您可以使用这样的查询来计算序列“cat”中存在给定字符串的数量:

select ?string ?match where {
  values ?string { "cart" "concatenate" "hat" "pot" "hop" }
  bind( replace( ?string, "^[^cat]*([c]?)[^at]*([a]?)[^t]*([t]?).*$", "$1$2$3" ) as ?match )
}

-------------------------
| string        | match |
=========================
| "cart"        | "cat" |
| "concatenate" | "cat" |
| "hat"         | "at"  |
| "pot"         | "t"   |
| "hop"         | ""    |
-------------------------

通过检查字符串和匹配的长度，您应该能够计算一些不同的相似性度量。作为一个使用您提到的“伦敦”输入的更复杂的示例。百分比列是与输入匹配的字符串的百分比。

select ?input
       ?string
       (strlen(?match)/strlen(?string) as ?percent)
where {
  values ?string { "London" "Londn" "London Fog" "Lando" "Land Ho!"
                   "concatenate" "catnap" "hat" "cat" "chat" "chart" "port" "part" }

  values (?input ?pattern ?replacement) {
    ("cat"   "^[^cat]*([c]?)[^at]*([a]?)[^t]*([t]?).*$"                              "$1$2$3")
    ("Londn" "^[^Londn]*([L]?)[^ondn]*([o]?)[^ndn]*([n]?)[^dn]*([d]?)[^n]*([n]?).*$" "$1$2$3$4$5")
  }

  bind( replace( ?string, ?pattern, ?replacement) as ?match )
}
order by ?pattern desc(?percent)

--------------------------------------------------------
| input   | string        | percent                    |
========================================================
| "Londn" | "Londn"       | 1.0                        |
| "Londn" | "London"      | 0.833333333333333333333333 |
| "Londn" | "Lando"       | 0.6                        |
| "Londn" | "London Fog"  | 0.5                        |
| "Londn" | "Land Ho!"    | 0.375                      |
| "Londn" | "concatenate" | 0.272727272727272727272727 |
| "Londn" | "port"        | 0.25                       |
| "Londn" | "catnap"      | 0.166666666666666666666666 |
| "Londn" | "cat"         | 0.0                        |
| "Londn" | "chart"       | 0.0                        |
| "Londn" | "chat"        | 0.0                        |
| "Londn" | "hat"         | 0.0                        |
| "Londn" | "part"        | 0.0                        |
| "cat"   | "cat"         | 1.0                        |
| "cat"   | "chat"        | 0.75                       |
| "cat"   | "hat"         | 0.666666666666666666666666 |
| "cat"   | "chart"       | 0.6                        |
| "cat"   | "part"        | 0.5                        |
| "cat"   | "catnap"      | 0.5                        |
| "cat"   | "concatenate" | 0.272727272727272727272727 |
| "cat"   | "port"        | 0.25                       |
| "cat"   | "Lando"       | 0.2                        |
| "cat"   | "Land Ho!"    | 0.125                      |
| "cat"   | "Londn"       | 0.0                        |
| "cat"   | "London"      | 0.0                        |
| "cat"   | "London Fog"  | 0.0                        |
--------------------------------------------------------

更新

上面的代码在 Apache Jena 中有效，但在 Virtuoso 中失败，因为该模式可以匹配空字符串。例如，如果您在 DBpedia 的端点(由 Virtuoso 提供支持)上尝试以下查询，您将收到以下错误:

select (replace( "foo", ".*", "x" ) as ?bar) where {}

Virtuoso 22023 Error The regex-based XPATH/XQuery/SPARQL replace() function can not search for a pattern that can be found even in an empty string

这让我很惊讶，但是 replace 的规范说它是基于 XPath fn:replace 。 fn:replace 的文档说:

An error is raised [err:FORX0003] if the pattern matches a zero-length string, that is, if the expression fn:matches("", $pattern, $flags) returns true. It is not an error, however, if a captured substring is zero-length.

不过，我们可以通过在模式和字符串的开头添加一个字符来解决这个问题:

select ?input
       ?string
       (strlen(?match)/strlen(?string) as ?percent)
where {
  values ?string { "London" "Londn" "London Fog" "Lando" "Land Ho!"
                   "concatenate" "catnap" "hat" "cat" "chat" "chart" "port" "part" }

  values (?input ?pattern ?replacement) {
    ("cat"   "^x[^cat]*([c]?)[^at]*([a]?)[^t]*([t]?).*$"                              "$1$2$3")
    ("Londn" "^x[^Londn]*([L]?)[^ondn]*([o]?)[^ndn]*([n]?)[^dn]*([d]?)[^n]*([n]?).*$" "$1$2$3$4$5")
  }

  bind( replace( concat('x',?string), ?pattern, ?replacement) as ?match )
}
order by ?pattern desc(?percent)

--------------------------------------------------------
| input   | string        | percent                    |
========================================================
| "Londn" | "Londn"       | 1.0                        |
| "Londn" | "London"      | 0.833333333333333333333333 |
| "Londn" | "Lando"       | 0.6                        |
| "Londn" | "London Fog"  | 0.5                        |
| "Londn" | "Land Ho!"    | 0.375                      |
| "Londn" | "concatenate" | 0.272727272727272727272727 |
| "Londn" | "port"        | 0.25                       |
| "Londn" | "catnap"      | 0.166666666666666666666666 |
| "Londn" | "cat"         | 0.0                        |
| "Londn" | "chart"       | 0.0                        |
| "Londn" | "chat"        | 0.0                        |
| "Londn" | "hat"         | 0.0                        |
| "Londn" | "part"        | 0.0                        |
| "cat"   | "cat"         | 1.0                        |
| "cat"   | "chat"        | 0.75                       |
| "cat"   | "hat"         | 0.666666666666666666666666 |
| "cat"   | "chart"       | 0.6                        |
| "cat"   | "part"        | 0.5                        |
| "cat"   | "catnap"      | 0.5                        |
| "cat"   | "concatenate" | 0.272727272727272727272727 |
| "cat"   | "port"        | 0.25                       |
| "cat"   | "Lando"       | 0.2                        |
| "cat"   | "Land Ho!"    | 0.125                      |
| "cat"   | "Londn"       | 0.0                        |
| "cat"   | "London"      | 0.0                        |
| "cat"   | "London Fog"  | 0.0                        |
--------------------------------------------------------