A filter that learns as it goes

classification probabilistic counting streaming hashing

A service identifies the language of messages by naive Bayes and learns on the fly: moderators add labelled sentences and remove wrongly labelled ones. Between edits queries arrive, and each must be answered from the sentences present at that moment.

The model’s rules are the same as in the problem “A language identifier”. All texts are lowercase letters and single spaces. The trigrams of a text t are triples of consecutive characters of the string “space + t + space”. Over the sentences present now: d_L is how many language L has, n how many in all, c_L(g) how many times trigram g occurs in the sentences of language L, N_L how many trigrams there are in them in all, V how many distinct trigrams there are in all sentences together. The answer to a query x is the language with d_L > 0 and the greatest

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

If several are greatest, the code that comes first alphabetically. If there are no sentences at all, the answer is -.

The third and fourth tests are built on the Tatoeba sentences from the article.

Input

The first line holds q, the number of operations (1 ≤ q ≤ 2·10⁵). Then q lines, each one of the operations:

+ L text: add a sentence in language L (a code of Latin letters); sentences are numbered from one in the order of addition;
- k: remove sentence number k; it was added and not yet removed;
? text: a query.

Texts are non-empty. All additions have at most 10⁶ characters in all, all queries at most 2·10⁵; there are at most 20 languages.

Output

For each query, a line with the language code or -.

Examples

Example 1

Input

11
? кот
+ ru кот спит
+ uk кіт спить
+ ru кот ест
? кіт
? кот
- 3
- 1
? кот
+ en the cat
? the cat

Output

-
uk
ru
uk
en

Example 2

Input

9
+ aa ab ab
+ bb ba ba
? ab
- 1
? ab
- 2
? ab
+ aa ab
? ba

Output

aa
bb
-
aa

Limits

Time · Python: 8000 ms
Time · Go: 2000 ms
Memory: 256 MB
Judging: 7 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

The solution “for each query compute the model anew from all sentences” is correct, but in the third test it is 1400 times over 21 thousand sentences. What in the counting changes when one sentence is added or removed?

2Hint 2

All quantities in the formula are sums over sentences. Adding a sentence adds its contribution, removing subtracts it. Hardest is V: when does it grow and when does it shrink?

3The idea

A naive Bayes model is counters, and counters can not only grow but also shrink. Keep for each language the dictionary c_L, the sum N_L and the number of sentences d_L; for each sentence, its language and trigrams, so as to subtract them later. Adding and removing cost as much as the number of characters in the sentence.

The number of distinct trigrams V cannot be got from per-language counters: a trigram may disappear from one language and remain in another. One more dictionary is needed: how many times each trigram occurs in all sentences together. V is the number of its keys with a non-zero value: a trigram whose counter reaches zero is removed from the dictionary, and V decreases.

4Walkthrough

For a query of k characters: for each language with d_L > 0, the sum of ln(c_L(g) + 1) over the query’s trigrams, minus k·ln(N_L + V), plus ln(d_L/n). The logarithms of the counters change along with the counters, so they cannot be stored in advance, but ln(c + 1) depends only on the integer c: a table of ln 1, ln 2, ln 3, … is computed once and grows as needed. Then a query costs k dictionary lookups per language and no logarithm in the loop.

The fifth test checks V specifically. At first there are two small languages, then a third is added, three hundred sentences of letters absent from the first two, and V grows by thousands. The denominator N_L + V grows relatively more for the language with short texts than for the one with long texts, and the answer to the same query changes. The third language is removed, and the answer must come back. If V only grows, it does not.

This is how trainable spam filters work: the “this is spam” button adds the message’s words to the spam counters, and “this is not spam” moves them back.

4+Solution

5Complexity

O(the length of the sentence) per addition and removal, O(L·the length of the query) per query; the memory is the counters plus the trigrams of the sentences themselves, O(the total length).

6Common mistakes

Recomputing everything for each query. Correct and slow: the time is the total length of all sentences times the number of queries.
V only grows. A counter of “ever seen” instead of “present now”. The fifth test.
A language without sentences. When all of a language’s sentences have been removed, it does not take part: its ln(d_L/n) = −∞. The first example.

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