Thierry Paquet

Laurent Heutte

Guillaume Koch

Clément Chatelain
email: clement.chatelain@insa-rouen.fr

A Categorization System for Handwritten Documents

Keywords: Document Categorization, Handwriting Recognition, Keyword Extraction, Shallow language model

This paper presents a complete system able to categorize handwritten documents, i.e. to classify documents according to their topic. The categorization approach is based on the detection of some discriminative keywords prior to the use of the well known tf-idf representation for document categorization. Two keyword extraction strategies are explored. The first one proceeds to the recognition of the whole document. However, the performance of this strategy strongly decreases when the lexicon size increases. The second strategy only extracts the discriminative keywords in the handwritten documents. This information extraction strategy relies on the integration of a rejection model (or anti-lexicon model) in the recognition system. Experiments have been carried out on an unconstrained handwritten document database coming from an industrial application concerning the processing of incoming mails. Results show that the discriminative keyword extraction system leads to better recall/precision tradeoffs than the full recognition strategy. The keyword extraction strategy also outperforms the full recognition strategy for the categorization task.

Introduction

These last years, the number of paper documents generated by administrative and economic activities has exploded. To facilitate the storage, processing and transferring of these documents, Electronic Document Management (EDM) systems have been developed, where paper documents are scanned, stored and transferred electronically. In this context, the automatic reading of the document image content has seen a fast expansion. We have thereby observed the development of applications for processing targeted, specific problems, such as the automatic reading of forms, postal addresses or bank checks [Plamondon 00, Koerich 05, Lorette 07]. Besides these specific applications, the automatic processing of handwritten documents remains a difficult and open problem: there is no system able to recognize an entire page of unconstrained cursive handwriting without using prior knowledge. This can be mainly explained by the huge variability in the writing style. In the literature, some recent works [Zimmermann 06, Vinciarelli 04, Bertolami 08] have addressed the processing of lightly constrained handwritten documents such as free mails. Among these projects, some address the full document recognition, whereas others are more oriented towards the rejection of misrecognized hypotheses or out of vocabulary words [Zimmermann 04,Koerich 05]. Some other projects e.g. [Cao 07] aim at indexing handwritten documents by their textual content for retrieval purposes. One alternative, called keyword spotting, has been proposed in order to provide indexation facilities of a collection of handwritten documents [Manmatha 97, Rath 07, Adamek 07]. In this case, word images are clustered using some appropriate features and elastic matching, thus avoiding the diffi-cult task of recognition. Although interesting 1 , these studies are not suitable for omni-writer mail documents since i) they are based on a word image matching process, assuming word images boundaries are known; and ii) these collections exhibit some stability in the writing styles of the various writers encountered in the collection.

