sqlite - 在 sqlite 中计算汉明距离和权重

Question

有没有一种在sqlite中计算汉明距离和重量的好方法？它支持按位运算符，但我想根据汉明权重对结果进行排序，并且 sqlite 不支持位计数。

更详细地说，假设我有这些行:
1011
1000
1100
0011
并且给定第一行(1011)，我想得到最后一行(0011)，如果你和它们，它有最多的 1。

在我的例子中，这些数字大约有 650 位长，我有大约 3500 行。

我发现这个解决方案适用于文本 block ，但我想要更优化的东西:

create table ts (x blob); 
insert into ts(x) values ('00010');
...
select x & '10011', length(replace( x & '10011','0','')) as weight from ts;

Answer 1

SQLite 没有 built-in functions这可以直接帮助解决这个问题。

在 SQLite 3.8.3 或更高版本中，您可以使用递归 common table expression手动计算匹配:

CREATE TABLE t(x);
INSERT INTO t VALUES ('1011'), ('1000'), ('1100'), ('0011');

WITH compare(matches, rest, pattern, original) AS (
  SELECT 0, x, '1011', x FROM t
  UNION ALL
  SELECT matches + (substr(rest, 1, 1) = '1' AND substr(pattern, 1, 1) = '1'),
         substr(rest, 2),
         substr(pattern, 2),
         original
  FROM compare
  WHERE rest != '')
SELECT matches, original
FROM compare
WHERE rest = ''
ORDER BY matches DESC;

3|1011
2|0011
1|1000
1|1100