Рассчитать расстояние Хемминга и вес в sqlite

Question

Есть хороший способ рассчитать расстояние Хэмминга и вес в sqlite? Он поддерживает побитовые операторы, но я хочу упорядочить результаты, основываясь на весе Хэмминга, и в sqlite нет поддержки для bitcount.

Чтобы быть более сложным, скажем, у меня есть эти строки: 1011 1000 1100 0011 и учитывая 1-ую строку (1011), я хотел бы получить в результате последнюю строку (0011), которая имеет наибольшее 1 с, если вы И их.

В моем случае число будет около 650 цифр, а у меня около 3500 строк.

Я нашел это решение, которое работает с каплями текста, но я хотел бы что-то более оптимальное:

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 не имеет встроенных функций, которые могли бы помочь с этим напрямую.

В SQLite 3.8.3 или более поздней версии вы можете использовать рекурсивное общее табличное выражение для вычисления совпадений вручную:

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