Errata
Notation: line -1 means the last line of a page, line -2 means the next-to-last,
and so on. Each entry is preceded by its page number.
Serious ones
Errata likely to compromise reader's understanding.
- 361
In the middle of the page, it says "As the k^2 children distribute
across k contiguous segments in the LOUDS layout, the cost that is
charged to v decreases to O(k)". This argument is correct when
reused for the nodes of type (2), but for nodes of type (1) all the children
are contained in the query, and then all the children are interesting, and
contiguous in the LOUDS layout. Therefore, the correct cost charged to
v is O(1). This allows us remove the factor k that
accompanies occ in the displayed formula of the final cost. Thanks
to Ariel Cáceres for noting this. Further, there is an extra closing
parenthesis at the end of this formula.
- 371
Near the bottom of the page,
by the same argument of the correction in page 361, the factor k^(d-1)
multiplying occ can be removed. Instead, q^(d-1) should rather
be d * q^(d-1) , which is the surface of the query.
- 374
The method for finding the m closest points via successively enlarging
the area until at least m points are found is not complete. Once those
points are found, we must take the distance to the mth closest one, and
perform a final query with this distance. Then we capture at least m
points again and then take the m closest ones. This is because a box
around the query may capture points that, with Manhattan distance, are farther
than some points not included in the box. Thanks to Patricio Huepe for
pointing this out.
Medium ones
Errata that affect technical correctness but either the reader is most
likely to easily spot them, or the errors are not important for the matter.
- 22
Example 2.10 is not totally consistent with Example 2.8, because here we are
considering the terminator $ for the string S, and in Example 2.8 we
are not. As a consequence, it could have been that the high-order entropy was
larger than the zero-order entropy.
Thanks to Sebastian Maneth for noting this.
- 68
In line -3, "= 5" should be "= C[5]".
Thanks to José Fuentes for noting this.
- 79
In Figure 4.4, the value "10" in the array R (on top) should not be grayed.
Thanks to Kajetan Johannes Hammerle for noting this.
- 80
In line 7 of Algorithm 4.6, the condition should be "<" instead of "≤".
Thanks to Kajetan Johannes Hammerle for noting this.
- 83
In the displayed formula, select_1(S,j) should be select_1(B,j).
Thanks to Rolando Kindelan for noting this.
- 88
In the middle of the page it says "If A contains zeros, we can instead
encode the values A[i]+i...". That "A[i]" should rather be
"sum(A,i)".
Thanks to Yusaku Kaneta for spotting this.
- 154
In line 2, it should have said n o(H_0(S)) bits, not
o(n H_0(S)) bits. Further, this can then be expressed as
o(n H_0(S)) + O(n) bits, which then matches correctly with the
rest of the analysis (see the small errata in page 127).
- 169
Right before Example 7.4, bwdsearch(B,i,-d-1) should be
bwdsearch(B,i,-d-1)+1, as implied by the formula of enclose(B,i)
in the previous page.
Thanks to Ariel Cáceres for noting this.
- 186
Before Example 7.10, we say we use fwdsearch(i-1,m). However, we have
described this algorithm only for the case m < 0, whereas it could be
that the minimum excess in the range is m=1. This exception can be
easily handled by noting that, in this case, fwdsearch(i-1,1) is always
i. The same holds a few lines later for fwdsearch(i-1,M) when
M = -1; the answer is i. Thanks to Ariel Cáceres for noting this.
- 193
In line 15, B should be V. Noted by Ariel Cáceres.
- 195
In line -10, V[i][j]+1 should be m[V[i][j]]+1. Communicated by
Kunihiko Sadakane.
- 284
The code for adj(G,v,u) is much more complicated than necessary. One
can remove lines 6-9 and add a line "if v < u then
exchange u and v" between lines 2 and 3.
Also, in line 18, b+j should be b-v+j.
- 316
The definition of L, "Every run of k (equal) brackets in
B_s...", could be clearer: "Every run of brackets belonging to the
same node in B_s (note that those brackets must be equal)...". Thanks to
Simon Gog for noting this.
- 334
Algorithm 9.19 claims to correspond to the algorithm "Face-2" referenced in
page 342, but they have some subtle differences, since our algorithm never
uses an edge that crosses the imaginary line and sometimes this is necessary.
In fact, one must remember the point (not necessarily node) p where
the edge would cross the line (initially p is the source), and allow
following edges if the cross the line exactly at point p. This fixes
some special cases where the general algorithm would fail.
- 458
In lines 17-18 of Algorithm 12.4 (procedure insw), the algorithm needs to
decrease i to account for the bits skipped in the left child, that is,
insert the instruction i = i - v.num. Thanks to Jan-Philipp Tarnowski
for noting this.
- 518
The space given for Gagie et al. 2012, under "Kernelization", is in addition
to a context-free grammar for the text, not standalone.
- 520
In Example 13.14, the penultimate block of S should look "ade ae"
rather than "adeae". The string is the same, but the logic of its generation
is apparent when properly segmented. Similarly, there should be a space after
the underlined "b" in the last string.
- 536
On the right of Figure 13.7, the trie node reached by "a" should have 5 inside,
not a 4.
Small ones
Errata on references, language, fonts, and other not really compromising
the content.
- 3
In line 3 of Section 1.2, "fluorished" should be "flourished".
Thanks to Kunihiko Sadakane for noting this.
- 118
In the bibliographic discussion on compressible permutations,
we found that an old paper [T. Takaoka,
A New Measure of Disorder in Sorting, Proc. CATS, pp. 77-86, 1998]
had already given the idea of merging in the order induced by the Huffman tree
to perform MergeSort. Followups were pubished much later in a conference
[T. Takaoka, Partial solution and entropy, Proc. 34th MFCS, pp. 700-711, 2009]
and then in a journal
[T. Takaoka, Entropy as computational complexity, Journal of Information
Processing 18:227-241, 2010]. Thanks to Jérémy Barbay for this
pointer.
- 127
In Footnote 1, it would be good to mention that a common way to express the
formula is o(n log sigma) + O(n).
- 188
In Secion 7.1.4, "deepest segments" should actually be "segments
with no children". Noted by Ariel Cáceres.
- 190
In line -12, "if have" should be "if we have". Further, we might note that the
access to C[.][l'] requires first shifting the bits of the last block
covering B[i,j].
- 201
In lines 13 and 14 we could have used i-1 instead of i and the
method would also work when t is of the same type of
P[i].
flexible text retrieval systems. Journal of Discrete Algorithms, 5, 12–22.
In this paper, he actually gives a general rmq_A solution using 4n+o(n)
bits by adding n-1 leaves to the Cartesian tree. Noted by Kunihiko
Sadakane.
- 209
We cite Sadakane (2007), but not the correct one: Succinct data structures for
flexible text retrieval systems. Journal of Discrete Algorithms, 5, 12–22.
In this paper, he actually gives a general rmq_A solution using 4n+o(n)
bits by adding n-1 leaves to the Cartesian tree. Noted by Kunihiko
Sadakane.
- 232
In line 5, it would be better to exchange u and v in this
comment, because we have just discussed how to compute the area below
v. Noted by Kunihiko Sadakane.
- 276
The bibliographic entry of Belazzougui et al. is missing its second author,
P. H. Cording.
- 308
Instead of "The exact entropy of planar graphs (without defining their mapping
to the plane) is unknown, but it must be less than 3.58e.", the
following would have been more accurate: "Planar graphs (without defining
their mapping to the plane) must have a lower entropy, but that value is
unknown."
- 330
In line 14, "brand" should be "branch". Thanks to Kunihiko Sadakane for this.
- 542
The second bibliographic entry of Belazzougui et al. (the last in the page) is missing
its second author, P. H. Cording.
Found an error? Please let us know
and enter our Hall of Fame!