#
15th International Symposium, SPIRE 2008, Melbourne, Australia, November 10-12, 2008. Proceedings

*S*is a (periodic) substring

*r*of

*S*of the form

*r*=

*u*

^{ }...

*s*=

*s*

_{1}..

*s*

_{ n }be a text (or sequence) on a finite alphabet

*Σ*. A fingerprint in

*s*is the set of distinct characters contained in one of its substrings. Fingerprinting a text consists in computing the set of all fingerprints of all its substrings. A fingerprint, , admits a number of maximal locations 〈

*i*,

*j*〉 in

*S*, that...

*s*-grams have been successfully used in cross-language information retrieval (CLIR) as an approximate string matching technique for translating out-of-vocabulary (OOV) words. For example,

*s*-grams have consistently outperformed other approximate string matching techniques, like edit distance or

*n*-grams. The Jaccard coefficient has traditionally been used as an

*s*-gram based string proximity...

*p*of length

*m*and a text

*t*of...

*i*> 1, iff

*k*is the largest integer such that . The prefix array is closely related to the : an integer array [1..

*n*] such that iff the length of the longest border of is

*k*. Border arrays or their variants are used in many string algorithms and prefix arrays can be used directly for pattern-matching...

*A*and

*B*with lengths

*m*and

*n*, respectively, the task is to compute, in

*n*successive iterations

*j*=

*n*...1, an encoding of the edit distances between

*A*and all prefixes of

*B*

_{ j..n }. Here

*B*

_{ j..n }is the suffix of

*B*that begins at its

*j*th character...

*base sequence*of length

*n*are repeated many times with small variations, forming a collection of total length

*N*. Examples of such collections are version control data and genome sequences of individuals, where the differences can be expressed by lists of basic edit operations. This paper is devoted to studying ways to store massive sets of...

*rank*,

*select*, and

*access*queries. While there are several theoretical solutions to the problem, only a few have been tried out, and there is little idea on how the others would perform, especially in the case of sequences with very large alphabets. We first present a new practical implementation of the compressed representation...

*a priori*induced cliques. The clustering quality is evaluated with an extension...