Как улучшить производительность этой рекурсивной функции?

Question

Я пытаюсь написать функцию, которая будет искать в str подстроку, учитывая различные возможности писать странные буквы, такие как æ, ø, å на датском языке. Например, вы можете искать «Ольборг», и функция вернет 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)

Answer 1

Я думаю, что вы должны полностью исключить рекурсию. Вместо того, чтобы делать все эти find и replace, вы можете, например, выбрать «нормальную форму» ваших входных строк, соответствующим образом преобразовать их (т.е. заменить эти «неоднозначные» символы) и сделать простой

return substring in string_

Обратите внимание, что вам не нужно звонить вместе find и replace, этого достаточно. Если строка поиска не найдена, замена просто ничего не заменит.

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 (ålbørg »или« ålbårg », или« aalborg », или« aalbørg », или« aalbårg », или« alborg », или« alborg », или« albårg », как указано в комментарии @ 101100)Затем регулярное выражение просто ищется в контексте.

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)