Массовую строку заменить в питоне?

Поскольку кто-то упомянул об использовании простого синтаксического анализатора, я подумал, что приготовлю его, используя pyparsing. Используя метод pyparsing transformString, pyparsing внутренне сканирует исходную строку, и строит список совпадающего текста и промежуточного текста. Когда все будет сделано, transformString, затем '' .join в этом списке, так что нет проблем с производительностью при построении строк с шагом. (Действие синтаксического анализа, определенное для ANSIreplacer, выполняет преобразование из совпадающих символов & _ в желаемую escape-последовательность и заменяет совпадающий текст выводом действия синтаксического анализа. Поскольку только совпадающие последовательности удовлетворяют выражению синтаксического анализатора, нет необходимости в действие синтаксического анализа для обработки неопределенных последовательностей & _.)

FollowedBy ('&') не является строго необходимым, но сокращает процесс синтаксического анализа, проверяя, действительно ли синтаксический анализатор расположен в амперсанде, прежде чем выполнять более дорогую проверку всех из параметры разметки.

from pyparsing import FollowedBy, oneOf

escLookup = {"&y":"\033[0;30m",
            "&c":"\033[0;31m",
            "&b":"\033[0;32m",
            "&Y":"\033[0;33m",
            "&u":"\033[0;34m"}

# make a single expression that will look for a leading '&', then try to 
# match each of the escape expressions
ANSIreplacer = FollowedBy('&') + oneOf(escLookup.keys())

# add a parse action that will replace the matched text with the 
# corresponding ANSI sequence
ANSIreplacer.setParseAction(lambda toks: escLookup[toks[0]])

# now use the replacer to transform the test string; throw in some extra
# ampersands to show what happens with non-matching sequences
src = "The &yquick &cbrown &bfox &Yjumps over the &ulazy dog & &Zjumps back"
out = ANSIreplacer.transformString(src)
print repr(out)

Отпечатки:

