Anime character stickers consist of a detailed illustration of characters that represents emotions. Generally, message apps let users save received stickers, but in some cases, the task of manual searching for a specific sticker may be frustrating when a large amount of them are stored. In this work, we propose a CNN-based tool for emotion indexing of message stickers. We built a dataset with 12.668 labeled stickers with 3 classes (Sad, Happy and Angry). In experiments, our model achieves 84.01% of global f1-score. Additionally, we describe our proposed tool for emotion indexing of message stickers that has three main functionalities: (1) sticker recommendation function that classifies stickers and recommends the class desired; (2) filter function that takes out the stickers it considers mislabeled; (3) ranking function that orders the labeled stickers.

We describe a structure learning system for unrestricted coreference resolution that explores two key modeling techniques: latent coreference trees and automatic entropy-guided feature induction. The latent tree modeling makes the learning problem computationally feasible because it incorporates a meaningful hidden structure. Additionally, using an automatic feature induction method, we can efficiently build enhanced nonlinear models using linear model learning algorithms. We present empirical results that highlight the contribution of each modeling technique used in the proposed system. Empirical evaluation is performed on the multilingual unrestricted coreference CoNLL-2012 Shared Task datasets, which comprise three languages: Arabic, Chinese and English. We apply the same system to all languages, except for minor adaptations to some language-dependent features such as nested mentions and specific static pronoun lists. A previous version of this system was submitted to the CoNLL-2012 Shared Task closed track, achieving an official score of 58.69, the best among the competitors. The unique enhancement added to the current system version is the inclusion of candidate arcs linking nested mentions for the Chinese language. By including such arcs, the score increases by almost 4.5 points for that language. The current system shows a score of 60.15, which corresponds to a 3.5% error reduction, and is the best performing system for each of the three languages.

Summary form only given. This paper proposes some additional strategies to prefix data compression algorithms to achieve both compressed and ciphered data with the use of a provably secure algorithm. It was shown that the use of homophonic substitution increases the security of the ciphertext and that breaking HSPC2 (homophonic substitution prefix codes with 2 homophones) is an NP-complete problem.

Summary form only given. Prefix codes allow text to be decoded without ambiguity, since this code is a variable-length type where no codeword is a prefix of the other. The problem of improving the decoding speed has received special attention in the data compression community. A scheme that employs length-restricted codes to generate the codewords and table look-up is proposed. In order to reduce the bit manipulation, lexical expansion is introduced to decode more than one symbol in a single decoding step.

Let us consider an ordered vector A[1:n]. If the cost of testing each position is similar, then the standard binary search is the best strategy to search the vector. This is true in both the average and worst case. However, if the costs are nonuniform, then the best strategy is not necessarily the standard binary search. The best algorithm to construct a strategy that minimizes the expected search cost runs in O(n 3 ) time and requires O(n 2 ) space. The same complexities hold for the best algorithm to construct a strategy that minimizes the worst case search cost. Here, we show how to efficiently construct search strategies that are at most at a constant factor from the optimal one. These constructions take linear time and use only linear space. For both the problem of minimizing the expected search cost, under uniform access probabilities, and the problem of minimizing the worst case search cost, we present algorithms that require O(n) space and give a $(2+\epsilon+o(1))$-approximated solution in O(n) time for any fixed value of $\epsilon > 0$.

Word-based Huffman coding has widespread use in information retrieval systems. Besides its compressing power, it also enables the implementation of both indexing and searching schema in the compressed file. In this work, an algorithm that adds securiry to compressed data is proposed. It shows a small loss in coding, decoding and compression performances. The algorithm uses homophonic substitution, canonical Huffman codes and a secret key for enciphering.

