辞書アプリの改良：高速化（４）

対策３：メタインデックス形式の変更

現在、1つの検索片でメタインデックスを検索するごとに約40回＋結果数回メタインデックスファイルからの読み込みを行っている。
この読み込み回数を減らすため、メタインデックスの形式を変更する。
現在のメタインデックスは[見出し語（2文字）＋辞書インデックスのoffset＋辞書インデックスのlength＋見出し語の出現位置]という形式になっており、メタインデックスファイル内にはこのメタインデックスが連続して記録されている。同一の見出し語でも他の部分が違うメタインデックスは別物として、それぞれメタインデックス内に記録されている。

検索片によるメタインデックス検索で対象になるのはこのうちの見出し語の部分だが、同一見出し語を持つメタインデックスが複数あるため、メタインデックスファイル内で対象となるメタインデックスが含まれている開始位置と終了位置を探すために2回のバイナリサーチが必要になっている。

そこで、同一見出し語を持つメタインデックスをまとめて

メタインデックス(header)

[見出し語＋メタインデックス(body)のoffset＋メタインデックス(body)のlength]

メタインデックス(body)

[同一見出し語を持つメタインデックスの[辞書インデックスのoffset＋辞書インデックスのlength＋見出し語の出現位置]を連続して接続]

に分け、それぞれメタインデックス(header)ファイルとメタインデックス(body)ファイルに記録する。

これによって、メタインデックス(header)ファイルには同一見出し語を持つメタインデックス(header)は必ず1つだけ持つようにすることができ、メタインデックス検索内のバイナリサーチをメタインデックス(header)の位置を探す1回だけに減らすことができる。

結果

正直、期待していたほど早くならなかった・・・。

ソース

MetaDictionary.groovy

class MetaDictionary extends BaseDictionary {
	def headerFile = null
	def bodyFile = null
	int count = 0
	int readCount = 0
	def MetaDictionary(fileName) {
		headerFile = new File(fileName + ".mh")
		bodyFile = new File(fileName + ".mb")
	}

	def search(key) {
		readCount = 0
		assert (key.length() <= MetaIndex.KEY_CHAR_LENGTH)
		def result = binarySearch(key, 0, ((int)(headerFile.length() / MetaIndex.HEADER_LENGTH) -1))
/*		println "read count: ${readCount}"*/
		return result
	}

	def getIndexHeader(int i) {
		readCount++
		return new MetaIndexHeader(read(headerFile, i*MetaIndex.HEADER_LENGTH, MetaIndex.HEADER_LENGTH))
	}
	
	def loadIndex(header) {
		byte[] buf = read(bodyFile, header.offset, header.length)
		int indexCount = header.length / MetaIndex.BODY_LENGTH
		def indexes = (0..<indexCount).collect {
			new MetaIndex(header, buf, it * MetaIndex.BODY_LENGTH)
		}
		return indexes
	}
	def binarySearch(key, int start, int end) {
		if (end < 0) return []
		int i = (int)Math.floor((start+end)/2)
		def idx = getIndexHeader(i)
		def c = idx.compareTo(key)
/*		println "start:${start}, end:${end}, i:${i}, c:${c}, idx:${idx}, key:${key}, key:${key.getBytes()}"*/
		if (c == 0) {
			return loadIndex(idx)
		} else if (start == end) {
			return []
		} else if (c > 0) {
			return binarySearch(key, start, i)
		} else {
			if ((end-start)==1) i = end
			return binarySearch(key, i, end)
		}
	}
}

MetaIndexHeader.groovy

class MetaIndexHeader extends BaseIndex implements Comparable {
	public static final int KEY_LENGTH = 12
	public static final int KEY_CHAR_LENGTH = 2
	public static final int HEADER_LENGTH = 20
	
