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

Question

给定一个输入字符串，我想找到 Levenshtein distance 内的所有其他字符串的集合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', '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 毫秒
Alain T. 的代码:1.58 s ± 60.7 ms。目前的赢家。
ddg的代码:1.85 s ± 28.4 ms

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)