To the best of our knowledge, only one specific study presented in [Vinciarelli 05] has been devoted to the categorization of handwritten documents. This pioneer study has been carried out using a mono-writer corpus built specifically. The proposed approach uses the word outputs of a mono-writer recognition system to feed a word vector representation optimized for the categorization task at end. The categorization stage is performed using a classifier such as SVM, or KNN. In this paper, we address the categorization task of omni-writer handwritten documents such as incoming mail documents. Thousands of such documents are received day by day in customer services of companies for various claims (address change, change of contract, contract cancellation, etc.). One example of such a document is illustrated on Figure 1 (two other documents can be found in appendix 6. Today, paper documents are scanned and then digitally sent to some remote service in charge of mail topic identification. The mail is finally sent to the appropriate department of the company. Automating this process requires the machine to read omni-writer handwritten documents for detecting its topic. This second task is known as categorization in the field of Information Retrieval [Aas 99, Baeza-Yates 99] and for document images [Doermann 98]. This task aims at classifying documents according to their subject matter. It is based on the detection of some specific keywords that are selected for their discriminative power among the various classes of documents. As opposed to keyword spotting where keywords are determined in an unsupervised manner, here keywords must be determined in a supervised manner considering the category (label) associated to each document. While the major difficulty in the categorization of electronic documents lies on the selection of these relevant keywords, the categorization task of handwritten documents also requires the system to detect these keywords in the document image, whatever the handwriting style. This is an additional difficulty that has not received very much attention until now except in [Vinciarelli 05] with a limitation to a single writer. This paper has two major contributions. First it addresses the question of omni-writer handwritten docu- ment categorization. The second contribution lies in the use of a shallow handwritten keywords extraction system on real-world documents. The three main processing stages of the proposed system are: layout analysis, keyword extraction and categorization (see figure 2). This article is organized as follows. Section 2 is dedicated to the definition of the document categorization task. Section 3 presents the recognition system of omni-writer handwritten words, based on a lexicon directed analytical approach with an explicit segmentation. The keyword extraction task is studied in section 4, where two statistical models of handwritten lines are proposed: the first one is based on a full recognition (FR) strategy, whereas the second one is based on a shallow language model dedicated to keyword extraction (KE). Section 5 is devoted to the experimental results for the incoming handwritten mail categorization task. Conclusion and future works are drawn in section 6.

Documents

Layout Analysis (line segmentation)

Extraction of keyword (FR or KE strategy)

Categorization

List of related topics

Lines of text

Word hypotheses

Fig. 2 Flowchart of the proposed system.

Categorization of electronic transcriptions of documents

This section is dedicated to the definition of the categorization task of textual documents, disregarding the writing recognition system performance and the difficulty in extracting textual information in the image of a handwritten document. In the first part, we review the concepts used in the field of electronic document analysis to describe and categorize these documents. In the second part, the retained approach is evaluated and compared to the literature on the Reuters 21578 reference corpus, then on the specific categorization task of incoming mail that we consider throughout this study.

Categorization of electronic documents

A document categorization system aims at detecting the topic addressed in the document through the examination of its textual information. It is a supervised classification task where each class is considered as a topic. To achieve such a task, one must first define a text characterization space (feature space) before defining a decision rule (of the classification system). This task has been widely studied in the literature for processing electronic documents. We can refer to [Sebastiani 02, Baeza-Yates 99] for a review of the possible techniques. One of the most effective approaches to characterize electronic documents is based on a vector model of documents known as "bag of words". This description is generally coupled with learning techniques such as neural networks. Like all pattern recognition systems, a document categorization system consists in three main sequential steps following the traditional diagram on Fig. 3. In the following paragraphs, we describe each step.

Preprocessing

The first step consists in eliminating all undesired characters. We have chosen to accept only alphabetical characters and to eliminate all the others. Following this, empty words are filtered. This is performed using a list of words considered as the most frequent empty words (571 empty words for English and 463 for French). Finally, stemming (suffix elimination) is traditionally carried out using Porter's algorithm [Porter 80]. The French version of the algorithm differs from the English version only by the set of rules used. We chose to implement the Tf.Idf feature, which is easy to compute and provides very good results in practice [Aas 99, Baeza-Yates 99, Salton 88]. The weight w ij assigned to the term t i of the document d j is defined by the following expression:

w i,j = tf i,j × idf i = freq i,j max k freq k,j × log N n i
Where:

-N is the number of documents in the database n i is the number of documents in which the term t i appears freq i,j is the number of occurrences of the term t i in the document d j Each document is represented by a vector of weights w i,j . The dictionary to refer to for the construction of the feature vector is determined during the learning stage of the system by performing feature selection.

Feature selection

It is generally necessary to reduce the size of the feature space because preprocessing produces a high dimensional description that consists in several thousands of words. Three common approaches are reported in the Information Retrieval domain [Yang 97]. They are based on frequency threshold, information gain and the χ 2 measure. For comparison purpose with other studies [Joachims 98] we choose to use the χ 2 measure.

Let the categories of the K documents be denoted c 1 , c 2 , . . . , c K ; the probability P (c i ) of category c i is estimated as the ratio of documents in the database that belong to the class c i and P (t) is estimated as the ratio of documents that contain term t. It follows that P (c i , t) can be computed by the fraction of documents of the class c i containing the term t. Similarly P (c i , t) is the fraction of documents of the class c i that do not contain the term t. The χ 2 measure is the correlation between a term t and a category c, computed as follows:

χ 2 (t, c i ) = N × P (t, c i )P (t, c i ) -P (t, c i )P (t, c i ) 2 P (c i )P (c i )P (t)P (t)
Usually, two scores are used for feature selection based on this measure, they are:

χ 2 mean (t) = K i=1 P (c i )χ 2 (t, c i ) χ 2 max (t) = max K i=1 χ 2 (t, c i )
The final list of retained terms is composed of those with the N best scores.

Classification

The classification of a document in a topic can be performed using different classification methods. K nearest neighbors, neural networks, SVM, are some of the most popular approaches [Sebastiani 02, Joachims 98, Vinciarelli 05]. In this study, we retained a K nearest neighbor classifier for its simplicity and performance. We used the classical "cosine" similarity measure that is the most popular metric defined by the following relation:

sim(q, d j ) = - → d j - → q |d j | × |q| = i w i,j × w i,q i w 2 i,j × i w 2 i,q
Where d j and q stand for the vector representations of respectively the document d on the learning database, and the query document q to be categorized.

Evaluation

The Reuters 21 578 corpus [Lewis 92] is used to validate the methodology by comparing the performance with those reported in the literature. Then it was possible to evaluate the incoming mail document categorization task using the electronic transcriptions of each document with the same system. This experimentation allows the determination of the optimal performance that we expect to achieve on the handwritten documents.

Reuters 21578 corpus

This widely used corpus is a set of 21 578 articles annotated according to their topic, among nearly 120 topics. The topic distribution is unbalanced: some topics are represented by over 3 700 articles, while some others are represented by less than 50. A protocol (modApte) describes how to split the database into a learning set and an evaluation set. This gives 7 063 documents in the learning set and 2 742 in the evaluation set. After having carried out the preprocessing of the learning database, a vocabulary of 15 453 terms is obtained.

The various parameters of the system are first optimized using the learning set. They are reported in Table 1 and compared with the values reported in [Joachims 98]. We observe a slight difference between the parameter values, which is certainly due to the characterfiltering step. Table 2 presents the results obtained with our categorization system as well as those obtained by [Joachims 98]. For each of the ten most frequent topics, the Break-Even-Point (BEP) is reported. This value is obtained when recall equals precision. Let us recall that recall is similar to a detection rate, and precision is similar to a pertinence rate. More formally, one can define recall and precision as:

recall = tp tp + f n and precision = tp tp + f p
where tp, f p and f n stand respectively for true positive, false positive and false negative rates. The micro average measure corresponds to the computation of the global BEP. This unique measure allows summarizing the system performance by one single measure. The results obtained are very similar to those presented in [Joachims 98

Incoming mail corpus

Performance of the categorization system is now determined on the incoming mail corpus. We use the ground truth of a handwritten mail corpus made of the electronic transcription of each handwritten document. These mails are classified into 43 topics: "standard cancellation" (A500), "changing of bank address" (A020), etc. The topic A500 ("standard cancellation") contains over 300 documents whereas topic A020 ("changing of bank address") contains only 30 documents. Note that the annotation of topics comes from a real-world database of handwritten mails addressed to a french company. The learning set contains two thirds of the documents of each category and the evaluation set contains the remaining third.

The optimal parameters of the system are as follows. The dictionary is composed of nearly 7000 terms. The lexicon is reduced to 980 words by removing the words that appear in less than five documents and using the χ 2 measure for term selection. This leads to retain 450 discriminative terms after stemming. Classification is carried out using a 5-nearest-neighbor classifier. Table 3 reports the results obtained on the 5 most frequent classes. The micro-average is computed using all the categories, which allows a global evaluation of the system. It appears that some topics are more difficult to model than others. The "information requests" (A240 and A255) are not as well classified as "cancellations" (A500 and A502). This can be due to more variability in this class. In fact, the two "cancellation" topics are very well defined whereas the "information requests" are more heterogeneous. With an equivalent amount of samples, it is not surprising that topic A502 is better recognized than topic A240. Finally, these results highlight the optimal categorization performance that can be expected on this particular corpus assuming that perfect recognition of the informative handwritten keywords can be achieved. The following section will now consider the adaptation of this categorization system for handwritten documents. Table 3 Categorization results obtained by the annotation on the basis of incoming handwritten mail.

Recognition of handwritten words

Despite the success of some very specific industrial applications such as the reading of postal addresses or bank checks, off-line handwriting recognition remains an open problem. From a methodological point of view, one can distinguish two major approaches in the literature [Pla-mondon00, Wang00, Koerich03, Lorette07]. The lexicon directed approaches, where the recognition process takes its decision at the lexical level only by discriminating the words that belong to the lexicon. The lexicon free approaches, where the decision comes at the character level. In this case the lexicon is used in the post-processing phase to correct the character recognition errors. Beyond the lexicon aspects, we can distinguish two main categories. The first one refers to the holistic approaches that consider the word as an indivisible entity. Words are recognized using global features extracted on the whole shape of the word. This kind of approach depends on a static, and often small lexicon. Note that word spotting approaches generally fall into this category. The second category of approaches refers to the analytic methods, where words are recognized through their constitutive characters [Kim97, ElYacoubi99, Wang00, Vinciarelli00, Ro-driguez08, Graves09]. Within this framework it is possible to model any word and thus any lexicon during the recognition phase. Among the analytic approaches, we can then distinguish the implicit and explicit segmentation approaches. Explicit segmentation methods introduce a segmentation stage which proposes several character segmentation hypotheses. These hypotheses are then validated by the recognition stage. Inversely, implicit segmentation approaches do not introduce any complex (adhoc) segmentation stage and they let the recognition process find the best segmentation into characters. Most of the recent approaches fall into this last category of methods by relying on the Hidden Markov Models [Grosicki09], including Vinciarelli's work for noisy text categorization. This success is mainly due to the relative ease of implementation of the approach, as opposed to the explicit segmentation, even if one major well-known drawback of Hidden Markov Models is their low capacity to discriminate between classes. In fact, Hidden Markov Models are generative models which are trained class by class by maximizing the likelihood of each training dataset (one per class). Some recent approaches have therefore propose the use of recurrent networks [Graves09] that use discriminative training to overcome this drawback, and this has proven to be efficient.

In this work, the handwritten word recognizer uses a lexicon driven analytical approach with explicit segmentation derived from [Koch04] with discriminative training of character models. Considering the state of the art in handwriting recognition the proposed approach combines the strength of discriminative training with a limitation due to the segmentation stage. We briefly present the word recognition system, and refer to the aforementionned paper for more implementation details.

A first preprocessing step is carried out on the binary word images and allows the reduction of writing variability using slant and skew corrections inspired by [Kimura94]. The segmentation step splits the images into informative zones known as graphemes. The graphemes, or groups of graphemes, are then submitted to a character recognizer. Finally, the word hypotheses are built by the exploration of the segmentation lattice.

The segmentation stage generates hypotheses of segmentation points through the analysis of the word contour: each local minimum and maximum of the upper contour of the word is considered as a potential segmentation point [Nosary 02].

For each word, a segmentation lattice is built (see Figure 4), containing elementary graphemes at level 1, and all possible aggregations of n adjacent elementary graphemes at level n. The segmentation hypotheses of the first level are likely to be oversegmented, whereas hypotheses of the last levels are likely to be undersegmented. The segmentation statistics demonstrate that the distribution of the number of graphemes is strongly unbalanced depending on the character classes. For example, character 'c' is frequently segmented into only one grapheme, whereas character 'm' is frequently segmented into 5 graphemes. We also observed that the maximum number of levels needed was 7 to prevent from under segmentation. In order to benefit from this a priori knowledge, we have chosen to model the segmentation process by a duration statistical model, presented in the following paragraph. In order to find the best segmentation path in the lattice, each aggregation hypothesis is submitted to a character recognizer which aims at providing the a posteriori probability of the character classes {a, b, . . . , z}.

To estimate these probabilities, several information sources are combined according to the diagram given on Figure 5.

Two classifiers are built to exploit complementary information on each grapheme, at each level. On one hand structural/statistical information such as curvatures, occlusions, horizontal and vertical strokes are coded into a 117 feature set according to [Heutte 98]. On the other hand, directional information on the contours is coded into a 128 feature set according to [ A statistical duration model then combines the segmentation information with the character hypothesis. The character distribution over the different segmentation levels is exploited during the recognition step. Let N s be the number of segments of a character, the term P (L i /N s ) is estimated by counting the number of character samples on the learning database that occur on a particular number of segments N s .

The final word recognition stage is performed through the exploration of the recognition lattice using dynamic programming. The introduction of lexical constraints at this stage reduces the number of solutions during the exploration. The lexicon is modeled by an automaton λ with N character states, such as the one shown in Figure 6.a . The complexity of this algorithm is of order (max-levels × N ) 2 × T = (7 × N ) 2 × T , where T is the length of the lattice. As the complexity is a function of N 2 , a reduction of the number of states will have a large influence on the computation time. This can be done by adopting a tree-structured representation of the lexicon. For example, the model presented in Figure 6.a can be reduced to the one in Figure 6.b. In this example, the number of states can be reduced from 41 to 27. The complexity is then reduced by a factor of 2.3 whereas the number of states is only reduced by a factor of 1.5.

Evaluation

The word recognition engine is evaluated using a learning database of 4600 words and a test database of 500 words, all coming from real incoming handwritten mail documents. Table 4 gives the word recognition rates for MLP-128, MLP-117 and the average combination of the two MLPs. Results are presented with and without considering the character duration model, and for different lexicon sizes N by randomly selecting N -1 words among a 1400 word lexicon (complete lexicon of the word database). We can observe that whatever the size of the lexicon, the combination of the two MLPs improves the word recognition performance sig- nificantly. These results also bring out the relevance of the character duration model. Figures 7 and8 show some examples of properly recognized words and misrecognized words from different writers. Our results appear to be fairly lower than state-of-the-art approaches such as [Kim97, Koerich05, Zimmermann06], but our real-world database exhibits multiple significant degradations due to: (i) low resolution (200 dpi) (ii) industrial digitizing stage (iii) strongly heterogeneous writing styles (see examples of Figure 7). Let us also notice that our system was probably trained using less data than in some other studies.

Keyword extraction in handwritten documents

As presented in section 2, the categorization of handwritten documents is based on a word vector model of discriminative keywords. We must therefore highlight that the main objective of the handwritten word recognition system is to detect and recognize these relevant keywords. As opposed to the full recognition of handwritten content, some studies focus on the detection of keywords that are useful in indexation or categorization tasks. The basic idea lies in the fact that a major part of the information contained in a document is useless to capture its overall meaning, e.g., empty or stop words. This strategy known as keyword spotting has been first proposed for printed documents. It became popular in the handwriting recognition community for querying databases of digitized historical documents, for instance the Georges Washington's manuscripts [Rath07]. Two different approaches can be distinguished depending on the nature of the documents considered. On the one hand, template-based methods try to match image queries with pre-labeled segmented word image templates [Gatos05,Terasawa09, Belongie02. This kind of approach is restricted to querying mono-writer document databases. On the other hand, recognition-based approaches allow to work on more heterogeneous data (from different writers for instance).

The recognition process involves a classification stage either as a holistic process [VanDerZant08,Rodriguez09] or as an analytical process involving character models [Rodriguez08,Koerich04]. A post-processing stage working on the recognition scores is generally needed to reject false hypotheses. Obviously, this second approach is also subject to limitations : it is assumed that word boundaries are known (line segmentation issues are avoided) and rejection is often carried out using a simple threshold on normalized scores.

In this article, we introduce a general line model for the extraction of keywords. This analytical model take account of keywords and out of keywords vocabulary. It also introduces an space model between words that allow line segmentation into words. This general model can be parametrized by any keyword lexicon and does not require any specific training when using a new keyword lexicon. This stochastic line model allows keyword detection, line segmentation and out of vocabulary word detection in a combined manner by using a dynamic programming decoding algorithm of each line of text. Two statistical models of handwritten lines are proposed in order to proceed to keyword spotting. Both of them rely on dynamic programming and integrate an inter-word space model within the line. They differ in the lexicon they use. The first one corresponds to the full recognition (FR) of the documents using a large lexicon (several thousands of words). The second one is based on a shallow language model dedicated to keyword extraction (KE). It is composed of a lexicon of relevant keywords and a stochastic bi-gram model of characters that accounts for irrelevant words. The two recognition strategies (FR and KE) are evaluated for their capacity to extract the relevant keywords in the handwritten documents as defined in section 2.

Full Recognition Model (FR)

Following the notations of section 3, we consider that each text line is composed of an observation lattice. The recognition of a text line consists in finding the best path in this lattice using dynamic programming and verifying the constraints of the considered model of the line. In this FR strategy, we consider that a line of text only contains words from the lexicon that are separated by an inter-word space. The line model is depicted in Figure 9 where state BL refers to the beginning of the line, state EL refers to the end of the line and state IW refers to the inter-word space state.

BL

Lexicon IW EL Fig. 9 Line model of the Full Recognition (FR) strategy.

We must highlight that the observation lattice contains the hypotheses of the 7 levels of segmentation as described in section 3, but also the observations characterizing spaces between connected components. The joint probability of the observation lattice and the word sequence can be decomposed according to the following relation:

P (O, Q * ) = N i=1 P (O * Mi /M i )P (o * MiMi+1 /IW ) × N i=2 P (M i /M i-1 )
Where:

o * MiMi+1 is the observation attached to space between word i and word j in the optimal path -O * Mi is the observation associated to word i in the optimal path -N is the number of words in the optimal match -Q * is the optimal state sequence -M i is the model of the i th word -IW is the inter word space This expression can further be decomposed by rewriting the word likelihood of the optimal path. It finally yields:

P (O, Q * ) = P o * M i M i+1 /IW Nm i=2 P (M i /M i-1 ) × Nm i=1 length(M i ) j=1 P o * i,j /q * i,j P o * i,j,j-1 /EL P q * i,j /q * i,j-1
Where q * i,j is the j th character in the word i o * i,j is the observation associated to the j th character of word i o * i,j,j-1 is the observation corresponding to the space between character j and character j -1. -EL is the state representing an inter-character space in a word

We must notice that in the lexicon directed strategy, the character transition probability is equal to 1 if the transition belongs to the automaton (the transition belongs to a word of the lexicon), and to 0 otherwise. Furthermore, if we do not use a language model, the equation simply reduces to:

P (O, Q * ) = P o * M i M i+1 /IW Nm i=2 P (M i /M i-1 ) × Nm i=1 length(M i ) j=1 P o * i,j /q * i,j P o * i,j,j-1 /EL
This probability is computed using dynamic programming in the same way as for the recognition of isolated words.

Keyword Extraction Model (KE)

The main objective of this second model is to limit the size of the vocabulary to the relevant keywords only. We expect to benefit from the reduced size of the keyword vocabulary so as to improve the recognition performance of the relevant information. We must however build a model of the irrelevant information so as to consider the set of all the other words that are irrelevant for the categorization task. This later model will act as a rejection model for the recognition system. It is a model of irrelevant words or out of keyword vocabulary words. Similar approaches have been proposed for speech processing [Yazgan 04]. We can consider that a line of text is a sequence of relevant and irrelevant words. These words are naturally separated by a space. Figure 10 The irrelevant lexicon is composed of many words because it is potentially made of all the words of the language except the relevant keywords. We have chosen to use a character bi-gram stochastic model. More precisely, this model is composed of 28 states among which 26 states correspond to characters. In addition, an initial and a final Non-Lexicon states are considered, modelling the beginning and the end of out of vocabulary words. Probabilities of bi-grams of characters can either be all equal, or determined on a set of examples. We can now clarify the expression of the joint probability of the observation lattice and the best word sequence conforming to this KE model. At first, let us consider the observation sequence that corresponds to the i th word in the observation sequence. Its likelihood is expressed in two different ways depending on whether word i is part of the relevant lexicon or not.

P (O * Mi /M i ) = max P (O * Mi /M i ) ∈ Relevant lexicon P (O * Mi /M i ) ∈ Irrelevant lexicon
Let us define:

β = P (M i ∈ Irrelevant lexicon)
Then the joint probability of the best observation sequence on a whole line is written as follows:

P (O, Q * ) = Nm i=1 max (1 -β)× P (O * M i /M i ∈ Relevant lexicon) β× P (O * M i /M i ∈ Irrelevant lexicon) ×P (o * MiMi+1 /IW )
Once again, this quantity can be computed using dynamic programming on each of the observation lattices associated to each line of text. When β = 0 one can notice that the model implements the Full Recognition strategy. When β = 1, the model implements a lexicon free recognition strategy. The whole KE model can be viewed as a model that puts in parallel models of the relevant keyword lexicon with the out of vocabulary word model which simply acts as a rejection model. The implementation of these two keyword extraction strategies (FR and KE) is depicted in the next subsection. Experimental results are presented in section 5.

Description of the keyword extraction system

At first, layout analysis allows the segmentation of the document into lines of text. Once layout analysis has been carried out, additional preprocessing steps help the recognition process (slant correction, diacritic filtering). Derived from these pre-processing steps, each line of text is represented by an observation lattice. All these pre-processing steps have been described in detail in section 3 and they are directly applied to the set of detected lines. In the following paragraph we give some details concerning layout analysis and the detection of possible word separators within lines of text.

Layout analysis

The line segmentation process is an important and difficult task, mainly due to variable skew angle along the document or even along a text line, and adjacent text lines. The recent handwriting segmentation contest [Gatos2009] has shown that many strategies perform well, such as run length analysis [Shi09], function minimization exploiting the distance between the separators and the local foreground density [Stafylakis08] or connected component bounding box analysis [Yin08]. We have chosen a connected component based approach, which has shown to perform well on real-world, free layout documents [Chatelain 06]. We now briefly describe this approach.

Lines of text are formed by successive merging of connected components based on a distance criterion. It is implemented in three steps after the detection of connected components (Figure 11). The first step detects alignment seeds. Then each alignment seed is extended to its nearest connected component using the following pixel distance:

d(a, b) = (x a -x b ) 2 × α(y a -y b ) 2
Where a and b are connected components and x and y are their centers of gravity. The parameter α allows to weight the horizontal (α > 1) or vertical direction (α < 1). The value of α has been experimentally fixed to 20. To build these alignments, only the most representative components (of sufficient size) are considered.

Segmentation results are reported in Table 5. A line is considered as being well segmented if all its components are grouped together. Three types of errors are counted. Over-segmentation is counted if the line is segmented into several alignments. We can observe that nearly 80% of the lines are properly segmented. Concerning segmentation failure (over and under segmentation), only one connected component (therefore one or two words) is often involved. In this situation, the other words of that line can still be recognized. We estimate that nearly 90 to 95% of the document words can be processed following this line segmentation process. The performance of document segmentation into lines of text is far from being perfect but seems sufficient to apply the two keyword extraction strategies that we have presented above.

Estimating inter-word and inter-character space probabilities

Spaces between two consecutive components of a line are assigned to the corresponding class (IW or IC). The measure is carried out using minimal Euclidean distance [Seni 94]. To eliminate the variability between different writers, the distance is normalized in reference to the median value of the width of the elementary graphemes. Two normalized distributions are obtained. Finally, the probability of an Inter Word space having a distance d is given by the equation below:

P (IW/d) = #IW (d) #IW (d) + #IC(d)
Where #IW (d) (respectively #IC(d)) matches the proportion of Inter-Word spaces (similarly Inter-Character spaces) that have a distance equal to d. We determine the same probability of inter-character spaces:

P (IC/d) = 1 -P (IW/d)
The distributions of these two probabilities are represented on Figure 12. These two a posteriori probabilities are considered as likelihood scores in the observation lattice. The integration of these observations is done with straightforward modifications of the observation lattice.

Cumulative probability IW and IC size distributions (in pixels) Fig. 12 Distribution of the inter-word space (IW) probability and the inter-character (IC) space versus the distance between components.

Experimental Results

In this section we present the keyword extraction system performance for both FR and KE strategies.

A document database for evaluating FR and KE strategies

A database of Incoming Handwritten Mails has been built for this purpose. A set of 1100 real documents have been scanned with a resolution of 200dpi, where the words of text bodies have been manually labeled. Of course, the word database used for training and testing the word recognizer has been design using a different set of documents than the document database. The 1100 documents are made of over 46000 word samples that compose a lexicon of 3700 distinct words. As this is an industrial database coming from real customers, it can not be diffused and personnal information have been hidden for this article. Exemple of documents can be found in appendix 6. One can note the presence of noise due to imperfect numerization and binarization. This noise has been deleted using standard and simple operations such as filtering of too small connected component and mathematical morphology.

Performance evaluation of the keyword extraction system

Let us remind that the first strategy for keyword extraction consists in carrying out the full document recognition (Full Recognition) then to retrieve keywords on the basis of the recognition results. The capacity of the system to detect keywords is directly related to the performance of the text recognition system that works with a large lexicon. For this experimentation, the entire lexicon composed of the 3700 different entries of the test database is used. In order to depict the recall precision curve, a variable threshold is applied on the recognition scores of the word recognition hypotheses. The score of the words is calculated by averaging the output score of the neural network classifier, and is normalised according to the length of the word.

The second strategy operates with a lexicon of relevant keywords and uses the particular strategy developed in section 4.1. This lexicon has a reduced size which can vary from 46 words up to 980 words. The irrelevant lexicon is modeled in our experimentation using a uniform ergodic stochastic model where parameter β varies between 0.01 up to 0.99 so that the whole recall precision curve can be explored. In the various experimentations, the relevant lexicon used is defined as "KE n" where the value n is the number of words in the keyword lexicon. Figure 5.2 illustrates the results obtained by keyword extraction on an incoming mail.

Figure 14 presents the set of results for the two strategies examined. These results illustrate the superiority of the keyword extraction strategy as compared to the full recognition strategy and whatever the keyword lexicon. The FR strategy provides 22% recall for 50% precision while working with a 3700 word lexicon. On the other hand, with a 295 keyword lexicon (lexicon "KE 295") the performance is 36% recall with 70% precision. We can see that the performance is rather stable when increasing the lexicon size from 46 to 295 keywords (with the "KE 46", "KE 96", "KE 165" and "KE 295" lexicons). These various lexicon sizes correspond respectively to 10,25,50 and 100 radicals. These results clearly highlight the contribution of the relevant keyword extraction strategy that allows focusing the recognition system only on the keyword lexicon while modeling irrelevant information by an ergodic character model.

Categorization of handwritten documents

In this section we analyze the interaction of the two systems (keyword extraction and document categorization) in order to optimize the overall performance of the handwritten document categorization. First we compare categorization performance for both FR and KE strategies. Then the role of the keyword lexicon is analyzed in depth regarding both the keyword recognition performance and the categorization performance.

Table 6 presents the categorization results obtained on the database of incoming handwritten mails following keyword extraction (KE 980). A global "BEP" of 62.3% is obtained despite relatively low performance of the keyword extraction system (27% recall and 57% precision). Compared to the ideal categorization system (TRANS) using the ground truthed document transcription, categorization performance only degrades by 14 points. The FR strategy gives an overall BEP of 46.4% which is very low compared to the 62.3% BEP obtained with the KE strategy.

Figure 15 allows a finer analysis of the results. Figure 13 clearly demonstrates that the KE strategy outperforms the FR strategy when considering the categorization task. The breakeven point only decreases by 14 points when using the KE strategy while the FR strategy loses 30 points. These results confirm the robustness of the categorization system with respect to keyword extraction errors. They also highlight the relevance of the proposed keyword extraction as opposed to the Full Recognition strategy. In the following sec- tion, we study the influence of the lexicon size on the categorization performance.

Control of the lexicon size

As seen in section 5.2, the performance of the keyword extraction engine improves when the number of words in the lexicon decreases. Thus, a trade-off must be found between a reduction of categorization performance caused by an important lexicon reduction, and a keyword extraction performance gain. To find this trade-off, we can analyze the performance of the system on the ground truthed transcription database (TRANS) when the size of the lexicon decreases. To achieve this, we have used the categorization system configuration presented in section 2.2.2 (selection of 450 terms by the "Information Gain" measure, description of documents by the Td.Idf measure, classification carried out with 10 NN). The different lexicon sizes are determined on a learning database using the χ 2 measure. Figure 16 presents the categorization performance obtained for different lexicon sizes. We observe that a 75% reduction (from 450 to 100 terms (radicals)), results in a slight performance decrease. The lexicon is however reduced from 980 to 295 words (70% reduction). To observe a significant performance decrease, we must reach a much reduced lexicon (10 terms/46 words). To allow comparison, the performance obtained using the recognition system (KE 980) is recalled. We observe that it is also lower than the performance of different categorization systems constructed with the transcription of the database (TRANS), in a situation of perfect recognition.

Fig. 16 Categorization performance on the annotated ground truthed corpus (TRANS) as a function of the keyword lexicon size and using KE strategy (KE).

Fig. 17 Recall/precision performance in handwritten document categorization as a function of the keyword lexicon size using KE strategy.

Figure 17 presents the handwritten categorization performance using the KE strategy for the same lexicon sizes. Without modifying the Break Even Point, which remains at approximately 62% in all cases, we observe nonetheless that a reduction of the lexicon causes a strong improvement of categorization performance for all values on the curve inferior to the BEP. In fact, with 96 keywords, the performance reaches 90% precision for 40% recall, which is very close to the performance obtained on the ground truthed annotated database (TRANS 96) without recognition. We are in a situation where categorization performance are very similar to theoretical performance caused by a decrease of recognition errors due to the reduction of the lexicon size.

However, we observe a performance decrease when the lexicon used for categorization becomes too small (46 keywords). This seems natural because, as the lexicon is substantially reduced, a recognition error has more impact on the document description. We can conclude that the size of the lexicon is a key factor for handwritten document categorization. In our application, the best compromise seems to be a lexicon of 100 keywords. In fact, a more important reduction of the lexicon slightly improves the keyword extraction performance but it strongly reduces categorization performance.

Having only a single database of ground truthed annotated documents, it is rather difficult at this stage to bring a full answer concerning the optimal performance that can be expected in more general conditions and other categorization tasks. A similar study with documents from another area (other terms, other topics, etc.) should allow confirming these results. It seems, however, that below 30% recall for 70% precision in keyword extraction, the categorization performance drops quickly.

We have presented a complete system for handwritten document categorization based on a word extraction strategy rather than a full recognition approach. Apart from the experiments which shows that KE outperforms FR approach, we believe that the proposed modelisation also outperforms an FR strategy for the following reasons:

-In KE strategy, the OOV words are really modelled, whereas FR strategy does not. -KE based on our line model is a dynamic approach able to take into account the lexicon size, the recognition, the rejection and the segmentation process, whereas in FR strategy the rejection is performed as a postprocessing stage using a threshold, which prevent from taking the best whole decision on the entire line of text. -As the lexicon size is smaller, the KE strategy is faster than FR approach.

As a conclusion, let us emphasize that a perfect recognition would make our approach obsolete. Unfortunately recents systems are still far from having acceptable recognition results on weakly constrained handwritten documents.

Conclusions and future works

Building an automatic handwritten document categorization system calls upon techniques proposed in sev-eral areas of document analysis: automatic document layout analysis for detecting lines of text, handwriting recognition techniques for extracting keywords, and information retrieval for document categorization. For the first time, a complete categorization system of handwritten documents has been proposed with promising results on a real handwritten document database.

To overcome the limitations of a full recognition approach based on a large lexicon word recognition strategy, a new information extraction model has been designed, capable of locating and recognizing a restricted set of discriminative keywords. The information extraction method is based on an Out-Of-Vocabulary word model which is able to handle irrelevant information. We have shown in this study that it leads to better results than a more classical approach based on a full recognition strategy.

This first study raises a set of comments to be put in perspective for further studies concerning handwritten document processing. It is to be noticed that the keyword extraction strategy developed for document categorization could also be used for information retrieval. This study opens interesting prospects for future applications of the indexation of handwritten documents, regardless of the kind of documents to be processed: commercial documents, such as incoming mail or any other handwritten document with a certain interest like for example historical handwritten documents preserved numerically in digital libraries. No doubt that these topics will be addressed by many of the forthcoming researches led by the research community in the field of handwriting recognition.

Fig. 1

 1 Fig. 1 An incoming mail document (for confidentiality reasons, personal information has been blurred).

Fig. 3

 3 Fig. 3 Categorization of electronic documents.

Fig. 4

 4 Fig. 4 Illustration of the segmentation lattice, where level n contains all the possible aggregations of n adjacent elementary graphemes.

Fig. 5

 5 Fig. 5 Architecture of the information combination in the character model.

Fig. 6 a

 6 Fig. 6 a) Flat lexicon and b) its tree-structured representation.

Fig. 7

 7 Fig. 7 Examples of correctly recognized words.

Fig. 8

 8 Fig. 8 Examples of mis-recognized words (correct labels within brackets).

  illustrates the line model used by the KE strategy. This Figure highlights the competition of the relevant lexicon model developed in the FR strategy with the model of irrelevant words that we clarify now.

Fig. 10

 10 Fig. 10 Line model in the keyword recognition strategy (KE)

Fig. 11

 11 Fig. 11 The three steps of line segmentation. a) Initial grouping of the largest components; b) fusion of alignment; c) aggregation of small components.

