code review 3752044: suffixarray: faster creation algorithm

suffixarray: faster creation algorithm

This implements the algorithm qsufsort using the sort package
as a sorting primitive. Its worst-case performance is O(N*log(N)), and it
uses only an additional slice of N ints of memory during creation.

Benchmarks (seconds):
           old    new
10k nulls          149    0.044
1M English corpus  32.0   3.6

[Eric Roshan Eisner, 2010-12-29 04:51:54]

Hello gri (cc: golang-dev@googlegroups.com),

I'd like you to review this change.

[gri, 2010-12-29 05:54:51]

Thanks, this was quick. I am on technically on vacation thus a thorough
review will have to wait until later next week.

Some initial feedback though after a cursory glance over the files:

1) The copyright notice in qsufsort.go should be as in the other files.
2) Where you refer to characters/chars in the comments/code you may want to
say "bytes" instead - the suffix array as it is just handles bytes (not
UTF-8 encoded chars)

Thanks,
- Robert

On Tue, Dec 28, 2010 at 8:51 PM, <eric.d.eisner@gmail.com> wrote:

> Reviewers: gri,
>
> Message:
> Hello gri (cc: golang-dev@googlegroups.com),
>
> I'd like you to review this change.
>
>
> Description:
> suffixarray: faster creation algorithm
>
> This implements the algorithm qsufsort using the sort package
> as a sorting primitive. Its worst-case performance is O(N*log(N)), and
> it
> uses only an additional slice of N ints of memory during creation.
>
> Benchmarks (seconds):
>           old    new
> 10k nulls          149    0.044
> 1M English corpus  32.0   3.6
>
> Please review this at http://codereview.appspot.com/3752044/
>
> Affected files:
>  M src/pkg/index/suffixarray/Makefile
>  A src/pkg/index/suffixarray/qsufsort.go
>  M src/pkg/index/suffixarray/suffixarray.go
>  M src/pkg/index/suffixarray/suffixarray_test.go
>
>
>

[Eric Roshan Eisner, 2010-12-30 16:58:38]

Hello gri (cc: golang-dev@googlegroups.com),

Please take another look.

[gri1, 2011-01-12 00:44:53]

I have only glanced over the details (and not tried to fully understand the
implementation), but this is really nice code.

It appears to be about 2x as fast when used to index godoc, which is great.

Mostly comments on cosmetics and a couple of questions.

