Proceedings of the Third NTCIR Workshop

Uniform Indexing and Retrieval Scheme for Chinese, Japanese, and Korean

Da-Wei Juang and Yuen-Hsien Tseng
Dept. of Library & Information Science,
Fu Jen Catholic University, Taipei, Taiwan, R.O.C., 242
tseng@blue.lins.fju.edu.tw
Abstract
This paper reports on our work at the third
NTCIR workshop on the subtasks of Chinese,
Japanese, and Korean monolingual information
retrieval (IR). A Chinese IR system is applied to all
document sets in these three languages. Based on the
n-gram indexing model and a phrase formulation
method to extract longer key terms for indexing, no
language-dependent modifications were made toapply the system to Japanese and Korean IR. Our
attempt is to see whether such a system originallydesigned for Chinese IR can still work for Japaneseor Korean documents. The results turn out that it
performs similarly among the document sets in thesethree different languages.

Keywords:
Chinese IR, Japanese IR, Korean IR, n-gram
indexing, keyword extraction.

1. Introduction
Major Asian languages, especially Chinese,
Japanese, and Korean, share many common
properties in information retrieval. They all have alarge set of characters that are encoded in two bytes,
instead of one as those in English and many
European languages. Words in these three languages
often consist of multiple characters and have noboundaries among them in written texts, making
them difficult to identify. Although themorphological and grammatical rules are different
among these languages, an information retrieval
system can bypass the processing of these rules
without affecting the retrieval effectiveness. Thus it
is interesting to show how similar will the IR systems
be for these three languages.
A number of researches have shown thatn-gram indexing is at least as effective as word-based
indexing for retrieval of Chinese texts [1-2]. The
same phenomenon is also observed in Japanese IR© 2003 National Institute of Informatics

and Korean IR [3-4]. By participating the single
language IR (SLIR) tracks of the CLIR task in
NTCIR-3 [5], this work attempts to show, if nolanguage-dependent resources and efforts are
involved, how such a simple indexing method will
perform if the same IR techniques are applied to the
document sets in these three different languages. In
fact, in this work we use the same IR system(designed for retrieving Chinese documents) toretrieve not only Chinese texts, but also Japanese andKorean texts, without any modifications. It turns outthat the performance of such a system in Japanese IR
and Korean IR is quite the same as that in ChineseIR.
To better describe the details of the indexing
scheme used in this work, the next section introduces
a keyword/key-phrase formulation method to extract
repeated strings as key terms for indexing. Thismethod is quite language independent such that it isapplicable not just to Chinese, but also to Japaneseand Korean with some success. Section 3 thendescribes the details of the indexing and the retrieval
scheme used in the experiment. Retrieval
effectiveness is shown in Section 4 with some failure
analysis. Finally Section 5 concludes this paper.

2. Keyword Extraction
Keywords are representative terms in
documents that have many applications in
information retrieval. However, keywords or
key-phrases have no lexical boundaries in texts,
making them hard to be identified. By repeatedly
merging back nearby tokens in the text based on amerging, dropping, and accepting rule, Tseng has
devised an algorithm that can extract maximallyrepeated strings as keywords [6]. By maximally, wemean either the repeated strings are the longest onesor they occur more often than the longer strings that
contain them. For example, a repeated term “publichigh school” may be extracted without extracting“public high” or “high school”, as they are exact
substrings of the longer term. Only if “high school”

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

occurs more often than “public high school” (in sucha case we may say: “high school” subsumes “publichigh school”), can “high school” be possibly
extracted. Figure 1 shows the algorithm. The rule formerging, dropping, and accepting terms is implicit
expressed in the algorithm. Figure 2 shows a running
example, in which each capital letter denotes acharacter.
1. Convert the input into a LIST.
2. Do Loop
2.1
Set MergeList to empty.
2.2
Put a separator to the end of LIST as a sentinel andset the occurring frequency of the separator to 0.
2.3 For I from 1 to NumOf(LIST) – 1 step 1, do
If LIST[ I ] is the separator, Go to Label 2.3.
If Freq(LIST[ I ]) > threshold andFreq(LIST[ I+1]) > threshold, thenMerge LIST[ I ] and LIST[ I +1] into Z.
Put Z to the end of MergeList.
Else
If Freq(LIST[ I ]) > threshold and LIST[ I ]did not merge with LIST[ I - 1], thenSave LIST[ I ] in FinalList.
If the last element of MergeList is not the
separator, thenPut the separator to the end of MergeList.
End of For loop
2.4
Set LIST to MergeList.
Until NumOf(LIST) < 2.

