编程介的小学生 2019-06-18 10:17 采纳率: 20.5%
浏览 143

单词序列上的字母的预测的算法问题,怎么使用C语言的程序的编写的技术有效实现的呢?

Problem Description
When little Sascha grew up, she lost her bad habit of pronouncing words in ways that were most easy for her, but did not always match the correct-pronunciation. However, she never lost the linguistic creativity she used to show as a little girl. When the Earth Allied Forces (EAF) discovered she also had brilliant mathematical insights and a knack for puzzles and secret messages,she was immediately offered the position of Head of the EAF Intelligence Department.

Sascha's current task is interpreting intercepted internal messages of the hostile Mars Feder-ation. Although Martian messages always consist of just one word, her task turns out not to be easy, as two factors in uence the content of the intercepted message:

a) Extraterrestrial environment conditions are so bad that errors can occur in intercepted messages, causing them to be quite obfuscated compared to the originally sent text. If such errors occur, the erroneous characters will be characters from the Martian alphabet, just as the original characters.

b) Furthermore, linguistic characteristics play an important role. In Martian, there are relations between two subsequent characters: for a given character, some characters are more likely predecessors than others (note that something similar occurs in English: for example, a h' in a word will more likely have been preceded by a 't' than by aq').

Fortunately, probabilities that a received character y actually was sent as an original Martian character x is known for all alphabet characters, as well as the probabilities that a certain character xi occurs in a clean Martian word if it was preceded by a Martian character x(i-1).

Given all these probabilities, Sascha wants to nd the so-called maximum likelihood text for a received message, which is the most likely message the Martians originally sent. As senior pro-grammer in the EAF Intelligence Department, you must write a program for her, achieving this goal for several intercepted messages in several local Martian dialects.

To give a simple example, consider a local Martian alphabet only consisting of the characters ‘a’ and ‘b’ and let the receiving error probabilities and character succession probabilities be as shown in Table 2. If the intercepted message just consists of an a', this can either originally have been ana' or a b'. With no previous characters available, only the error probabilities are considered: it then turns out that the maximum likelihood message is ana' as well, with probability 0.9.

Table 2: Example Receiving Error Probabilities (left) and Character Succession Probabilities(right).

To extend the example, if the intercepted message was ab', we also need the character succession probabilities. The probability that the original message wasaa' is

p(received a' indeed was originally sent asa')

*p(received 'b' was originally sent as a') *p(charactera' succeeds previous `a')

= 0.9 * 0.1 * 0.8:

Similarly, the probability that the original message was bb',ab' or ba' are 0.1 * 0.9 * 0.95, 0.9* 0.9 * 0.05 and 0.1 * 0.1 *0.2, respectively. Hence, the maximum likelihood message now isbb'. In all cases asked for, there will always be a unique maximum likelihood message.

Input
The _rst line of input consists of the integer number n, the number of test cases;

Then, for each test case:

  • An integer number a (0 < a < 30), which is the number of characters in the local Martian alphabet;

  • A line containing the a unique characters c1; c2; ..... ; ca of the local Martian alphabet,separated by single spaces. Whitespace characters will not occur in the alphabet;

  • a lines, specifying receiving error probabilities for the a alphabet characters in the orderin which they were presented. The ith line corresponds to the error probabilities for the original alphabet character ci and contains:

  • a floating point numbers ei1; ei2; .....; eia, separated by single spaces. Number eij(0 <=eij <= 1) indicates the probability that an observed character cj originally was sent as the character ci (hence );

  • a lines, specifying character succession probabilities for the a alphabet characters in theorder in which they were presented. The ith line corresponds to the character succession probabilities for cases where the original alphabet character ci was the immediate predecessor and contains:

  • a floating point numbers si1; si2; .... ; sia, separated by single spaces. Number sij indicates the probability that a certain character cj has character ci as immediate predecessor (hence );

  • An integer number w (0 < w < 50), indicating the number of intercepted messages in the local Martian alphabet specified;

  • Then, for each intercepted message:

  • A line containing the intercepted message. These messages are non-empty, case-sensitive and will not exceed 300 characters in length.

Given _oating point numbers never have more than 10 decimal numbers following the separator '.'

Output
For each message in each test case, the output will consist of a single line with a single string: the maximum likelihood original Martian message given the intercepted message.

Sample Input
1
2
a b
0.9 0.1
0.1 0.9
0.8 0.05
0.2 0.95
2
a
ab

Sample Output
a
bb

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥20 怎么在stm32门禁成品上增加记录功能
    • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面
    • ¥50 NT4.0系统 STOP:0X0000007B
    • ¥15 想问一下stata17中这段代码哪里有问题呀
    • ¥15 flink cdc无法实时同步mysql数据
    • ¥100 有人会搭建GPT-J-6B框架吗?有偿
    • ¥15 求差集那个函数有问题,有无佬可以解决
    • ¥15 【提问】基于Invest的水源涵养
    • ¥20 微信网友居然可以通过vx号找到我绑的手机号
    • ¥15 解riccati方程组