Single-pass Multiple Replace (Python recipe) by Xavier Defrang

ActiveState Code (http://code.activestate.com/recipes/81330/)

Nice algorithm; needs one fix and one optimization. If dict has no entries, then the regex matches everything. Need to have an explicit check so as not to call re.sub() in that case.

The dict-like object is IMO the way to go. Now, if we have one of these, then we may (probably?) be using it more than once. So, we ought to keep the compiled regex around. There's no harm in keeping the text regex around either: it's nice for debugging, and we can get a further optimization out of it, too.

Here's what I came up with based on your original code:

# Original algorithm by Xavier Defrang.
# http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/81330
# This implementation by alane@sourceforge.net.

import re
import UserDict

class textsub(UserDict.UserDict):
    def __init__(self, dict = None):
        self.re = None
        self.regex = None
        UserDict.UserDict.__init__(self, dict)

    def compile(self):
        if len(self.data) > 0:
            tmp = "(%s)" % "|".join(map(re.escape,
                                        self.data.keys()))
            if self.re != tmp:
                self.re = tmp
                self.regex = re.compile(self.re)

    def __call__(self, match):
        return self.data[match.string[match.start():match.end()]]

    def sub(self, s):
        if len(self.data) == 0:
            return s
        return self.regex.sub(self, s)

Performance tweaking..

I like this re based function a lot and was interested to compare it to a similar string replace function
I already use -- the results are interesting:

import time
vars = {'%_fred':'hello','%_dick':'world','%_freddy':'sunny'}
line = "%_fred beautiful %_dick"

def string_replace(dict,text):
    keys = dict.keys()
    keys.sort()
    for n in keys:
        if '%' not in text: break
        text = text.replace(n,dict[n])
    return text

start = time.time()
for n in range(1000):
    multiple_replace(vars,line)
print 1000/(time.time()-start)

start = time.time()
for n in range(1000):
    string_replace(vars,line)
print 1000/(time.time()-start)

On my PIII 1.1GHz machine:
multiple_replace 3831.41707853 loops/sec
string_replace 50000.0476838 loops/sec
However.. if the re.compile statement is moved out of the function
new_multiple_replace 10000.0095368 loops/sec

If you can arrange to compile outside of the routine then the re
version is best otherwise the longer string based function has the performance.

Re: Performance tweaking. Actually, the

keys.sort()

shown in the string_replace() function doesn't do any thing useful and could be omitted. For the small number of keys, three, shown in the example, doing this doesn't speed up the routine very much.

However, it can be useful to sort the keys by the reverse of their string lengths, like this instead:

keys.sort(lambda a,b: len(b)-len(a))

because doing this will try matches with the longest patterns first. This can be signficant if one or more of the keys are substrings of others -- as the case with '%_fred' and '%_freddy' in the example.

If the keys are not sorted by length (either the default way, as originally shown, or not at all), the following string:

"%_freddy beautiful %_dick"

will become:

"hellody beautiful world"

instead of:

"sunny beautiful world"

The down side of the reverse length sort is that it does slow the routine down (about 50% on my machine).

All versions above might also benefit by placing a "str(...)" call around the dictionary lookups. This allow the replacement values to be numbers and other object, as well as strings. I find this useful when the replacement values are calculated.

Re: Performance tweaking. Interestingly, removing the line:

if '%' not in text: break

from the string_replace() function speeds it up fairly significantly, with no detrimental effects. Another advantage to leaving the line out is that it makes the routine more general, since keys no longer all have to start with a "%" character.

Futher Tweaking... You're right of course - the sort needs to be reversed and done outside of the function if possible :D

I did some more checking... With modifed code, using the same small sample string and increasing the size of the dictionary:

keys,string,regex

20,20k,10k

40,11k,10k

200,2k,10k

2000,250,12k

As the dictionary grew > 40 items, the perfomance of the regex routine was unaffected whereas my string replace function started to perfom badly - we live and learn!

Thanx! I used it in a script for xchat to display rhythmbox's output (http://www.schitterendedingen.com/scripts/rhy.py).. now users can easily change extensions I used it in a script for xchat to display rhythmbox's output (http://www.schitterendedingen.com/scripts/rhy.py).. now users can easily change extensions

great compact class !! To ignore breaking spaces before the key. just need to change one line:

def compile(self):
        if len(self.data) > 0:
            tmp = r"(\b%s)" % "|" r"\b".join( map( re.escape,
                                        self.data.keys() ) )
            if self.re != tmp:
                self.re = tmp
                self.regex = re.compile(self.re)

for those who don't know:

to match breaking spaces you need to use r"\b"

so reg exp. r"\bPYTHON\b" will be matched in "I love PYTHON"

but not "PYTHON_version"

what i just realized is that the above change in compile doesn't account for

breaking spaces after the string!

it is too late to fool around with python ;>

Maybe just use this.

import re
def strTr( text, dic ):
    """ Replaces keys of dic with values of dic in text. 2005-02 by Emanuel Rumpf """
    pat = "(%s)" % "|".join( map(re.escape, dic.keys())  )
    return re.sub( pat, lambda m:dic[m.group()], text )

add breaking spaces after each string. This is a simple change to the code to include breaking spaces before and after each of the keys:

tmp = r"(\b%s)" % "|" r"\b".join( map( re.escape, change to: tmp = r"(\b%s\b)" % r"\b" "|" r"\b".join( map( re.escape,

To resolve the longest to shortest key issue in the original function multiple_replace above, I wrote this bit to replace the one-liner:

regex = re.compile("(%s)" % "|".join(map(re.escape, dict.keys())))

With:

keys = dict.keys()
# Sort keys by length, longest first
keys.sort(lambda a,b: len(b)-len(a))
expression = []
for item in keys:
  expression.append(re.escape(item))
regex = re.compile("(%s)" % "|".join(expression))

It's not nearly so brief, and I'm sure others could find a way to condense or make clearer, but now keys which are subsets of longer keys won't get in the way.

This method was broken in python 2.6 and later:

Try this instead:

keys = sorted(dictobj.keys(), key=lambda a: len(a))
expression = []
for item in keys:
  expression.append(re.escape(item))
regex = re.compile("(%s)" % "|".join(expression))

or even better:

keys = sorted(dict.keys(), key=len)

Or even better:

keys = sorted(dict.keys(), key=len)

One other thing, don't forget to reverse the sort, so that the longest items are first.

keys = sorted(dict.keys(), key=len)
keys.reverse()

sorted takes a keyword argument:

keys = sorted(dict.keys(), key=len, reverse=True)

I noticed this only worked for strings (not regex groups and repetition etc ) so I wrote some code for that.

I fixed the sorting (thanks Martin Miller) and empty dict input (thanks Alan Eldridge). There are some problems with lookahead/lookbehind/beginning/end regex. I'm not an advanced programmer, and this isn't optimizated at all.

import regex as re


def SimultaneouslyReplaceEachIn__DictOn__String ( dict_of_things_im_looking_for , text_thats_getting_changed ):
  # if the dict is empty, don't change anything
  if len(dict_of_things_im_looking_for) == 0:
    return text_thats_getting_changed

  list_of_all_of_the_things_to_find = dict_of_things_im_looking_for.keys()
  all_of_those_things_in_order = sorted(list_of_all_of_the_things_to_find, key=lambda x: len(x))
  all_of_them_in_a_regex_string = "("  + "|".join(all_of_those_things_in_order) + ")" 

  def Is__RegexIn__String(regexstring,string): 
    output = re.search(regexstring,string) != None 
    return output

  def the_corrisponding_replacement(regex_found):
    string_that_was_found = regex_found.group()
    for each_item in all_of_those_things_in_order:
      # the below line could cause problems for lookahead / lookbehind / beginning / end regex 
      if Is__RegexIn__String( each_item , string_that_was_found ):
        # if an item was found, then return it's corrisponding replace value
        return dict_of_things_im_looking_for[ each_item ] 

    print "probably an error with Simultanious Replacement"
    print "may be due lookahead/lookbehind/beginning/end regex"
    return string_that_was_found

  return re.sub( all_of_them_in_a_regex_string , the_corrisponding_replacement , text_thats_getting_changed )


########################
# Test 

source_copy = " AB = ab  ,  BA = ba "

replacements_dict = {
r'b'           : "(the letter b)" ,
r'(a|e|i|o|u)' : "(a basic vowel)" ,
}


#normally r'(a|e|i|o|u)' 
#would replace the e's in "(the letter b)" 
#And vise versa for b in "(a basic vowel)"

#this gets around this issue 

print source_copy 
print SimultaneouslyReplaceEachIn__DictOn__String( replacements_dict , source_copy )

Here is the same function, condensed:

def SimulSub ( dict_ , string_ ):
  if len(dict_) == 0:
    return string_
  def repl_(regex_):
    match_ = regex_.group()
    for x in (sorted(dict_.keys(), key=lambda x: len(x))):
      # the below line could cause problems for lookahead / lookbehind / beginning / end regex 
      if (re.search( x , match_ ) != None): return dict_[ x ] 
    print "error with SimulSub"
    print "check lookahead/lookbehind/beginning/end regex"
    return match_
  return re.sub( "(" + "|".join(sorted(dict_.keys(), key=lambda x: len(x))) + ")"  , repl_ , string_ )