BIO Entity Span Extractor

easyFREENamed Entity RecognitionNLP 2: Applications

Given a sentence's words and their BIO tags, extract all entity spans with their types.

Input:

words: a list of words (the sentence, already split on spaces)
tags: a list of BIO tags of the same length, one per word (B-TYPE, I-TYPE, or O)

Output: A list of strings, one per entity in sentence order, each formatted as "WORDS: TYPE" (the entity's words separated by single spaces). If there are no entities, return ["No entities found"].

Example

Input

John Smith works at New York

Output

John Smith: PERSON
New York: LOC

Reasoning

words is the sentence split into 6 words, and tags holds one BIO label per word at the same position: B-PERSON, I-PERSON, O, O, B-LOC, I-LOC.
Each label has a prefix (B begins an entity, I continues the entity just begun, O is outside any entity) and, for B and I, a type after the hyphen.
Words 1 and 2: "John" begins a PERSON and "Smith" continues it. Word 3, "works", is O, which closes the span, giving "John Smith" with type PERSON.
Word 5, "New", begins a LOC, "York" continues it, and the sentence ends, which also closes the span: "New York" with type LOC.
The result is a list of two strings in sentence order, each the span's words separated by single spaces, then a colon, a space and the type:
John Smith: PERSON
New York: LOC
Notice that a span also ends when a fresh B appears, so tags B-PERSON, B-PERSON mean two one-word people, not one. If every tag is O, the list holds just No entities found.

Constraints

B-TYPE starts a new entity
I-TYPE continues the previous entity
O means no entity
Output format: "WORDS: TYPE" per line

Learn this in

Named Entity RecognitionNLP Study Plan

More from NLP 2: Applications

Simple Entity Taggereasy Sentiment Word Countereasy Keyword Classifiereasy One-Hot Sequence Encodereasy Sequence Paddereasy

Concept primer

Background Knowledge

Named Entity Recognition (NER) is a fundamental task in Natural Language Processing (NLP) that involves identifying and categorizing named entities in unstructured text into predefined categories. These categories can include names of persons, organizations, locations, dates, times, and more. The BIO tagging scheme is a common approach used in NER, where each word in a sentence is labeled with one of three tags: B- (beginning of an entity), I- (inside an entity), or O (outside an entity).

In the context of this problem, understanding the BIO tagging scheme is crucial. For example, given a sentence "John Smith is a developer at Google", the corresponding BIO tags might be "B-PER I-PER O O O B-ORG", indicating that "John Smith" is a person and "Google" is an organization. Recognizing these entities and their types is essential for various NLP applications, including information extraction, question answering, and text summarization.

The concept of entity spans is also important. An entity span refers to the sequence of words that constitute an entity. For instance, in the sentence mentioned above, "John Smith" is an entity span of type "PER" (person). Extracting these spans with their corresponding types is the primary objective of the "BIO Entity Span Extractor" problem.

Algorithm/Approach

The general approach to solving this problem involves iterating through the sentence and its corresponding BIO tags to identify entity spans. This can be achieved by maintaining a state machine that tracks whether we are currently inside an entity or not. When a B- tag is encountered, it signals the beginning of a new entity, and when an I- tag is encountered, it indicates that we are still inside the current entity. The entity span and its type can be determined by accumulating the words corresponding to the B- and subsequent I- tags until an O tag or the end of the sentence is reached.

Step-by-Step Strategy

To implement the solution:

Read the input sentence and its BIO tags.
Initialize variables to store the current entity span and its type.
Iterate through the words and their corresponding BIO tags.
For each tag:

If the tag is B-, start a new entity span with the current word and update the entity type.
If the tag is I-, add the current word to the ongoing entity span.
If the tag is O, or if we've reached the end of the sentence, finalize the current entity span (if any) and print it along with its type.

After iterating through all tags, check if any entities were found and print the appropriate message.

Common Pitfalls

Failing to reset the entity span and type when transitioning from one entity to another.
Incorrectly handling the case where an entity spans multiple words.
Not checking for the "No entities found" condition at the end.

Time & Space Complexity

The expected time complexity for this problem is $O(n)$ , where $n$ is the number of words in the sentence, since we are iterating through the sentence and its tags once. The space complexity is also $O(n)$ , as in the worst case, we might need to store all words as part of an entity span. However, in practice, the space complexity will typically be less than $O(n)$ , depending on the actual number and size of the entity spans in the sentence.

solution.py

Python 3.13

Test results