	def MetaIndexHeader() {}
	def MetaIndexHeader(String w, int o=0, int l=0) {
		word = w
		offset = o
		length = l
	}
	def MetaIndexHeader(byte[] buf) {
		word = new String(buf, 0, KEY_LENGTH, "UTF-8").trim()	// 余計なバイト(0)をtrimで削除
		offset = byte2int(buf, KEY_LENGTH, 4)
		length = byte2int(buf, KEY_LENGTH+4, 4)
	}
	
	int compareTo(MetaIndex target) {
		if (word != target.word) return word.compareTo(target.word)
		if (offset != target.offset) return offset <=> target.offset
		return 0
	}
	int compareTo(Object target) {
		if (target instanceof MetaIndexHeader) return compareTo((MetaIndexHeader)target)
		if (target instanceof String) return word.compareTo(target)
		return -1
	}
	
	byte[] toBytes() {
		ByteArrayOutputStream byteStream = new ByteArrayOutputStream()
		dumpWord(byteStream)
		dumpOffsetLength(byteStream)
		return byteStream.toByteArray()
	}
	def dumpWord(byteStream) {
		byte[] w = word.getBytes("UTF-8")
		byteStream.write(w, 0, w.length)
		(w.length..<KEY_LENGTH).each {byteStream.write(0)}
	}
	def dumpOffsetLength(byteStream) {
		byte[] o = int2byte(offset)
		byte[] l = int2byte(length)
		byteStream.write(o, 0, o.length)
		byteStream.write(l, 0, l.length)
	}
}

MetaIndex.groovy

class MetaIndex extends MetaIndexHeader implements Comparable {
	public static final int LENGTH = 24
	public static final int BODY_LENGTH = 12
	
	int wordOffset = 0
	def MetaIndex(String w, int o=0, int l=0, int wo=0) {
		word = w
		offset = o
		length = l
		wordOffset = wo
	}
	def MetaIndex(MetaIndexHeader header, byte[] buf, int o) {
		word = header.word
		offset = byte2int(buf, o, 4)
		length = byte2int(buf, o+4, 4)
		wordOffset = byte2int(buf, o+8, 4)
	}
	def MetaIndex(byte[] buf) {
		parse(buf, 0)
	}
	def MetaIndex(byte[] buf, int o) {
		parse(buf, o)
	}
	def parse(byte[] buf, int o) {
		word = new String(buf, o, KEY_LENGTH, "UTF-8").trim()	// 余計なバイト(0)をtrimで削除
		offset = byte2int(buf, o+KEY_LENGTH, 4)
		length = byte2int(buf, o+KEY_LENGTH+4, 4)
		wordOffset = byte2int(buf, o+KEY_LENGTH+8, 4)
	}
	
	int compareTo(MetaIndex target) {
		if (word != target.word) return word.compareTo(target.word)
		if (offset != target.offset) return offset <=> target.offset
		if (wordOffset != target.wordOffset) return wordOffset <=> target.wordOffset
		return 0
	}
	int compareTo(Object target) {
		if (target instanceof MetaIndex) return compareTo((MetaIndex)target)
		if (target instanceof String) return word.compareTo(target)
		return -1
	}
	
	byte[] toBytes() {
		ByteArrayOutputStream byteStream = new ByteArrayOutputStream(LENGTH)
		dumpWord(byteStream)
		dumpOffsetLength(byteStream)
		dumpWordOffset(byteStream)
		return byteStream.toByteArray()
	}
	byte[] toBodyBytes() {
		ByteArrayOutputStream byteStream = new ByteArrayOutputStream(LENGTH)
		dumpOffsetLength(byteStream)
		dumpWordOffset(byteStream)
		return byteStream.toByteArray()
	}
	def dumpWordOffset(byteStream) {
		byte[] wo = int2byte(wordOffset)
		byteStream.write(wo, 0, wo.length)
	}
	String toString() {
		return "{word: ${word},\toffset:${offset},\tlength:${length},\twordOffset:${wordOffset}}"
	}
}

Indexer.groovyもね。

fileName = args[0]
workDir = new File("work")
deleteTmpFile()
workDir.mkdirs()

