String Kernels Based on
Variable-Length-Don’t-Care Patterns
Kazuyuki Narisawa1 , Hideo Bannai1 , Kohei Hatano1 ,Shunsuke Inenaga2 , and Masayuki Takeda1
1

2

Department of Informatics, Kyushu University
Graduate School of Information Science and Electrical Engineering,
Kyushu University
744 Motooka, Nishiku, Fukuoka, 819–0395 Japan.
{k-nari,bannai,hatano,takeda}@i.kyushu-u.ac.jp
inenaga@c.csce.kyushu-u.ac.jp

Abstract. We propose a new string kernel based on variable-lengthdon’t-care patterns (VLDC patterns). A VLDC pattern is an element of(Σ ∪{⋆})∗ , where Σ is an alphabet and ⋆ is the variable-length-don’t-caresymbol that matches any string in Σ ∗ . The number of VLDC patterns
matching a given string s of length n is O(22n ). We present an O(n5 )algorithm for computing the kernel value. We also propose variations of
the kernel which modify the relative weights of each pattern. We evaluate
our kernels using a support vector machine to classify spam data.

1

Introduction

Text classiﬁcation techniques in machine learning have a wide range of applications such as natural language processing and bioinformatics. These techniques
are based on the similarity of words, sequences or other string units with a dictionary of natural language, biological actions and periodicities. It is a challenging
task to eﬃciently compute these similarity measures, and the kernel method is
one of the classical approaches for evaluating string similarity.
Several string kernels have been developed for various types of data. Mismatch kernels [1] are used for biological data such as DNA and protein sequences.
This kernel allows mismatches between sequences. Rational kernels [2, 3] can separate regular languages, using weighted transducers or rational relations.
The string subsequence kernels (SSKs) and N -gram kernels (NGKs) [4] arepopular string kernels. They are easy to compute, and can be applied to a variety of data since they do not make too many assumptions about the underlying
text structure. SSKs map strings to a feature space where each dimension corresponds to a subsequence of length n. The value of the dimension depends on asubsequence gap weight and how the subsequence occurs in each string. NGKs
map strings to a feature space where each dimension corresponds to a substringof length n, or n-gram. The value of the dimension depends on how many ofeach n-gram the string contains.

2

These kernels, however, have limitations. That is, these kernels are not suitable when the label of the texts depend not only on some relevant pattern (substring or subsequence) appearing in the texts, but on the order of such relevant
patterns. For example, assume that labels of texts are positive if the word “aab”
appears, followed by another word “aba”. For such tests, NGKs cannot capture
the order of strings in the texts. SSKs takes into account the orders of subsequences, but cannot capture the order of strings, either. In the case of SSKs, dissimilar strings may be judged similar due to the dimensions of subsequence. For
example, strings “xxxabcxxx” and “yayybyycy” are clearly diﬀerent. However,they may be judged similar because they have the same subsequence dimension“abc”. Although the SSK resolves this issue by the gap weight, preferring thateach character of the subsequence occur closer together, it cannot handle theorder of two (near-substring) subsequences as in the ﬁrst example.
In this paper, we propose a new string kernels based on variable-length-don’tcare (VLDC ) patterns [5–7]. A VLDC pattern is an element of Π = (Σ ∪ {⋆})∗ ,where Σ is alphabet and ⋆ is a wildcard that matches any string. In the running
example, the VLDC pattern ab ⋆ bb ⋆ ba matches abaabbaba by replacing the ⋆’swith aa and a, respectively. The VLDC pattern gives the best of both worlds andmore, since it contains both the set of substrings and subsequences as a subset.
Unlike NGKs and SSKs, our kernel can handle the situations where the order of
relevant strings inﬂuence the labels. Our kernel is not limited to exact matching
substrings as in NGKs, and can also handle the order of two substrings.
The number of VLDC patterns that matches a given string s of length nis O(22n ). We deﬁne several versions of kernels based on the VLDC pattern,
and propose algorithms that compute kernels, for example, for a given a pair ofstrings in O(max{n4 , ℓ2ℓ |Σ|ℓ }) time and O(n4 ) space, where ℓ is the length of
VLDC patterns and n is the maximum length of given strings. Unfortunately,
the time and space complexity of computing VLDC kernels are still quite highto apply for large data, but our kernels can be applied for data of small size inreasonable computation time.
We show the running times of VLDC kernel computation in a preliminary
experiment, and compare with that of SSKs, using random text data. Our main
experiment is a comparison of the performance in text classiﬁcation, using spamdata. The experiment shows that VLDC kernels outperform both SSKs and
NGKs.