Fig. 13

 13 Fig. 13 Example of the keyword extraction result on an incoming mail document.

Fig. 14

 14 Fig. 14 Keyword extraction performance. "KE n"stands for keyword extraction with a lexicon of n keywords; "FR" refers to the Full Recognition strategy with a 3700-word lexicon.

Fig. 15

 15 Fig. 15 Recall/Precision curves of the categorization task using ground truthed transcription (TRANS), Keyword Extraction strategy (KE 980) and Full Recognition strategy (FR).

Table 2

 2 ], and thus validate our categorization approach.

	topic	# of samples	Joachims98	Our approach
		per topic	(BEP)	(BEP)
	earn	1044	97.3	96.9
	acq	643	92.0	92.2
	money-fx	141	78.2	78.7
	grain	134	82.2	84.6
	crude	161	85.7	83.5
	trade	113	77.4	78.2
	interest	100	74.0	74.4
	ship	85	79.2	82.8
	wheat	66	76.6	62.1
	corn	48	77.9	73.7
	Micro average		82.3	81.9

Break Even Point (BEP) of Joachims's categorization system and our system on the Reuters 21578 corpus.

Table 4

 4 Word recognition performance for different configurations of the character recognition engine, for a lexicon size of 100/1000 words.

		Lexicon 100/1000 words
		Classifier P (L i /Ns)	Top 1	Top 2	Top 5	Top 10
	MLP-128	without duration	71.8/42.4	82.2/57.8	92.2/69.2	96.6/78.0
		with duration	80.2/58.0	88.0/68.2	94.2/80.6	97.8/87.2
	MLP-117	without duration	79.6/49.0	88.4/64.0	94.0/78.2	96.0/85.2
		with duration	81.6/57.0	90.0/69.2	93.6/80.4	96.8/86.8
	Average	without duration	85.0/58.6	92.2/72.2	96.0/84.8	98.2/91.2
		with duration	85.6/65.6	92.8/76.8	97.0/86.8	99.0/91.6