'The \x1b[0;30mquick \x1b[0;31mbrown \x1b[0;32mfox \x1b[0;33mjumps over 
 the \x1b[0;34mlazy dog & &Zjumps back'

Это, конечно, не выиграет ни одного конкурса производительности,

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

str = "The &yquick &cbrown &bfox &Yjumps over the &ulazy dog"

dict = {"&y":"\033[0;30m",
        "&c":"\033[0;31m",
        "&b":"\033[0;32m",
        "&Y":"\033[0;33m",
        "&u":"\033[0;34m"}

def rep(s):
  return dict["&"+s[0:1]] + s[1:]

subs = str.split("&")
res = subs[0] + "".join(map(rep, subs[1:]))

print res

Конечно, возникает вопрос, что происходит, когда амперсанд исходит из самой строки, вы нужно было бы каким-то образом избежать этого, прежде чем кормить через этот процесс, а затем отменить экранирование после этого процесса.

Конечно, как это обычно бывает с проблемами производительности, время для различных подходов в вашем типичном (а также наихудшем случае) наборе данных и их сравнение - это хорошая вещь.

EDIT:

Проблема с выполнением этой массовой замены в Python заключается в неизменности строк: каждый раз, когда вы заменяете один элемент в строке, вся новая строка будет перераспределяться снова и снова из кучи.

Итак, если вам нужно самое быстрое решение, вам нужно либо использовать изменяемый контейнер (например, список), либо написать этот механизм на простом C (или лучше на Pyrex или Cython). В любом случае я бы предложил написать простой синтаксический анализатор на основе простого конечного автомата и передавать символы вашей строки один за другим.

Предлагаемые решения, основанные на регулярных выражениях, работающих аналогичным образом, потому что регулярное выражение работает с использованием fsm за сценой .

Не уверен в скорости этого решения, но вы можете просто просмотреть свой словарь и многократно вызывать встроенную

str.replace (old, new)

Это может неплохо работать, если исходная строка не слишком длинная, но, очевидно, пострадает, если строка станет длиннее.

Вот версия с использованием split / join

mydict = {"y":"\033[0;30m",
          "c":"\033[0;31m",
          "b":"\033[0;32m",
          "Y":"\033[0;33m",
          "u":"\033[0;34m"}
mystr = "The &yquick &cbrown &bfox &Yjumps over the &ulazy dog"

myparts = mystr.split("&")
myparts[1:]=[mydict[x[0]]+x[1:] for x in myparts[1:]]
print "".join(myparts)

В случае, если есть амперсанды с недопустимыми кодами, вы можете использовать это, чтобы сохранить их

myparts[1:]=[mydict.get(x[0],"&"+x[0])+x[1:] for x in myparts[1:]]

Питер Хансен указал, что это не удается, когда есть двойные амперсанд. В этом случае используйте эту версию

mystr = "The &yquick &cbrown &bfox &Yjumps over the &&ulazy dog"
myparts = mystr.split("&")
myparts[1:]=[mydict.get(x[:1],"&"+x[:1])+x[1:] for x in myparts[1:]]
print "".join(myparts)

Этот кажется, что он делает то, что вы хотите - одновременная замена нескольких строк с помощью регулярных выражений. Вот соответствующий код:

def multiple_replace(dict, text): 
    # Create a regular expression  from the dictionary keys
    regex = re.compile("(%s)" % "|".join(map(re.escape, dict.keys())))

    # For each match, look-up corresponding value in dictionary
    return regex.sub(lambda mo: dict[mo.string[mo.start():mo.end()]], text)

print multiple_replace(dict, str)

Вот подход к расширению C для python

const char *dvals[]={
    //"0-64
    "","","","","","","","","","",
    "","","","","","","","","","",
    "","","","","","","","","","",
    "","","","","","","","","","",
    "","","","","","","","","","",
    "","","","","","","","","","",
    "","","","","",
    //A-Z
    "","","","","",
    "","","","","",
    "","","","","",
    "","","","","",
    "","","","","33",
    "",
    //
    "","","","","","",
    //a-z
    "","32","31","","",
    "","","","","",
    "","","","","",
    "","","","","",
    "34","","","","30",
    ""
};

int dsub(char*d,char*s){
    char *ofs=d;
    do{
        if(*s=='&' && s[1]<='z' && *dvals[s[1]]){

            //\033[0;
            *d++='\\',*d++='0',*d++='3',*d++='3',*d++='[',*d++='0',*d++=';';

            //consider as fixed 2 digits
            *d++=dvals[s[1]][0];
            *d++=dvals[s[1]][1];

            *d++='m';

            s++; //skip

        //non &,invalid, unused (&) ampersand sequences will go here.
        }else *d++=*s;

    }while(*s++);

    return d-ofs-1;
}

Коды Python, которые я тестировал

from mylib import *
import time

start=time.time()

instr="The &yquick &cbrown &bfox &Yjumps over the &ulazy dog, skip &Unknown.\n"*100000
x=dsub(instr)

end=time.time()

print "time taken",end-start,",input str length",len(x)
print "first few lines"
print x[:1100]

Результаты

time taken 0.140000104904 ,input str length 11000000
first few lines
The \033[0;30mquick \033[0;31mbrown \033[0;32mfox \033[0;33mjumps over the \033[0;34mlazy dog, skip &Unknown.
The \033[0;30mquick \033[0;31mbrown \033[0;32mfox \033[0;33mjumps over the \033[0;34mlazy dog, skip &Unknown.
The \033[0;30mquick \033[0;31mbrown \033[0;32mfox \033[0;33mjumps over the \033[0;34mlazy dog, skip &Unknown.
The \033[0;30mquick \033[0;31mbrown \033[0;32mfox \033[0;33mjumps over the \033[0;34mlazy dog, skip &Unknown.
The \033[0;30mquick \033[0;31mbrown \033[0;32mfox \033[0;33mjumps over the \033[0;34mlazy dog, skip &Unknown.
The \033[0;30mquick \033[0;31mbrown \033[0;32mfox \033[0;33mjumps over the \033[0;34mlazy dog, skip &Unknown.
The \033[0;30mquick \033[0;31mbrown \033[0;32mfox \033[0;33mjumps over the \033[0;34mlazy dog, skip &Unknown.
The \033[0;30mquick \033[0;31mbrown \033[0;32mfox \033[0;33mjumps over the \033[0;34mlazy dog, skip &Unknown.
The \033[0;30mquick \033[0;31mbrown \033[0;32mfox \033[0;33mjumps over the \033[0;34mlazy dog, skip &Unknown.
The \033[0;30mquick \033[0;31mbrown \033[0;32mfox \033[0;33mjumps over the \033[0;34mlazy dog, skip &Unknown.

Предположим, он может работать на O (n) , и Только 160 мс (в среднем) для 11 МБ строки в My Mobile Celeron 1.6 GHz PC

Он также будет пропускать неизвестные символы как есть, например и Unknown ] вернется как есть

Сообщите мне, если у вас возникнут проблемы с компиляцией, ошибки и т. д.

Если вы действительно хотите вникнуть в тему, взгляните на это: http://en.wikipedia.org/wiki/Aho-Corasick_algorithm

Очевидное решение от перебор словаря и замена каждого элемента в строке занимает O (n * m) времени, где n - размер словаря, m - длина строки.

В то время как Aho- Алгоритм Корасика находит все статьи словаря в O (n + m + f) , где f - количество найденных элементов.

Общее решение для определения правил замены заключается в использовании подстановки регулярных выражений с использованием функции для предоставления карты (см. re.sub () ).

import re

str = "The &yquick &cbrown &bfox &Yjumps over the &ulazy dog"

dict = {"&y":"\033[0;30m",
        "&c":"\033[0;31m",
        "&b":"\033[0;32m",
        "&Y":"\033[0;33m",
        "&u":"\033[0;34m"}

def programmaticReplacement( match ):
    return dict[ match.group( 1 ) ]

colorstring = re.sub( '(\&.)', programmaticReplacement, str )

Это особенно удобно для нетривиальных замены (например, все, что требует математических операций для создания замены).

Попробуйте это, используя подстановку регулярных выражений и стандартное форматирование строк:

# using your stated values for str and dict:
>>> import re
>>> str = re.sub(r'(&[a-zA-Z])', r'%(\1)s', str)
>>> str % dict
'The \x1b[0;30mquick \x1b[0;31mbrown \x1b[0;32mfox \x1b[0;33mjumps over the \x1b[0;34mlazy dog'

Вызов re.sub () заменяет все последовательности амперсанда, за которыми следует одной буквой с шаблоном% (..) s, содержащим тот же шаблон.

Форматирование% использует возможность форматирования строки, которая может использовать словарь для определения подстановки, а не более часто встречающиеся позиционные аргументы.

Альтернатива может сделать это непосредственно в re.sub, используя обратный вызов:

>>> import re
>>> def dictsub(m):
>>>    return dict[m.group()]
>>> str = re.sub(r'(&[a-zA-Z])', dictsub, str)

На этот раз я использую закрытие для ссылки на словарь изнутри функции обратного вызова. Такой подход может дать вам немного больше гибкости. Например, вы можете использовать что-то вроде dict.get (m.group (), '??') , чтобы избежать возникновения исключений, если у вас есть строки с нераспознанными последовательностями кода.

(Кстати, оба "dict "и" str "- встроенные функции, и вы столкнетесь с проблемами, если будете часто использовать эти имена в своем собственном коде. На всякий случай, если вы этого не знали. Они, конечно, подходят для такого вопроса.)

Редактировать: Я решил проверить тестовый код Tor и пришел к выводу, что он далеко не репрезентативный и на самом деле содержит ошибки. В сгенерированной строке даже нет амперсандов (!). Пересмотренный ниже код генерирует репрезентативный словарь и строку, аналогичные входным параметрам OP.

Я также хотел убедиться, что выходные данные каждого алгоритма совпадают. Ниже приведена обновленная программа испытаний. только с кодом Tor, моим и Клаудиу - потому что другие ломались на вводе образца. (Я думаю, что они все хрупкие, если словарь не отображает в основном все возможные последовательности амперсанда, которые выполнял тестовый код Tor.) Этот код правильно заполняет генератор случайных чисел, чтобы каждый запуск был одинаковым. Наконец, я добавил небольшую вариацию с использованием генератора, который позволяет избежать накладных расходов на вызов функций, для небольшого улучшения производительности.

from time import time
import string
import random
import re

random.seed(1919096)  # ensure consistent runs

# build dictionary with 40 mappings, representative of original question
mydict = dict(('&' + random.choice(string.letters), '\x1b[0;%sm' % (30+i)) for i in range(40))
# build simulated input, with mix of text, spaces, ampersands in reasonable proportions
letters = string.letters + ' ' * 12 + '&' * 6
mystr = ''.join(random.choice(letters) for i in range(1000))

# How many times to run each solution
rep = 10000

print('Running %d times with string length %d and %d ampersands'
    % (rep, len(mystr), mystr.count('&')))

# Tor Valamo
# fixed from Tor's test, so it actually builds up the final string properly
t = time()
for x in range(rep):
    output = mystr
    for k, v in mydict.items():
        output = output.replace(k, v)
print('%-30s' % 'Tor fixed & variable dict', time() - t)
# capture "known good" output as expected, to verify others
expected = output

# Peter Hansen

# build charset to use in regex for safe dict lookup
charset = ''.join(x[1] for x in mydict.keys())
# grab reference to method on regex, for speed
patsub = re.compile(r'(&[%s])' % charset).sub

t = time()
for x in range(rep):
    output = patsub(r'%(\1)s', mystr) % mydict
print('%-30s' % 'Peter fixed & variable dict', time()-t)
assert output == expected

# Peter 2
def dictsub(m):
    return mydict[m.group()]

t = time()
for x in range(rep):
    output = patsub(dictsub, mystr)
print('%-30s' % 'Peter fixed dict', time() - t)
assert output == expected

# Peter 3 - freaky generator version, to avoid function call overhead
def dictsub(d):
    m = yield None
    while 1:
        m = yield d[m.group()]

dictsub = dictsub(mydict).send
dictsub(None)   # "prime" it
t = time()
for x in range(rep):
    output = patsub(dictsub, mystr)
print('%-30s' % 'Peter generator', time() - t)
assert output == expected

# Claudiu - Precompiled
regex_sub = re.compile("(%s)" % "|".join(mydict.keys())).sub

t = time()
for x in range(rep):
    output = regex_sub(lambda mo: mydict[mo.string[mo.start():mo.end()]], mystr)
print('%-30s' % 'Claudio fixed dict', time() - t)
assert output == expected

Я забыл включить результаты тестов раньше:

    Running 10000 times with string length 1000 and 96 ampersands
    ('Tor fixed & variable dict     ', 2.9890000820159912)
    ('Peter fixed & variable dict   ', 2.6659998893737793)
    ('Peter fixed dict              ', 1.0920000076293945)
    ('Peter generator               ', 1.0460000038146973)
    ('Claudio fixed dict            ', 1.562000036239624)

Также, фрагменты входных данных и правильный выход:

mystr = 'lTEQDMAPvksk k&z Txp vrnhQ GHaO&GNFY&&a...'
mydict = {'&p': '\x1b[0;37m', '&q': '\x1b[0;66m', '&v': ...}
output = 'lTEQDMAPvksk k←[0;57m Txp vrnhQ GHaO←[0;67mNFY&&a P...'

Сравнивая с тем, что я видел в выходных данных тестового кода Tor:

mystr = 'VVVVVVVPPPPPPPPPPPPPPPXXXXXXXXYYYFFFFFFFFFFFFEEEEEEEEEEE...'
mydict = {'&p': '112', '&q': '113', '&r': '114', '&s': '115', ...}
output = # same as mystr since there were no ampersands inside

Если количество ключей в списке большое, а количество срабатываний в строке низкое (а в основном нулевое), то можно провести итерацию по срабатываниям амперсандов в строке, а также использовать словарь, клавиатура которого задана первым символом подстроки. Я не часто кодирую на питоне, так что стиль может быть немного неаккуратный, но вот мой взгляд на это:

str = "The &yquick &cbrown &bfox &Yjumps over the &ulazy dog"

dict = {"&y":"\033[0;30m",
        "&c":"\033[0;31m",
        "&b":"\033[0;32m",
        "&Y":"\033[0;33m",
        "&u":"\033[0;34m"}

def rep(s):
  return dict["&"+s[0:1]] + s[1:]

subs = str.split("&")
res = subs[0] + "".join(map(rep, subs[1:]))

print res

Конечно, есть вопрос, что происходит, когда есть амперсанд, который исходит из самой строки, вам нужно будет каким-то образом избежать его, прежде чем подавать через этот процесс, а затем распускать после этого процесса.

Конечно, как это обычно бывает с проблемами производительности, определение времени для различных подходов к вашему типичному (а также наихудшему) набору данных и сравнение их - хорошая вещь.

EDIT: поместите его в отдельную функцию для работы с произвольным словарем:

def mysubst(somestr, somedict):
  subs = somestr.split("&")
  return subs[0] + "".join(map(lambda arg: somedict["&" + arg[0:1]] + arg[1:], subs[1:]))

EDIT2: избавьтесь от ненужной конкатеннации, кажется, все еще немного быстрее, чем предыдущая на многих итерациях.

def mysubst(somestr, somedict):
  subs = somestr.split("&")
  return subs[0].join(map(lambda arg: somedict["&" + arg[0:1]] + arg[1:], subs[1:]))