BIO Tag Converter

easyPRONamed Entity RecognitionNLP 2: Applications

Convert entity annotations to BIO (Beginning-Inside-Outside) tag sequences.

In NER, each token gets a tag:

B-TYPE: Beginning of an entity of type TYPE
I-TYPE: Inside (continuation of) an entity of type TYPE
O: Outside any entity

Input:

tokens: a list of token strings
entities: a list of (start_index, end_index, entity_type) tuples (may be empty)

start_index and end_index are inclusive token indices.

Output: A list of BIO tags, one per token.

Example

Input

John Smith lives in New York City
2
0 1 PER
4 6 LOC

Output

['B-PER', 'I-PER', 'O', 'O', 'B-LOC', 'I-LOC', 'I-LOC']

Reasoning

Inputs: tokens is the sentence split into 7 words, positions 0 to 6: John, Smith, lives, in, New, York, City. entities holds two spans, each a (start, end, type) triple with both ends included: positions 0 to 1 are a person (PER), positions 4 to 6 are a location (LOC).
First span: it covers 2 tokens. The first, John, opens the entity and gets B-PER; the second, Smith, continues it and gets I-PER.
Second span: it covers $6 - 4 + 1 = 3$ tokens. New opens it as B-LOC, then York and City both continue it as I-LOC.
Everything else: lives and in sit in no span, so they are O.
Output: one tag per token, in token order, so the list has length 7: ['B-PER', 'I-PER', 'O', 'O', 'B-LOC', 'I-LOC', 'I-LOC'].
Notice that a one-token span, such as a span from 3 to 3, produces only a B- tag and no I- tags, and a sentence with no spans is all O.

Constraints

Indices are 0-based and inclusive
Entities do not overlap
Tag format: B-TYPE for first token, I-TYPE for remaining tokens of entity
All non-entity tokens get tag "O"

Learn this in

Introduction to NLPNLP Study Plan Named Entity RecognitionNLP Study Plan

More from NLP 2: Applications

BIO Entity Span Extractoreasy Simple Entity Taggereasy Sentiment Word Countereasy Keyword Classifiereasy One-Hot Sequence Encodereasy

Concept primerPREVIEW

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, and more. In the context of NER, each token (or word) in a sentence is assigned a label or tag that indicates whether it is part of a named entity and, if so, what type of entity it is.

The BIO (Beginning-Inside-Outside) tagging scheme is a common approach used in NER to annotate entities. In this scheme, each token is labeled with one of three possible tags: B-TYPE (beginning of an entity of type TYPE), I-TYPE (inside an entity of type TYPE), or O (outside any entity). This tagging scheme helps in identifying the boundaries and types of entities in a sentence. For example, in the sentence "John Smith is a developer," "John" and "Smith" would be labeled as B-PER (beginning of a person's name) and I-PER (inside a person's name), respectively, while "is," "a," and "developer" would be labeled as O.

Understanding the BIO tagging scheme and how it applies to NER tasks is crucial for solving this problem. Additionally, familiarity with basic string manipulation and indexing in programming is necessary for implementing the solution. The problem requires converting given entity annotations into BIO tag sequences, which involves iterating through the tokens and annotations to assign the appropriate BIO tags based on the entity types and their positions in the sentence.

Algorithm/Approach

The general approach to solving this problem involves iterating through the given entity annotations and applying the BIO tagging rules to each token in the sentence. This can be achieved by using a simple iterative algorithm that checks each token against the entity annotations to determine its corresponding BIO tag. The algorithm should handle cases where a token is part of multiple entities or none at all, ensuring that the correct B-TYPE, I-TYPE, or O tag is assigned.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

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.

solution.py

Python 3.13

Test results