aboutsummaryrefslogtreecommitdiff
path: root/src/pkg/index/suffixarray/suffixarray.go
AgeCommit message (Collapse)Author
2011-07-08sort: rename helpers: s/Sort// in sort.Sort[Float64s|Ints|Strings]Andrew Gerrand
Includes 'sorthelpers' gofix and updates to tree. R=golang-dev, gri CC=golang-dev https://golang.org/cl/4631098
2011-04-20src/pkg: make package doc comments consistently start with "Package foo".Nigel Tao
R=rsc CC=golang-dev https://golang.org/cl/4442064
2011-01-24suffixarray: use binary search for both ends of LookupEric Eisner
This prevents many unnecessary comparisons when n is large. R=gri, gri1, rsc CC=golang-dev https://golang.org/cl/4068043
2011-01-11suffixarray: faster creation algorithmEric Eisner
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 https://golang.org/cl/3752044
2010-12-17suffixarray: implememted FindAllIndex regexp searchRobert Griesemer
Implementation uses fast suffixarray lookup to find initial matches if the regular expression starts with a suitable prefix without meta characters. R=r, rsc CC=golang-dev https://golang.org/cl/3720042
2010-12-14suffixarray: rename Data() -> Bytes()Robert Griesemer
R=rsc CC=golang-dev https://golang.org/cl/3540042
2010-12-13suffixarray: provide accessor to dataRobert Griesemer
R=r CC=golang-dev https://golang.org/cl/3574044
2010-12-08throughout: simplify two-variable ranges with unused second variableRyan Hitchman
R=golang-dev, gri CC=golang-dev https://golang.org/cl/3529041
2010-11-19index/suffixarray: use sort.SearchRuss Cox
R=gri CC=golang-dev https://golang.org/cl/3200041
2010-09-22suffixarray: cleanup per suggestion from Roger PeppeRobert Griesemer
R=rsc CC=golang-dev https://golang.org/cl/2213045
2010-09-21suffixarray: a package for creating suffixarray-based indexesRobert Griesemer
This is a replacement for pending CL 2219042. It only contains the raw suffixarray functionality with two methods: - New create a new index from some data - Lookup lookup occurences of a bytes slice in the data Any other functionality (dealing with multiple data sets and the corresponding position lists) is generic and doesn't have to be part of this package. Known performance bug: This implementation works fine for data sets up to several megabytes as long as it doesn't contain very long contiguous sequences of equal bytes. For instance, index creation for all .go files under GOROOT (250KLOCs, approx. 9MB) takes ~50s on 2.66 GHz Intel Xeon as long as test/fixedbugs/257.go is excluded. With that file, index creation times takes several days. 257.go contains a string of 1M smiley faces. There are more sophisticated suffixarray creation algorithms which can handle very long common prefixes. The implementation can be updated w/o the need to change the interface. R=rsc, r, PeterGo CC=golang-dev https://golang.org/cl/2265041
generated by cgit v1.3-5-g9baa (git 2.53.0) at 2026-04-17 10:49:54 +0000