Subject: Efficient Dictionary Look Up for Chinese Input Method

From: Ng Liang Shing <[email-masked]>
Date: Wed, 3 Aug 1994 14:23:59 MYT

In search for the most efficient and the simplest
Dictionary Look Up Algorithm

Chinese Input Method (CIM) constitutes the Chinese Character Input System. A
CIM can be defined in various form. The most general form of a CIM would be a
'dictionary'. A dictionary is a look up table. Each entry in a dictionary has
two sides: the key and the target. The key may be a sequence of characters,
usually corresponding to a sequence of key strokes, intended to define the
target. The target may be one Chinese character, one Chinese phrase (i.e. a
string of Chinese characters), or a list of single Chinese characters, or a
list of Chinese phrase. Hence, each key and target pair forms a one to many
mapping. Conversely, more than one key may have target of the same meaning,
but they can be treated as different entries. For example:

Key     Target
a       a1 a1la1bo2 a1la1ba1ma3    <--- a list of phrase/character
bb      a1 bo1                     <--- a list of characters
abc     dong1nan2xi1bei3

The 'raw' form of a dictionary is in a human readable form, or, readable and
editable using a simple word editor or file viewer. The key and target may be
separated by a TAB or a single space, characters or phrases separated by a
single space.

The program takes in a sequence of key input by a user. It then searches the
dictionary to find the matching key and returns the corresponding
character/phrase.  The core is a dictionary look up algorithm.  Various
algorithms have been developed/implemented over the years, each varying in
degree of complexity and flexibility.  Here I shall present what I think as
the most efficient and the simplest dictionary look up algorithms.

The Efficient and Simple Dictionary Look Up Algorithm (DLU)

This DLU first builds a table of pointers.  Each entry in the table of
pointers has two pointers, one pointing to the key and the other pointing to
the target.  The table is sorted according to the key.  Since each entry is
fix-sized, binary search is used to searched for the matching key.

Implementation

One of the most complete collection of raw dictionaries in the public domain
would be the cxterm-dictionary collection. It can be found at various ftp
sites, one of which is ifcss.org:/software/x-win/cxterm-dictionary.

Other people may develop their own format of raw dictionary, such as those
used in NJSTAR.

To build the table of pointers, firstly the main body of the raw dictionary is
extracted. Since the raw dictionary may contain different header information,
the DLU should look for the BEGIN and END keywords for the main body. These
keywords must be reconfigurable, e.g. take as an argument in the command line.

The table of pointers must be sorted accoring to the key. So first build a
unsorted table with pointers to keys and targets. Then sort this table using a
well known sorting algorithm.

We need only to build the table of pointers occasionally, i.e. only when the
dictionary is updated.  So the table of pointers may be saved a file and
loaded directly for reuse next time.

Now we have a sorted table of pointers. To look for a matching key, we can use
binary search because the table is sorted.

Memory Consideration

The most intensive part should be put into the RAM. This would be the table of
pointers. The size required for the table is the most essential in memory
considerations.

If the dictionary file is less than 64K, then the whole of the dictionary is
addressable using 16-bit pointers. So each entry in the table of pointers has
two pointers, so it is 4 bytes wide. The number of entries in the table is
equal to the number of keys in the dictionary. This may vary from several
hundreds to several thousand depending on the rules or characteristic of the
CIM itself.

For example, in Pinyin, there are only about 500 or so keys. So we need 500
entries in the table. This would take up 2000 bytes.

For other radical based input methods or Pinxing, e.g. Cangjie, there may be
up to 7000 keys. The memory required would be 28000.

If the dictionary exceeds 64K, we need to use 32-bit pointers. This would
immediately double the size required for the table of pointers.

Various compression can be used to reduce the size of the dictionary. This
again depends on the nature of the CIM itself.

The compressed form of the dictionary is usually in binary format. So it is no
longer human readable. Many software packages ship their dictionary in this
form.

In short, the size of the table increases linearly with respect to the number
of keys in the dictionary. This is good because it does not depend on the
number of characters/phrases in the target nor the length of the key.

This DLU also combines both phrase and character input method together.

Predictive Input

There are two levels of predictive input. One is to predict the next character
given the past history of characters. The other is to predict the next
key-stroke given the history of key-strokes.  A sorted table of pointers
enables the predictive key-stroke input to be implemented easily.

This is very useful when the user is not so sure of the complete sequence of
key strokes and wishes to see all characters matching the key strokes he knows
of. This can be accomplished simply by outputting the entries following the
matching key in the dictionary. The user may then wish to select the choice
using a number. Since usually the screen may not accomodate all the choice,
the program must list the choice one page at a time and let the user walk
through the pages.

In practice, to give a sense of interactivity during input, the program must
not wait for the user to enter the complete key sequence. The program must
instead list all choices of phrase/character immediately after the user hits a
single key-stroke. Upon hitting the second key-stroke, the program narrow down
the list of choice. Upon hitting the third key-stroke, the program again
narrow donw the list of choice.

Reverse Look Up

This means give a character/phrase, to find the corresponding key. The above
sorted table of pointers does not provide a random access reverse look up
mechanism. Sequenctial reverse look up is possible. This may be satisfactory
in most cases because reverse look up is occasional. For example, I use two
input methods, Cangjie and Pinyin. When I forgot the Cangjie key for a
particular character, I use pinyin, then use reverse look up for the Cangjie
key. This facility is available in NJSTAR and ETEN.

However, in certain applications, we may need a very efficient reverse look up
algorithm. For example, we may wish to print out all the pinyin of the
characters in a given document. This is especially useful for the learners of
the Chinese language. In such applications, we need need to construct a
structure which enable random access reverse dictionary look up.

Other issues

There is a wide range of issues related to Chinese Input Methods which is
beyond the scope of this article, such as pen input or optical character
recognition.  Many of those require some implementation of artificial
intelligence.

Dictionary look up is the easiest to implement because it involves simple
keyboard (and possibly mouse) as input device. The DLU itself employs well
known sorting and searching algorithms. It is both popular and simple.

--
Ng Liang Shing            |   This is an Internet node host inside
Sungai Petani, Malaysia   |   an old 286.  A few years back, this place
[email-masked]          |   was not more than a small town.