Figure 1. The keyword extraction algorithm.
Example: Given an input string: BACDBCDABACD.
Let threshold=1, separator=x.
Step 1: Create a list of single tokens:
LIST = (B:3, A:3, C:3, D:3, B:3, C:3, D:3, A:3, B:3,
A:3, C:3, D:3)
Step 2:After 1st iteration :MergeList = (BA:2, AC:2, CD:3, DB:1, BC:1, CD:3,
DA:1, AB:1, BA:2, AC:2, CD:3)
FinalList = ( )After 2nd iteration :MergeList = (BAC:2, ACD:2, x, BAC:2, ACD:2)
FinalList = (CD:3)
After 3rd iteration :MergeList = (BACD:2, x, BACD:2)
FinalList = (CD:3)
After 4th iteration :MergeList = (x)FinalList = (CD:3, BACD:2)

Figure 2. A running example of the algorithm, where
the number following a semicolon denotes theoccurring frequency of the associated token.
The above algorithm is based on theassumption that a document concentrating on a topic
is likely to mention a set of strings a number of times.
Many natural language documents have this property,
including melody strings in music [6]. We found that

Figure3.
A
Japanese
articlefrom
http://www.asahi.com/national/update/0823/015.html(firstrow),aKoreanarticlefrom
http://www.korealink.co.kr/11_home/199903/h10114
3.htm (middle row), extracted keywords from theJapanese article (left column), and extracted
keywords from the Korean article (right column).

a longest repeated string often is a correct word (orphrase), since its repetition provides evidence fordecision on its left and right boundaries as a word.
Similarly, a repeated string that subsumes the others
may also be likely to be a legal term. The sources oferrors in Chinese keyword extraction mainly comefrom some single-character functional words that

Proceedings of the Third NTCIR Workshop

occur together with other words. The algorithm canextract key-phrases without any resources (such as
corpora, lexicons, or dictionaries) with a precisionlevel of 86% for Chinese news articles [7]. As toother languages, Figure 3 shows as examples two
articles in Japanese and in Korean respectively andtheir extracted keywords. As can be seen, thealgorithm is not optimized for Japanese and Koreansuch that some commas and functional words are notfiltered in the extracted terms.

3. Indexing and Retrieval Scheme
An n-gram is a string of n consecutive
characters in a text document. To select a set of terms
for representing a document for indexing, n-grams,
although maybe meaningless, are a good choice inaddition to document words themselves. Thesen-grams can overlap with each other and can havevariable lengths instead of a fixed length. Because no
language-dependant knowledge is required, n-gram
indexing is often used in multilingual or OCR
degraded text retrieval [8]. In monolingual text
retrieval, n-gram indexing also shows good
performance, despite that it leads to larger index sizeand slower query response.
However, the selection of a suitable n for
determining the length of the n-gram requires someanalysis of the text collections and the language ofthe texts. Our previous studies on Chinese text
retrieval in a collection of 8438 OCR documents
showed that a combination of unigrams andoverlapping bigrams for indexing outperforms
overlapping bigram indexing alone and unigrams
indexing as well [9]. This may be due to the fact that
longer n-grams provide better discriminant power
among documents while shorter n-grams help match
desired documents in case of vocabulary mismatch
so that a combination of them yields better results
than using each alone.
Thus we use unigrams and overlapping
bigrams in this experiment for indexing. In addition,
because the collection sizes in NTCIR-3 are quite
large, a total of 381,681 documents in Chinese,
249,387 documents in Japanese, and 66,146 in
Korean, for n-grams to have higher discriminant
power longer n-grams than bigrams are considered
for indexing. However, due to the large sizes ofcharacters in CJK (Chinese, Japanese, and Korean)
languages, n-grams where n longer than 2 yield
tremendous index terms that may severely degrade
the efficiency of a retrieval system. To overcome thisproblem, we add longer keywords instead of all
longer n-grams in the index to reduce the index size.
The keywords are those extracted by the algorithm
mentioned above. Since they are maximally repeatedstrings, they are in some sense the representatives ofthe documents in which they occur and they are farless in number than those arbitrary longer n-grams.
These index terms are then used to compute thesimilarity between a query and each of the
documents by the following formula:∑T

