Word-Level Translator

easyFREEMachine TranslationNLP 3: Advanced

Given a word-level translation dictionary and a source sentence, translate each word. If a word is not in the dictionary, keep it unchanged.

Input format:

Line 1: Number of dictionary entries
Next n lines: "source_word target_word"
Last line: Source sentence to translate

All matching is case-insensitive, but output the translation in its original form from the dictionary.

Function: translate(dictionary, sentence) receives the entries already parsed into a dictionary (lowercase source word → target word) and the sentence as a string. Return the translated sentence as a string, with words separated by single spaces.

Example

Input

3
hello hola
world mundo
good bueno
hello world

Output

hola mundo

Reasoning

Inputs: dictionary holds three source → target pairs with lowercase keys: hello → hola, world → mundo, good → bueno. sentence is hello world, two words separated by a space.
Word 1: "hello", compared without regard to case, matches the key hello, so it is replaced by hola.
Word 2: "world" matches the key world and becomes mundo. The pair good → bueno is never used: the dictionary may contain far more words than the sentence does.
Output: the translated words in their original order, separated by single spaces: hola mundo. Every source word maps to exactly one output word, so the output has the same word count (2) as the input.
Notice: case is ignored only when matching. The replacement is copied from the dictionary exactly as stored, and a word with no entry passes through untouched with its original capitalisation, so "Hello there World" would give "hola there mundo".

Constraints

Case-insensitive lookup
Unknown words kept as-is
Output: Translated sentence

Learn this in

Introduction to NLPNLP Study Plan

More from NLP 3: Advanced

Temperature Samplereasy ROUGE-1 Score Calculatoreasy Context Window Findereasy Keyword Answer Extractoreasy Levenshtein Distanceeasy

Concept primer

Background Knowledge

The "Word-Level Translator" problem falls under the category of Machine Translation, which is a subfield of Natural Language Processing (NLP). Machine Translation involves using computers to translate text or speech from one language to another. In this problem, we're dealing with a simple form of machine translation where we have a dictionary that maps words from a source language to their translations in a target language.

The key concept here is the idea of a translation dictionary, which is a collection of word pairs where each pair consists of a word in the source language and its corresponding translation in the target language. This dictionary serves as the basis for our translation system. Another important concept is case-insensitive matching, which means that when we look up words in the dictionary, we ignore the case (uppercase or lowercase) of the letters. This allows us to match words regardless of their case in the input sentence.

In the context of NLP, tokenization is also an important concept, which refers to the process of breaking down text into individual words or tokens. In this problem, we'll need to tokenize the input sentence into individual words and then look up each word in the translation dictionary to find its translation. Understanding these concepts will help you approach the problem with a solid foundation in NLP and machine translation.

Algorithm/Approach

The general approach to solving this problem involves using a dictionary lookup algorithm, where we iterate through each word in the input sentence and check if it exists in the translation dictionary. If a word is found in the dictionary, we replace it with its translation; otherwise, we leave it unchanged. This approach relies on string matching and dictionary data structures, which are fundamental in computer science.

Step-by-Step Strategy

To solve this problem, follow these steps:

Read the number of dictionary entries and create a data structure to store the word pairs.
Populate the data structure with the word pairs from the input.
Tokenize the input sentence into individual words.
Iterate through each word in the sentence and check if it exists in the dictionary (case-insensitive).
If a word is found, replace it with its translation; otherwise, leave it unchanged.
Output the translated sentence.

Common Pitfalls

When implementing the solution, watch out for the following:

Ensure that the dictionary lookup is case-insensitive.
Handle words that are not in the dictionary correctly (i.e., leave them unchanged).
Preserve the original case of the translations from the dictionary.

Time & Space Complexity

The expected time complexity for this problem is $O(n + m)$ , where $n$ is the number of dictionary entries and $m$ is the number of words in the input sentence. This is because we need to read and process each dictionary entry and each word in the sentence once. The space complexity is also $O(n + m)$ , as we need to store the dictionary entries and the input sentence in memory.

solution.py

Python 3.13

Test results