2

Preliminaries

2.1

VLDC Patterns

Let Σ be a ﬁnite alphabet of size σ. An element of Σ ∗ is called a string. Strings
x, y and z are said to be a preﬁx, substring, and suﬃx of the string u = xyz.
The length of any string u is denoted by |u|. Let ε denote the empty string, that
is, |ε| = 0. Let Σ + = Σ ∗ − {ε}. The i-th character of a string u is denoted by
u[i] for 1 ≤ i ≤ |u|, and the substring of u that begins at position i and ends at
position j is denoted by u[i, j] for 1 ≤ i ≤ j ≤ |u|.

3

Let ⋆ denote a special symbol called a variable length don’t care (VLDC ) ora wildcard, which matches any string in Σ ∗ . Let Π = (Σ ∪ {⋆})∗ . Any element pof Π is called a variable-length-don’t-care pattern (or a VLDC pattern in short).
The length of any VLDC pattern p, denoted |p|, is the number of characters plus
the number of ⋆’s contained in p.
Deﬁnition 1. For any string x ∈ Σ ∗ and any VLDC pattern p ∈ Π, p is said
to match x iﬀ x is obtained by replacing the ⋆’s in p with some strings in Σ ∗ .
We write p ≼ x when p matches x.
Since ⋆ matches the empty string ε, for any string x ∈ Σ ∗ there are an
inﬁnite number of VLDC patterns matching x. To limit the number of VLDC
patterns matching x, consider the subset Π ′ ⊂ Π of VLDC patterns which startand end with ⋆ and contain no consecutive ⋆’s. For instance, ⋆a ⋆ b⋆ ∈ Π ′ but⋆a ⋆ ⋆b⋆ ∈/ Π ′ and a ⋆ b⋆ ∈/ Π ′.
Deﬁnition 2. For any string x ∈ Σ ∗ , we deﬁne P (x) by
P (x) = {p ∈ Π ′ | p ≼ x}.
For any string x of length n, the size of P (x) is O(2n−1 σ n ). Note that P (x) stillcontains all interesting VLDC patterns matching x, and contains only those.
Using the running example, ⋆a ⋆ b⋆ ∈ Π ′ matches a string x if and only if⋆a ⋆ ⋆b⋆ ∈/ Π ′ matches x. Also, we have that ⋆a ⋆ b⋆ ∈ Π ′ matches x if a ⋆ b⋆ ∈/ Π′matches x (the opposite is not true).
For each VLDC pattern p, we consider the multiset of the “maximal run” ofcharacters of Σ in p, as follows.
Deﬁnition 3. For any VLDC pattern p ∈ Π ′ , we deﬁne the multiset Con(p) ofstrings as{{w1 , . . . , wn } if p = ⋆w1 ⋆ · · · ⋆ wn ⋆ and wi ∈ Σ + (1 ≤ i ≤ n),Con(p) =∅if p = ⋆.
2.2

Support Vector Machines and Kernels

In this subsection, we review the outline of Support Vector Machines(SVMs)
and kernels. SVMs are a machine learning algorithm based on the idea of akernel mapping, and were introduced by Boser et al [8]. This methods learn thehyperplane in order to separate two sets of points so as to maximize the margin
distance, using several statistic properties. One of its properties is the mapping
to high dimensional feature space, that shape the performance of SVM. So calledkernels, denoted by
K(s, t) = ϕ(s) · ϕ(t),are used in this method. The function K(s, t) calculates the inner product between instance s and t in a high dimensional feature space deﬁned by a mapping
ϕ.

4

3

VLDC Kernels

For a given string, we ﬁrst deﬁne the VLDC kernel which considers the hyperspace where each dimension represents a VLDC pattern and its value is 1 if
the pattern matches the string, and 0 otherwise. Thus, the kernel can then bedeﬁned as the number of VLDC patterns that match both strings.
Deﬁnition 4 (VLDC Kernel). For any strings s, t ∈ Σ ∗ , we deﬁne the VLDC
kernel K(s, t) by∑
K(s, t) =δ(p, s, t),
p∈Π ′

{
1
δ(p, s, t) =
0

where

if p ∈ P (s) ∩ P (t),otherwise.

In many situations, it is more natural to prefer patterns where the occurrenceof each character is closer together, in order to better capture the characteristicsof the text. In the SSKs, this is achieved through gap weights. For the VLDC
kernel, we can achieve this by preferring longer contiguous constant parts in the
VLDC pattern, as follows:
Deﬁnition 5 (Weighted VLDC Kernel). For any strings s, t ∈ Σ ∗ , we deﬁne the weighted VLDC kernel K ′ (s, t) by∑K ′ (s, t) =δ ′ (p, s, t),
p∈Π ′

where

{∑

x∈Con(p) λ′δ (p, s, t) =0|x|

if p ∈ P (s) ∩ P (t) and Con(p) ̸= ∅,otherwise,for some λ > 1.
For the weighted VLDC kernel, we also consider a version where the lengthof the VLDC pattern is limited, keeping the calculation tractable.
Deﬁnition 6 (Length Restricted Weighted VLDC Kernel). For any stringss, t ∈ Σ ∗ , we deﬁne the length restricted weighted VLDC kernel Kℓ′′ (s, t) by∑
Kℓ′′ (s, t) =δ ′′ (p, s, t, ℓ),
p∈Π ′

where

{∑

x∈Con(p) λ′′δ (p, s, t, ℓ) =0

for some λ > 1 and ℓ ≥ 1.

|x|

if p ∈ P (s) ∩ P (t), Con(p) ̸= ∅ and |p| ≤ ℓ,otherwise,5

We can also restrict the number of wildcards (VLDCs) used in the pattern,
as follows.
Deﬁnition 7 (Wildcard Restricted Weighted VLDC Kernel). For any
strings s, t ∈ Σ ∗ , we deﬁne the wildcard restricted weighted VLDC kernel
Kr′′′ (s, t) by∑
δ ′′′ (p, s, t, r),Kr′′′ (s, t) =
p∈Π ′

where

{∑

x∈Con(p) λ′′′δ (p, s, t, r) =0|x|

if p ∈ P (s) ∩ P (t), 0 < |Con(p)| ≤ r + 1,
otherwise,for some λ > 1 and r ≥ 1.

4

Algorithms to Compute VLDC Kernels

In this section we present our algorithms to compute string kernels based on
VLDC patterns introduced in the previous section.
We use the following data structure in our algorithms.
Deﬁnition 8 (WDAWG). The Wildcard DAWG (WDAWG) of a string x,
denoted WDAWG(x), is the smallest automaton that accepts all VLDC patternsp ∈ Π such that p ≼ x.
WDAWG(x) with x = abbab is shown in Fig. 1.
By deﬁnition, every VLDC pattern q ∈ P (x) is accepted by WDAWG(x).
This implies that there is always a path spelling out q from the initial state of
WDAWG(x).
Theorem 1 ([9, 10]). For any string x of length n, WDAWG(x) requires O(n2 )space and can be constructed in linear time in the output size.
Using WDAWGs we obtain the following results:
Theorem 2. For any strings s and t, K(s, t) can be computed in O(n5 ) timeand space, where n = max{|s|, |t|}.
Proof. It follows from Theorem 1 that WDAWG(s) and WDAWG(t) can beconstructed in O(n2 ) time and space. Then we can easily construct a DFA which
accepts every element of P (s)∩P (t) by combining WDAWG(s) and WDAWG(t).
4The size of∑ such a DFA will be O(n ) in the worst case. Furthermore, sinceK(s, t) = p∈Π δ(p, s, t) = |P (s) ∩ P (t)|, K(s, t) can be computed by a simple
linear-time depth-ﬁrst traversal on the combined DFA, to count the number ofpaths from the initial state to all accepting states which start and end with ⋆and contain no consecutive ⋆’s. However, since the number of such paths canbe very large, that is, up to O(2n σ n ), treating these numbers at each state canrequire up to O(n) time and space. Therefore, K(s, t) can be calculated in a
total of O(n5 ) time and space in the worst case.
⊓
⊔

6

b

a

b
b

a

b

a

b

b
a

b
b
a

a
b

a
a
b
b

Fig. 1. WDAWG(x) with x = abbab.

Theorem 3. For any strings s and t, K ′ (s, t) can be computed in O(n22n ) timeand O(n4 ) space, where n = max{|s|, |t|}.
Proof. For each VLDC
∑pattern p ∈ P (s) ∩ P (t) with Con(p) ̸= ∅, we need tocompute δ ′ (p, s, t) = x∈Con(p) λ|x| . Hence we execute a depth-ﬁrst traversal
on the DFA for all the paths from the initial state to all accepting states whichstart and end with ⋆ and contain no consecutive ⋆’s. There are O(22n ) suchpaths. At each state corresponding to VLDC pattern p, the value of δ ′ (p, s, t)
can be computed in O(n) time utilizing information of the parent state in thetraversal. Overall, the total time cost is O(n2n σ n ). The value of K ′ (s, t) grows
up to O(22n λn ) which requires O(n) bits. Thus the space requirement is boundedby O(n4 ), the size of the combined DFA.
⊓⊔
Due to the above theorem, computing the weighted VLDC kernel K ′ (s, t) is not
feasible for large n (long strings). However, the next theorem states that thelength restricted weighted VLDC kernel Kℓ′′ (s, t) is computable in cases where ℓis small.
Theorem 4. For any strings s, t and integer ℓ, Kℓ′′ (s, t) can be computed inO(max{n4 , ℓ2ℓ σ ℓ }) time and O(n4 ) space, where n = max{|s|, |t|}.
Proof. Since we have only to consider the VLDC patterns of length at most ℓ, thetotal number of paths we traverse in the DFA is O(2ℓ σ ℓ ). At each state p we needO(ℓ) time to compute δ ′′ (p, s, t, ℓ). Hence the time cost is O(max{n4 , ℓ2ℓ σ ℓ }).
The space requirement is O(n4 ) since ℓ ≤ n.
⊓⊔
The wildcard restricted VLDC kernel Kr′′′ (s, t) is also computable when r issmall, since:

7

Theorem 5. For any strings s, t and integer r, Kr′′′ (s, t) can be computed inO(nr+1 r) time and O(n4 ) space, where n = max{|s|, |t|}.
Proof. The number of VLDC patterns which have at most r wildcard symbols⋆ and match both s and t isO(r∑×n−1 Ci−2 × n2 (i − 1)) = O(nr r).

i=2

Since at each state p we need O(n) time to compute δ ′′′ (p, s, t, r), the total time
cost is O(nr+1 r). The space requirement is O(n4 ) since r ≤ n.
⊓⊔5Computational Experiments

In this section, we compare our VLDC kernels with SSK and NGK by experiments.
5.1

Time ComparisonFirstly, we show our experiments for comparison of computational times withrandomly generated strings. The parameters of random strings are the alphabet
size such as 4, 25 and 52 and string length such as 100, 200, · · · , 500. We
compare the length restricted VLDC kernel K ′′ with SSK. The lengths of the
VLDC patterns for K ′′ and the subsequence for SSK are set to 5, 10 and 15. We
utilized the SSK algorithm of [4]. We used a CentOS Linux desktop computerwith two 3GHz dual core Xeon processors and 16GB memory.
Table 1 shows the running times (sec) for computing the length restricted
VLDC kernel K ′′ for each VLDC pattern length. We have not computed kernel
values for the cells with “-”, since it will take too much time. Since our algorithm
traverses all possible paths in the DFA where each state has at most σ transitions,the running time grows exponentially with respect to the alphabet size σ (seeTheorem 4). Table 2 shows the running times (sec) for computing the SSK
for each subsequence length. The running time of the SSK algorithm does notdepend on the alphabet size.
5.2

Performance Comparison

We evaluated the performances of our VLDC kernels K and K ′′ , compared toother kernels SSK and NGK. The classiﬁcation algorithm we used was a free
software SVMlight1 .
The values of our VLDC kernels may be huge, and thus we used the normalized value K for K, as follows:
K(s, t)K(s, t) = √,K(s, s)K(t, t)
1

http://svmlight.joachims.org/

8
Table 1. Computational times (sec) of the VLDC Kernel K ′′ values for random strings,
with alphabet sizes 4, 26 and 52 and string lengths 100, 200, · · · , 500. The the VLDC
pattern length parameter ℓ was set to 5, 10 and 15. We did not compute the kernel
value for each cell marked with “-”, as it will apparently take too much time.
alphabet VLDC pattern
string length
size
length
100
200
300
400
500
5
0.1125 0.7650 1.7250
2.91504.72504
100.1156 0.7356 1.4467
2.75004.5633150.3500 1.3500 1.900
3.31005.130050.1550 0.9525 2.1350
3.87256.447526
106.6400 34.2989 41.5500 49.6400 58.1067
157468.7900
50.21751.445 3.5825
6.805011.275052
1024.2500 307.26 859.6867 1530.8200 2098.3830
15
Table 2. Computational times (sec) of the SSK value for random strings, with alphabet sizes 4, 26 and 52 and string lengths 100, 200, · · · , 500. The subsequence lengthparameter in SSK was set to 5, 10 and 15.
alphabet subsequencesize
length
5
4
10
15
5
26
10
15
5
52
10
15

100
0.00040.00120.00360.00000.00200.00200.00040.00120.0020200
0.00400.01200.01840.00400.01080.01800.00400.01080.0172string length300
0.01320.02560.04520.01160.02720.04040.0116
0.02640.0388400
0.02440.05040.07800.02120.05000.07120.02280.04880.0720500
0.03840.07360.12160.03560.07920.11800.03680.07600.1144

where s, t ∈ Σ ∗ . The normalized value K ′′ for K ′′ is deﬁned similarly.
In our experiments, we used spam data collected from the forum of Yahoo!
Japan Finance2 , which were also used in [11]. We used 4 data sets of forum ID“4936”, “4974”, “6830”, and “8473”. The website contains a lot of spam messages, and the administrators watch over the forums and delete spam messages.
We classiﬁed the deleted messages as spam and other remaining messages as
non-spam. In order for our algorithms to run in a reasonable amount of time,
we only used messages of length at most 200 in each data set. Table 3 shows thenumber of instances (messages) in each data set.
In Table 4, we show the accuracy (%) of classiﬁcation with our VLDC kernels
K, K ′′ , SSK and NGK. The length restricted VLDC kernel K ′′ , SSK and NGK
2

http://quote.yahoo.co.jp

9
Table 3. The number of instances in each data set.
ID
4296
4974
6830
8473

spam
24
4
28
22

nonspam
48
14
102
84

require the following parameters; K ′′ : VLDC pattern length ℓ and weight λ,SSK: subsequence length and gap weight, NGK: substring length.
Shorter patterns tend to give good performances for all kernels except for K
which has no length parameter. The weight parameter λ of K ′′ was the best with
λ = 2.0. Observe that, for all the forums, our length restricted VLDC kernel K ′′shows the best performance.

6

Conclusions and Future WorkIn this paper we proposed four types of string kernels based on VLDC patterns.
Firstly, we introduced the VLDC kernel based on the all common VLDC patterns for a given pair of strings. This kernel is computable in O(n5 ) time andspace, where n is the input string length. The needlessness of parameters forpattern length or weights is a merit of this kernel. Secondly, the weighted VLDC
kernel was introduced, in which the consecutive constant characters are weighted
according to the length of the consecutiveness. This kernel requires O(n22n ) timeand O(n4 ) space. The third kernel, the length restricted weighted VLDC kernel,
has a parameter ℓ for the length of VLDC patterns, and thus is computable inO(max{n4 , ℓ2ℓ σ ℓ }) time and O(n4 ) space. Lastly, we also proposed the wildcard
restricted weighted VLDC kernel where the number of ⋆’s in each VLDC pattern is restricted by a parameter r. This kernel can be computed in O(nr+1 r)time and O(n4 ) space. We evaluated performances of our VLDC kernels for thecomputation time and text classiﬁcation ability by experiments. Computing our
VLDC kernels took longer time than SSKs and NGK. VLDC kernels, however,outperformed SSK and NGK in the classiﬁcation accuracy in the spam detecting
experiments.
Our VLDC kernels are shown to have high potential to classify text data.
However, their computational complexities may be too large to apply to large
text datasets. We are currently investigating ways to lower this complexity, whilestill retaining the high classiﬁcation accuracy.
Rational Kernels [2, 3] are known to be able to classify regular languages.
We would also like to investigate the expressiveness of our VLDC kernels in thisdirection, and determine the class of languages that they can classify.

10

Table 4. The performances of VLDC kernels K, K ′′ , SSK and NGK. Each cell shows
the accuracy(%) by SVMlight. In the results of the length restricted VLDC kernel K ′′ ,“length” means the VLDC pattern length ℓ and “weight” means consecutive string
weight λ > 1. In the results of SSK, “length” means subsequence length, and “weight”
means the gap weight 0 < δ < 1. In the results of NGK, “length” means substring
length, and NGK needs no string weight parameters.

Kernel Length Weight
VLDC K
1.1
5
1.5
VLDC K ′′
2.0
1.1
10
1.5
2.0
0.1
0.3
5
0.5
0.7
0.9
0.1
0.3
SSK
10
0.5
0.7
0.9
0.1
0.3
15
0.5
0.7
0.9
5
6
NGK
7
8
9
10

4296
66.67
68.06
68.06
76.39
66.67
66.67
66.67
63.89
66.67
66.67
69.45
69.44
66.67
50.00
66.67
66.67
66.67
66.67
66.67
66.67
65.28
66.67
70.84
70.84
69.45
69.45
69.45
69.45

data set ID
4974
6830
77.78
80.00
77.78
91.54
77.78
91.54
72.23
93.08
72.23
89.23
72.23
89.23
72.23
89.23
77.78
70.77
72.23
76.93
72.23
83.08
72.23
67.69
66.67
62.31
50.00
79.24
72.23
74.62
72.23
76.92
72.23
82.31
72.23
78.46
77.78
21.54
50.00
78.46
72.23
76.92
72.23
83.08
77.78
82.31
72.23
90.00
72.23
90.00
72.23
89.23
72.23
90.00
72.23
88.46
72.23
86.92

8473
79.25
95.29
95.29
96.23
93.40
93.40
93.40
79.25
86.79
89.62
86.80
67.92
51.89
78.31
81.14
83.97
79.25
20.75
79.25
79.25
79.25
79.25
92.46
89.63
88.68
87.74
85.85
84.91

11

References
1. Leslie, C.S., Eskin, E., Weston, J., Noble, W.S.: Mismatch string kernels for svm
protein classiﬁcation. In: Advance in Neural Information Processing Systems 15.
(2002) 1417–1424
2. Cortes, C., Haﬀner, P., Mohri, M.: Rational kernels: Theory and algorithms. Journal of Machine Learning Research 5 (2004) 1035–1062
3. Cortes, C., Kontorovich, L., Mohri, M.: Learning languages with rational kernels.
In: Proceedings of the 20th Annual Conference on Learning Theory. (2007) 349–364
4. Lodhi, H., Saunders, C., Shawe-Taylor, J., Cristianini, N., Watkins, C.: Text classiﬁcation using string kernels. Journal of Machine Learning Research 2 (2002)
419–444
5. Inenaga, S., Bannai, H., Shinohara, A., Takeda, M., Arikawa, S.: Discovering
best variable-length-don’t-care patterns. In: Proceeding of the 5th International
Conference Discovery Science(DS). Lecture Notes in Computer Science (LNCS)(2002) 86–97
6. Rahman, M.S., Iliopoulos, C.S., Lee, I., Mohamed, M., Smyth, W.F.: Finding patterns with variable length gaps or don’t cares. In: Proc. 12th Annual International
Computing and Combinatorics Conference (COCOON’06). (2006) 146–155
7. Navarro, G., Raﬃnot, M.: Fast and simple character classes and bounded gaps
pattern matching. Journal of Computational Biology 10(6) (2003) 903–923
8. Boser, B.E., Guyon, I.M., Vapnik, V.N.: A training algorithm for optimal marginclassiﬁers. In: COLT ’92: Proceedings of the ﬁfth annual workshop on Computational learning theory, ACM (1992) 144–152
9. Inenaga, S., Takeda, M., Shinohara, A., Hoshino, H., Arikawa, S.: The minimum
DAWG for all suﬃxes of a string and its applications. In: Proceeding of 13th
Annual Symposium on Combinatorial Pattern Matching(CPM). Volume 2373 ofLecture Notes in Computer Science (LNCS). (2002) 153–167
10. Inenaga, S., Shinohara, A., Takeda, M., Bannai, H., Arikawa, S.: Space-economical
construction of index structures for all suﬃxes of a string. In: Proceeding of
27th International Symposium on Mathematical Foundations of Computer Science(MFCS). Volume 2420 of Lecture Notes in Computer Science (LNCS). (2002)
341–352
11. Narisawa, K., Bannai, H., Hatano, K., Takeda, M.: Unsupervised spam detection
based on string alienness measures. In: Proceeding of the 10th International Conference Discovery Science(DS). Lecture Notes in Computer Science (LNCS) (2007)
159–172