def indexes = loadCompleteIndex()

List metaList = []
int i=0
for (idx in indexes) {
	metaList.addAll(idx.toMetaIndexList())
	
	i++
	if (i%5000 == 0) {
		makeTmpFile(metaList)
		metaList = []
		println ("parsing:" + (i*100/indexes.size()) + "%")
	}
}
makeTmpFile(metaList)
makeMetaFile()

def makeMetaFile() {
	File headerFile = new File(fileName + ".mh")
	File bodyFile = new File(fileName + ".mb")
	headerFile.delete()
	bodyFile.delete()
	headerFile.createNewFile()
	bodyFile.createNewFile()
	def headerStream = new BufferedOutputStream(new FileOutputStream(headerFile))
	def bodyStream = new BufferedOutputStream(new FileOutputStream(bodyFile))
	def offset = 0
	listTmpFiles().each {f ->
			println ("writing: " + hex2str(f.name) + ":" + f.length() + ":" + (f.length() / MetaIndex.LENGTH))
			def buf = f.readBytes()
			def map = [:]
			def i = 0
			while ((i*MetaIndex.LENGTH) < buf.length) {
				def metaIndex = new MetaIndex(buf, i*MetaIndex.LENGTH)
				map.get(metaIndex.word, []) << metaIndex
				i++
			}
			map.keySet().sort().each {
				def header = new MetaIndexHeader(it)
				header.offset = offset
				
				map.get(it).sort().each {
					def bodyBuf = it.toBodyBytes()
					bodyStream.write(bodyBuf)
					offset += bodyBuf.length
				}
				header.length = offset - header.offset
				headerStream.write(header.toBytes())
			}
		}
	headerStream.close()
	bodyStream.close()
}

def listTmpFiles() {
	def list = workDir.listFiles().toList()
	return list.sort {l,r ->
			return hex2str(l.name).compareTo(hex2str(r.name))
		}
}

def makeTmpFile(metaList) {
	metaList.sort()
	def prev = str2Hex("a")
	def tmpFile = new BufferedOutputStream(new FileOutputStream(new File(workDir, prev), true))
	for (m in metaList) {
		def first = str2Hex(m.word.substring(0,1))
		if (prev != first) {
			prev = first
			tmpFile.close()
			tmpFile = new BufferedOutputStream(new FileOutputStream(new File(workDir, prev), true))
		}
		tmpFile.write(m.toBytes())
	}
	tmpFile.close()
}

def str2Hex(String val) {
	byte[]  bytes = val.getBytes()
	def result = ""
	bytes.each {
		result += Integer.toHexString(it & 0xff)
	}
	return result
}
def hex2str(val) {
	byte[] buf = new byte[(val.length() / 2)]
	int i=0
	while (val.length() > 0) {
		buf[i] = Byte.parseByte(val.substring(0, 1), 16) * 16 + Byte.parseByte(val.substring(1, 2), 16)
		val = val.substring(2)
		i++
	}
	return new String(buf, "UTF-8")
}

def deleteTmpFile() {
	workDir.listFiles().each {
		it.delete()
	}
	workDir.delete()
}

def loadCompleteIndex(indexOffset = 0, indexLength = -1) {
	if (indexOffset < 0) indexOffset = 0
	RandomAccessFile randomFile = new RandomAccessFile(fileName + ".idx", "r")
	if (indexLength == -1) indexLength = randomFile.length()
	def buf = new byte[indexLength]
	randomFile.seek(indexOffset)
	randomFile.read(buf)
	randomFile.close()

	def i=0
	int offset = 0
	int count = 0
	def indexes = new ArrayList();
	while (i<buf.length) {
		if (buf[i] == 0) {
			def idx = new Index(buf, offset, i-offset+9)
			if (idx.word.length() > 0) indexes.add(idx)
			offset = i+9
			i = i+8
			count++
		}
		i++
		if (i%200000 == 0) println ("loading:" + (i*100/(indexLength)) + "%")
	}
	return indexes
}