R3lib Library Home Page

Last updated: May 15 2007

Description

R3lib is an open-source library of functions for finding maximal repeats in data (text or binary). For more information see home page of my diploma thesis.

Features

find maximal repeats in optimal time
efficient linear-space internal memory structure for representing all maximal repeats in string - R3 tree
create suffix array and lcp-table over strings of bytes

Download

File	Comment
r3lib1.0.1.zip	Latest R3Lib version
svndump.zip	Subversion repository dump (May 15 2007)

Performance

Following table gives an idea how fast is R3lib on different types of input. These files were used as input and they were free to download at the time when the measurement took place, link to download location is given for each of them. Machine used for measurement was 3GHz Intel Pentium 4, 1GB RAM. Measurements were done on Linux and Windows, 4 times on each.

File	Link	Size	TimeWin	TimeLinux	Peak	Mem	rPeak	rMem
gimp-2.2.9.tar.gz	link	18,400,967	149.701	174.265	691,693,912	416,358,967	37.59	22.63
Azureus_2.5.0.4a_Win32.setup.exe	link	10,007,784	57.460	67.203	362,287,916	206,977,004	36.20	20.68
180907088.jpg	link	4,611,403	22.031	25.509	164,415,064	92,187,563	35.65	19.99
183899999.jpg	link	1,993,582	7.649	8.850	69,729,972	38,079,982	34.98	19.10
184722357.jpg	link	1,065,155	3.080	3.617	36,752,568	19,964,923	34.50	18.74
rbcru10.txt	link	653,492	3.364	4.073	27,613,492	16,417,866	42.26	25.12
zlib123.zip	link	583,873	1.756	2.116	20,627,024	11,447,525	35.33	19.61
2ws2610.txt	link	193,004	0.898	1.098	8,072,116	4,839,906	41.81	25.07
1ws2510.txt	link	150,662	0.712	0.892	6,355,132	3,797,228	42.18	25.20
1ws1810.txt	link	145,500	0.673	0.831	6,125,588	3,647,890	42.10	25.07
1ws3410.txt	link	129,092	0.597	0.734	5,435,572	3,245,222	42.11	25.14
1ws1710.txt	link	121,446	0.560	0.695	5,114,920	3,053,803	42.12	25.15
1ws0610.txt	link	105,421	0.480	0.585	4,445,260	2,651,660	42.17	25.15
19033.txt	link	74,726	0.353	0.396	3,178,480	1,916,273	42.54	25.64

Legend:

File = file that was used as input text
Link = link to file
Size = size of input in bytes
TimeWin = average time taken to construct R3 tree in seconds (OS: Windows XP SP1, gcc 3.4.4 cygwin)
TimeLinux = average time taken to construct R3 tree in seconds (OS: Linux Ubuntu 6.06, Kernel 2.6.15-27-386, gcc 4.0.3)
Peak = Peak memory usage in bytes (only input size dependent data structures are counted)
Mem = Memory occupied by R3 tree in bytes (only input size dependent data structures are counted)
rPeak = Peak/Size
rMem = Mem/Size

R3lib documentation

R3lib development environment setup

Changelog

1.0.1 - findPairs query bugfix

1.0.0 - Release for diploma thesis, added some comments

0.9.2 - Fixes needed to compile on linux

0.9.1 - I decided to start version numbering with this verison. All versions before my diploma thesis deadline will be 0.9.x. Version 1.0.0 will be the version that will be submitted with my thesis. Version will have tree components A.B.C. A will be incremented with major conceptual change of R3lib. B will be incremented with new feature and C will be incremented with bugfix releases.