From @UGA.CC.UGA.EDU:owner-ccnet-l@UGA.CC.UGA.EDU Sat Aug  6 15:03:55 1994
Return-Path: <@UGA.CC.UGA.EDU:owner-ccnet-l@UGA.CC.UGA.EDU>
Received: from uga.cc.uga.edu by ifcss.org (4.1/IFCSS-Mailer)
	id AA03749; Sat, 6 Aug 94 15:03:54 CDT
Message-Id: <9408062003.AA03749@ifcss.org>
Received: from UGA.CC.UGA.EDU by uga.cc.uga.edu (IBM VM SMTP V2R2)
   with BSMTP id 2362; Sat, 06 Aug 94 16:02:43 EDT
Received: from UGA.CC.UGA.EDU (NJE origin LISTSERV@UGA) by UGA.CC.UGA.EDU (LMail V1.1d/1.7f) with BSMTP id 2150; Sat, 6 Aug 1994 16:02:42 -0400
Date:         Sat, 6 Aug 1994 13:01:10 -0700
Reply-To: "Bruce H. Liu" <bliu@NETCOM.COM>
Sender: Chinese Computing Network <CCNET-L@uga.cc.uga.edu>
From: "Bruce H. Liu" <bliu@NETCOM.COM>
Subject:      Re: Efficient Dictionary Look Up for Chinese Input Method
Comments: To: Ng Liang Shing <liang@HSNG.PL.MY>
Comments: cc: Multiple recipients of list CCNET-L <CCNET-L@uga.cc.uga.edu>
To: Multiple recipients of list CCNET-L <CCNET-L@uga.cc.uga.edu>
In-Reply-To:  <199408051123.EAA12086@mail.netcom.com>
Status: RO

On Fri, 5 Aug 1994, Ng Liang Shing wrote:

> On Wed, 03 Aug 1994 16:33:30 -0400 (EDT), jaring!UTKVX.UTCC.UTK.EDU!ZHANG wrote:
> > Is there
> > a book or any kind document about this ? It doesn't have to be about Chinese,
> > For Chinese in particular, is there a freeware or
> > commerce-ware I can get/buy (my budget on this is about 500 bucks :-) ?
>
> I know of one pen input called "Shen2Diao1Bi3". It works under Eten. It is
> getting popular here.  The software driver is installed on top of Eten.  The
> hardware is of course a "pen" plus a drawing board.  The package is sold under
> $500, I think.  But as I know it, it works only under Eten.

The device Mr. Ng mentioned works under MS Chinese Windows too. It is
available in the U.S. for under $300.

There are also other similar products from other companys but I cannot
recall their names on top of my head.

>
> I first saw it last summer. To my delight, after a year it is still
> surviving, hence I think it is getting popular.
>
> Of course, one of my interest is to hack the hell out of its data binaries.
> But I don't this is simple because even if I can understand its data binaries,
> the analytical algorithm binaries would be very difficult if not impossible to
> decode without a proper documentation.
>
> But the real concern with me is that, company like this should license their
> product and resources to application developers or other systems developers.
>

I don't know if they have any licensing policy for that but have you
tried to contact with them? I think you should make the first move to
talk to them if you are serious about it.

>
> --
> Ng Liang Shing            |   This is an Internet node host inside
> Sungai Petani, Malaysia   |   an old 286.  A few years back, this place
> liang@hsng.pl.my          |   was not more than a small town.
>



Bruce H. Liu
bliu@netcom.com

From @UGA.CC.UGA.EDU:owner-ccnet-l@UGA.CC.UGA.EDU Wed Aug  3 06:09:37 1994
Return-Path: <@UGA.CC.UGA.EDU:owner-ccnet-l@UGA.CC.UGA.EDU>
Received: from uga.cc.uga.edu by ifcss.org (4.1/IFCSS-Mailer)
	id AA11554; Wed, 3 Aug 94 06:09:33 CDT
Message-Id: <9408031109.AA11554@ifcss.org>
Received: from UGA.CC.UGA.EDU by uga.cc.uga.edu (IBM VM SMTP V2R2)
   with BSMTP id 8411; Wed, 03 Aug 94 07:06:25 EDT
