Feature request: keep shorter spans in util.filter_spans

[ktobah]

According to the util.filter_spans docs, it says:

Filter a sequence of Span objects and remove duplicates or overlaps. Useful for creating named entities (where one token can only be part of one entity) or when merging spans with Retokenizer.merge. When spans overlap, the (first) longest span is preferred over shorter spans.

I was wondering if it is possible to make this function more flexible and allow the user to choose to either keep the shorter or longer spans? In my case, I need to keep the shorter spans.

[svlandeg]

Hi! Sure, that sounds like a good idea. It shouldn't be too much work I think, adding a new parameter and adjusting the sort function accordingly. And add a few unit tests to make sure it works correctly.

Do you want to make the PR?

[ktobah]

Hi,

I checked the method definition and made the following changes:

def filter_spans(spans, keep_longest=True):
    """Filter a sequence of spans and remove duplicates or overlaps. Useful for
    creating named entities (where one token can only be part of one entity) or
    when merging spans with `Retokenizer.merge`. When spans overlap, the (first)
    longest span is preferred over shorter spans.
    spans (Iterable[Span]): The spans to filter.
    keep_longest (bool): Specify whether to keep longer or shorter spans.
    RETURNS (List[Span]): The filtered spans.
    """
    get_sort_key = lambda span: (span.end - span.start, -span.start)
    sorted_spans = sorted(spans, key=get_sort_key, reverse=keep_longest)
    result = []
    seen_tokens = set()
    for span in sorted_spans:
        # Check for end - 1 here because boundaries are inclusive
        if span.start not in seen_tokens and span.end - 1 not in seen_tokens:
            result.append(span)
            seen_tokens.update(range(span.start, span.end))
    result = sorted(result, key=lambda span: span.start)
    return result

It worked for my case; however, I am not sure if this logic is the correct one.

There are few other files to amend, but they are mostly documentation (easy to do). Except for the tests file, it has:

A doc variable generated from this sentence: "This is a sentence. This is another sentence. And a third."

The old test for longer spans produces:

spans = [doc[1:4], doc[1:3], doc[5:10], doc[7:9], doc[1:4]] 
# [is a sentence, is a, This is another sentence ., another sentence, is a sentence]
filtered = filter_spans(spans) 
# [is a sentence, This is another sentence .]

With the keep_longer = False, we get:

spans = [doc[1:4], doc[1:3], doc[5:10], doc[7:9], doc[1:4]] 
# [is a sentence, is a, This is another sentence ., another sentence, is a sentence]
filtered = filter_spans_edit(spans, keep_longest=False) 
# [is a, This is another sentence ., another sentence]

Does this result look ok to you?

[svlandeg]

Hm, that doesn't look right, because you still have overlapping spans in the last case?

[adrianeboyd]

Also, if you have reverse=False, you might want the sort key to prefer earlier equally short spans over later short spans:

get_sort_key = lambda span: (span.end - span.start, span.start)

We've tripped over this several times internally in various places where spans are filtered.

Overall, I personally think it might be better to keep filter_spans as it is in the library. It's such a short method that it shouldn't be a problem for users who need custom filtering behavior to implement their own methods, and adding all the potential filtering options here will get difficult to maintain. (For a user glancing at the API docs, what does keep_longest=False mean?)

[ktobah]

Hi,

@svlandeg you are right. There is overlapping. @adrianeboyd suggestion helps to solve the sorting issue; however even with that, we get the same result. After debugging, I see that the reason is this line inside the for loop:

if span.start not in seen_tokens and span.end - 1 not in seen_tokens:

For such list [is a, another sentence, is a sentence, is a sentence, This is another sentence .], it would ignore "is a sentence" but it will append "This is another sentence ." because both its start and end positions pass the if check. So, I am not sure if this is the expected behavior when the starting tokens are different (doesn't seem like it in this case).

@adrianeboyd I think the filtering here will only concern two cases, longer spans which is the default or shorter ones. So, I still think it is a valid option to add but I am not sure how complex things will turn to be. As for the documentation, of course, it will have to be written again to be more clear. For now, I was just focusing on the implementation if it makes sense and is correct.

[ktobah]

I have rewritten the method as follow:

def filter_spans(spans, keep_longest=True):
    """Filter a sequence of spans and remove duplicates or overlaps. Useful for
    creating named entities (where one token can only be part of one entity) or
    when merging spans with `Retokenizer.merge`. When spans overlap, the (first)
    longest span is preferred over shorter spans.
    spans (Iterable[Span]): The spans to filter.
    keep_longest (bool): Specify whether to keep longer or shorter spans.
    RETURNS (List[Span]): The filtered spans.
    """
    get_sort_key = lambda span: (span.end - span.start, span.start)
    sorted_spans = sorted(spans, key=get_sort_key, reverse=keep_longest)
    result = []
    seen_tokens = set()
    for span in sorted_spans:
        if not keep_longest:
            if all([token_pos not in seen_tokens for token_pos in range(span.start, span.end)]):
                result.append(span)
                seen_tokens.update(range(span.start, span.end))
        else:
            # Check for end - 1 here because boundaries are inclusive
            if span.start not in seen_tokens and span.end - 1 not in seen_tokens:
                result.append(span)
                seen_tokens.update(range(span.start, span.end))
    result = sorted(result, key=lambda span: span.start)
    return result 

This one returns the expected result of [is a, another sentence].

The idea is for the next span to check, only append it if none of its tokens has been seen before. What do you think?

If this solution gives the desired behavior, we can improve it by moving the if not keep_longest: test out of the loop, so it would be checked only once for performance gain.