这段查找字符串邻域的代码可以加快速度吗？

Question

给定一个输入字符串，我想找到Levenshtein distance2内所有其他字符串的集合。例如，如果输入字符串为“aaa”，字母表为['a'，'b']，则我们有：

{'baaa', 'aab', 'a', 'aaaaa', 'baab', 'abbaa', 'abaa', 'aaabb', 'abb', 'aaab', 'ababa', 'aa', 'aabb', 'baba', 'baaab', 'aabab', 'aaaab', 'abaaa', 'aabaa', 'bbaaa', 'abaab', 'aaaa', 'baaaa', 'bab', 'bba', 'aba', 'aaaba', 'ba', 'aabba', 'abab', 'baa', 'aaa', 'bbaa', 'baaba', 'aaba', 'abba', 'ab', 'babaa'}

我有代码来做这件事，但它是低效的。在这里，它使用所有可打印的ascii字符作为字母表和输入字符串aaaaaaaaaa

import string

input_string = "a" * 10
f = (
    lambda input_string, dist=2, i=0: dist * input_string[i - 1 :]
    and {
        k[:i] + char + k[i + w:]
        for k in f(input_string, dist - 1)
        for char in [""] + list(string.printable)
        for w in (0, 1)
    }
    | f(input_string, dist, i + 1)
    or {input_string}
)
f(input_string)

我需要用不同的输入字符串运行多次。这段代码需要我桌面上当前的2.9秒来生成1631129个不同的字符串。有人知道如何使它更快吗

---

到目前为止的排名表（使用可打印字母表）：

我的代码：2.98秒±146毫秒

阿兰T.的代码：1.58秒±60.7毫秒。目前的获胜者

ddg代码：1.85秒±28.4毫秒

Answer 1

我认为生成一整套可能的编辑不会显著提高速度

通过避免在第一次编辑后重新扩展产生相同结果的字符串，可以节省35%到50%的执行时间。这可能会在编辑距离更大的情况下产生更显著的差异。改进程度还取决于实际字符串/单词（可能不是由单个重复字母组成）

在任何情况下，以下是该函数的优化版本：

import string
from collections import deque

def makeEdits(S,count=1,charSet=None):
    if charSet is None: charSet = string.printable
    result   = set([S])
    expand   = deque(result)
    lastEdit = False

    def addEdit(s):
        if s in result: return 
        result.add(s)
        if not lastEdit: expand.append(s)

    for edit in range(count):
        editing = expand.copy()
        expand.clear()
        lastEdit = edit == count-1
        for eString in editing:
            for i,char in enumerate(eString):
                left,right = eString[:i],eString[i+1:]                       
                addEdit(left+right)                  # deletion
                for newChar in charSet:                    
                    addEdit(left+newChar+char+right) # insertions before
                    addEdit(left+newChar+right)      # replacement                   
            for newChar in charSet:
                addEdit(eString+newChar)             # insertion at end
    return result

在我的笔记本电脑上进行测试和性能测试：

from timeit import timeit
count = 1
input_string = "a" * 10

print('makeEdits()...')
print(len(makeEdits(input_string,2)))
t = timeit(lambda:makeEdits(input_string,2),number=count)
print(t)

print('f()...')
print(len(f(input_string)))
t = timeit(lambda:f(input_string),number=count)
print(t)

makeEdits()...
1631129
2.0302121050000004
f()...
1631129
3.145120027999999

请注意，较小的字符集（如string.ascii_字母）将显著提高性能结果（通过生成较少的字符串）：

timeit(lambda:makeEdits(input_string,2,string.ascii_letters),number=count)

# 0.48669491199999015

len(makeEdits(input_string,2,string.ascii_letters)) # 433913

timeit(lambda:makeEdits(input_string,2,string.ascii_lowercase),number=count)

# 0.10699477299999671

len(makeEdits(input_string,2,string.ascii_lowercase)) # 104805

如果您正在制作拼写检查器，那么在处理之前将所有字符都转换为小写，并将所有特殊字符视为包含在字符集中的单个字符是合理的。这将允许您的程序获得较小字符集的性能提升（在本例中快30倍）。您只需要添加一些字符串的预处理，也许还需要在之后对结果进行一些调整

Answer 2

使用迭代器（避免在内存中加载所有内容），我可以将时间缩短到0.17秒。有了更多关于您的用例的上下文（为什么您需要所有这些？对于拼写检查器？），就有了可能的替代方法来避免列举所有的可能性

from string import ascii_lowercase
from itertools import product

def validate(start: str):
    assert set(start) <= set(ascii_lowercase)

def iter_deletion(string) -> str:
    for i in range(len(string)):
        yield string[:i] + string[i+1:]
        
def iter_insertion(string) -> str:
    for i,c in product(range(len(string)+1), ascii_lowercase):
        yield string[:i] + c + string[i:]

def iter_replacement(string) -> str:
    for i,c in product(range(len(string)), ascii_lowercase):
        yield string[:i] + c + string[i+1:]

def iter_steps(string):
    yield from iter_deletion(string)
    yield from iter_insertion(string)
    yield from iter_replacement(string)

def view_all(string):
    validate(string)
    for d1 in iter_steps(string):
        yield from iter_steps(d1)

from timeit import timeit
timeit(lambda: set(view_all('aaaaaaaaaa')), number=1)