Merging two almost identical strings

user_4348534 0
Viewed 146

I have two objects, one which is a list of tuples with (int, str), like this:

first_input = [
    (0  ,  "Lorem ipsum dolor sit amet, consectetur"),
    (1  ,  " adipiscing elit"),
    (0  ,  ". In pellentesque\npharetra ex, at varius sem suscipit ac. "),
    (-1 ,  "Suspendisse luctus\ncondimentum velit a laoreet. "),
    (0  ,  "Donec dolor urna, tempus sed nulla vitae, dignissim varius neque.")
]
# Note that the strings contain newlines `\n` on purpose.

The other object is a string, which is the result of a series of operations(*) which, by design, will result in a concatenation of all the strings above but with some additional newlines \n inserted.

(* : that can't be done while conserving the list of tuples structure, obviously)

For instance: 

second_input = "Lorem ipsum dolor sit amet,\nconsectetur adipiscing elit. In pellentesque\npharetra ex, at varius sem\nsuscipit ac. Suspendisse luctus\ncondimentum velit a laoreet. Donec dolor urna, tempus sed\nnulla vitae, dignissim varius neque."
# Note that there are 3 new newlines,  here ^ for instance
# but also in "sem\nsuscipit" and "sed\nnulla"

My goal is to go back to the first structure, but keeping the additional newlines. So in my example, I would get:

expected_output = [
    (0  ,  "Lorem ipsum dolor sit amet,\nconsectetur"),  # new newline here
    (1  ,  " adipiscing elit"),
    (0  ,  ". In pellentesque\npharetra ex, at varius sem\nsuscipit ac. "), # new newline here
    (-1 ,  "Suspendisse luctus\ncondimentum velit a laoreet. "),
    (0  ,  "Donec dolor urna, tempus sed\nnulla vitae, dignissim varius neque.") # new newline here
]

Do you have a smart way to do it, other than reconstructing the string with a character by character comparison?

(NB: I don't care in which of the two tuples it ends if a new \n is at the limit of a string. E.g. getting [(0, "foo\n"), (1, "bar")] or [(0, "foo"), (1, "\nbar")] doesn't matter.)

Edit: what I want to avoid, is to do something like this:

position=0
output = []
for tup in first_input:
    reconstructed_string = ""
    for letter in tup[1]:
        if letter == second_input[position]:
            reconstructed_string = reconstructed_string + letter
        else:
            reconstructed_string = reconstructed_string + second_input[position]
        position +=1
    output.append((tup[0], reconstructed_string))
# Note: this is hastily written to give you an idea, I have no idea if it would work properly, probably not
# Well, it does seem to work without bug, at least in my example. That's unexpected lol. Anyway, if you can think of a better solution...!

That is, going through each character of the strings and compare them to reconstruct the strings character by character.

merge python string
3 Answers

I think the easiest way would be to translate whatever operations you are performing on the combined string back to the pieces, but I guess you already thought of this. Instead, one could not insert any newline characters but generate a list of positions at which they would be entered. Keeping track of the length of the string bits, this could look like this, assuming the positions at which a ' ' is to be replaced by '\n' are stored in the variable posis:

 import numpy as np
 posis = [27,98187,227] # position of the newlines in your sample, length of full string as last entry
 lengths = [len(string) for _, string in first_input]
 covered_distance = 0 # lengths of all strings we looked at already                                           
 j = 0  # iterating index for positions                                                                       
 output = []                                                                     
 rel_pos = posis[0]-covered_distance # initialize relative position in the current string                    
 inserted_newlines = 0 # keep track of newlines we added already                  
 for i, [n, string] in enumerate(first_input):                                                                           
     while rel_pos < lengths[i]:                                                 
         string = string[:rel_pos+inserted_newlines]+'\n'\                       
                 +string[rel_pos+inserted_newlines+1:]  # replace the character at the relative position                         
         j += 1 # advance to the next newline to be inserted                              
         rel_pos = posis[j]-covered_distance # update the relative position                     
         inserted_newlines += 1  # keep track of inserted newlines      
     output.append((n, string))  # store resulting string               
     covered_distance += lengths[i]  # update the number of characters we passed                        
     rel_pos = posis[j]-covered_distance

This is not very beautiful but it works for the sample, in order to do proper testing I would need some more information on possible cases and maybe the operations determining the newline positions.

user_134891150

The way I would do it - written in terrible code. I wrote this pretty hastily 

import re
first_input = [
(0  ,  "Lorem ipsum dolor sit amet, consectetur"),
    (1  ,  " adipiscing elit"),
    (0  ,  ". In pellentesque\npharetra ex, at varius sem suscipit ac. "),
    (-1 ,  "Suspendisse luctus\ncondimentum velit a laoreet. "),
    (0  ,  "Donec dolor urna, tempus sed nulla vitae, dignissim varius neque.")
]
second_input = "Lorem ipsum dolor sit amet,\n consectetur adipiscing elit. In pellentesque\npharetra ex, at varius sem\n suscipit ac. Suspendisse luctus\ncondimentum velit a laoreet. Donec dolor urna, tempus sed\n nulla vitae, dignissim varius neque."

first_sanitized = [x[1].replace('\n', '') for x in first_input]
second_sanitized = second_input.replace('\n', '')
newline_positions = [m.start() for m in re.finditer('\n' ,second_input, re.M)]
new_output = []
i = 0
print(second_sanitized)
newlines_so_far = 0
for first_str in first_sanitized:
   print(first_str)
   index = second_sanitized.index(first_str)
   number_of_newlines_in_between = sum([1 for x in newline_positions if (x > index and x < index + len(first_input[i][1]))])
   new_string = second_input[index : (index + len(first_input[i][1]) + number_of_newlines_in_between + newlines_so_far)]
   newlines_so_far += number_of_newlines_in_between
   new_element = (first_input[i][0], new_string)
   new_output.append(new_element)
   i = i + 1

user_60468200

Ok, considering that NO CHARACTERS are replaced or modified (as the OP stated), here's what I could come up to:

first_input_no_newline = list(map(lambda x: (x[0], x[1].replace('\n', '')), first_input))

expected_output = []
for item in first_input_no_newline:
    next_index = len(item[1])

    second_input_copy = second_input
    offset = 0
    while True:
        amount = second_input_copy[:next_index].count("\n")
        if not amount:
            next_index += offset
            break
        offset += amount
        second_input_copy = second_input_copy.replace('\n', '', amount)

    expected_output.append((item[0], second_input[:next_index]))
    second_input = second_input[next_index:]

print(expected_output)

Explaining: you don't have to keep track of the newlines or anything like that. Also the newlines in "first_input" doesn't really matter, because we have all of them in the second input (plus more of them).

So, just take the length of each item of first_input_no_newline, this should also be the length of the substring in second_input if there were no newlines in it but, if there are newlines, ok, just keep counting and removing them from a copy of the second_input and add this result as an offset to cut the original second_input.

Input sample (fixed OP's original input, adding the missing white characters in between some phrases):

first_input = [
        (0, "Lorem ipsum dolor sit amet, consectetur"),
        (1, " adipiscing elit"),
        (0, ". In pellentesque\npharetra ex, at varius sem suscipit ac. "),
        (-1, "Suspendisse luctus\ncondimentum velit a laoreet. "),
        (0, "Donec dolor urna, tempus sed nulla vitae, dignissim varius neque.")
    ]

second_input = "Lorem ipsum dolor sit amet, \nconsectetur adipiscing elit. In pellentesque\npharetra ex, at varius sem \nsuscipit ac. Suspendisse luctus\ncondimentum velit a laoreet. Donec dolor urna, tempus sed \nnulla vitae, dignissim varius neque."

Output:

[
    (0, 'Lorem ipsum dolor sit amet, \nconsectetur'), 
    (1, ' adipiscing elit'), 
    (0, '. In pellentesque\npharetra ex, at varius sem \nsuscipit ac. '), 
    (-1, 'Suspendisse luctus\ncondimentum velit a laoreet. '), 
    (0, 'Donec dolor urna, tempus sed \nnulla vitae, dignissim varius neque.')
]
user_126034210
Related