473,238 Members | 1,727 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,238 software developers and data experts.

converting text and spans to an ElementTree

I have some text and a list of Element objects and their offsets, e.g.::
>>text = 'aaa aaa aaabbb bbbaaa'
spans = [
... (etree.Element('a'), 0, 21),
... (etree.Element('b'), 11, 18),
... (etree.Element('c'), 18, 18),
... ]

I'd like to produce the corresponding ElementTree. So I want to write a
get_tree() function that works like::
>>tree = get_tree(text, spans)
etree.tostring(tree)
'<a>aaa aaa aaa<b>bbb bbb<c /></b>aaa</a>'

Perhaps I just need some more sleep, but I can't see an obvious way to
do this. Any suggestions?

Thanks,

STeVe
May 22 '07 #1
9 1960
En Tue, 22 May 2007 03:02:34 -0300, Steven Bethard
<st************@gmail.comescribió:
I have some text and a list of Element objects and their offsets, e.g.::
>>text = 'aaa aaa aaabbb bbbaaa'
>>spans = [
... (etree.Element('a'), 0, 21),
... (etree.Element('b'), 11, 18),
... (etree.Element('c'), 18, 18),
... ]

I'd like to produce the corresponding ElementTree. So I want to write a
get_tree() function that works like::
>>tree = get_tree(text, spans)
>>etree.tostring(tree)
'<a>aaa aaa aaa<b>bbb bbb<c /></b>aaa</a>'

Perhaps I just need some more sleep, but I can't see an obvious way to
do this. Any suggestions?
I need *some* sleep, but the idea would be as follows:

- For each span generate two tuples: (start_offset, 1, end_offset,
element) and (end_offset, 0, -start_offset, element). If start==end use
(start_offset, -1, start_offset, element).
- Collect all tuples in a list, and sort them. The tuple is made so when
at a given offset there is an element that ends and another that starts,
the ending element comes first (because it has a 0). For all the elements
that end at a given point, the shortest comes first.
- Initialize an empty list (will be used as a stack of containers), and
create a root Element as your "current container" (CC), the variable
"last_used" will keep the last position used on the text.
- For each tuple in the sorted list:
- if the second item is a 1, an element is starting. Insert it into the
CC element, push the CC onto the stack, and set the new element as the new
CC. The element data is text[last_used:start_offset], and move last_used
to start_offset.
- if the second item is a 0, an element is ending. Discard the CC, pop
an element from the stack as the new CC. The element data is
text[last_used:end_offset], move last_used up to end_offset.
- if the second item is a -1, it's an element with no content. Insert it
into the CC element.

You can play with the way the tuples are generated and sorted, to get
'<a>aaa aaa aaa<b>bbb bbb</b><c />aaa</a>' instead.

--
Gabriel Genellina

May 22 '07 #2
On May 21, 11:02 pm, Steven Bethard <steven.beth...@gmail.comwrote:
I have some text and a list of Element objects and their offsets, e.g.::
>>text = 'aaa aaa aaabbb bbbaaa'
>>spans = [
... (etree.Element('a'), 0, 21),
... (etree.Element('b'), 11, 18),
... (etree.Element('c'), 18, 18),
... ]

I'd like to produce the corresponding ElementTree. So I want to write a
get_tree() function that works like::
>>tree = get_tree(text, spans)
>>etree.tostring(tree)
'<a>aaa aaa aaa<b>bbb bbb<c /></b>aaa</a>'

Perhaps I just need some more sleep, but I can't see an obvious way to
do this. Any suggestions?

It seems you're looking to construct an Interval Tree:

http://en.wikipedia.org/wiki/Interval_tree

--
Hope this helps,
Steven

May 22 '07 #3
at*************@gmail.com wrote:
On May 21, 11:02 pm, Steven Bethard <steven.beth...@gmail.comwrote:
>I have some text and a list of Element objects and their offsets, e.g.::
> >>text = 'aaa aaa aaabbb bbbaaa'
>>spans = [
... (etree.Element('a'), 0, 21),
... (etree.Element('b'), 11, 18),
... (etree.Element('c'), 18, 18),
... ]

I'd like to produce the corresponding ElementTree. So I want to write a
get_tree() function that works like::
> >>tree = get_tree(text, spans)
>>etree.tostring(tree)
'<a>aaa aaa aaa<b>bbb bbb<c /></b>aaa</a>'

