请教一个模糊查询的算法问题

[Lixin Yu]

需要做一个从大量数据里模糊查找特定字段的查询。

是用 python 实现的，就不加 OT 了吧。。

1 被查询数据是一串字符流，只有4种字母，假设是ABCD，量很大。

2 要查询的特定字段是已知的，以下假设查找目标为：‘ABCDABCD’

3 需要严格的按顺序比对。并可以手动调节可容忍的差异字母的个数。

   例如：当设定为2时，''ABCDABBB‘ 可以通过，’ABCDBCDA‘失败。

目前的方法是差异字母数为0的时候调用正则。

大于0的时候从字符流初始位置开始，一个个截取等长的字符串，然后 for 循环遍历计算差异字符数。感觉速度太慢了。。

由于需要查询的字段很多。想整个好点的算法。

求问有没有什么好的方法可以加速这种模糊比对的？

--

Never say die

[Shell Xu]

你在做基因检索？
好像有这种库，优先考虑一下？
如果要手工实现，考虑一下多模式匹配。这种应用下用正则太辛苦了。

--
来自: python-cn`CPyUG`华蟒用户组(中文Python技术邮件列表)
发言: pyth...@googlegroups.com
退订: python-cn+...@googlegroups.com (向此发空信即退!)
详情: http://code.google.com/p/cpyug/wiki/PythonCn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
无能者无所求，饱食而遨游，泛若不系之舟

[MuSheng]

用多進程或多線程協同處理會快些.

[Lixin Yu]

嗯，是的~

找了下貌似没有找到合适的库。。

多模式匹配好像挺有意思，稍后研究下。

2011/3/9 Shell Xu <shell...@gmail.com>

--

Never say die

[依云]

感觉和 agrep 差不多，你可以去看看 agrep 是怎么做的。

--
Best regards,
lilydjwg

Linux Vim Python 我的博客
http://bit.ly/lilydjwg or http://goo.gl/y4Gsy

[redaready]

https://github.com/sunlightlabs/jellyfish

http://code.google.com/p/simile-vicino/

[john]

我记得某个搜索引擎的开发者，在飞机上写了一段Python的搜索算法，很短的，非常好。

后来写成简短的教材，放在网上，被中文化了。

你可以搜搜，看起来和你的需求很相似。

在 2011年3月9日 下午8:26，redaready <redare...@gmail.com>写道：

https://github.com/sunlightlabs/jellyfish

http://code.google.com/p/simile-vicino/

[Rujia Liu]

2011/3/9 Lixin Yu <lixi...@gmail.com>:

> 需要做一个从大量数据里模糊查找特定字段的查询。
> 是用 python 实现的，就不加 OT 了吧。。
> 1 被查询数据是一串字符流，只有4种字母，假设是ABCD，量很大。

量很大是多大？1M个字符和1G个字符，用到的算法是完全不一样的。

> 2 要查询的特定字段是已知的，以下假设查找目标为：'ABCDABCD'
> 3 需要严格的按顺序比对。并可以手动调节可容忍的差异字母的个数。
> 例如：当设定为2时，''ABCDABBB' 可以通过，'ABCDBCDA'失败。
> 目前的方法是差异字母数为0的时候调用正则。
> 大于0的时候从字符流初始位置开始，一个个截取等长的字符串，然后 for 循环遍历计算差异字符数。感觉速度太慢了。。
> 由于需要查询的字段很多。想整个好点的算法。
> 求问有没有什么好的方法可以加速这种模糊比对的？

agrep之类的东西（以及前面几个回复提到的库），都不能处理超大的串，至于搜索引擎的开发者在飞机上写的那个，很可能针对的是搜索引擎平时处理的关键字序列（借助倒排索引中找），而不是DNA字符串（借助suffix
tree/array），问题不一样，方法不能通用。当然，如果文本是几M的级别，还能忍。再大的话，肯定挂。这时候一般要用到filtering。你这个是hamming
distance，可以用spaced seeds。BLAST中有实现，但是开源的库我就不知道了。搜一搜相关论文有没有公布的code吧。

总之，楼主先弄清楚自己面临的数据量，以及最大可以容忍的差异字母个数，然后再决定是用简单办法，还是复杂的。

- Rujia

[xiong zicheng]

ABCD 编码成0001 0010 0100 1000 然后进行位运算，看结果中1的个数 

可以结合KMP

[Rujia Liu]

2011/3/10 xiong zicheng <xiong...@gmail.com>:

> ABCD 编码成0001 0010 0100 1000 然后进行位运算，看结果中1的个数
> 可以结合KMP

如何结合？貌似很难吧
而且就算结合了，仍然每次要扫描整个文本串，处理不了大数据。

- Rujia

[azer]

猜一下：是高通量测序序列的barcode search吗?

2011/3/9 Lixin Yu <lixi...@gmail.com>

[Lixin Yu]

@aze，是 TAL target search。

@Rujia Liu
数据用的是DNA库，最小的库是几十M，加起来肯定过G。。差异数看配对情况，一般最多5、6个的样子。

