计算方格的汉明距离和重量 [英] calculate hamming distance and weight in sqlite

问题描述

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

Is there a good way to calculate hamming distance and weight in sqlite? It supports bit-wise operators but I want to order results based on hamming weight, and there is no support for bitcount in sqlite.

更详细地说，假设我有这些行: 1011 1000 1100 0011 并给出第一行(1011)的结果，我想得到的最后一行(0011)如果与它们相加，则得出的数字最多.

To be more elaborate, let's say I have those rows: 1011 1000 1100 0011 and given the 1st row (1011) I would like to get as a result last row (0011) which has the most 1s if you AND them.

在我的情况下，数字的长度约为650位，我大约有3500行.

In my case the numbers will be about 650 digits long, and I have about 3500 rows.

我已经找到了适用于文本斑点的解决方案，但是我想要更优化的方法:

I've found this solution which works with blobs of text, but I would like something more optimal:

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

推荐答案

SQLite没有内置函数可以直接帮助解决这个问题.

SQLite has no built-in functions that could directly help with this.

在SQLite 3.8.3或更高版本中，您可以使用递归公用表表达式进行计算手动进行比赛:

In SQLite 3.8.3 or later, you could use a recursive common table expression to compute the matches by hand:

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

这篇关于计算方格的汉明距离和重量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！