如何提高这个递归函数的性能？

Question

我正在尝试编写一个函数，用于在字符串中搜索子字符串，考虑到丹麦语中不同的奇怪字母的写法，例如æ、ø、å。例如，您可以搜索'Ålborg'，如果在字符串中存在'Aalborg'，则函数将返回true。

以下函数可行，但性能无法承受。您有什么建议可以提高性能？

def danish_tolerating_search(substr, str):
    '''Figure out if substr is in str, taking into account
    possible deviations in writing letters æ, ø, å.
    æ  <->  ae a ea
    ø  <->  oe o
    å  <->  aa a o
    '''

    # normalize input
    substr = substr.lower().replace('aa',u'å')
    str = str.lower()

    # normalized recursive search
    # TODO fix perfomance
    def s(substr, str):
        if str.find(substr) >= 0: return True
        if substr.find(u'æ') >= 0:
            if    s(substr.replace(u'æ','ae', 1), str): return True
            elif  s(substr.replace(u'æ', 'a', 1), str): return True
            elif  s(substr.replace(u'æ','ea', 1), str): return True
        if str.find(u'æ') >= 0:
            if    s(substr, str.replace(u'æ','ae', 1)): return True
            elif  s(substr, str.replace(u'æ', 'a', 1)): return True
            elif  s(substr, str.replace(u'æ','ea', 1)): return True
        if substr.find(u'ø') >= 0:
            if    s(substr.replace(u'ø','oe', 1), str): return True
            elif  s(substr.replace(u'ø', 'o', 1), str): return True
        if str.find(u'ø') >= 0:
            if    s(substr, str.replace(u'ø','oe', 1)): return True
            elif  s(substr, str.replace(u'ø', 'o', 1)): return True
        if substr.find(u'å') >= 0:
            if    s(substr.replace(u'å','aa', 1), str): return True
            elif  s(substr.replace(u'å', 'a', 1), str): return True
            elif  s(substr.replace(u'å', 'o', 1), str): return True
        if str.find(u'å') >= 0:
            if    s(substr, str.replace(u'å','aa', 1)): return True
            elif  s(substr, str.replace(u'å', 'a', 1)): return True
            elif  s(substr, str.replace(u'å', 'o', 1)): return True
        return False

    return s(substr, str)

- Vladimir Keleshev

---

字符串是标准库中的一个模块名称，因此在使用变量名时请三思而后行。 - jforberg

@jforberg，@KennyTM，我在“真实”函数中有不同的名称，这只是一个例子。 - Vladimir Keleshev

你有一些用于基准测试的测试吗？ - kennytm

只是为了明确，"ålborg" 应该匹配到 "ålbørg" 或者 "ålbårg" 或者 "aalborg" 或者 "aalbørg" 或者 "aalbårg" 或者 "alborg" 或者 "albørg" 或者 "albårg"，对吗？ - 101100

@101100 你说得没错，但这有点过头了。我这样实现是因为拼写错误非常频繁，而且非丹麦语母语者通常会搞砸拼写，比如写成ålbårg之类的东西... - Vladimir Keleshev

Answer 1

我认为你应该完全消除递归。不要进行所有的find和replace，相反，你可以决定一个输入字符串的“标准形式”，并相应地进行转换（即替换那些“模棱两可”的字符），然后进行简单的处理。

return substring in string_

注意，您不需要同时调用find和replace函数，后者就足够了。如果搜索字符串未找到，则替换函数将不会替换任何内容。

- jena

Answer 2

尝试

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import re

def danish_tolerating_search(search, content):
    search = search.lower()
    content = content.lower()

    variants = {
        u'a': u'[aæå]',
        u'o': u'[oøå]',
        u'ae': u'(?:ae|æ)',
        u'ea': u'(?:ea|æ)',
        u'aa': u'(?:aa|å)',
        u'oe': u'(?:oe|ø)',
        u'\\å': u'(?:[oå]|aa?)',
        u'\\ø': u'(?:ø|oe?)',
        u'\\æ': u'(?:æ|ae?|ea)',
    }

    search = re.escape(search)
    search = re.sub(ur'[ae]a|[ao]e?|\\[åøæ]', lambda m: variants[m.group(0)], search)
    return re.search(search, content) is not None

我没有测试它的性能，因为OP没有发布任何信息。我只是假设正则表达式引擎比递归调用OP的s()函数并进行大量的.find和.replace操作更加优化。

在这里，搜索字符串中的关键字母被替换为可能等效于正则表达式类的字符，例如Ålborg变成了(?:[oå]|aa?)lb[oøå]rg。这个正则表达式应该包括所有等效于Ålborg的可能变体（如@101100评论中提到的"ålbørg"或"ålbårg"或"aalborg"或"aalbørg"或"aalbårg"或"alborg"或"albørg"或"albårg"）。然后，将正则表达式简单地与上下文进行匹配。

- kennytm

---

非常好，比我的更详细。我特别喜欢在re.sub中的地图。 - Spencer Rathbun

Answer 3

这是一个解析器的经典示例。请阅读类似lex和yacc的内容，您不需要它们的所有功能，但原则仍然适用。

之后，使用python re模块来匹配相应的正则表达式。如果您需要更多功能，请使用pyparsing库。

def danish_tolerating_search(substr, str):
'''Figure out if substr is in str, taking into account
possible deviations in writing letters æ, ø, å.
æ  <->  ae a ea
ø  <->  oe o
å  <->  aa a o
for all of these combinations replace with appropriate regex as in example
'''
substring = substring.lower().replace('aa', '[ae]{1,2}')
string = string.lower()
re.search(substring, string)

- Spencer Rathbun

---

关键在于进行替换时不要过度扩展，因为_å_可以是a或aa或å，而a可以是a或_å_或æ。您实际上需要9个不同的替换（用于æ、ø、å、a、o、ae、ea、oe和aa）。一旦完成了棘手的替换，re.search就应该可以工作了。编辑：请参见KennyTM的答案。 - 101100