Table 5

 5 Evaluation of the line segmentation process.

		Number of lines	%
	Well segmented	262	79
	Over segmented	29	9
	Under segmented	0	0
	Other error	42	12
	Total	333	100

Table 6 Categorization

 6

	topic	# of document	TRANS	KE 980	FR
	A500 (cancellation)	206	86.6	73.5	68.1
	A255 (info pass / serv)	26	62.7	34.6	27.6
	A020 (change bank address)	23	71.1	39.1	32.3
	A030 (change postal address)	21	87.9	48.7	42.8
	A240 (claim / info fact)	16	25.8	0.0	0.0
	A502 (cancel. with portability)	12	43.5	25.0	19.5
	micro-average		76.6	62.3	46.4

break even points on ground truthed transcription mails (TRANS) and on recognized mails using the keyword extraction strategy (KE 980), and the full recognition strategy (FR).

See[Richard 91] for the proof that a MLP generates approximations of a posteriori probability outputs. In practice, the MLP outcomes are normalized using a softmax function.


Pascal Maillard

A note on stable point processes occurring in branching Brownian motion

Keywords: stable distribution, point process, random measure, branching Brownian motion, branching random walk. MSC2010. 60G55, 60G57

We call a point process Z on R exp-1-stable if for every α, β ∈ R with e α + e β = 1, Z is equal in law to T α Z + T β Z ′ , where Z ′ is an independent copy of Z and T x is the translation by x. Such processes appear in the study of the extremal particles of branching Brownian motion and branching random walk and several authors have proven in that setting the existence of a point process D on R such that Z is equal in law to ∞ i=1 T ξi D i , where (ξ i ) i≥1 are the atoms of a Poisson process of intensity e -x dx on R and (D i ) i≥1 are independent copies of D and independent of (ξ i ) i≥1 . In this note, we show how this decomposition follows from the classic LePage decomposition of a (union)-stable point process. Moreover, we give a short proof of it in the general case of random measures on R.

