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

Question

给定一个输入字符串，我想找到Levenshtein 距离2内的所有其他字符串的集合。例如，如果输入字符串是“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', '巴巴'}

我有代码可以做到这一点，但效率低下。这里它使用所有可打印的 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 毫秒

Alain T. 的代码：1.58 秒 ± 60.7 毫秒。目前的赢家。

ddg 的代码：1.85 秒 ± 28.4 毫秒

Answer 1

使用迭代器（以避免加载内存中的所有内容）我可以将时间缩短至 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)