Received: from UGA.CC.UGA.EDU (NJE origin LISTSERV@UGA) by UGA.CC.UGA.EDU (LMail V1.1d/1.7f) with BSMTP id 4886; Wed, 3 Aug 1994 07:06:24 -0400
Date:         Wed, 3 Aug 1994 14:23:59 MYT
Reply-To: Ng Liang Shing <liang@HSNG.PL.MY>
Sender: Chinese Computing Network <CCNET-L@uga.cc.uga.edu>
From: Ng Liang Shing <liang@HSNG.PL.MY>
Subject:      Efficient Dictionary Look Up for Chinese Input Method
Comments: To: Chinese Computing Network <ccnet-l@uga.cc.uga.edu>
To: Multiple recipients of list CCNET-L <CCNET-L@uga.cc.uga.edu>
Status: RO

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
liang@hsng.pl.my          |   was not more than a small town.

From owner-ccnet-l@UGA.CC.UGA.EDU Tue Nov  7 14:13:08 1995
Received: from uga.cc.uga.edu (uga.cc.uga.edu [128.192.1.5]) by ccic.ifcss.org (8.6.11/8.6.11) with SMTP id OAA06010 for <yjj@IFCSS.ORG>; Tue, 7 Nov 1995 14:13:05 -0500
Message-Id: <199511071913.OAA06010@ccic.ifcss.org>
Received: from UGA.CC.UGA.EDU by uga.cc.uga.edu (IBM VM SMTP V2R3)
   with BSMTP id 7927; Tue, 07 Nov 95 14:06:34 EST
Received: from UGA.CC.UGA.EDU (NJE origin LISTSERV@UGA) by UGA.CC.UGA.EDU (LMail V1.2a/1.8a) with BSMTP id 3359; Tue, 7 Nov 1995 14:00:24 -0500
Date:         Wed, 8 Nov 1995 03:02:09 +0800
Reply-To: Y M Chan <chanym@HK.SUPER.NET>
Sender: Chinese Computing Network <CCNET-L@UGA.CC.UGA.EDU>
From: Y M Chan <chanym@HK.SUPER.NET>
Subject:      Try Hanin Input Method
To: Multiple recipients of list CCNET-L <CCNET-L@UGA.CC.UGA.EDU>
Status: R

Yoshitaka Matsushima wrote:
>
>I'm using Apple computer LC475 in Japan. The system is Japanese 7.1.2 with
>a Chinese language Kit7.1.2.. I use Chinese character sometime. But Chinese
>input method of Macintosh system contains almost no phrases when I use
>Chinese input method, it's not useful.
>
>Therefore, I'm now using Shareway's Chinese input method: Cihui. The
>Cihui's original the dictionary has few prhases we use often. So I enriched
>the dictionary, I can somehow use it now. There are many ways to input
>Chinese characters, but here we use the Ping-in system. However, since the
>Cihui system is not stable, we are concerned that the Cihui system may not
>work when it's transferred to Power Mac.
>
>We are now searching for an input method for Macintosh better than the
>Cihui system.
>
>I'll appreciate it if someone will let me know.
>
>sincerely yours

Try the Hanin input method which is done by Matsushita (well, their Taiwan
subsidiary)!!! It is available in the Traditional ChineseSystem and you can
just move the files over and it will work under CLK.

Hope that helps.

Y M Chan
Hong Kong SuperNet

From owner-ccnet-l@UGA.CC.UGA.EDU Thu Jan  2 10:07:48 1997
Received: from listmail.cc.uga.edu (listmail.cc.uga.edu [128.192.232.10]) by ccic.ifcss.org (8.6.11/8.6.11) with ESMTP id KAA28970 for <yjj@IFCSS.ORG>; Thu, 2 Jan 1997 10:07:46 -0500
Message-Id: <199701021507.KAA28970@ccic.ifcss.org>
Received: from uga.cc.uga.edu by listmail.cc.uga.edu (LSMTP for Windows NT v1.0a) with SMTP id C61A8B90 ; Thu, 2 Jan 1997 10:00:25 -0500
Received: from UGA.CC.UGA.EDU (NJE origin LISTSERV@UGA) by UGA.CC.UGA.EDU (LMail V1.2a/1.8a) with BSMTP id 9422; Thu, 2 Jan 1997 09:59:01 -0500
Date:         Thu, 2 Jan 1997 16:06:34 -0800
Reply-To: liming@WOODCHEM.KTH.SE
Sender: Chinese Computing Network <CCNET-L@UGA.CC.UGA.EDU>
From: Liming Zhang <liming@WOODCHEM.KTH.SE>
Subject:      New PinYin based Chinese input method
To: Multiple recipients of list CCNET-L <CCNET-L@UGA.CC.UGA.EDU>
Status: RO

Please try a new PinYin based Chinese input method at

http://home2.swipnet.se/~w-26184/

or

http://193.12.122.36/~w-26184/

Happy New Year!

Liming