Introduction

Let D be a point process on R, (D i ) i≥1 be independent copies of D and (ξ i ) i≥1 be the atoms of a Poisson process of intensity e -x dx on R and independent of (D i ) i≥1 . Suppose that the point process Z, defined as follows, exists.

Z = ∞ i=1 T ξ i D i (1.1)
It is then easy to see that for every α, β ∈ R with e α +e β = 1, Z is equal in law to T α Z +T β Z ′ , where Z ′ is an independent copy of Z and T x is the translation by x. We call this property exp-1-stability or exponential 1-stability for a reason which will become clear later. Processes of the form (1.1) arose during the study of the extremal particles in branching Brownian motion. Brunet and Derrida [7,p. 18] asked the following question: Is it true that every exp-1-stable point process Z admits the decomposition (1.1)? This question was answered in the affirmative by the author [START_REF] Maillard | A characterisation of superposable random measures[END_REF], and independently in the special case appearing in branching Brownian motion by Arguin, Bovier, Kistler [START_REF] Arguin | Genealogy of extremal particles of branching Brownian motion[END_REF][START_REF]The extremal process of branching Brownian motion[END_REF] and Aïdékon, Berestycki, Brunet, Shi [START_REF] Aïdékon | The branching Brownian motion seen from its tip[END_REF]. The decomposition (1.1) was also shown for the branching random walk by Madaule [START_REF] Madaule | Convergence in law for the branching random walk seen from its tip[END_REF], relying on the author's result. See also [START_REF] Kabluchko | Persistence of competing systems of branching random walks[END_REF] for a related result concerning branching random walks. Note that the Poisson process with intensity e -x dx is well-known in extreme value theory and describes the maxima of random variables which are independent and identically distributed according to a law in the domain of attraction of the Gumbel distribution (see [START_REF] Resnick | Extreme values, regular variation, and point processes, Applied Probability[END_REF]Corollary 4.19]). It therefore arises naturally here and in similar situations, for example in the theory of max-stable processes [START_REF] Kabluchko | Stationary max-stable fields associated to negative definite functions[END_REF].

Immediately after the article [START_REF] Maillard | A characterisation of superposable random measures[END_REF] was published on the arXiv, the author was informed by Ilya Molchanov that the representation (1.1) could be obtained from a classic result known as the LePage decomposition of a stable point process, which holds true in much more general settings.

The purpose of this note is two-fold: First, we want to outline how the theory of stability in convex cones as developped by Davydov, Molchanov and Zuyev [START_REF] Davydov | Strictly stable distributions on convex cones[END_REF] yields the abovementioned LePage decomposition of stable point processes and with it the decomposition (1.1). This is the content of Section 2. Second, we give a succinct proof of the decomposition (1.1) for easy reference, a proof which uses more elementary methods than those of [START_REF] Davydov | Strictly stable distributions on convex cones[END_REF]. Furthermore, we give the extension of (1.1) to random measures, which cannot be directly obtained through the results of [START_REF] Davydov | Strictly stable distributions on convex cones[END_REF] (see Section 2). The statements of the results (Theorem 3.1 and Corollary 3.2) and their proofs are the content of Section 3.

Branching Brownian motion

In the remainder of this introduction, we outline the way exp-1-stable processes appear in branching Brownian motion (BBM). Define BBM as follows: Starting with one initial particle at the point x of the real line, this particle performs Brownian motion until an exponentially distributed time of parameter 1/2, at which it splits into two particles. Starting from the position of the split, both particles then repeat this process independently.

We are interested in the point process formed by the right-most particles (draw the real line horizontally). It turns out that an important quantity is the so-called derivative martingale

W t = i (t -X i (t)) exp(X i (t) -t)
, where we sum over all particles at time t and denote the position of the i-th particle by X i (t). This martingale has an almost sure limit W = lim t W t > 0 and it has been known since Bramson's [START_REF] Bramson | Convergence of solutions of the Kolmogorov equation to travelling waves[END_REF] and Lalley and Sellke's [START_REF] Lalley | A conditional limit theorem for the frontier of a branching Brownian motion[END_REF] work that the position of the right-most particle, centred around t -(3/2) log t + log W , converges in law to a Gumbel distribution. By looking at a suitable Laplace transform [START_REF] Madaule | Convergence in law for the branching random walk seen from its tip[END_REF], one can strengthen this result to the whole point process Z t formed by the particles at time t. One obtains the existence of a point process Z on R, such that, starting from any configuration of finitely many particles, T -t+(3/2) log t-log W Z t converges in law to Z as t → ∞.

Once the convergence of the point process is established, one now readily sees that the limiting process is exp-1-stable [START_REF]A branching random walk seen from the tip[END_REF][START_REF] Madaule | Convergence in law for the branching random walk seen from its tip[END_REF]: Take two BBMs and denote their derivative martingale limits by W and W ′ , respectively. The union of both processes is then again a BBM with derivative martingale limit W ′′ = W + W ′ . Applying the before-mentioned convergence result to both BBMs as well as to their union, we get that for almost every realisation of W and W ′ , T log(W +W ′ ) Z is equal in law to T log W Z + T log W ′ Z ′ , where Z and Z ′ are iid and independent of W and W ′ . Since W and W ′ can take any positive value (for example by varying the initial configurations), this yields the exp-1-stability of Z.

We emphasise that with this approach, one does not need to characterise the point process Z directly, as it has been done before [START_REF] Arguin | Genealogy of extremal particles of branching Brownian motion[END_REF][START_REF]The extremal process of branching Brownian motion[END_REF][START_REF] Aïdékon | The branching Brownian motion seen from its tip[END_REF]. This is helpful for models where such a direct characterisation would be complicated, for example for branching random walks [START_REF] Madaule | Convergence in law for the branching random walk seen from its tip[END_REF].

Stability in convex cones

Let Z be an exp-1-stable point process on R. Define Y to be the image (in the sense of measures) of Z by the map x → e x (this was suggested by Ilya Molchanov). Y is then a 1stable point process on (0, ∞), i.e. Y is equal in law to aY + bY ′ , where Y ′ is an independent copy of Y , a, b ≥ 0 with a+b = 1 and aY is the image of Y by the map x → ax. Note that if Y is a simple point process (i.e. every atom has unit mass), then the set of its points is a random closed subset of (0, ∞) and the stability property is then also known as the union-stability for random closed sets (see e.g. [START_REF] Ilya | Theory of random sets[END_REF]Ch. 4.1]).