我觉得 xiong zicheng 的方法应该可以加速每一个字串的比较吧，这样不用对每一个字串都遍历一下查找差异数了。

不过怎样快速检测一01字串里有多少个1呢？。。

2011/3/10 azer <aze...@gmail.com>

--

Never say die

[azer]

将01字符串转成2进制

def bitcount(num):

    cn = 0

    while num:

        cn += 1

        num &= num -1

    return cn

for i in range(10):

    print i, bin(i), bitcount(i)

2011/3/10 Lixin Yu <lixi...@gmail.com>

[Rujia Liu]

2011/3/10 Lixin Yu <lixi...@gmail.com>:

> @aze，是 TAL target search。
>
> @Rujia Liu
> 数据用的是DNA库，最小的库是几十M，加起来肯定过G。。差异数看配对情况，一般最多5、6个的样子。

所有库都要找么？

> 我觉得 xiong zicheng 的方法应该可以加速每一个字串的比较吧，这样不用对每一个字串都遍历一下查找差异数了。

当然可以加速，但是看你的需求了。数据量太大的话，这种加速时不够的。你说查询很多（一般来说“很多”的意思至少得有上万个吧？），上G的数据，每次查询都得全部遍历一遍，乘以1万的话，相当于要处理10T的数据，光是I/O时间就不短了。当然，如果“每次查询都需要几分钟”对你来说是可以承受的时间（或者你有条件较好的并行化），就像这样用位运算加速直接找就可以了。

> 不过怎样快速检测一01字串里有多少个1呢？。。
下面是一个链接，你可以自己比较一下里面的方法

http://gurmeet.net/puzzles/fast-bit-counting-routines/

- Rujia

[HYRY]

以前在ChinaUnix上回答过一个类似的问题，你可以看看对你是否有帮助：

http://bbs2.chinaunix.net/viewthread.php?tid=1713955&extra=page%3D1&ordertype=1&page=1

[HYRY]

下面的地址的讨论似乎更全一些，你可以看看。也许和你的问题不太一样，不过也许能有所启发。

http://bbs.chinaunix.net/archiver/?tid-1713955.html

[jame2981]

从这上面看来，其实还是自符串查找。
字符串查找主要是，要尽量跳过字符来提高速度。比如目标数据是abcdabdd,要查的是abdd当目标数据的第3位和查找数据的第3位对比时， 发现数据不相等。就直接跳过目标数据的第4位和查找数据的第4位进行比较，直接拿目标数据的第5位和查找数据的第一位进行比较。

差异字母个数，只是记录不相等的字符的时候的一个记数，为0的时候就是字符串查找。设置的的值就是允许对应位置不相等的次数。

[jame2981]

回复有误。。 第一段最后一句话“直接拿目标数据的第4位和查找数据的第一位进行比较。”

On 03/09/2011 05:47 PM, Lixin Yu wrote:

[Rujia Liu]

你描述的是KMP算法。但是对于模糊匹配，貌似很难修改KMP算法以达到同样的时间效率（即：文本串指针永不回溯）。反正我没想出来怎么修改。如果你想出来了，可以share一下，最好贴个程序

2011/3/10 jame2981 <jame...@gmail.com>:

[-]

请问python中有像java中JUNG这样的软件包吗？

[saner w]

试写了一个，但没测试效率，要查的目标只能是纯字母

code：

import re

def Match(scrStr, regStr, num=None):

  if num:

    regs = []

    for i in range(len(regStr)-num+1):

      if i == 0:

        start = ''

      else:

        start = regStr[0:i]

      m = '[ABCD]{%s}'%num

      end = regStr[i+num:]

      regs.append(start+m+end)

    for p in regs:

      print p

      if re.search(p, scrStr):

        return True

    return False

  else:

    if re.search(regStr, scrStr):

      return True

    else:

      return False

# end

[Rujia Liu]

效率才是重点。不然随便怎么写都可以的 :)

2011/3/10 saner w <san...@gmail.com>:

[saner w]

在 2011年3月10日 下午5:52，Rujia Liu <ruji...@gmail.com>写道：

效率才是重点。不然随便怎么写都可以的 :)

哈哈！ 是这个理，我只是手痒 

[Rujia Liu]

2011/3/10 saner w <san...@gmail.com>:

>
>
> 在 2011年3月10日 下午5:52，Rujia Liu <ruji...@gmail.com>写道：
>>
>> 效率才是重点。不然随便怎么写都可以的 :)
>
> 哈哈！ 是这个理，我只是手痒

赞执行力！（干活去，不闲聊了）

[Yu Hai]

把所有可以接受的模式串构建一棵trie树然后遍历原串，

for substr in string

  if sub in trie tree

    output

发自我的 iPad

[redaready]

果然是DNA的。

可以看看biopython有没有现成能用的。

http://biopython.org/wiki/Biopython

另外后缀树也经常用于基因查找，比较。

http://en.wikipedia.org/wiki/Suffix_tree

[jame2981]

刚刚想了一下，可能会出现点意外，可能只可以最小的回溯。我晚上试一下