A language guesser

classification probabilistic counting hashing numerical precision

Build a language identifier, the one in the article on naive Bayes, by exact rules.

There are n training sentences, each with a known language, and m queries. All texts are already cleaned: they contain only lowercase letters and single spaces, with no spaces at the ends. The trigrams of a text t are all consecutive triples of characters of the string “space + t + space”; a character is a letter or a space (in UTF-8 a letter may take several bytes). A text of length k has exactly k trigrams.

For each language L compute: d_L, how many training sentences it has; c_L(g), how many times trigram g occurred in its sentences; N_L, how many trigrams its sentences have in all. V is how many distinct trigrams there are in all training sentences together. The answer to a query x is the language with the greatest

$$\ln\frac{d_L}{n} + \sum_{g \in x} \ln\frac{c_L(g) + 1}{N_L + V},$$

where the sum runs over all the query’s trigrams with repetitions. If several are greatest, the answer is the code that comes first alphabetically.

The third and fourth tests are Tatoeba sentences in 14 languages, the same as in the article; in the fourth the queries are long, forty sentences in a row each.

Input

The first line holds n and m (1 ≤ n, m ≤ 25,000). Each of the next n lines holds a language code (Latin letters, no spaces), a space and a sentence. Then m lines with queries. Every sentence and every query is non-empty; the sentences have at most 10⁶ characters in all, the queries at most 2·10⁵; there are at most 20 languages.

Output

m lines: the language code for each query.

Examples

Example 1

Input

6 4
ru мама мыла раму
ru кот спит на окне
uk мама мила раму
uk кіт спить на вікні
en mother washed the frame
en the cat sleeps
кот мыл окно
кіт мив вікно
the frame sleeps
zzz

Output

ru
uk
en
ru

Example 2

Input

3 3
aa ab ab ab
bb ba ba ba
bb ba ba
ab
ba
c

Output

aa
bb
bb

Limits

Time · Python: 8000 ms
Time · Go: 2000 ms
Memory: 256 MB
Judging: 8 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

A query from the fourth test is several thousand characters. What order of magnitude does a product of several thousand probabilities, each below a hundredth, have? Will it fit in a double?

2Hint 2

The logarithm is an increasing function: comparing languages by the logarithms of probabilities is the same as by the probabilities. And the logarithm of a product is a sum of logarithms.

3The idea

Training is counting: for each language a dictionary “trigram → how many times”, the total number of trigrams N_L and the number of sentences d_L; a common dictionary of all trigrams gives V. The answer is a sum of logarithms, exactly as in the statement’s formula. The product of probabilities cannot be computed: with an average trigram probability of about 10⁻³, already at a hundred characters it is below the smallest positive double, 4.9·10⁻³²⁴, becomes zero for all languages, and the answer is decided by the order of iteration. In the third test 14 ordinary sentences break this way, the shortest of them 89 characters long.

4Walkthrough

The logarithms of the probabilities of familiar trigrams are conveniently computed once after training: for each language a dictionary “trigram → ln((c + 1)/(N_L + V))” and a separate number for an unfamiliar trigram, ln(1/(N_L + V)). Then the answer to a query of k characters is k dictionary lookups per language and not a single logarithm.

Smoothing gives a funny effect, visible in the first example. The query “zzz” resembles no language: all its trigrams are unfamiliar to all three. Each costs 1/(N_L + V), and it is dearest for the language with the longest texts. The language with the smallest N_L wins, here “ru”. Smoothing hands the unfamiliar to whoever has seen least.

A training line is conveniently cut at the first space: a language code contains no spaces, while a sentence does. In Go trigrams are cut by runes: a Cyrillic or Polish letter takes two bytes in UTF-8.

4+Solution

5Complexity

Training is O(the total length of the sentences), answers O(L · the total length of the queries) for L languages. The memory is one counter for each “language, trigram” pair that occurred.

6Common mistakes

A product instead of a sum of logarithms. It works on short phrases and silently breaks on long ones: all languages get 0.0, and the first alphabetically wins.
Forgetting smoothing. An unfamiliar trigram gives ln 0 = −∞ for a language where it did not occur, and almost every query has one. The answer becomes random.
V over the language’s trigrams only. In the statement V is the common vocabulary of all languages, one for all. If each language takes its own vocabulary, the probabilities shift, and in some tests the answer is different.
Length in bytes. In Python and Go string length and slicing are counted differently: in Go len is bytes. Trigrams “by bytes” cut letters in half.

Algorithms behind it

ML Algorithm Naive Bayes Counts how often each feature occurs in each class and adds up the logarithms of these frequencies. O(N) training, O(L·m) per answer 2 problems DS Data structure Hash table Search, insert and delete by key in O(1) on average: the key turns into the number of an array cell. O(1) on average 2 problems