Задача B. BLEU ≡

Условие

Метрика BLEU (Bi-Lingual Evaluation Understudy) чаще всего используется для оценки качества машинного перевода. Эта метрика предназначена для сравнения исходного предложения s₁ и предложения s₂, полученного в результате перевода.

Основная идея метрики BLEU заключается в подсчёте количества совпадающих фраз.

На первой стадии для предложений s₁ и s₂ выписываются множества всех встречающихся слов и подсчитывается количество совпадающих слов в первом и втором предложении. Эту величину обозначим 1gram. Далее величина 1gram делится на количество слов в предложении s₂.

Так для s₁ = "This is the wolf." и s₂ = "The the the the the.", значение 1gram = 1 / 5 = 0.2.

На второй стадии выписываются все пары соседних слов предложений s₁ и s₂, и вычисляется количество совпадающих пар, эту величину обозначим 2gram. Величина 2gram также делится на количество пар соседних слов в предложении s₂.

Аналогичным образом вычислим 3gram и 4gram.

Помимо указанных выше величин при расчёте метрики BLEU используется штраф за то, что сгенерированный перевод слишком короткий Brevity Penalty (BP). BP = |s₂| / |s₁|. Где |s| — длина строки s.

BLEU = BP ⋅ ⁴√1gram ⋅ 2gram ⋅ 3gram ⋅ 4gram

На изображении приведён пример. SYSTEM A — это перевод первой системы машинного перевода, SYSTEM B — второй системы, REFERENCE — эталонный перевод.

Формат входных данных

Первая строка входного файла содержит строку s₁.

Вторая строка входного файла содержит строку s₂.

Входные строки состоят из латинских букв, пробелов и знаков препинания. Заглавные и строчные буквы не различаются при сравнении слов. Словом считается любая последовательность подряд идущих букв, ограниченная с обеих сторон концом строки, пробелом или знаком препинания.

Формат выходных данных

Выходной файл должен содержать единственное число — значение метрики BLEU для предложений s₁ и s₂ с точностью не менее 5 десятичных знаков после запятой.

Ограничения

1 ≤ |s₁|, |s₂| ≤ 1000

Примеры тестов

Israeli officials are responsible for airport security.
Israeli officials responsibility of airport safety.

0

Israeli officials are responsible for airport security.
Airport security Israeli officials are responsible.

0.517950068118303 

This is the police Department of the city of Moscow in the Leninsky district.
This is the police Department of the the city of Leninsky district the Moscow.

0.5847065326973129