GitHub - xidianzyh/mKD-GBWT: mKD-GBWT index: an external memory full-text index

xidianzyh / mKD-GBWT Public

Notifications You must be signed in to change notification settings
Fork 0
Star 1

mKD-GBWT index: an external memory full-text index

Notifications

Name		Name	Last commit message	Last commit date
Latest commit History 5 Commits
sdsl		sdsl
test		test
tools		tools
.gitattributes		.gitattributes
.gitignore		.gitignore
DiskFile.cpp		DiskFile.cpp
DiskFile.h		DiskFile.h
DiskGBWT.cpp		DiskGBWT.cpp
DiskGBWT.h		DiskGBWT.h
DiskKDNode.cpp		DiskKDNode.cpp
DiskKDNode.h		DiskKDNode.h
DiskKDTree.cpp		DiskKDTree.cpp
DiskKDTree.h		DiskKDTree.h
DiskSBT.cpp		DiskSBT.cpp
DiskSBT.h		DiskSBT.h
KDDisk.cpp		KDDisk.cpp
KDDisk.h		KDDisk.h
KDNode.cpp		KDNode.cpp
KDNode.h		KDNode.h
KDPointDisk.cpp		KDPointDisk.cpp
KDPointDisk.h		KDPointDisk.h
KDTree.cpp		KDTree.cpp
KDTree.h		KDTree.h
KDTreeDiskHeader.cpp		KDTreeDiskHeader.cpp
KDTreeDiskHeader.h		KDTreeDiskHeader.h
KDVirtualDisk.cpp		KDVirtualDisk.cpp
KDVirtualDisk.h		KDVirtualDisk.h
LICENSE		LICENSE
Makefile		Makefile
README		README
Suffix.cpp		Suffix.cpp
Suffix.h		Suffix.h
critbit_node.h		critbit_node.h
critbit_tree.cpp		critbit_tree.cpp
critbit_tree.h		critbit_tree.h
gbwt.cpp		gbwt.cpp
gbwt.h		gbwt.h
libdivsufsort.a		libdivsufsort.a
libdivsufsort64.a		libdivsufsort64.a
libsdsl.a		libsdsl.a
main_AVE.cpp		main_AVE.cpp
main_BUILD.cpp		main_BUILD.cpp
main_MYGBWT.cpp		main_MYGBWT.cpp
point.cpp		point.cpp
point.h		point.h
rect.cpp		rect.cpp
rect.h		rect.h
sb_tree.cpp		sb_tree.cpp
sb_tree.h		sb_tree.h
sbt_util.h		sbt_util.h
sbtmpfile.cpp		sbtmpfile.cpp
sbtmpfile.h		sbtmpfile.h
test_critbit_tree.cpp		test_critbit_tree.cpp
test_critbit_tree.h		test_critbit_tree.h
test_diskgbwt.cpp		test_diskgbwt.cpp
test_diskgbwt.h		test_diskgbwt.h
test_gbwt.cpp		test_gbwt.cpp
test_gbwt.h		test_gbwt.h
test_kdtree.cpp		test_kdtree.cpp
test_kdtree.h		test_kdtree.h
test_sbt.cpp		test_sbt.cpp
test_sbt.h		test_sbt.h

Repository files navigation

mKD-GBWT(multiple KD-tree GBWT) is an external memory full-text index.

The basis of mKD-GBWT is Geometric Burrows-Wheeler Transform. The biggest improvement of mKD-GBWT is that it uses multiple KD-tree as its orthogonal range searching data structure, so it has a good I/O performance.

Install:

1. First you need install SAscan and LCPscan.
		[1] https://www.cs.helsinki.fi/group/pads/SAscan.html
		[2] https://www.cs.helsinki.fi/group/pads/LCPscan.html

2. Down load mKD-GBWT index from https://github.com/xidianzyh/mKD-GBWT.
	
	modify the location of index:
		2.1 Open file sbt_util.h, modify the `#define GBWT_INDEX_POSITION  "/media/软件/GBWT-Index-position/"` into location of yourself.
		2.2 Open file tools/sam_sa_lcp.cpp, modify the `#define GBWT_INDEX_POSITION  "/media/软件/GBWT-Index-position/"` into location of yourself.

	$ cd mKD-GBWt
	$ make
	$ cd test
	$ make


Generate index of data

1. 	$ cd SAscan-???
	$ cd src
	$ ./sascan <data>

2.	$ cd LCPscan-???
	$ cd build
	$ ./construct_lcp <data>

3.	$ cd mKD-GBWT
	$ ./gen_sa_lcp <data>

4.	$ cd mKD-GBWT
	$ ./sam_sa_lcp <data> <step>
	$ ./build	<data>	<disk-page-size-in-bytes> <step>


Pattern-matching
	$ cd mKD-GBWT
	$ ./mygbwt <data> <disk-page-size-in-bytes> <step>


Example
	
	the data file is `/data/english`, disk-page is 4096 bytes, step = 4

	First generate the index of data

		1. 	$ cd SAscan-???
			$ cd src
			$ ./sascan /data/english

		2.	$ cd LCPscan-???
			$ cd build
			$ ./construct_lcp /data/english

		3.	$ cd mKD-GBWT
			$ ./gen_sa_lcp /data/english

		4.	$ cd mKD-GBWT
			$ ./sam_sa_lcp /data/english 4
			$ ./build	/data/english	4096  	4

	Second, pattern mathcing
	
			$ cd mKD-GBWT
			$ ./mygbwt /data/english 4096 4