QOJ.ac

QOJ

时间限制: 5 s 内存限制: 256 MB 总分: 100

#2324. 二元语法语言模型

统计

在自然语言处理中,语言模型通过为所有可能的句子分配概率分布,来给出某个英文句子在特定语境(例如日常对话、学术论文或新闻网站)中出现的可能性。二元语法(Bigram)语言模型通过估计从前一个词到下一个词的转移概率来处理这种建模问题。形式上:

$$P(S = w_1w_2 \dots w_m) = P(w_1)P(w_2 \mid w_1) \dots P(w_m \mid w_{m-1})$$

我们可以根据从语境中收集的语料库(一组句子的集合)来估计从词 $s$ 到词 $t$ 的转移概率:

$$P(t \mid s) = \frac{c(s, t)}{\sum_{t' \in V} c(s, t')}$$

其中 $V$ 表示词汇表(即语料库中所有词的集合),$c(s, t)$ 表示词 $t$ 在语料库中紧跟在词 $s$ 之后出现的总次数(在同一个句子内)。

Suzukaze 收集了一个语料库,并试图计算一些句子的概率。他需要你的帮助来获取一些转移概率。你能帮帮他吗?

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 1000$),表示语料库中的句子数量。

接下来的 $n$ 行中,第 $i$ 行以一个整数 $m_i$ ($1 \le m_i \le 100$) 开头,表示第 $i$ 个句子中的单词数量。随后是 $m_i$ 个以空格分隔的单词。

下一行包含一个整数 $q$ ($1 \le q \le 10^4$),表示查询的数量。

接下来的 $q$ 行中,每行包含两个以空格分隔的单词 $s$ 和 $t$,查询从词 $s$ 到词 $t$ 的估计转移概率。

语料库和查询中的所有单词长度均不超过 10 个字符,且仅包含小写字母。

输出格式

对于每个查询,输出一行,包含所查询词对的估计转移概率。请将结果表示为不可约分数。(详见样例)

如果无法根据语料库估计转移概率,请输出 "Insufficient data"。

样例

样例输入 1

5
7 get busy living or get busy dying
4 stay hungry stay foolish
6 whatever you do do it well
6 everything you can imagine is real
5 the things you can find
8
get busy
busy living
hungry stay
foolish stay
do do
you do
you can
can do

样例输出 1

1/1
1/2
1/1
Insufficient data
1/2
1/3
2/3
0/1

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.