Sim( d i , q j ) =k =1

d i ,k q j ,k(bytesize d i ) 0.375

∑

T
k =1

q 2j ,kwhere the byte size denotes the number of bytes of adocument. The use of byte size as the normalization
factor is first introduced in the work of Singhal, et al[10] for OCR text retrieval, where the authors foundthat the commonly used cosine normalization factor
has negative effects on retrieval when documents
contain erroneous terms, such as those garbled by
OCR errors or those mistyped or misspelled terms.
Singhal et al also applied this byte size normalization
to large collections of TREC documents. They foundthat it also leads to better effectiveness than cosine
normalization for ordinary documents. Besides, thebyte size normalization is easier to compute than thecosine normalization. Thus we use this formula inour retrieval experiment.
The document term weight di,k in the above iscalculated by the term frequency (tf) and the inverse
document frequency (df), i.e., log(1+tf) x log(N/df),
where N is the collection size. The query term weight
qj,k is calculated by the term frequency in the queryand the length of the term, i.e., tf x (3 w – 1), where
w is the number of characters in the term.
The above indexing and retrieval techniques
were applied to each of the Chinese, Japanese, andKorean collections for monolingual retrieval, without
making any modifications.

4. Experiment Results
The CLIR task is concerned with retrieval of
documents in one language by queries in anotherlanguage. NTCIR-3 provides three document sets inthree Asian languages, namely, Chinese, Japanese,and Korean. Monolingual retrieval or single language
information retrieval (SLIR), i.e., retrieving
documents with queries in the same language isprovided as a subtask (also called track) in the CLIR
task. Thus there are 3 SLIR tracks, denoted as C-C,
J-J, and K-K, representing the tracks of Chinese to
Chinese IR, Japanese to Japanese IR, and Korean to
Korean IR, respectively. Due to limited manpower
and resources, we only participate the 3 SLIR tracks
in the CLIR task this year.
The query topics provided by NTCIR-3 consistof title, description, narrative, and concept fields. We
submit two runs for each of the three SLIR tracks forevaluation. One run uses the texts in the description
field as the query string (denoted as D in the runname), the other run uses the concept terms in theThe Third NTCIR Workshop, Sep.2001 - Oct. 2002

concept field (denoted as C in the run name). Overall,there are six runs submitted, where the run names are
C-C-D, C-C-C, J-J-D, J-J-C, K-K-D, and K-K-C, allof them are prefixed with our group name: FJUIR.
Each submitted run is evaluated in two criteria, one
is relax, meaning that the relevance judgment is donein a less strict way, the other is rigid, meaning thatthe relevance is judged is in a more rigid sense.

4.3 K-K track
The K-K track consists of 30 topics. Eightgroups submit a total of 17 runs. Of these 17 runs, 9
runs used the description field as queries and 2 runs
used the concept field. Table 3 shows the average
precision of our runs and the maximum, average, andminimum values of the average precisions of all runs
using the same fields.