Perhaps I just need some more sleep, but I can't see an obvious way to
do this. Any suggestions?

It seems you're looking to construct an Interval Tree:

http://en.wikipedia.org/wiki/Interval_tree
No, I'm looking to construct an ElementTree from intervals. ;-) Could
you elaborate on how an Interval Tree would help me?

STeVe
May 22 '07 #4
On May 21, 11:02 pm, Steven Bethard <steven.beth...@gmail.comwrote:
I have some text and a list of Element objects and their offsets, e.g.::
>>text = 'aaa aaa aaabbb bbbaaa'
>>spans = [
... (etree.Element('a'), 0, 21),
... (etree.Element('b'), 11, 18),
... (etree.Element('c'), 18, 18),
... ]

I'd like to produce the corresponding ElementTree. So I want to write a
get_tree() function that works like::
>>tree = get_tree(text, spans)
>>etree.tostring(tree)
'<a>aaa aaa aaa<b>bbb bbb<c /></b>aaa</a>'

Perhaps I just need some more sleep, but I can't see an obvious way to
do this. Any suggestions?

It seems you're looking to construct an Interval Tree:

http://en.wikipedia.org/wiki/Interval_tree

--
Hope this helps,
Steven

May 22 '07 #5
Gabriel Genellina wrote:
the idea would be as follows:

- For each span generate two tuples: (start_offset, 1, end_offset,
element) and (end_offset, 0, -start_offset, element). If start==end use
(start_offset, -1, start_offset, element).
- Collect all tuples in a list, and sort them. The tuple is made so when
at a given offset there is an element that ends and another that starts,
the ending element comes first (because it has a 0). For all the
elements that end at a given point, the shortest comes first.
- Initialize an empty list (will be used as a stack of containers), and
create a root Element as your "current container" (CC), the variable
"last_used" will keep the last position used on the text.
- For each tuple in the sorted list:
- if the second item is a 1, an element is starting. Insert it into
the CC element, push the CC onto the stack, and set the new element as
the new CC. The element data is text[last_used:start_offset], and move
last_used to start_offset.
- if the second item is a 0, an element is ending. Discard the CC, pop
an element from the stack as the new CC. The element data is
text[last_used:end_offset], move last_used up to end_offset.
- if the second item is a -1, it's an element with no content. Insert
it into the CC element.

Thanks a lot! This put me on the right track (though the devil's
definitely in the details). It's working now::

>>tree = xmltools.text_and_spans_to_etree('aaa aaa aaaccc cccaaa', [
.... (etree.Element('a'), 0, 21),
.... (etree.Element('b'), 11, 11),
.... (etree.Element('c'), 11, 18),
.... ])
>>etree.tostring(tree)
'<a>aaa aaa aaa<b /><c>ccc ccc</c>aaa</a>'
>>tree = xmltools.text_and_spans_to_etree('bbb\naaaccc\nccc aaa', [
.... (etree.Element('a'), 0, 17),
.... (etree.Element('b'), 0, 4),
.... (etree.Element('c'), 7, 14),
.... (etree.Element('b'), 14, 14),
.... ])
>>etree.tostring(tree)
'<a><b>bbb\n</b>aaa<c>ccc\nccc</c><b />aaa</a>'
>>tree = xmltools.text_and_spans_to_etree('abc', [
.... (etree.Element('a'), 0, 3),
.... (etree.Element('b'), 0, 3),
.... (etree.Element('c'), 0, 3),
.... ])
>>etree.tostring(tree)
'<a><b><c>abc</c></b></a>'
And for the sake of any poor soul who runs into a similar problem,
here's the code I wrote using Gabriel's hints above::
def text_and_spans_to_etree(text, spans):
# Create a list of element starts and ends, sorting them in the
# order they would appear in an XML version of the text. So for
# example, with XML text like:
# <aa <bb </ba </a>
# we will see:
# starting <a>
# starting <b>
# ending </b>
# ending </a>
empty = -1
starting = 0
ending = 1
tuples = []
root_elem = None
for i, (elem, start, end) in enumerate(spans):
# validate spans
if start < 0 or end len(text):
msg = 'spans must be in the range 0-%i'
raise ValueError(msg % len(text))

# save the first element that spans the entire text as the root
elif root_elem is None and start == 0 and end == len(text):
root_elem = elem