Davydov, Molchanov and Zuyev [START_REF] Davydov | Strictly stable distributions on convex cones[END_REF] have introduced a very general framework for studying stable distributions in convex cones, where a convex cone K is a topological space equipped with two continuous operations: addition (i.e. a commutative and associative binary operation + with neutral element e) and multiplication by positive real numbers, the operations satisfying some associativity and distributivity conditions1 . Furthermore, K\{e} must be a complete separable metric space. For example, the space of compact subsets of R d containing the origin is a convex cone, where the addition is the union of sets, the multiplication by a > 0 is the image of the set by the map x → ax and the topology is induced by the Hausdorff distance (see Example 8.11 in [START_REF] Davydov | Strictly stable distributions on convex cones[END_REF]). Furthermore, it is a pointed cone, in the sense that there exists a unique origin 0, such that for each compact set K ⊂ R d , aK → 0 as a → 0 (the origin is of course 0 = {0}). The existence of the origin permits to define a norm by K = d(0, K), where d is the Hausdorff distance. An example of a convex cone without origin (Example 8.23 in [START_REF] Davydov | Strictly stable distributions on convex cones[END_REF]) is the space of (positive) Radon measures on R d \{0} equipped with the topology of vague convergence, the usual addition of measures and multiplication by a > 0 being defined as the image of the measure by the map x → ax, as above.

A random variable Y with values in K is called α-stable, α > 0, if a 1/α Y + b 1/α Y ′ is equal in law to (a+b) 1/α Y for every a, b > 0, where Y ′ is an independent copy of Y . With the theory of Laplace transforms and infinitely divisible distributions on semigroups (the main reference to this subject is [START_REF] Berg | Harmonic analysis on semigroups[END_REF]), the authors of [START_REF] Davydov | Strictly stable distributions on convex cones[END_REF] show that to every α-stable random variable Y there uniquely corresponds a Lévy measure Λ on a certain second dual of K which is homogeneous of order α, i.e. Λ(aB) = a α Λ(B) for any Borel set B. Since Λ is a priori only defined on this second dual of K, a considerable part of the work in [START_REF] Davydov | Strictly stable distributions on convex cones[END_REF] is to give conditions under which Λ is supported by K itself. Moreover, and this is their most important result, under some additional conditions, Y can be represented by its LePage series, i.e. the sum over the atoms of a Poisson process on K with intensity measure Λ.

Assuming that all the above conditions are verified, one can now disintegrate the homogeneous Lévy measure Λ into a radial and an angular component, such that Λ = cr -α-1 dr × σ for c > 0 and some measure σ on the unit sphere S = {x ∈ K : x = 1}. This is also called the spectral decomposition and σ is called the spectral measure. If σ has unit mass, then the LePage series can be written as

Y = i ξ i X i , (2.1)
where ξ 1 , ξ 2 , . . . are the atoms of a Poisson process of intensity cr -α-1 dr and X 1 , X 2 , . . . are iid with law σ, independent of the ξ i . This allows us to prove the decomposition (1.1) for a simple exp-1-stable point process Z:

If Y is the point process obtained from Z through the exponential transformation from the beginning of this section then supp Y ∪ {0} is a random compact subset of R containing the origin, assuming the process Z almost surely has only finitely many points in R + (we will prove this simple fact in Lemma 3.6 below). Hence, it is a random element of the cone from the first example given above. This cone satisfies the conditions required in [START_REF] Davydov | Strictly stable distributions on convex cones[END_REF], such that the results there can be applied to yield the LePage decomposition (2.1) of Y . This immediately implies the decomposition (1.1) for Z.

If Z is a general random measure on R, the same exponential transformation can be applied, such that Y becomes a 1-stable random measure on (0, ∞), i.e. an element of the cone from the second example above. Unfortunately, this cone does not satisfy the conditions in [START_REF] Davydov | Strictly stable distributions on convex cones[END_REF], such that their results cannot be used directly2 , although their very general methods could probably be applied in this setting as well.

A succinct proof of the decomposition (1.1)

As mentioned in the introduction, we will give here a short proof of the decomposition (1.1) and its extension to random measures, effectively yielding a LePage decomposition for stable random measures on (0, ∞). Instead of applying the general methods of harmonic analysis on semigroups used in [START_REF] Davydov | Strictly stable distributions on convex cones[END_REF], we will rely on the much more elementary treatment of Kallenberg [START_REF] Kallenberg | Random measures[END_REF] on random measures. We hope that our proof will be more accessible to probabilists who are not familiar with the methods used in [START_REF] Davydov | Strictly stable distributions on convex cones[END_REF]. Note that it can be easily generalised to give a LePage decomposition for stable random measures on R d \{0} or more general spaces. However, for simplicity and because of its interest in applications, we will stick to the onedimensional setting. For the same reasons, we will also keep the notion of exp-stability instead of the usual stability.

Definitions and notation

We denote by M the space of (positive) Radon measures on R. Note that µ ∈ M if and only if µ assigns finite mass to every bounded Borel set in R. We further denote by N the subspace of counting (i.e. integer-valued) measures. It is known (see e.g. [START_REF] Daley | An introduction to the theory of point processes[END_REF], p. 403ff) that there exists a metric d on M which induces the vague topology and under which (M, d) is complete and separable. We further set M * = M\{0} (where 0 denotes the null measure), which is an open subset and hence a complete separable metric space when endowed with the metric

d * (µ, ν) = d(µ, ν) + |d(µ, 0) -1 -d(ν, 0) -1 |, equivalent to d on M * ([5], IX.6.1, Proposition 2).
The spaces N and N * = N \{0} are closed subsets of M and M * , and therefore complete separable metric spaces as well ( [START_REF] Bourbaki | Elements of mathematics. General topology[END_REF], IX.6.1, Proposition 1).

For every x ∈ R, we define the translation operator T x : M → M, by (T x µ)(A) = µ(A-x) for every Borel set A ⊂ R. Furthermore, we define the measurable map

M : M → R ∪ {+∞} by M (µ) = inf{x ∈ R : µ((x, ∞)) < 1 ∧ (µ(R)/2)},
where we use the notation x∧y = min(x, y) and define inf ∅ = ∞ (in particular, M (0) = +∞). Note that for µ ∈ M * , we have M (µ) < ∞ if and only if µ(R + ) < ∞. If furthermore µ ∈ N * , then M (µ) is the position of the rightmost atom of µ, i.e. M (µ) = esssup µ. It is easy to show that the maps (x, µ) → T x µ and M are continuous, hence measurable.

A random measure Z on R is a random variable taking values in M. If Z takes values in N , we also call Z a point process. Let F denote the set of non-negative measurable functions f : R → R + = [0, ∞). For every f ∈ F , we define the cumulant

K(f ) = K Z (f ) = -log E [exp(-Z, f )] ∈ [0, ∞],
where µ, f = R f (x)µ(dx). The cumulant uniquely characterises Z ([9], p. 161).

We say that Z is exp-1-stable or simply exp-stable if for every α, β ∈ R with e α + e β = 1, Z is equal in law to T α Z + T β Z ′ , where Z ′ is an independent copy of Z.

The following theorem and its corollary are precise statements of the decomposition (1.1) and form the main results of this paper. Theorem 3.1. A function K : F → R + is the cumulant of an exp-stable random measure on R if and only if for every f ∈ F ,

K(f ) = c R e -x f (x) dx + R e -x M * [1 -exp(-µ, f )]T x ∆(dµ) dx, (3.1)
for some constant c ≥ 0 and some measure ∆ on M * , such that for every bounded Borel set

A ⊂ R, R e x ∞ 0 (1 ∧ y)∆(µ(A + x) ∈ dy) dx < ∞. (3.2)
Moreover, ∆ can be chosen such that ∆(M (µ) = 0) = 0, and as such, it is unique.

Infinitely divisible random measures

Our proof of Theorem 3.1 is based on the theory of infinitely divisible random measures as exposed in Kallenberg [START_REF] Kallenberg | Random measures[END_REF]. A random measure Z is said to be infinitely divisible if for every n ∈ N there exist iid random measures Z (1) , . . . , Z (n) such that Z is equal in law to Z (1) n) . It is said to be infinitely divisible as a point process if Z (1) can be chosen to be a point process. Note that a (deterministic) counting measure is infinitely divisible as a random measure but not as a point process.

