php's strtr для python

PHP имеетstrtr  функция:

strtr('aa-bb-cc', array('aa' => 'bbz', 'bb' => 'x', 'cc' => 'y'));
# bbz-x-y

Он заменяет словарные ключи в строке соответствующими значениями и (что важно) не заменяет уже замененные строки. Наивная попытка написать то же самое на python:

def strtr(strng, replace):
    for s, r in replace.items():
        strng = strng.replace(s, r)
    return strng

strtr('aa-bb-cc', {'aa': 'bbz', 'bb': 'x', 'cc': 'y'})

возвращаетсяxz-x-y чего мы не хотим (bb получил замену снова). Как изменить вышеупомянутую функцию так, чтобы она вела себя как ее аналог php?

(Я бы предпочел ответ без регулярных выражений, если это возможно).

Upd: некоторые отличные ответы здесь. Я рассчитал их и обнаружил, что для коротких струн Gumbo-версия оказывается самой быстрой, а для длинных струн победителем становитсяre решение:

# 'aa-bb-cc'
0.0258 strtr_thg
0.0274 strtr_gumbo
0.0447 strtr_kojiro
0.0701 strtr_aix

# 'aa-bb-cc'*10
0.1474 strtr_aix
0.2261 strtr_thg
0.2366 strtr_gumbo
0.3226 strtr_kojiro

Моя собственная версия (которая немного оптимизирована для Gumbo):

def strtr(strng, replace):
    buf, i = [], 0
    while i < len(strng):
        for s, r in replace.items():
            if strng[i:len(s)+i] == s:
                buf.append(r)
                i += len(s)
                break
        else:
            buf.append(strng[i])
            i += 1
    return ''.join(buf)

Полные коды и сроки:https://gist.github.com/2889181

Ответы на вопрос(5)

Ответы в этой теме настолько устарели. Вот так...

Option #1: Use the str.format() function to handle this:
"Hello there {first_name} {last_name}".format(first_name="Bob", last_name="Roy")
Option #2: Use the Template class
from string import Template
t = Template('Hello there $first_name $last_name')
t.substitute(first_name="Bob", last_name="Roy")

Ссылка: Рекомендации по форматированию строк в Python

str.translate является эквивалентом, но может отображаться только на отдельные символы.

 georg07 июн. 2012 г., 13:52
Да, плохой пример. Я редактировал вопрос.
def strtr(strng, replace):
    if replace and strng:
        s, r = replace.popitem()
        return r.join(strtr(subs, dict(replace)) for subs in strng.split(s))
    return strng

j=strtr('aa-bb-cc', {'aa': 'bbz', 'bb': 'x', 'cc': 'y'})
assert j=='bbz-x-y', j
 07 июн. 2012 г., 14:55
Хорошо, это довольно круто
 georg07 июн. 2012 г., 16:51
Выглядит круто, но делает1+2+...+len(repl) рекурсивные вызовы ... я не знаю.
 07 июн. 2012 г., 17:26
Эй, вы просили версию без регулярных выражений, которая ведет себя как php, вы не просили быстро. ;) (Кроме того, я подозреваю, что копирование слова хуже, чем рекурсивные вызовы.)
 georg07 июн. 2012 г., 17:51
Кстати, есть ли причина, почему вы использовали** вместо простоdict(replace)?
 georg07 июн. 2012 г., 17:50
@kojiro: достаточно справедливо. Вы определенно выиграете приз красоты в этой теме. Жаль, что я не могу принять несколько ответов ...

Следующее использует регулярные выражения, чтобы сделать это:

import re

def strtr(s, repl):
  pattern = '|'.join(map(re.escape, sorted(repl, key=len, reverse=True)))
  return re.sub(pattern, lambda m: repl[m.group()], s)

print(strtr('aa-bb-cc', {'aa': 'bbz', 'bb': 'x', 'cc': 'y'}))

Как и версия PHP, здесь предпочтение отдается более длинным совпадениям.

 georg07 июн. 2012 г., 16:53
Спасибо, это решение кажется самым быстрым на более длинных предметных строках (см. Обновление).
 07 июн. 2012 г., 15:18
@Duncan: Как удивительно, спасибо за указание (я всегда думал, что Pythonre дал самый длинный матч, но ясно, что это не так.)
 07 июн. 2012 г., 15:54
@ Дункан: Это имеет смысл, спасибо за разъяснения (я знал о жадных и не жадных повторениях, но не знал о| оператор).
 07 июн. 2012 г., 15:05
Нет, он не дает предпочтения более длинным совпадениям, это зависит от произвольного порядка словарных ключей:strtr('xxa-bb-cc', { 'xx': 'bbz', 'xxa': 'bby'}) - & GT;'bbza-bb-cc', С помощьюsorted(repl.keys(), key=len, reverse=True) на местеrepl.keys() должен это исправить.
 07 июн. 2012 г., 15:52
Повторыx*, x+, x? а такжеx{m,n} все жадные, поэтому они повторятсяx настолько, насколько они могут и могут,x*?, x+?, x??, x{m,n}? все не жадные, поэтому они соответствуют как можно короче.x|y также не жадный в том смысле, что еслиx соответствует двигателю, который даже не учитываетсяy, Вот что здесь произошло: чередование проверяется строго слева направо и останавливается, как только оно находит совпадение.
Решение Вопроса

Вот наивный алгоритм:

Используйте индекс для обхода исходной строки посимвольно и проверяйте для каждого индекса, совпадает ли одна из строк поиска со строкой из текущего индекса. Если совпадение найдено, поместите замену в буфер и продолжите индекс по длине совпадающей строки. Если совпадений не найдено, продолжайте индексирование на единицу. В конце объедините строки в буфере в одну строку.

def strtr(strng, replace):
    buffer = []
    i, n = 0, len(strng)
    while i < n:
        match = False
        for s, r in replace.items():
            if strng[i:len(s)+i] == s:
                buffer.append(r)
                i = i + len(s)
                match = True
                break
        if not match:
            buffer.append(strng[i])
            i = i + 1
    return ''.join(buffer)
 georg07 июн. 2012 г., 16:54
Спасибо, это работает отлично (за исключением опечатки).
 07 июн. 2012 г., 14:34
Мы оба упускаем это (из документа strtr): сначала будут пробовать самые длинные ключи.

Ваш ответ на вопрос