相关疑难解决方法(0)

我想创建一个模糊搜索算法.然而,经过数小时的研究,我真的很挣扎.

我想创建一个算法,在学校名称列表上执行模糊搜索.

这是我到目前为止所看到的:

我的大部分研究都指向Google和Stackoverflow上的" 字符串指标 ",例如:

• Levenshtein距离
• Damerau-Levenshtein距离
• Needleman-Wunsch算法

然而,这仅仅给出了两个字符串相似的分数.我可以想到将其实现为搜索算法的唯一方法是执行线性搜索并对每个字符串执行字符串度量算法,并返回分数高于某个阈值的字符串.(原来我把我的琴弦存放在一棵树上,但这显然不会帮助我!)

虽然这对于小型列表来说并不是一个坏主意,但对于名为100,000个名称的列表来说,这将是一个问题,并且用户执行了许多查询.

我看到的另一种算法是拼写检查方法,您只需搜索所有可能的拼写错误.然而,这也是非常低效的,因为对于长度为7的单词而言需要超过75,000个单词并且错误计数仅为2.

我需要的？

有人可以建议我一个很好的高效模糊搜索算法.有:

• 算法的名称
• 它是如何工作的或它是如何工作的链接
• Pro和cons以及何时最佳使用(可选)

我知道所有算法都有其优点和缺点,没有最好的算法.

我想编写一个从未真正产生任何东西的Python生成器函数.基本上它是一个"无所事事"的插件,可以被其他代码用来调用生成器(但并不总是需要它的结果).到目前为止我有这个:

def empty_generator():
    # ... do some stuff, but don't yield anything
    if False:
        yield

现在,这可行,但我想知道是否有更具表现力的方式来说同样的事情,即声明一个函数是一个生成器,即使它从不产生任何值.我上面使用的技巧是在我的函数中显示Python一个yield语句,即使它无法访问.

我有大量包含序列的记录('ATCGTGTGCATCAGTTTCGA ...'),最多500个字符.我还有一个较小序列的列表,通常是10-20个字符.我想使用Levenshtein距离来在记录中找到这些较小的序列,允许小的变化或插入(L_distance <= 2).

问题是我还想获得这些较小序列的起始位置,显然它只比较相同长度的序列.

>>> import Levenshtein
>>> s1 = raw_input('first word: ')
first word: ATCGTAATACGATCGTACGACATCGCGGCCCTAGC
>>> s2 = raw_input('second word: ')
first word: TACGAT
>>> Levenshtein.distance(s1,s2)
29

在这个例子中,我想获得位置(7)和距离(在这种情况下为0).

有没有一种简单的方法来解决这个问题,或者我是否必须将较大的序列分解为较小的序列然后为所有这些序列运行Levenshtein距离？这可能需要太多时间.

谢谢.

更新#Naive实现在查找完全匹配后生成所有子字符串.

def find_tag(pattern,text,errors):       
    m = len(pattern)
    i=0
    min_distance=errors+1
    while i<=len(text)-m:
        distance = Levenshtein.distance(text[i:i+m],pattern)
        print text[i:i+m],distance #to see all matches.
        if distance<=errors:
            if distance<min_distance:
                match=[i,distance]
                min_distance=distance
        i+=1
    return match

#Real example. In this case just looking for one pattern, but we have about 50.
import re, Levenshtein

text = …