# insert a single tuple for empty elements
elif start == end:
tuples.append((start, empty, -end, i, elem))

# insert starts and ends for all other elements
else:
tuples.append((start, starting, -end, i, elem))
tuples.append((start, ending, -end, -i, elem))
tuples.sort()

# make sure we found a root element
if root_elem is None:
raise ValueError('one element must span the entire text')

# iterate through the element starts and ends,
# updating element texts, tails and children
last_offset = 0
last_elem = root_elem
last_type = starting
stack = [root_elem]
for start, offset_type, neg_end, _, elem in tuples:

# start of an element:
# add it as a child and add it to the stack
# next text chunk goes up to the start offset
if offset_type is starting:
stack[-1].append(elem)
stack.append(elem)
offset = start

# end of an element:
# pop if off the stack
# next text chunk goes up to the end offset
elif offset_type is ending:
if elem is not stack[-1]:
print elem, stack[-1]
assert False
assert elem is stack.pop()
offset = -neg_end

# empty element:
# add it as a child
# next text chunk goes up to the start offset
elif offset_type is empty:
stack[-1].append(elem)
offset = start

# should never get here
else:
assert False

# calculate the next text chunk, and then determine what to do
# with it based on what we did the last time around:
# * started an element -set its .text
# * ended an element (or inserted an empty) -set its .tail
last_text = text[last_offset:offset]
if last_type is starting:
last_elem.text = last_text
elif last_type is ending:
last_elem.tail = last_text
elif last_type is empty:
last_elem.tail = last_text
else:
assert False

# save what we did this time for inspection next time
last_offset = offset
last_type = offset_type
last_elem = elem

# add any final text before the close of the root element
last_elem.tail = text[last_offset:]

return root_elem
Thanks again,

