Python: replace string, matched from a list

Question

Trying to match and mark character based n-grams. The string

txt = "how does this work"

is to be matched with n-grams from the list

ngrams = ["ow ", "his", "s w"]

and marked with <> – however, only if there is no preceding opened quote. The output i am seeking for this string is h<ow >does t<his w>ork (notice the double match in the 2^-nd part, but within just 1 pair of expected quotes).

The for loop i’ve tried for this doesn’t, however, produce the wanted output at all:

switch = False

for i in txt:
    if i in "".join(ngrams) and switch == False:
        txt = txt.replace(i, "<" + i)
        switch = True
    if i not in "".join(ngrams) and switch == True:
        txt = txt.replace(i, ">" + i)
        switch = False

print(txt)

Any help would be greatly appreciated.

Answer 1

This solution uses the str.find method to find all copies of an ngram within the txt string, saving the indices of each copy to the indices set so we can easily handle overlapping matches.

We then copy txt, char by char to the result list, inserting angle brackets where required. This strategy is more efficient than inserting the angle brackets using multiple .replace call because each .replace call needs to rebuild the whole string.

I've extended your data slightly to illustrate that my code handles multiple copies of an ngram.

txt = "how does this work now chisolm"
ngrams = ["ow ", "his", "s w"]
print(txt)
print(ngrams)

# Search for all copies of each ngram in txt
# saving the indices where the ngrams occur
indices = set()
for s in ngrams:
    slen = len(s)
    lo = 0
    while True:
        i = txt.find(s, lo)
        if i == -1:
            break
        lo = i + slen 
        print(s, i)
        indices.update(range(i, lo-1))

print(indices)

# Copy the txt to result, inserting angle brackets
# to show matches
switch = True
result = []
for i, u in enumerate(txt):
    if switch:
        if i in indices:
            result.append('<')
            switch = False
        result.append(u)
    else:
        result.append(u)
        if i not in indices:
            result.append('>')
            switch = True

print(''.join(result))

output

how does this work now chisolm
['ow ', 'his', 's w']
ow  1
ow  20
his 10
his 24
s w 12
{1, 2, 10, 11, 12, 13, 20, 21, 24, 25}
h<ow >does t<his w>ork n<ow >c<his>olm

---

If you want adjacent groups to be merged, we can easily do that using the str.replace method. But to make that work properly we need to pre-process the original data, converting all runs of whitespace to single spaces. A simple way to do that is to split the data and re-join it.

txt = "how  does this\nwork  now chisolm hisow"
ngrams = ["ow", "his", "work"]

#Convert all whitespace to single spaces
txt = ' '.join(txt.split())

print(txt)
print(ngrams)

# Search for all copies of each ngram in txt
# saving the indices where the ngrams occur
indices = set()
for s in ngrams:
    slen = len(s)
    lo = 0
    while True:
        i = txt.find(s, lo)
        if i == -1:
            break
        lo = i + slen 
        print(s, i)
        indices.update(range(i, lo-1))

print(indices)

# Copy the txt to result, inserting angle brackets
# to show matches
switch = True
result = []
for i, u in enumerate(txt):
    if switch:
        if i in indices:
            result.append('<')
            switch = False
        result.append(u)
    else:
        result.append(u)
        if i not in indices:
            result.append('>')
            switch = True

# Convert the list to a single string
output = ''.join(result)

# Merge adjacent groups
output = output.replace('> <', ' ').replace('><', '')
print(output)

output

how does this work now chisolm hisow
['ow', 'his', 'work']
ow 1
ow 20
ow 34
his 10
his 24
his 31
work 14
{32, 1, 34, 10, 11, 14, 15, 16, 20, 24, 25, 31}
h<ow> does t<his work> n<ow> c<his>olm <hisow>

Answer 2

Here's a method with only one for loop. I timed it and it's about as fast as the other answers to this question. I think it's a bit more clear, although that might be because I wrote it.

I iterate over the index of the first character in the n-gram, then if it matches, I use a bunch of if-else clauses to see whether I should add a < or > in this situation. I add to the end of the string output from the original txt, so I'm not really inserting in the middle of a string.

txt = "how does this work"
ngrams = set(["ow ", "his", "s w"])
n = 3
prev = -n
output = ''
shift = 0
open = False
for i in xrange(len(txt) - n + 1):
    ngram = txt[i:i + n]
    if ngram in ngrams:
        if i - prev > n:
            if open:
                output += txt[prev:prev + n] + '>' + txt[prev + n:i] + '<'
            elif not open:
                if prev > 0:
                    output += txt[prev + n:i] + '<'
                else:
                    output += txt[:i] + '<'
                open = True
        else:
            output += txt[prev:i]
        prev = i
if open:
    output += txt[prev:prev + n] + '>' + txt[prev + n:]
print output

Answer 3

This should work:

txt = "how does this work"
ngrams = ["ow ", "his", "s w"]

# first find where letters match ngrams
L = len(txt)
match = [False]*L
for ng in ngrams:
    l = len(ng)
    for i in range(L-l):
        if txt[i:i+l] == ng:
            for j in range(l):
                match[i+j] = True

# then sandwich matches with quotes 
out = []
switch = False
for i in range(L):
    if not switch and match[i]:
        out.append('<')
        switch = True
    if switch and not match[i]:
        out.append('>')
        switch = False
    out.append(txt[i])
print "".join(out)