Entity Span Extractor
Extract entity spans from a BIO-tagged token sequence.
Given tokens and their BIO tags, extract all entity spans as (text, type) tuples, where text is the concatenation of entity tokens joined by spaces.
Input format:
- Line 1: Space-separated tokens
- Line 2: Space-separated BIO tags
Output: A list of tuples: (entity_text, entity_type), in order of appearance.
Example:
John Smith lives in New York City today B-PER I-PER O O B-LOC I-LOC I-LOC O
[('John Smith', 'PER'), ('New York City', 'LOC')]Scan through tags:
- "John" B-PER: start new PER entity
- "Smith" I-PER: continue PER entity
- "lives" O: end entity -> emit ("John Smith", "PER")
- "in" O: nothing
- "New" B-LOC: start new LOC entity
- "York" I-LOC: continue LOC entity
- "City" I-LOC: continue LOC entity
- "today" O: end entity -> emit ("New York City", "LOC")
Constraints:
- B-TYPE starts a new entity (even if previous tag was I-TYPE of different type)
- I-TYPE continues the current entity only if it matches the type of the previous B/I tag
- If I-TYPE follows O or mismatches type, treat it as B-TYPE
- Output entities in order of appearance
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. In the context of this problem, we're dealing with a specific type of NER output known as BIO tagging. BIO stands for "Beginning, Inside, Outside," which refers to the tagging scheme used to mark the boundaries of entities in a sentence. A token tagged as 'B' marks the beginning of an entity, 'I' marks a token inside an entity, and 'O' marks a token outside any entity.
The BIO tagging scheme is crucial for understanding how entities are represented in the input. For example, if we have a sentence "John Smith is going to New York," the BIO tags for the entities could be "B-Person I-Person O O O B-Location." This tells us that "John" and "Smith" together form a person entity, and "New" and "York" together form a location entity. Understanding this tagging scheme is essential for extracting entity spans correctly.
In the context of entity span extraction, our goal is to take a sequence of tokens and their corresponding BIO tags and extract all the entities present in the text. This involves identifying the start and end of each entity based on the BIO tags and then concatenating the tokens within those boundaries to form the entity text. The entity type is determined by the tag associated with the entity (e.g., Person, Location, Organization).
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.