+ • • • + Z (
The main result about infinitely divisible random measures is the following (see [START_REF] Kallenberg | Random measures[END_REF], Theorem 6.1 or [START_REF]An introduction to the theory of point processes[END_REF], Proposition 10.2.IX, however, note the error in the theorem statement of the latter reference: F 1 may be infinite as it is defined).

K(f ) = λ, f + M * [1 -exp(-µ, f )]Λ(dµ),
where λ ∈ M and Λ is a measure on M * satisfying ∞ 0

(1 ∧ x)Λ(µ(A) ∈ dx) < ∞, (3.4)
for every bounded Borel set A ⊂ R.

The probabilistic interpretation ( [START_REF] Kallenberg | Random measures[END_REF], Lemma 6.5) of this fact is that Z is the superposition of the non-random measure λ and of the atoms of a Poisson process on M * with intensity Λ. In the general framework of infinitely divisible distributions on semigroups used in [START_REF] Davydov | Strictly stable distributions on convex cones[END_REF] the measures λ and Λ are called the Gaussian component and the Lévy measure, respectively. Fact 3.4 has the following analogue in the case of point processes ([10], Proposition 10.2.V), where the measure Λ is also called the KLM measure. Note that the Gaussian component disappears.

Fact 3.4. A point process Z is infinitely divisible as a point process if and only if λ = 0 and Λ is concentrated on N * , where λ and Λ are the measures from Fact 3.3. Then, (3.4) is equivalent to Λ(µ(A) > 0) < ∞ for every bounded Borel set A ⊂ R.

In particular, the Lévy/KLM measure of a Poisson process on R with intensity measure ν(dx) is the image of ν by the map x → δ x .

Proof of Theorem 3.1

We can now prove Theorem 3.1 and Corollary 3.2. For the "if" part, we note that (3.2) implies (3.4) for the measure Λ = e -x T x ∆ dx, such that the process with cumulant given by (3.1) exists. The exp-stability is readily verified. Further note that for point processes the condition (3.3) is equivalent to (3.2).

It remains to prove the "only if" parts. Let Z be an exp-stable random measure. Then, for α, β ∈ R, such that e α + e β = 1, we have

K(f ) = -log E[exp(-Z, f )] = -log E[exp(-T α Z, f )] -log E[exp(-T β Z, f )] = K(f (• + α)) + K(f (• + β)). Setting ϕ(x) = K(f (• + log x)) for x ∈ R + (with ϕ(0) = 0) and replacing f by f (• + log x) in the above equation, we get ϕ(x) = ϕ(xe α ) + ϕ(xe β ) for all x ∈ R + , or ϕ(x) + ϕ(y) = ϕ(x + y)
for all x, y ∈ R + . This is the famous Cauchy functional equation and since ϕ is by definition non-negative on R + , it is known and easy to show [START_REF] Darboux | Sur le théorème fondamental de la géométrie projective[END_REF] that ϕ(x) = ϕ(1)x for all x ∈ R + . As a consequence, we obtain the following corollary:

Corollary 3.5. K(f (• + x)) = e x K(f ) for all x ∈ R.
Furthermore, it is easy to show that exp-stability implies infinite divisibility. We then have the following lemma. Lemma 3.6. Let λ, Λ be the measures corresponding to Z by Fact 3.3.

1. There exists a constant c ≥ 0, such that λ = ce -x dx. 2. For every x ∈ R, we have T x Λ = e x Λ. 3. For Λ-almost every µ, we have µ(R + ) < ∞.

Proof. The measures T x λ, T x Λ are the measures corresponding to the infinitely divisible random measure T x Z by Fact 3.3. But by Corollary 3.5, the measures e x λ and e x Λ correspond to T x Z, as well. Since these measures are unique, we have T x λ = e x λ and T x Λ = e x Λ. The second statement follows immediately. For the first statement, note that Lemma 3.7. The measure Λ admits the decomposition Λ = e -x T x ∆ dx, where ∆ is a unique measure on M * with ∆(M (µ) = 0) = 0.

c 1 = λ([0, 1)) < ∞, since [0, 1) is a bounded set. It follows that λ([0, ∞)) = n≥0 λ([n, n + 1)) =
Proof. We follow the proof of Proposition 4.2 in [START_REF] Rosinski | On series representations of infinitely divisible random vectors[END_REF]. Set M * 0 := {µ ∈ M * : M (µ) = 0} and M * R := {µ ∈ M * : M (µ) < ∞}, which are measurable subspaces of the complete separable metric space M * and therefore Borel spaces [START_REF]Foundations of modern probability, Probability and its Applications[END_REF]Theorem A1.6]. By the continuity of (x, µ) → T x µ, the map φ :

M * R → M * 0 × R defined by φ(µ) = (T -M (µ) µ, M (µ)
) is a Borel isomorphism, i.e. it is bijective and φ and φ -1 are measurable. The translation operator T x acts on M * 0 × R by T x (µ, m) = (µ, m + x). Now note that Λ is supported on M * R by the third part of Lemma 3.6. Denote by Λ φ the image of Λ by the map φ and set (3.4). By the theorem on the existence of conditional probability distributions (see e.g. [START_REF]Foundations of modern probability, Probability and its Applications[END_REF], Theorems 5.3 and 5.4) there exists then a measure ∆ 0 on M * 0 with ∆ 0 (A n ) < ∞ for every n ∈ N and a measurable kernel K(µ, dm), with

A n = {µ ∈ M * 0 : µ([-2n, 2n]) ≥ 1/n}. Then Λ φ (A n ×[-n, n]) < ∞ for every n ∈ N by
K(µ, [-n, n]) < ∞ for every n ∈ N, such that Λ φ (dµ, dm) = M * 0 ∆ 0 (dµ)K(µ, dm).
Moreover, we can assume in the above construction that K(µ, [0, 1]) = 1 for every µ ∈ M * 0 and n ∈ N, and with this normalization, ∆ 0 is unique. By Lemma 3.6, we now have T x K(µ, dm) = e x K(µ, dm) for every x ∈ R and µ ∈ M * 0 . As in the proof of the first statement of Lemma 3.6, we then conclude that K(µ, dm) = c(µ)e -m dm for some constant c(µ) ≥ 0, and by the above normalization, c(µ) ≡ c := e/(e -1). Setting ∆(dm) = c∆ 0 (dm) then gives

Λ φ (dµ, dm) = M * 0 ∆(dµ)e -m dm.
Mapping Λ φ back to M * R by the map φ -1 finishes the proof.

The "only if" part of Theorem 3.1 now follows from the previous lemmas and Fact 3.3. As for the proof of Corollary 3.2, if Z is a point process, then Fact 3.4 implies that λ = 0 and that Λ is concentrated on N * , hence ∆ as well. Equation (3.2) then implies that ∆(µ(A) > 0) < ∞ for any bounded Borel set A ⊂ R. In particular, this holds for A = {0}. But by Lemma 3.7, ∆ is concentrated on N * 0 = {µ ∈ N * : M (µ) = 0} and is therefore a finite measure, since µ ∈ N * 0 implies µ({0}) > 0. Now, if P(Z = 0) > 0 (the other case is trivial), then ∆(N * 0 ) > 0 and we set m = log ∆(N * 0 ). The measure ∆ ′ = e -m T m ∆ is then a probability measure and Λ = e -x T x ∆ ′ dx. Furthermore, Z satisfies (1.1), where D follows the law ∆ ′ . Uniqueness of the pair (m, D) follows from Lemma 3.7. This finishes the proof of Corollary 3.2.

Finiteness of the intensity

If Z is an exp-stable point process and has finite intensity (i.e. E[Z(A)] < ∞ for every bounded Borel set A ⊂ R), then it is easy to show that the intensity is proportional to e -x dx. However, in the process which occurs in the extremal particles of branching Brownian motion or branching random walk, the intensity of the point process D grows with |x|e |x| , as x → -∞ [8, Section 4.3]. The following simple result shows that in these cases, Z does not have finite intensity.

Corollary 3 . 2 .

 32 A point process Z on R is exp-stable if and only if it has the representation (1.1) for some point process D on R satisfying ∞ 0 P(D(A + x) > 0)e x dx < ∞. (3.3) Moreover, if the above holds, then there exists a unique pair (m, D) with m ∈ R ∪ {+∞} and D a point process on R such that P(M (D) = m) = 1 and (1.1) and (3.3) are satisfied.

Fact 3 . 3 .

 33 A random measure Z with cumulant K(f ) is infinitely divisible if and only if

n≥0 c 1 e 1 0

 11 -n = c 1 e e -1 =: c, hence λ([x, ∞)) = ce -x for every x ∈ R. The first statement of the lemma follows. For the third statement, let I n = [n, n + 1) and I = [0, 1). By (3.4), we have 1 0 Λ(µ(I) > x) dx = xΛ(µ(I) ∈ dx) < ∞. By monotonicity, the first integral is greater than or equal to xΛ(µ(I) > x) for every x ∈ [0, 1], hence Λ(µ(I) > x) ≤ C/x for some constant 0 ≤ C < ∞. By the second statement, it follows that Λ(µ(I n ) > e -n/2 ) = e -n Λ(µ(I) > e -n/2 ) ≤ Ce -n/2 , for every n ∈ N. Hence, n∈N Λ µ(I n ) > e -n/2 < ∞. By the Borel-Cantelli lemma, Λ lim sup n→∞ µ(I n ) > e -n/2 = 0, which implies the third statement.

Proposition 3 . 8 .

 38 Let Z be an exp-stable point process on R and let D be the point process from Corollary 3.2. Then Z has finite intensity if and only if E[ D, e x ] < ∞.Proof. By the Fubini-Tonelli theorem,E[Z(A)] = E i∈N E[T ξ i D(A) | ξ] = R E[D(Ay)e -y ] dy = E R D(Ay)e -y dy , for every bounded Borel set A ⊂ R. Again by the Fubini-Tonelli theorem we have R D(Ay)e -y dy = R R ½ A-y (x)e -y dy D(dx) = D, R ½ A-y (•)e -y dy . For x ∈ R, x ∈ Ay implies y ∈ [min Ax, max Ax]. Since e -y is decreasing, we therefore have |A|e -max A e x ≤ R ½ A-y (x)e -y dy ≤ |A|e -min A e x , where |A| denotes the Lebesgue measure of A. We conclude that E[Z(A)] < ∞ if and only if E[ D, e x ] < ∞.

One requires in particular that a(x + y) = ax + ay for every a > 0, x, y ∈ K, but not that (a + b)x = ax + bx for every a, b > 0, x ∈ K.

In particular, the theorems in[START_REF] Davydov | Strictly stable distributions on convex cones[END_REF] require that the cone be pointed and that the stable random elements have no Gaussian component, both conditions being violated by the cone of random measures (see the remark after Fact

3.3 for the second condition). Note however that although the cone does not have an origin, it is still possible to define a "norm" on the subspace of random measures which assign finite mass to[1, ∞), see the definition of the map M in Section 3.1.

Acknowledgements

I thank two anonymous referees for having spotted several typographical errors in the manuscript and for having requested more details and explanations, which greatly benefitted the presentation. One referee pointed out the reference [14].


Guillaume Rizk

Dominique Lavenier

Rayan Chikhi
email: rayan.chikhi@ens-cachan.org

DSK: k-mer counting with very low memory usage

Counting all the k-mers (substrings of length k) in DNA/RNA sequencing reads is the preliminary step of many bioinformatics applications. However, state of the art k-mer counting methods require that a large data structure resides in memory. Such structure typically grows with the number of distinct k-mers to count.

