给定一个输入字符串,我想找到 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
最佳答案
使用迭代器(以避免将所有内容加载到内存中)我可以缩短到 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)
关于python - 可以加快查找字符串邻域的代码吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65330519/