Information Technology Reference
In-Depth Information
There are also other distance functions in use for Hamming spaces. One is the
r
-contiguous bit rule [11]. Its definition is based on the
XOR
-function like the distance
function above. The rule adopts the maximum of a certain set of values that is defined
by
{
}
( )
()
()
()
(9)
U
u
=
ones
s
s
is
a
substring
of
u
with
ones
s
=
length
s
The condition in
U
guarantees that the selected substrings only contain 1's. By means
of the set
U
the
r
-contiguous bit rule can be formulated as
(
)
(
(
)
)
(10)
r
−
cont
x
,
y
=
max
U
XOR
x
,
y
It is easy to see that this definition of the
r
-contiguous-rule satisfies the first three
conditions of a metric. But it does not satisfy the triangle inequation. Figure 5 gives a
counterexample. Thus, for any set of binary strings
H
, (
H
,
r-cont
) is not a metric
space.
x
1 0 1 1 1 0 1 0 1 1
r-
cont(
x
,
y
) = 3
y
1 1 1 0 0 1 1 0 0 1
r-
cont(
x
,
z
) = 1
z
1 0 1 0 1 1 1 0 0 1
r-
cont(
y
,
z
) = 1
Fig. 5.
An example showing that the r-contiguous-rule does not satisfy the triangle inequation
A variant of the r-contiguous rule is the multiple contiguous bit rule [9]. For its
definition the following set
V
is required:
⎧
⎫
s
is
the
i
th
substring
of
u
with
⎪
⎨
⎪
⎬
(11)
(
)
()
V
x
,
y
=
ones
s
i
i
()
()
(
)
ones
s
=
length
s
≥
2
and
u
=
XOR
x
,
y
⎪
⎩
⎪
⎭
By means of the set
V
the multiple contiguous bit rule can be defined as follows:
(
)
(
(
)
)
∑
()
(12)
weight
s
mult
−
cont
x
,
y
=
ones
XOR
x
,
y
+
2
i
i
Like the r-contiguous bit rule, the multiple contiguous bit rule trivially satisfies the
conditions of a distance function. However, it does not satisfy the triangle inequation.
This can be shown with the example of figure 5. Figure 6 shows the strings
XOR
(
x
,
y
),
XOR
(
x
,
z
), and
XOR
(
y
,
z
) and the value of
mult-cont
for these strings. So again,
(
H
,
mult-cont
) is not a metric space.
XOR
(
x
,
y
)
mult-cont
(
x
,
y
) = 13
0 1 0 1 1 1 0 0 1 0
XOR
(
x
,
z
)
mult-cont
(
x
,
z
) = 3
0 0 0 1 0 1 0 0 1 0
0 1 0 0 1 0 0 0 0 0
mult-cont
(
y
,
z
) = 2
XOR
(
y
,
z
)
Fig. 6.
The strings
XOR
(
x
,
y
),
XOR
(
x
,
z
), and
XOR
(
y
,
z
) with
x
,
y
, and
z
as in figure 6