We present a new streaming algorithm for k-mer counting, called DSK (disk streaming of k-mers), which only requires a fixed, userdefined amount of memory and disk space. This approach realizes a memory, time and disk trade-off. The multi-set of all k-mers present in the reads is partitioned and partitions are saved to disk. Then, each partition is separately loaded in memory in a temporary hash table. The k-mer counts are returned by traversing each hash table. Lowabundance k-mers are optionally filtered.

DSK is the first approach that is able to count all the 27-mers of a human genome dataset using only 4.0 GB of memory and moderate disk space (160 GB), in 17.9 hours.

INTRODUCTION

Determining the abundance of each distinct k-mer in a set of sequencing reads is a conceptually simple yet fundamental task. It is used in many bioinformatics applications related to sequencing, e.g. genome and transcriptome assembly, variants detection and read error correction. For de novo assembly, one is often interested in counting k-mers to discard those with low abundance, which likely stem from sequencing errors.

State of the art methods for k-mer counting rely on hash tables [START_REF] Marc | A fast, lock-free approach for efficient parallel counting of occurrences of k-mers[END_REF] and/or Bloom filters [START_REF] Melsted | Efficient counting of k-mers in dna sequences using a bloom filter[END_REF]. These structures need to reside in memory for random access. Sequencing errors induce erroneous k-mers, in a volume typically greater or comparable to that of correct k-mers. Hence, counting k-mers for a human dataset with either a hash table or a Bloom filter is a task that requires tens of gigabytes of memory [START_REF] Marc | A fast, lock-free approach for efficient parallel counting of occurrences of k-mers[END_REF][START_REF] Melsted | Efficient counting of k-mers in dna sequences using a bloom filter[END_REF].

In the Methods section, we describe a fixed-memory and fixeddisk space streaming algorithm, DSK, and its worst-case complexity is analyzed in function of the desired memory and disk usage. In the Results section, DSK is used to count all the 27-mers of a wholegenome human dataset (Illumina reads). Furthermore, the trade-off between memory and disk space is analyzed on two smaller datasets. Finally, we discuss some advantages of DSK over related methods, and show a situation where a parallel implementation significantly improved the running time. for each index j = 0..np do 13:

METHODS

Initialize a hash table T with M bits of memory 14:

for each k-mer m in dj do 15:

T [m] ← ( T [m] + 1, if m is present in T 1, otherwise 16: output (m, T [m]) for each m in T 17: Delete T 18: Delete {d0, ..., dn p } function h(•) maps a k-mer to a numeric value in [0; H],
where H is a large integer (typically 2 64 ). In the following analysis, we make a simplifying assumption. Let d be the total number of distinct k-mers in the input, we assume that the number of distinct k-mers having a given hash value x ∈ [0; H] is at most ⌈d/H⌉. In other words, the set of distinct k-mer values can be uniformly partitioned by this hash function. Each k-mer is encoded using the classical 2 bits representation in the smallest available integer type, i.e. using 2 ⌈log 2 (2k)⌉ bits. The abundance of each k-mer is stored as a 32 bits integer. For convenience, let b = 2 ⌈log 2 (2k)⌉ . Each k-mer m present in S is examined n i = ⌈vb/D⌉ times (once per iteration), and written to disk only once, at the (h(m) mod n i )-th iteration. Using the uniform repartition hypothesis, a multi-set of v/n i ≤ ⌈D/b⌉ k-mers are written to disk at each iteration. Since each k-mer is encoded using b bits, the maximal disk usage of the algorithm is D bits.

The maximal memory usage of the algorithm is M bits, since Steps 7-11 require no memory, and Steps 12-17 load a single partition in T which requires exactly M bits. With an open-addressing mechanism, each distinct k-mer occupies exactly (b + 32) bits in T . To prove that the algorithm terminates, it suffices to show that T never overflows, i.e. that strictly c Oxford University Press 2012. expected time with open-addressing, as long as the load factor is strictly below 1 (which was proved above). Hence, the expected time complexity of Steps 12-17 (including the iteration loop) is O(v). Thus, Algorithm 1 runs in expected time O(v 2 b/D). The algorithm runs in expected linear time with respect to v when D = ω(v), e.g. setting D equal to the reads file size. In practice, the simplifying assumption on the uniform repartition of the hash function h does not hold exactly. Some partitions contain a slightly larger number of distinct k-mers than ⌈v/H⌉. Hence, the actual disk usage of the algorithm is slightly above D, and the load factor of T could, in theory, be above 0.7 (due to high k-mer redundancy, this is not the case in practice).

G. Rizk et al

RESULTS

In Table 1, we compared the execution time and memory usage of DSK with Jellyfish (version 1.1.5) and BFCounter (version 0.2) on a human genome Illumina dataset. The target disk usage of DSK was set to 160 GB, equal to the size of the reads file. Since the algorithm relies heavily on I/O to the disk, we also tested DSK with a solidstate drive (DSK-SSD). The reads file was placed on a standard hard disk drive, and partitions of redundant kmers were written on a 256 GB SSD. In this configuration, we noticed the algorithm is no longer limited by disk I/O and could benefit from multi-threading. The two for loops lines 7 and 12 were parallelized using openMP (4 threads). DSK-SSD ran in 3.5 hours using 4 × 1 GB of memory. Although this experiment required specific hardware, it is worth noting that the running time of DSK can be greatly reduced with a SSD and multi-core parallelism.

To further assess the trade-off between time, memory and disk usage, we executed DSK (using a standard hard drive) on two smaller E. coli and D. ananassae datasets, with various target memory and disk usage parameters. For the executions with 100 MB and 1 GB memory usage, the running time of DSK on both datasets decreases as the target disk space increases. This is a consequence of the decreasing number of iterations ni. The running times reaches a plateau at roughly the reads file size (where ni = 1). memory usage. However, at the smallest tested memory usage (10 MB), the execution time on both datasets is slightly higher, possibly due to consecutive disk writes to a large number of partitions. Note that in practice, the memory usage of DSK cannot be arbitrarily low: it is limited by the number of files that can be simultaneously opened on the system (the partitions {d0, ..., dn p } are all opened simultaneously). In the Drosophilia dataset, DSK failed to run with 10 MB of memory and 6 GB disk space for this reason.

DISCUSSION

Compared to other methods, DSK has three strong points:

• Low memory usage: Only an arbitrarily small subset of kmers is loaded in memory at any time. In contrast, BFCounter stores all the k-mers with count ≥ 2 in a hash table.

In principle, Jellyfish can use arbitrarily small hash tables, however storing the intermediate results requires a prohibitive amount of disk (≥ 1 TB for human genome reads using a hash table of size 5 GB). • Parameters are automatically inferred: the only mandatory argument is the k-mer length. Optionally, target memory and disk usages can be specified. Jellyfish and BFCounter require the user to specify respectively a hash table size and an upperbound on the number of distinct k-mers. • Supports arbitrarily large values of k: as opposed to up to 32 for Jellyfish (unbounded for BFCounter).

ACKNOWLEDGMENT

Funding: ANR MAPPI, ANR-10-COSI-0004

Fig. 1 .

 1 Fig. 1. Execution time of DSK (k = 21) in function of memory and disk usage, on the E. coli (Illumina DNA SRR001665, 20.8•10 6 reads of average length 36 bp) and D. ananassae datasets (Illumina RNA-Seq SRR332538 9.1 • 10 6 reads of average length 150 bp).

  Algorithms 1 describes the DSK k-mer counting algorithm. The hash

	Algorithm 1 The DSK algorithm
	1: Input: The set S of sequences, k-mer length k, target memory
		usage M (bits), target disk space D (bits), hash function h(•)
	2: v ←	P s∈S |s| -k + 1	{Number of k-mers}
	3: ni ← ⌈v • 2 ⌈log 2 (2k)⌉ /D⌉	{Number of iterations}
	4: np ← ⌈ 5: for each iteration i = 0..ni do v(2 ⌈log 2 (2k)⌉ + 32) ⌉ 0.7niM	{Number of partitions}
	6:	Initialize a set of empty lists {d0, ..., dn p } stored on disk
	7:	for each sequence s in S do
	8:		for each k-mer m in s do
	9:		if (h(m) mod ni) = i then
	10:		j ← h(m)/ni mod np
	11:		Write m to disk in dj
	12:

Table 1 .

 1 Wall-clock time and memory usage for counting 27mers in whole-genome human data of 1.4 billion of reads of average length 100 bp (160 GB file size). Jellyfish used 8 threads, DSK-SSD used 4 threads, DSK and BFCounter are single-threaded. The disk column indicates the temporary amount of disk space used by each method. * Executed on a desktop computer equipped with two hard drives including a SSD. The algorithm creates (n i np) ≤ ⌈v(b + 32)/(0.7M )⌉ temporary hash tables, inserting at most ⌈(0.7M/(b + 32))⌉ elements in each. Hash tables accesses and insertions (Step 15) are done in constant

	Program	Time (hours) Memory (GB) Disk (GB)
	DSK	17.9	4	160
	DSK-SSD *	3.5	4	240
	BFCounter	41.2	56	0
	Jellyfish	3.5	70	211
	The dataset used is the NA18507 human genome (SRX016231),
	unfiltered, consisting

less than M/(b + 32) distinct k-mers are inserted in T . At each iteration, (v/n i ) k-mers are split into np partitions. Each partition contains at most v/(n i np) ≤ ⌈0.7M/(b + 32)⌉ k-mers. In the worst case, all these kmers are distinct, thus the load factor is upper-bounded by 0.7 (a classical threshold above which hash table performance degrades).

The time complexity of Steps 7-11 (including the iteration loop) is O(v 2 b/D).