The minimum-redundancy prefix code problem is to determine, for a given list W=[/spl omega//sub 1/,..., /spl omega//sub n/] of n positive symbol weights, a list L=[l/sub 1/,...,l/sub n/] of n corresponding integer codeword lengths such that /spl Sigma//sub i=1//sup n/ 2/sup -li//spl les/1 and /spl Sigma//sub i=1//sup n/ /spl omega//sub i/l/sub i/ is minimized. Let us consider the case where W is already sorted. In this case, the output list L can be represented by a list M=[m/sub 1/,..., m/sub H/], where m/sub l/, for l=1,...,H, denotes the multiplicity of the codeword length l in L and H is the length of the greatest codeword. Fortunately, H is proved to be O(min(log(1/p/sub 1/),n)), where p/sub 1/ is the smallest symbol probability, given by /spl omega//sub 1///spl Sigma//sub i=1//sup n/ /spl omega//sub i/. We present the Fast LazyHuff (F-LazyHuff), the Economical LazyHuff (E-LazyHuff), and the Best LazyHuff (B-LazyHuff) algorithms. F-LazyHuff runs in O(n) time but requires O(min(H/sup 2/, n)) additional space. On the other hand, E-LazyHuff runs in O(n+nlog(n/H)) time, requiring only O(H) additional space. Finally, B-LazyHuff asymptotically overcomes, the previous algorithms, requiring only O(n) time and O(H) additional space. Moreover, our three algorithms have the advantage of not writing over the input buffer during code calculation, a feature that is very useful in some applications.

Proposes an algorithm for finding a binary search tree that minimizes the worst-case cost when the access costs are non-uniform and depend on the last accessed key. For this kind of problem, which is commonly found when accessing data stored on magnetic or optical disks, we present an algorithm that finds an optimal search strategy with an expected running time of O(n/sup 2/log n), under some reasonable assumptions on the cost matrix. It is worth mentioning that the best previous algorithm for this problem runs in /spl Theta/(n/sup 3/) time.

Given an alphabet {a, 1 , . . . ,a n } with the corresponding list of weights [w 1 , . . . ,w n ], and a number $L \geq \lceil \log n \rceil $, we introduce the WARM-UP algorithm, a Lagrangian algorithm for constructing suboptimal length restricted prefix codes. Two implementations of the algorithm are proposed. The first one has time complexity $ O(n \log n + n \log \fMax) $, where {\mbox{$\overline{w}$} } is the highest presented weight. The second one runs in O(nL log (n/L)) time. The number of additional bits per symbol generated by WARM-UP when comparing to Huffman encoding is not greater than ${1/ \psi^{L-\lceil \log (n+ \lceil \log n \rceil -L) \rceil-2}}$. Even though the algorithm is approximated it presents an optimal behavior for practical settings. An important feature of the proposed algorithm is its implementation simplicity. The algorithm is basically a selected sequence of Huffman tree constructions for modified weights. The approach gives some new insights on the problem.

Given an alphabet /spl Sigma/={a/sub 1/,...,a/sub n/) and a corresponding list of weights [w/sub 1/,...,w/sub n/], a Huffman code for this alphabet is a prefix code that minimizes the weighted length of a code string, defined to be /spl Sigma//sub i=1//sup n/w/sub i/l/sub i/, where l/sub i/ is the length of the code assigned to a/sub i/. We present ES-ParHuff, a work-efficient PRAM CREW algorithm for constructing Huffman codes. An important feature of the algorithm is its simplicity. This algorithm is a direct parallelization of Huffman's algorithm. ES-ParHuff runs in O(Hloglog(n/H)) time with O(n) work, where H is the length of the longest generated code.

[Summary form only given]. For data communication purposes, the initial parsing required by the static Huffman algorithm represents a big disadvantage. This is because the data must be transmitted on-line. As soon as the symbol arrives at the transmitter, it must be encoded and transmitted to the receiver. In these situations, adaptive Huffman codes have been largely used. This method determines the mapping from symbol alphabet to codewords based upon a running estimate of the alphabet symbol weights. The code is adaptive, just changing to remain optimal for the current estimates. Two methods have been presented in the literature for implementing dynamic Huffman coding. The first one was the FGK algorithm (Knuth, 1985) and the second was the /spl Lambda/ algorithm (Vitter, 1987). Vitter proved that the total number of bits D/sub t/ transmitted by the FGK algorithm for a message with t symbols is bounded below by S/sub t/-n+1, where S/sub t/ is the number of bits required by the static Huffman method and bounded above by 2S/sub t/+t-4n+2. Furthermore, he conjectured that D/sub t/ is bounded above by S/sub t/+O(t). We present an amortized analysis to prove this conjecture by showing that D/sub t//spl les/S/sub t/+2t-2k-[log min(k+1,n)], where k is the number of distinct symbols in the message. We also present an example where D/sub t/=S/sub t/+2t-2k-3[(t-k)/k]-[log(k+1)], showing that the proposed bound is asymptotically tight. These results explain the good performance of FGK observed by some authors through practical experiments.

The minimum redundancy prefix code problem is to determine, for a given list W=[w/sub 1/,...,w/sub n/] of n positive symbol weights, a list L=[l/sub 1/,...,l/sub n/] of n corresponding integer codeword lengths such that /spl Sigma//sub i=1//sup n/2/sup -li//spl les/1 and /spl Sigma//sub i=1//sup n/w/sub i/l/sub i/ is minimized. Let us consider the case where W is already sorted. In this case, the output list L can be represented by a list M=[m/sub 1/,...,m/sub H/], where m(l/sub 1/), for l=1,...,H, denotes the multiplicity of the codeword length l in L and H is the length of the greatest codeword. Fortunately, H is proved to be O(min{log(1/(p/sub 1/)),n}), where p/sub 1/ is the smallest symbol probability, given by w/sub 1///spl Sigma//sub i=1//sup n/w/sub i/. We present the F-LazyHuff and the E-LazyHuff algorithms. F-LazyHuff runs in O(n) time but requires O(min{H/sup 2/,n}) additional space. On the other hand, E-LazyHuff runs in O(nlog(n/H)) time, requiring only O(H) additional space. Finally, since our two algorithms have the advantage of not writing at the input buffer during the code calculation, we discuss some applications where this feature is very useful.

Huffman codes, combined with word-based models, are considered efficient compression schemes for full-text retrieval systems. The decoding rate for these schemes can be substantially improved if the maximum length of the codewords is not greater then the machine word size L. However, if the vocabulary is large, simple methods for generating optimal length-restricted codes are either too slow or require a significantly large amount of memory. We present an in-place, simple and fast implementation for the BRCI (Build, Remove, Condense and Insert) algorithm, an approximative method for length-restricted coding. It overwrites a sorted input list of n weights with the corresponding codeword lengths in O(n) time. In addition, the worst-case compression loss introduced by BRCI codes with respect to unrestricted Huffman codes is proved to be negligible for all practical values of both L and n.

The Belief Function Model for automatic indexing and ranking of documents with respect to a given user query is proposed. The model is based on a controlled vocabulary, like a thesaurus, and on term frequencies in each document. Descriptors in this vocabulary are terms chosen from among their synonyms to be used as index terms. A descriptor can have a subset of broader descriptors, a subset of narrower descriptors, and a subset of related descriptors. Thus, descriptors are not mutually exclusive and naive probabilistic models are inadequate for handling them. However, a belief function can still be defined over a thesaurus of descriptors. Belief functions over the descriptors can represent a document or a user query. We can compute the agreement between a document belief function and a query belief function. Therefore, we propose that the set of documents be ranked according to their agreement with the given user query. We show that the Belief Function Model is wider in scope than the Standard Vector Space Model. © 1993 John Wiley & Sons, Inc.