Proceedings of the Third NTCIR Workshop

NTCIR-3 CLIR Experiments at Osaka Kyoiku University—Comparison of Gram-based Indices—
Takashi SATO Koto HAN
Osaka Kyoiku University
4-698-1 Asahigaoka, Kashiwara, Osaka, Japansato@cc.osaka-kyoiku.ac.jp
Abstract
Long gram-based indices are experimented atN-gram stores strings (character sequences), whichstart every character in a text. The length of strings is lessthan 3 (such as 1-gram or 2-gram) in common cases. We

NTCIR-3 CLIR task. To make gram-based indices, noanalyses such as morphological ones are required.

realized longer than 4-grams in average by encoding
grams in wg byte. wg is set 5 or 6 in most cases. At first,Indices in three languages (i.e. Japanese, English andChinese) are made at this task. They are quite different insome point. The difference of index overhead comes fromcharacters are coded in varying length bit in accordancewith their frequency of appearance. Then they are staffed
within wg . Figure 1 shows an example gram coding.

the difference of character code for example.
Keywords: gram-based index, gram

3coding,J-J subtask

multi-lingual, NTCIR

3.1 Index making

1Introduction

We computed grams, document by document. We
made two indices as inverted files of gram. One is madeWe participated one of traditional NTCIR task, CLIR.
We make indices of three languages (i.e. Japanese,English and Japanese). Index overhead (i.e. the ratio offrom headline tag and the other is text tag. During index
making, we sort grams. We also made wide range map ofgram, which are put in main memory when we searchindex size to corpus) is quite different language bylanguage.

grams.
At this subtask, gram length, the number of characters

2 Index for arbitrary string searchin a gram, ranges from 2 to 6 and 4.3 in average. And
they are coded into wg =6 byte. That is, a gram has almost
same length as 3-gram if not coded. Computer used is

N-gram [1-4] and suffix [5-7] array are known as
index structures, which enable arbitrary string search.

Compaq DS-20 (64bit architecture, 4GB main memory).
Table 1 shows the size of corpus, extracted tag fields
and two indices, which are made from headline and text
tag field. Index size overhead against extracted tag fields
is 140%. Table 2 shows time to make indices.

wg

CiCi +1

Ci + 2

Ci + 3

Ci +1

Ci + 2

Ci + 3Ci + 4

Ci + 2

Ci + 3 Ci + 4

Ci + 5

Ci + 3 Ci + 4

Ci + 4

Ci + 5

Ci + 5

Ci + 5
Ci + 6

Figure 1. Example of gram coding© 2003 National Institute of Informatics

Table 1. Size of corpus, tag fields andindices (J -J)
corpus

301Mbyte<headline> tag28.7Mbyte<text> tag259Mbyte<headline> index<test> index

43.1Mbyte
361Mbyte

The Third NTCIR Workshop, Sep.2001 - Oct. 2002

Table 2. Time to make indices (J-J)

Table 4. Size of corpus, tag fields andindices (E-E)<headline>

3.29min<text>

27.7mincorpus

60.7Mbyte

total

31.0min<headline> tag<text> tag

0.96Mbyte
55.9Mbyte<headline> index

3.42Mbyte<test> index

95.1Mbyte

3.2 Query making
We extract query words using morphological analysis
from TITLE and DESC tags in given 50 topics (001-050).
Compound words are segmented in words, and then all
possible combinations of words are made of a compoundword.

Table 5. Time to make indices (E-E)<headline>

0.71min<text>

6.27mintotal

6.98min

3.3 Index search and document ranking
Our index has tree structure, which has sorted gram
and wide range map of them. So, not only query words
whose length is equal to gram length, but also shorter or

5 J-C subtask

longer words can be searched efficiently. When wesearch a longer word, every gram in the words isbyte. At this task, no specific tag fields are extracted, sograms are made of entire corpus. Table 6 shows the sizeof corpus and an index. Index size overhead against

searched. Then retrieved sets of document numbers areintersected.
From set of retrieved documents for query words, we
compute tf-idf and similarity using probabilistic model[8] for document ranking. Table 3 shows index search
time.
Table 3. Index search time (J-J)
index

4

<headline><text>

word searched

203

327

time to search

3.02sec

20.8sec

average time per word

18.1msec

63.4msecmedian time per word

11.7msec

25.4msec

We computed grams as 3.1. They are coded into wg =6

corpus is 192%.
Table 6. Size of corpus and index (J-C)
corpus212Mbyte

index

407Mbyte

This is the only cross-lingual subtask we participated.
We made Chinese indices from Chinese corpus. In orderto make search keys against corpus, we extracted words
and compound words from Japanese topics. Next wetranslated them into Chinese words. Then we expanded
them by synonym in turn. We did not expanded words
from topics by synonym in Japanese before translation
because this approach was not able to get good results.

E-E subtask
6 Discussions

We computed grams as 3.1. At this subtask, gramlength ranges from 4 to 13 and 8.1 in average. And they
are coded into wg =6 byte.
Table 4 shows the size of corpus, extracted tag fields
and two indices. Index size overhead against extracted
tag fields is 173%. Table 5 shows time to make indices.

The size of gram-based index depends on many
parameters. For example, they include the length (wg ) inwhich grams are coded, pointer size, the number of byte
for document numbering. Moreover the number of grams
themselves differs at most twice by whether characters indocuments are 1byte or 2byte even if documents are inthe same length. Whereas we were able to make longProceedings of the Third NTCIR Workshop

gram-based indices, which are less than 200% overhead,at all subtasks we participated.

[3] Sato, T. et al., Gram based full test search system and its
application, IPSJ SIG Notes, 98-DBS-114-2 (1998).
[4] Sato, T, et al., NTCIR-3 PAT experiments at Osaka Kyoiku

7 Conclusions

university, in this proceedings.
[5] Gonnet, G., Baeza-Yates, R. and Snider, T., New Indices for

We participated one of traditional NTCIR task, CLIR.
We make indices of three languages. Index overhead isquite different language by language. Though it depends

Text: Pat Trees, in Information Retrieval: Data Structure &of many parameters. Whereas we were able to make longgram-based indices, which are less than 200% overhead,[6] Shang, H. and Merrett T., Trees for approximate stringat all subtasks we participated.

Algorithms chapter 5, Frakes, W. and Baeza-Yates, R. Ed., pp.
66-82 (1992).
matching, IEEE Trans. Knowledge and Data Eng., Vol. 8, No.
4, pp. 540-547 (1996).
[7] Yamashita, T., Fujio M. and Matsumoto Y., Language

References

Independent Tools for Natural Language, Proc. 18thICCPOL, pp.237-240 (1999).

[1] Sato, T., Fast full test search with free word using TS-file,Proc. 19th ACM SIGIR Conf., p.342 (1996).

[8] Robertson, S.E. and Walker, S., Some simple effective
approximations to the 2-Poisson model for probabilistic[2] Sato, T., Fast full test retrieval using gram based tree

weighted retrieval, Proc. 17th Int. Conf. Research andstructure, Proc. ICCPOL '97, Vol.~2, pp. 572--577 (1997).

Development in Information Retrieval, pp. 232-241 (1994).