Also, have you submitted the CLA? (see
http://golang.org/doc/contribute.html#copyright )

- gri

PS: Apologies for the delayed review.

http://codereview.appspot.com/3752044/diff/7001/src/pkg/index/suffixarray/qsu...
File src/pkg/index/suffixarray/qsufsort.go (right):

http://codereview.appspot.com/3752044/diff/7001/src/pkg/index/suffixarray/qsu...
src/pkg/index/suffixarray/qsufsort.go:1: // Copyright 2010 The Go Authors. All
rights reserved.
s/2010/2011/

http://codereview.appspot.com/3752044/diff/7001/src/pkg/index/suffixarray/qsu...
src/pkg/index/suffixarray/qsufsort.go:10: // This algorithm computes the suffix
array by computing its inverse.
s/array/array sa/

http://codereview.appspot.com/3752044/diff/7001/src/pkg/index/suffixarray/qsu...
src/pkg/index/suffixarray/qsufsort.go:20: // the first element of a sorted group
of length -sa[i], and can be skipped.
s/the //

http://codereview.appspot.com/3752044/diff/7001/src/pkg/index/suffixarray/qsu...
src/pkg/index/suffixarray/qsufsort.go:42: for sa[0] > -len(sa) { // until all
suffixes are one big sorted group
Q: in the paper this is a >= . What is the difference?

http://codereview.appspot.com/3752044/diff/7001/src/pkg/index/suffixarray/qsu...
src/pkg/index/suffixarray/qsufsort.go:46: for pi < len(sa) {
Q: in the paper this is a <= . What is the difference?

http://codereview.appspot.com/3752044/diff/7001/src/pkg/index/suffixarray/qsu...
src/pkg/index/suffixarray/qsufsort.go:95: 
please add an empty line here

http://codereview.appspot.com/3752044/diff/7001/src/pkg/index/suffixarray/qsu...
src/pkg/index/suffixarray/qsufsort.go:120: if sa[i] < 0 {
if sa[i] >= 0 {
   ...
}

and you don't need the continue

http://codereview.appspot.com/3752044/diff/7001/src/pkg/index/suffixarray/qsu...
src/pkg/index/suffixarray/qsufsort.go:146: 
please add an empty line here

http://codereview.appspot.com/3752044/diff/7001/src/pkg/index/suffixarray/suf...
File src/pkg/index/suffixarray/suffixarray.go (right):

http://codereview.appspot.com/3752044/diff/7001/src/pkg/index/suffixarray/suf...
src/pkg/index/suffixarray/suffixarray.go:37: return &Index{data, sa}
return &Index{data, qsufsort(data)}

and get rid of sa

http://codereview.appspot.com/3752044/diff/7001/src/pkg/index/suffixarray/suf...
File src/pkg/index/suffixarray/suffixarray_test.go (right):

http://codereview.appspot.com/3752044/diff/7001/src/pkg/index/suffixarray/suf...
src/pkg/index/suffixarray/suffixarray_test.go:215: 
please add an extra empty line here

[Eric Roshan Eisner, 2011-01-12 03:14:37]

Hello gri, gri1 (cc: golang-dev@googlegroups.com),

Please take another look.

[Eric Roshan Eisner, 2011-01-12 03:26:30]

On Tue, Jan 11, 2011 at 19:44, <gri@google.com> wrote:

> I have only glanced over the details (and not tried to fully understand
> the implementation), but this is really nice code.
>
> It appears to be about 2x as fast when used to index godoc, which is
> great.
>
> Mostly comments on cosmetics and a couple of questions.
>

Fixed the cosmetic stuff.

Also, have you submitted the CLA? (see
> http://golang.org/doc/contribute.html#copyright )
>

Just submitted it.


>
>
http://codereview.appspot.com/3752044/diff/7001/src/pkg/index/suffixarray/qsu...
> src/pkg/index/suffixarray/qsufsort.go:42: for sa[0] > -len(sa) { //
> until all suffixes are one big sorted group
> Q: in the paper this is a >= . What is the difference?
>

In the paper's implementation, n+1 is the size of the data. This is to allow
for their magic "end-of-string smaller than all other symbols" which doesn't
really work when dealing with arbitrary byte sequences.


>
>
http://codereview.appspot.com/3752044/diff/7001/src/pkg/index/suffixarray/qsu...
> src/pkg/index/suffixarray/qsufsort.go:46: for pi < len(sa) {
> Q: in the paper this is a <= . What is the difference?
>

Same as above.


-Eric Eisner

[gri1, 2011-01-12 04:18:06]

LGTM
Thanks for doing this!
- gri

On Tue, Jan 11, 2011 at 7:14 PM, <eric.d.eisner@gmail.com> wrote:

> Hello gri, gri1 (cc: golang-dev@googlegroups.com),
>
> Please take another look.
>
>
>
> http://codereview.appspot.com/3752044/
>

[gri, 2011-01-12 05:46:53]

*** Submitted as http://code.google.com/p/go/source/detail?r=d2ab7d15a2da ***

suffixarray: faster creation algorithm

This implements the algorithm qsufsort using the sort package
as a sorting primitive. Its worst-case performance is O(N*log(N)), and it
uses only an additional slice of N ints of memory during creation.

Benchmarks (seconds):
           old    new
10k nulls          149    0.044
1M English corpus  32.0   3.6

R=gri, gri1
CC=golang-dev
http://codereview.appspot.com/3752044

Committer: Robert Griesemer <gri@golang.org>