计算汉明距离的索引访问

Question

我有一个表格，在数据库列中填充了字符串。我正在计算该列与绑定变量的汉明距离，然后使用单独的语句输出所有字符串值，例如汉明距离小于或等于3。

由于字符串值已经被绑定，所以无法在期望结果上使用虚拟列，因为据我所知，这需要函数具有静态参数。此外，我不能使用基于函数的索引，因为我的输出是派生列。

是否有一种替代方案来优化查询而不执行完整的表扫描？当前扫描需要5-7秒钟，我希望将其缩短到300毫秒。谢谢。

以下是部分源代码：

CREATE OR REPLACE FUNCTION HAMMING_DIS(string1 IN varchar2, string2 IN varchar2)
RETURN number IS
distance number := 0;
BEGIN
   FOR counter IN 1..length(string1) LOOP
      IF substr(string1, counter, 1) = substr(string2, counter, 1) THEN
        distance:= distance + 1;
      END IF;
   END LOOP;
RETURN distance;
END;

SELECT * FROM
(SELECT FULL_NM AS FULL_NAME, HAMMING_DIS(FIRST_NM,'&A') AS HAMMING_DISTANCE 
 FROM STRINGS_OF_NAMES
 )
WHERE HAMMING_DISTANCE > 3;

- Francis

---

你具体要比较什么？是一个带变量的列吗？还是与该列的每个其他实例进行比较？此外，您能否提供有关这些值的一些信息？它们始终具有相同的长度吗？如果不是，则我假设函数或查询需要丢弃具有不同长度的值。 "小于或等于3"是静态的，还是您想比较不同的值？ - Jon Heller

你是否使用PL/SQL函数来计算汉明距离？如果是的话，请展示一下这个函数的源代码。可能会受到SQL-PL/SQL上下文切换的影响。 - krokodilko

Answer 1

感谢澄清...我会删除我的另一个答案。

如果...这是很大的"如果"...

• A) 你总是想要找到汉明距离小于3的字符串(例如不是有时小于3，有时小于5)，并且
• B) 你的表足够静态以允许使用BITMAP索引，

那么你也许可以利用这样一个事实：任何对你的查询的答案都必须在前4个字符中至少有2个匹配项。

所以，

CREATE TABLE matt1 ( id number, str varchar(30) );

INSERT INTO matt1 SELECT rownum, dbms_random.string('U', dbms_random.value(1,30)) from dual connect by rownum <= 10000;

CREATE BITMAP INDEX i1 ON matt1 ( substr(rpad(str,4,' '),1,1) );
CREATE BITMAP INDEX i2 ON matt1 ( substr(rpad(str,4,' '),2,1) );
CREATE BITMAP INDEX i3 ON matt1 ( substr(rpad(str,4,' '),3,1) );
CREATE BITMAP INDEX i4 ON matt1 ( substr(rpad(str,4,' '),4,1) );


SELECT m.*, hamming_dis(str,:input) FROM matt1 m WHERE 
(
(substr(rpad(str,4,' '),1,1) = substr(rpad(:input,4,' '),1,1) AND 
substr(rpad(str,4,' '),2,1) = substr(rpad(:input,4,' '),2,1))
OR
(substr(rpad(str,4,' '),1,1) = substr(rpad(:input,4,' '),1,1) AND 
substr(rpad(str,4,' '),3,1) = substr(rpad(:input,4,' '),3,1))
OR
(substr(rpad(str,4,' '),1,1) = substr(rpad(:input,4,' '),1,1) AND 
substr(rpad(str,4,' '),4,1) = substr(rpad(:input,4,' '),4,1))
OR
(substr(rpad(str,4,' '),2,1) = substr(rpad(:input,4,' '),2,1) AND 
substr(rpad(str,4,' '),3,1) = substr(rpad(:input,4,' '),3,1))
OR
(substr(rpad(str,4,' '),2,1) = substr(rpad(:input,4,' '),2,1) AND 
substr(rpad(str,4,' '),4,1) = substr(rpad(:input,4,' '),4,1))
OR
(substr(rpad(str,4,' '),3,1) = substr(rpad(:input,4,' '),3,1) AND 
substr(rpad(str,4,' '),4,1) = substr(rpad(:input,4,' '),4,1))
)
AND hamming_dis(str,:input) <= 3;

您应该看到有许多BITMAP OR和BITMAP AND操作的执行计划。

这可能会更快，因为您将限制实际需要计算精确汉明距离的行数。

注意：我看到您想要的是<=3，而不是<3。这种方法应该一直可扩展到一定程度。

- Matthew McPeak