4.1 C-C track
The C-C track consists of 42 topics. There are
14 groups submitting a total of 33 runs in the C-C
track this year. Among these 33 runs, 14 runs usedthe description field as the sources of queries and 4
runs used the concept field as the source of thequeries. Table 1 shows the average precision of ourruns and the maximum, average, and minimum
values of the average precisions of all runs using thesame field.
Table 1: Average precisions of the C-C track.
Relax
Rigid
FJUIR-C-C-D
0.22810.1858Max of C-C-D
0.49900.3933
Avg of C-C-D
0.26700.2130Min of C-C-D
0.04430.0347FJUIR-C-C-C
0.24030.1997Max of C-C-C
0.29290.2386
Avg of C-C-C
0.26050.2104Min of C-C-C
0.24030.18314.2 J-J track
The J-J track also consists of 42 topics. There
are 14 groups submitting a total of 33 runs in the J-J
track. Among these 33 runs, 19 runs used thedescription field as queries and 2 runs used theconcept field. Table 2 shows the average precision of
our runs and the maximum, average, and minimum
values of the average precisions of all runs using thesame field.
Table 2: Average precisions of the J-J track.
Relax
Rigid
FJUIR-J-J-D
0.22400.1920Max of J-J-D
0.39980.3457
Avg of J-J-D
0.26400.2199Min of J-J-D
0.04600.0396FJUIR-J-J-C
0.26740.2308Max of J-J-C
0.28980.2448Avg of J-J-C
0.2786
0.2378Min of J-J-C
0.26740.2308

Table 3: Average precisions of the K-K track.
Relax
Rigid
FJUIR-K-K-D
0.18260.1375Max of K-K-D
0.36020.2691
Avg of K-K-D
0.25010.1915Min of K-K-D
0.1256
0.0936FJUIR-K-K-C
0.26750.2075Max of K-K-C
0.29380.2157
Avg of K-K-C
0.28070.2116Min of K-K-C
0.26750.2075

4.4 Failure analysis
The average precisions shown above
demonstrate that the simple IR techniques without
language-dependant knowledge achieve similareffectiveness in three different SLIR tracks, showing
the robustness of this approach. However, its
performance is under the average of all runs,
indicating that there is room for improvement. Afterinspecting a number of retrieval results, some factorsthat affect the performance were identified.
First, most systems participating the CLIR
tasks apply pseudo relevance feedback (PRF) to
improve retrieval effectiveness. This techniquechooses the top n documents from the result list of an
initial search and adds more terms selected fromthese high-similarity documents to the original query
for a second-run search. Normally the second-run
search result is better in performance than the initial
search, especially when the initial query contains too
few terms. In contrast, we did not use this techniquein our experiment. Thus the effectiveness is less thanmost of the others in NTCIR 3. Since it is not easy tocompare with those runs without using PRF from theresult sets distributed by NTCIR 3, we compare tosome published results from NTCIR 2. Table 4 lists
our results using the Chinese collection of NTCIR 2.
Compared to some C-C runs of NTCIR 2 without
using PRF, the narrative run of NTHU (National
Tsing Hua University, Taiwan) has an average
precision of 0.5009 [11], the question run ofBerkeley is 0.4758 [3], and Trans-Ez achieves anaverage precision of 0.3880 [12]. As can be seenfrom these figures, the performance of our system is
not so bad as that in NTCIR 3.

Proceedings of the Third NTCIR Workshop

Table 4: Average precisions for NTCIR 2
Title

Question Narrative Concepts

References

Relax

0.47300.48800.55870.6751[1]

Rigid

0.32080.36460.4376

0.5736[2]

Second, the similarity measure between aquery and a document is represented in only one byte
in our implemented IR system (although double
precision is used during the calculation). This
careless decision leads to small discrepancy between
retrieved documents especially when there are
hundreds of thousands of documents in the collection.
Sorting these retrieved documents may loose someaccuracy due to the small range of the similarities.
Third, when processing the query string, only
1-grams, 2-grams, and the longest keywords found in
the index are extracted as query terms. Thisobviously did not use all the indexed terms that may
be helpful to the retrieval effectiveness. A better
query term extraction method that also includes the
keywords whose length is longer than 2-gram andshorter than the longest indexed terms should be
explored in the future.

[3]

[4]

[5]
[6]

[7]