STeVe
May 22 '07 #6
On 2007-05-22, Steven Bethard <st************@gmail.comwrote:
Thanks a lot! This put me on the right track (though the
devil's definitely in the details). It's working now::

>tree = xmltools.text_and_spans_to_etree('aaa aaa aaaccc cccaaa', [
... (etree.Element('a'), 0, 21),
... (etree.Element('b'), 11, 11),
... (etree.Element('c'), 11, 18),
... ])
>etree.tostring(tree)
'<a>aaa aaa aaa<b /><c>ccc ccc</c>aaa</a>'
>tree = xmltools.text_and_spans_to_etree('bbb\naaaccc\nccc aaa', [
... (etree.Element('a'), 0, 17),
... (etree.Element('b'), 0, 4),
... (etree.Element('c'), 7, 14),
... (etree.Element('b'), 14, 14),
... ])
>etree.tostring(tree)
'<a><b>bbb\n</b>aaa<c>ccc\nccc</c><b />aaa</a>'
>tree = xmltools.text_and_spans_to_etree('abc', [
... (etree.Element('a'), 0, 3),
... (etree.Element('b'), 0, 3),
... (etree.Element('c'), 0, 3),
... ])
>etree.tostring(tree)
'<a><b><c>abc</c></b></a>'
And for the sake of any poor soul who runs into a similar
problem, here's the code I wrote using Gabriel's hints above::
When I saw you manually keeping a stack, I called Captain
Recursion on my Red-Alert Recursion Phone.

(I'm sorry he left out the Element stuff, which he doesn't know
or use yet. The Captain's get_tree just returns the string)

def get_tree(text, spans):
"""
>>text = 'aaa aaa aaabbb bbbaaa'
spans = [
... ('a', 0, 21),
... ('b', 11, 18),
... ('c', 18, 18),
... ]

I'd like to produce the corresponding ElementTree. So I want to write a
get_tree() function that works like::
>>get_tree(text, spans)
'<a>aaa aaa aaa<b>bbb bbb<c /></b>aaa</a>'
"""
if not spans:
return ''
else:
head, tail = spans[0], spans[1:]
elem, start, end = head
if tail:
_, follow_start, follow_end = tail[0]
else:
follow_start, follow_end = (end, end)
if end start:
return ("<%s>%s%s%s</%s>" %
(elem,
text[start:follow_start],
get_tree(text, tail),
text[follow_end:end],
elem))
else:
return "<%s />%s" % (elem, get_tree(text, tail))

--
Neil Cerutti
May 23 '07 #7
Neil Cerutti wrote:
On 2007-05-22, Steven Bethard <st************@gmail.comwrote:
>Thanks a lot! This put me on the right track (though the
devil's definitely in the details). It's working now::

>>>>tree = xmltools.text_and_spans_to_etree('aaa aaa aaaccc cccaaa', [
... (etree.Element('a'), 0, 21),
... (etree.Element('b'), 11, 11),
... (etree.Element('c'), 11, 18),
... ])
>>>>etree.tostring(tree)
'<a>aaa aaa aaa<b /><c>ccc ccc</c>aaa</a>'
>>>>tree = xmltools.text_and_spans_to_etree('bbb\naaaccc\nccc aaa', [
... (etree.Element('a'), 0, 17),
... (etree.Element('b'), 0, 4),
... (etree.Element('c'), 7, 14),
... (etree.Element('b'), 14, 14),
... ])
>>>>etree.tostring(tree)
'<a><b>bbb\n</b>aaa<c>ccc\nccc</c><b />aaa</a>'
>>>>tree = xmltools.text_and_spans_to_etree('abc', [
... (etree.Element('a'), 0, 3),
... (etree.Element('b'), 0, 3),
... (etree.Element('c'), 0, 3),
... ])
>>>>etree.tostring(tree)
'<a><b><c>abc</c></b></a>'
And for the sake of any poor soul who runs into a similar
problem, here's the code I wrote using Gabriel's hints above::

When I saw you manually keeping a stack, I called Captain
Recursion on my Red-Alert Recursion Phone.

(I'm sorry he left out the Element stuff, which he doesn't know
or use yet. The Captain's get_tree just returns the string)
Heh heh.

I actually thought about writing it recursively, but note that you need
both recursive and non-recursive parts of this algorithm to do the
ElementTree part right:

* the recursive (or stack) part assigns children to parents
* the non-recursive part assigns text or tail to the previous element
(note that's previous in a sequential sense, not a recursive sense)

I'm sure I could implement this recursively, passing around annother
appropriate argument, but it wasn't obvious to me that the code would be
any cleaner.

STeVe
May 23 '07 #8
On 2007-05-23, Steven Bethard <st************@gmail.comwrote:
Neil Cerutti wrote:
>On 2007-05-22, Steven Bethard <st************@gmail.comwrote:
>>Thanks a lot! This put me on the right track (though the
devil's definitely in the details). It's working now::
>tree = xmltools.text_and_spans_to_etree('aaa aaa aaaccc cccaaa', [
... (etree.Element('a'), 0, 21),
... (etree.Element('b'), 11, 11),
... (etree.Element('c'), 11, 18),
... ])
>etree.tostring(tree)
'<a>aaa aaa aaa<b /><c>ccc ccc</c>aaa</a>'
>tree = xmltools.text_and_spans_to_etree('bbb\naaaccc\nccc aaa', [
... (etree.Element('a'), 0, 17),
... (etree.Element('b'), 0, 4),
... (etree.Element('c'), 7, 14),
... (etree.Element('b'), 14, 14),
... ])
>etree.tostring(tree)
'<a><b>bbb\n</b>aaa<c>ccc\nccc</c><b />aaa</a>'
>tree = xmltools.text_and_spans_to_etree('abc', [
... (etree.Element('a'), 0, 3),
... (etree.Element('b'), 0, 3),
... (etree.Element('c'), 0, 3),
... ])
>etree.tostring(tree)
'<a><b><c>abc</c></b></a>'
And for the sake of any poor soul who runs into a similar
problem, here's the code I wrote using Gabriel's hints above::

When I saw you manually keeping a stack, I called Captain
Recursion on my Red-Alert Recursion Phone.

(I'm sorry he left out the Element stuff, which he doesn't know
or use yet. The Captain's get_tree just returns the string)

Heh heh.

I actually thought about writing it recursively, but note that
you need both recursive and non-recursive parts of this
algorithm to do the ElementTree part right:
You mean... I left out the hard part? Shucks. I had really hoped
it didn't matter.
* the recursive (or stack) part assigns children to parents
* the non-recursive part assigns text or tail to the previous element
(note that's previous in a sequential sense, not a recursive sense)

I'm sure I could implement this recursively, passing around
annother appropriate argument, but it wasn't obvious to me that
the code would be any cleaner.
Moreover, it looks like you have experience in writing that sort
of code. I'd have never even attempted it without recursion, but
that's merely exposing one of my limitations. ;)

--
Neil Cerutti
May 24 '07 #9
On 2007-05-24, Neil Cerutti <ho*****@yahoo.comwrote:
On 2007-05-23, Steven Bethard <st************@gmail.comwrote:
You mean... I left out the hard part? Shucks. I had really
hoped it didn't matter.
>* the recursive (or stack) part assigns children to parents
* the non-recursive part assigns text or tail to the previous element
(note that's previous in a sequential sense, not a recursive sense)

I'm sure I could implement this recursively, passing around
annother appropriate argument, but it wasn't obvious to me
that the code would be any cleaner.

Moreover, it looks like you have experience in writing that
sort of code. I'd have never even attempted it without
recursion, but that's merely exposing one of my limitations. ;)
You'll be happy to know I found a way to salvage my simple
recursive solution, and make it generate an ElementTree!

def get_tree(text, spans):
"""
>>text = 'aaa aaa aaabbb bbbaaa'
spans = [
... (etree.Element('a'), 0, 21),
... (etree.Element('b'), 11, 18),
... (etree.Element('c'), 18, 18),
... ]

I'd like to produce the corresponding ElementTree. So I want to write a
get_tree() function that works like::
>>etree.tostring(get_tree(text, spans))
'<a>aaa aaa aaa<b>bbb bbb<c /></b>aaa</a>'
"""
def helper(text, spans):
if not spans:
return ''
else:
head, tail = spans[0], spans[1:]
elem, start, end = head
if tail:
_, follow_start, follow_end = tail[0]
else:
follow_start, follow_end = (end, end)
if end start:
return ("<%s>%s%s%s</%s>" %
(elem.tag,
text[start:follow_start],
helper(text, tail),
text[follow_end:end],
elem.tag))
else:
return "<%s />%s" % (elem.tag, helper(text, tail))
return etree.XML(helper(text, spans))

But at least I learned just a *little* about XML and Python
during this arduous process. ;)

--
Neil Cerutti
The concert held in Fellowship Hall was a great success. Special thanks are
due to the minister's daughter, who labored the whole evening at the piano,
which as usual fell upon her. --Church Bulletin Blooper
May 24 '07 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

8
by: Robert Oschler | last post by:
Has anybody seen a Python module that will take an XML document (not a colossal one), and convert it to a Python nested class object? I'm basically looking for something that would allow me to...
7
by: Stewart Midwinter | last post by:
I want to parse a file with ElementTree. My file has the following format: <!-- file population.xml --> <?xml version='1.0' encoding='utf-8'?> <population> <person><name="joe" sex="male"...
1
by: Greg Wilson | last post by:
I'm trying to convert from minidom to ElementTree for handling XML, and am having trouble with entities in DTDs. My Python script looks like this: ...
11
by: Max M | last post by:
I am writing a "find-free-time" function for a calendar. There are a lot of time spans with start end times, some overlapping, some not. To find the free time spans, I first need to convert the...
3
by: svintuss | last post by:
Hi. I'm trying to create a widget for Tiger, which should use a web-dictionary. I want the widget to display translation within its window, so it has to copy all the data within the tags <span...
2
by: mirandacascade | last post by:
Situation is this: 1) I have inherited some python code that accepts a string object, the contents of which is an XML document, and produces a data structure that represents some of the content of...
5
by: saif.shakeel | last post by:
#!/usr/bin/env python from elementtree import ElementTree as Element tree = et.parse("testxml.xml") for t in tree.getiterator("SERVICEPARAMETER"): if t.get("Semantics") == "localId":...
5
by: Jan Danielsson | last post by:
Hello all, I'm using mod_python+ElementTree to build XHTML pages. But I stumbled across this problem: -------------------- def foo(req, desc = None): ...
2
by: mndprasad | last post by:
Hi friends, Am new to AJAX coding, In my program am going to have two texbox which going to implent AJAX from same table. One box is going to retrieve the value of other and vice...
3
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 3 Jan 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). For other local times, please check World Time Buddy In...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
0
by: Aftab Ahmad | last post by:
So, I have written a code for a cmd called "Send WhatsApp Message" to open and send WhatsApp messaage. The code is given below. Dim IE As Object Set IE =...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.