5. Conclusions
An IR system designed for Chinese text
retrieval is applied to Japanese and Korean IR task
without modifications. The results show that it
performs similarly among the documents sets inthese three different languages. This is a little
surprise to us since we expected that it might degrade
noticeably in the Japanese and Korean IR subtasks
since the IR system is optimized for Chinese only.
However, our performance is under the average of all
similar runs. The high performance of other systems
is also a little surprise to us. Without further
information on how these systems work at the time
this article is written, we wonder whether it is simply
the retrieval models or the retrieval strategies (suchas relevance feedback) that make this difference.
Anyway, we expect that our system will performbetter in the near future after learning some lessons
from this workshop.
This is our first year in participating NTCIR
workshop. Although we have good experience inrelatively small collections of OCR text retrieval[13-14], dealing with large collections in multiple
languages poses another challenges to us, especially
under the environment of lack of time, manpower,
and hardware and software resources. However, we
will benefit from participating and attending thisworkshop and hopefully will make more
contributions to this community for the years to
come.

[8]

[9]

[10]

[11]

[12]

[13]

[14]

J. He, J. Xu, A. Chen, J. Meggs and F. C. Gey,
“Berkeley Chinese Information Retrieval at TREC-5:
Technical Report”, TREC-5, http://trec.nist.gov/
Aitao Chen, Jianzhang He, Liangjie Xu, Fredric C.
Gey, Jason Meggs, "Chinese Text Retrieval Without
Using a Dictionary", Proceedings of the 20th ACM
SIGIR Conference on Research and Development inInformation Retrieval, 1997, pp.42-49.
Aitao Chen, Fredric C. Gey and Hailing Jiang,“Berkeley at NTCIR-2: Chinese, Japanese, andEnglish IR experiments,” Proceedings of the second
NTCIR workshop, 2001, Japan.
Joon Ho Lee, Hyun Yang Cho, Hyouk Ro Park,“N-gram-based Indexing for Korean Text Retrieval,”
Information Processing and Management, Vol. 35,
1999, pp. 427-441.
“Cross-Language Retrieval Task in NTCIR
Workshop 3” http://research.nii.ac.jp/ntcir/workshop/clir/.
Yuen-Hsien Tseng, "Content-Based Retrieval forMusic Collections," Proceedings of the 22ndInternational ACM SIGIR Conference on Researchand Development in Information Retrieval - Aug.
15-19, Berkeley, U.S.A., 1999, pp.176-182.
Yuen-Hsien Tseng and Yu-I Lin "Evaluation of
Fuzzy Search, Term Suggestion, and Term
Relevance Feedback in an OPAC System," (inChinese) Bulletin of the Library Association ofChina, No. 61, 1998, pp.103-126.
Claudia Pearce and Charles Nicholas, "TELLTALE:
Experiments in a Dynamic Hypertext Environmentfor Degraded and Multilingual Data," Journal of theAmerican Society for Information Science, 47(4),1996, pp.263-275.
Yuen-Hsien Tseng and Douglas W. Oard,"Document Image Retrieval Techniques for Chinese"
Proceedings of the Fourth Symposium on Document
Image Understanding Technology, Columbia
Maryland, April 23-25th, 2001, pp. 151-158.
Amit Singhal, Gerard Salton, and Chris Buckley,"Length Normalization in Degraded Text
Collections," Proceedings of Fifth Annual
Symposium on Document Analysis and Information
Retrieval, April 15-17, 1996, pp. 149-162.
Jason Chang, David Yu, Ching Ting Shen, AfraCheng, Garfield Shen, Giordano Shen and David
Wong, "Nathu IR System at NTCIR-II," Proceedingsof the second NTCIR workshop, 2001, Japan.
Guo-Wei Bian and Chi-Ching Lin, "Trans-EZ at
NTCIR-2 : Synset Co-occurrence Method forEnglish-Chinese
Cross-Lingual
Information
Retrieval," Proceedings of the second NTCIR
workshop, 2001, Japan.
Yuen-Hsien Tseng, "Error Correction in a Chinese
OCR Test Collection," Proceedings of the 25th
International ACM SIGIR Conference on Researchand Development in Information Retrieval - SIGIR'02, Aug. 11-15, Tampere, Finland, 2002,
pp.429-430.
Yuen-Hsien Tseng, "Automatic Cataloguing and
Searching for Retrospective Data by Use of OCR
Text", Journal of American Society for Information
Science and Technology, Vol. 52, No. 5, 2001, pp.
378-390.